Lokalnost referenci

U informatici‎, lokalnost referenci (takođe poznata kao princip lokaliteta) je pojava koji opisuje istu vrednost, ili odgovarajuće lokacije za skladištenje kojima se često pristupa, odnosno kojima će se pristupiti u bliskoj budućnosti. Postoje dve osnovne vrste referentnih lokaliteta. Vremenska lokalnost, odnosi se na upotrebu određenih (istih) podataka, i/ili sredstava, u relativno malom vremenskom intervalu. Prostorna lokalnost, odnosi se na korišćenje podataka u relativno bliskim memorijskim lokacijama. Sekvencijalni lokalitet, kao specijalni slučaj prostornog lokaliteta, nastaje kada su podaci tako raspoređeni da im se pristupa u linearnom vremenu, kao što je pristup članovima jednodimenzionalnog niza.

Lokalitet je samo jedan od tipova predviđanja koji se javljaju u računarskim sistemima. Sistemi koji ispoljavaju jaku lokalnost referenci, kandidati su za optimizaciju performansi kroz komponente kao što su keš i mnoge druge.

Lokalnost referenci uredi

Lokalnost referenci, takođe poznata kao princip lokalnosti, otkriva, pomoću analize lokacija podataka referisanih u skorašnjem vremenskom periodu, da izabrana lokacija može biti relativno predvidljiva. Važni specijalni slučajevi lokalnosti su vremenska, prostorna, ekvidistancijalna i lokalnost grananja.

Vremenska lokalnost: Ako je u jednom trenutku određeni deo memorije referenciran, onda je velika verovatnoća da će taj isti deo memorije biti referenciran u bliskoj budućnosti. Možemo reći da postoji vremenska blizina izmeću dva referenciranja istog dela memorije. U ovom slučaju, nameće se, da je potrebno čuvati kopije podataka u posebnim memorijama za skladištenje kojima se pristupa brže. Takođe poznato je da je vremenska lokalnost veoma poseban slučaj prostorne lokalnosti, odnosno moguća naredna lokalnost je upravo sadašnja lokalnost.

Prostorna lokalnost: Ako je u određeno vreme referencirana određena lokacija u memoriji, onda je velika verovatnoća da će u bliskoj budućnosti biti referencirane upravo one lokacije koje se nalaze u blizini trenutne. Za pobonjšanje performansi ovim slučajem potrebno je odrediti veličinu područja oko trenutno referencirane lokacije i taj blok pripremiti za brži pristup.

Lokalnost grananja: Ako postoji samo nekoliko mogućih alternativa za budući deo putanje u prostorno-vremenskoj koordinati prostora. To je slučaj ako petlja instrukcija ima jednostavnu strukturu, ili ako je mogući ishod malog sistema uslovnih instrukcija grananja ograničen na mali izbor mogućnosti. Lokalitet grananja obično nije prostorni lokalitet, jer nekoliko mogućnosti može da se nalazi daleko jedna od druge

Lokalitet jednakog odstojanja: On je između prostornog lokaliteta i lokaliteta grananja. Zamisslite petnju pristupa lokaciji po šablonu jednakog odstojanja, odnosno put u prostorno-vremenske koordinate prostora je isprekidana linija. U ovom slučaju, prosta linearna funkcija može predvideti kojoj lokaciji će se pristupiti u bliskoj budućnosti.

Da bi imali korist od veoma čestih pojavljivanja vremenskih i prostornih vrsta lokaliteta, većina sistema za skladištenje informacija je hijerarhijski organizovana, vidi ispod. Lokalitet jednakog odstojanja je obično podržan od strane različitih netrivijalnih dopunskih instrukcija procesora. U slučaju lokaliteta grane, savremeni procesori imaju sofisticirane prediktore grana, a na osnovu ovog predviđanja upravljač memorije procesora pokušava da prikupi i obradi podatke mogućih alternativa.

Razlozi za lokalitet uredi

Postoji nekoliko razloga za lokalitet. Ovi razlozi su ili ciljevi za postići ili razlozi za prihvatiti, u zavisnosti od aspekta. Ispod su prikazani razlozi, od naopštijeg slučaja, do specijalnih slučajeva:

Predvidljivost: Zapravo lokalitet je samo jedan tip predvidljivog ponašanja u računarskim sistemima. Srećom, mnogi od praktičnih problema su tako decidirani da program za njihovo rešavanje može da bude predvidljiv, ako je dobro napisan

Struktura programa: Lokalnost se dešava često, zbog načina na koji su računarski programi stvoreni, za rešavanje decidiranih problema. Generalno, slični podaci se čuvaju u obližnjim lokacijama u skladištu. Jedan zajednički obrazac u računarstvu podrazumeva obradu nekoliko stavki, jednu po jednu. To znači da ako je mnogo obrađivanja završeno, određenim stavkama će biti pristupljeno više puta, što dovodi do vremenske lokalnosti reference. Štaviše, prelazak na sldeću stavku podrazumeva da će sledeća stavka biti pročitana, pa imamo prostornu lokalnost reference.

Linearne strukture podataka: Lokalitet se često dešava zato što sadrži petlje koje imaju tendenciju da upute na nizove ili druge strukture podataka pomoću indeksa. Sekvencijalni lokalitet, poseban slučaj prostornog lokaliteta, javlja se kada su relevantni elementi podataka organizovani i pristupa im se linearno. Na primer, jednostavan prolazak elemenata u jednodimenzionalnom nizu, od bazne adrese do najvišeg elementa će iskoristiti sekvencijalni lokalitet niza u memoriji. Opštiji lokalitet jednakog odstojanja se javlja kada je linearni prelazak preko dužeg područja susednih struktura podataka koje imaju identičnu strukturi i veličinu. I pored toga, nisu cele strukture pristupne, nego samo međusobno odgovarajući isti elementi struktura. Ovo je slučaj kada je matrica predstavljena kao sekvencijalna matrica redova i uslov je da se pristupi jednoj koloni matrice.

Opšta upotreba lokanosti uredi

Ako se većinu vremena značajan deo ukupnih referenci skuplja u klastere, i ako se oblik ovog sistema klastera može dobro predvideti, onda se može koristiti za optimizaciju brzine. Postoji nekoliko načina da se dobiju beneficije od klastera. Uobičajene tehnike za optimizaciju su:

Povećanje lokalnosti referenci

Ovo se obično postiže softverski.

Iskorišćavanje lokalnosti reference

Ovo se obično postiže hardverski. Vremenski i prostorni lokaliteti se mogu kapitalizovati po hijerarhijskim hardverskim skladištima. Lokalnost jednakog odstojanja može se koristiti na odgovarajući način od strane specijalizovanih instrukcija procesora, ova mogućnost nije samo odgovornost hardvera, nego i softvera takođe, bilo da je njena struktura pogodna za izradu binarnog programa koji uzima specijalizovane instrukcije u obzir. Lokalitet grane je složenija mogućnost, stoga je potrebno više napora oko razvoja, ali postoji mnogo veća rezerva za buduće istraživanje u ovoj vrsti lokaliteta, nego u bilo kojoj od preostalih.

Korišćenje prostornog i vremenskog lokaliteta uredi

Hijerarhijska memorija uredi

Hijerarhijska memorija je hardverska optimizacija koja koristi prostorni i vremenski lokalitet i možđe se koristiti u više nivoa hijerarhije memorije. Straničenje očigledno ima korist od prostornog i vremenskog lokaliteta. Keš je jednostavan primer eksploatacije vremenskog lokaliteta, jer posebno dizajniran, brz, a mali memorijski prostor, uglavnom korišćen da bi čucao nedavno referencirane podatke i podatke blizu njih, što može dovesti do potencijalnog povećanja performansi.

Podaci u kešu moraju obavezno da odgovaraju podacima koji su prostorno blizu u glavnoj memoriji, međutim elementi podataka su devedeni u keš , jednu po jednu keš liniju. Ovo implicira da je prostorni lokalitet ponovo važan: ako je jedan element refernciran, nekoliko susednih elemenata će se takođe dovesti u keš. Konačno, vremenski lokalitet igra ulogu na najnižem nivou, jer se rezultati koji su referencirani nalaze veoma blizu jedan drugom te se mogu čuvati u registrima mašine. Programski jezici kao što je C omogućavaju programeru da predloži da se određene promenljive čuvaju u registrima.

Lokalitet podataka je tipična memorijska referentna karakteristika uobičajenih programa(mada postoje mnogi neuobičajeni šabloni). To čini raspored hijerarhijske memorije profitabilnim. U računarima, memorija je podeljena hijerarhijski da bi se ubrzao pristup podacima. Nizi nivoi memorijske hijerarhije teže da budu sporiji, ali veći. Dakle, program će postići bolje rerformanse ako koristi memoriju keširanu na višem nivou hijerarhije, i ako izbegava dovođenje podataka u viši nivo hijerarhije koji će svrgnitu podatke koji će se koristiti u bližoj budućnosti. Ovo je idealno, i poneda se ne može postići.

Tipična memorijska hijerarhija(vremena pristupa i keš veličine su približne tipičnim vrednostima od 2013 za potrebe diskusije; stvarne vrednosti i stvarni brojevi nivoa u hijerarhiji mogu varirati)

Procesorski registar (8-256 registara)– trenutni pristup, i to brzinom najbržeg jezgra procesora
L1 CPU keš (32 KiB to 512 KiB) – brz pristup, brzinom memorijske magistrale.
L2 CPU keš (128 KiB to 24 MiB) – nešto sporiji pristup, brzinom memorijske magistrale između dva jezgra
L3 CPU keš (2 MiB to 32 MiB) – još sporiji pristup, brzinom memorijske magistrale između još više jezgara procesora.
Glavna, fizička memorija (RAM) (256 MiB to 64 GiB) – spor pristup, brzina koja je ograničena prostornom udaljenosti i opštim hardverskim interfejsom između procesora i memorijskih modula na matičnoj ploči.
Disk (virtuelna memorija) (1 GiB to 256 TiB) – veoma spora,
Udaljena memorija (sa drugih računara ili interneta) (praktično beskonačna) – brzina varira od veoma sporih do neverovatno sporih

Množenje matrica uredi

Zajednički primer je množenje matrica:

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Kada se radi o velikim matricama, ovaj algoritam ima tendenciju da previše duplira podake. Kako je potrebno pomnožiti svaki član reda jedne matrice sa svakim članom kolone druge dolazi do višestrukom pristupu istim podacima, kao i višestrukom dobijanju istih rezultata.

Može se primetiti da od j zavisi kolona ove matrice C i B i ona treba da se vrti u unutrašnjoj petlji(to će popraviti iteratore redova, i i k dok se j kreće preko svake kolone u redu). Ovo neće promeniti matematički rezultat ali se poboljšava efikasnost. Prelaskom j i k petlji vremenska zahtevnost za veće matrice dramatično raste. (U ovom slučaju, 'veliki' znači, otprilike, više od 100.000 elemenata u svakoj matrici, ili dovoljno elemenata tako da matrice ne mogu da stanu u L1 i L2 keš.)

Vremenska zahtevnost može biti poboljšana u prethodnom primeru, koristeći tehniku koja se zove blokiranje. Veća matrica se može podeliti na ravnomerno velike sub-matrice, tako da se manji blokovi množe nekoliko puta dok su u memoriji.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      for (i = ii; i < ii + BLOCK_SIZE && i < SIZE; i++)
        for (k = kk; k < kk + BLOCK_SIZE && k < SIZE; k++)
          for (j = jj; j < jj + BLOCK_SIZE && j < SIZE; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

Vremenska složenost rešenja iznad je bolje jer blok može da se koristi nekoliko puta pre nego što pređete na naredni, tako da manje gubimo kad on ode u donje nivoe hijerarhije . Prostorni lokalitet je poboljšan, jer elementi sa susedne memorijske adrese imaju tendenciju da se povuku zajedno kroz memorijsku hijerarhiju.

Pogledaj još uredi

Reference uredi

Literatura uredi

P.J. Denning, The Locality Principle, Communications of the ACM, Volume 48, Issue 7, (2005), Pages 19–24
P.J. Denning, S.C. Schwartz, Properties of the working-set model, Communications of the ACM, Volume 15, Issue 3 (March 1972), Pages 191-198