Algoritmi keširanja

U informatici, algoritmi keširanja (koji se često nazivaju i alogritmima zamene ili politikama zamene) su algoritmi koji u računarskom programu ili u hadverski održavanoj strukturi služe za upravljanje sa informacijama sladištenim u kešu na računaru. Kada je taj keš pun, algoritam mora da odluči koje informacije da izbaci iz keša da bi napravio mesta za nove.

Prosečno vreme referenciranja memorije

$T=m*T_{m}+T_{h}+E$

where

$T$ = Prosečno vreme referenciranja memorije

$m$ = stepen promašivanja = 1 - (stepen pogodaka)

$T_{m}$ = Vreme pristupa glavnoj memoriji kada je došlo do promašaja (ili u slučaju keša u više nivoa , prosečno vreme referenciranja memorije za sledeći keš nižeg nivoa)

$T_{h}$= kašnjenje: vreme referanciranja keša kad je došlo do pogodka

$E$ = različiti sekundarni efekti, kao što su čekanje u redu kod multiprocesorskih sistema

Dve glavne odlike keša su: Kašnjenje i stepen pogodaka.

Pored ovih odlika keša postoji i određen broj sekundarnih faktora koji mogu da utiču na performanse keša.

"Stepen pogodaka" keša predstavlja koliko često se tražena informacija zaista nalazi u kešu.

Efikasne politike zamene prate koriščenje informacija u cilju poboljšanja stepena pogodaka (za datu veličinu keša).

Kašnjenje keša predstavlja koliko dugo nakon zahteva za traženom informacijom je keš može vratiti (pod uslovom da je u pitanju pogodak).

Brže strategije zamene tipično prate koje se informacije manje koriste, ili kao u slučaju direktno preslikanog keša, nikakve informacije ne prate da bi smanjili vreme potrebno da bi se da informacija ažurirala.

Svaka strategija zamene je kompromis između stepen pogodaka i kašnjenja.

Merenja "stepena pogodaka" se obično vrše pomoću referentnih testova.

Stvarni stepen pogodaka varira u zavisnoti od aplikacija gde se upotrebljava . Na primer, video i audio reprodukavanje u realnom vremenu često imaju stepen pogodaka blizu 0, jer svaki bit podataka u toku se čita prvi put (što je obavezni promašaj), koristi, i nakon toga se nikad ne upisuje ili čita.

Još gore, mnogi algoritmi keširanja (posebno LRU) dozvole da tok podatake da napuni keš, izbacujući na taj način iz keša informaciju koji će se koristiti ponovo uskoro (zagađenje keša).

Primeri

Beladijev Algoritam

Najefikasniji algoritam keširanja bi bio onaj koji uvek odbacuje informacije koje neće biti potrebne najduže vreme u budućnosti. Ovaj optimalni rezultat je poznat kao Beladijev optimalni algoritam ili vidovnjački algoritam. Pošto je generalno nemoguće predvideti kad će u budućnosti informacija biti potrebna, ovo je generalno nije primenljivo. Praktični minimum se može dobiti samo nakon ekspreimentisanja i potrebno ga je uporediti sa zaista izabranim algortimom keširanja.

LRU

Least Recently Used (srp. najmanje korišćena ): odbacuje najmanje korišćene informacije prvo. Algoritam zahteva da se prati šta je bilo korišćeno i kad , što može biti skupo ako neko želi da se osigura da se odbacuje zaista najmanje korišćene informacija.Generalna implementacija podrazumeva čuvanje "bitova starosti" za linije keša i praćenje Least Recently Used linije keša u zasnovanu na tim bitovima. U takvoj implemetaciji kad god se neka linija keša iskoriti starost ostalih linija se promeni.

MRU

Most Recently Used (srp. najčešče korišćena): prvo odbacuje, za razliku od LRU, najčešče korišćene informacije. U zaključcima koji su izneti na 11-toj VLDB konferenciji, Chou i Dewitt su primetili da "Kada se fajl stalno skenira u sekvencijalnoj petlji obrascu pristupa, MRU je najbolji algoritam keširanja." Kasnije su drugi istraživači na 22-goj VLDB konferenciji došli do saznanja obrasci slučajnog pristupa i ponovljenja skeniranja nad velikim skupovima podataka (obrasci cilkičnog pristupa).MRU algoritam keširanja ima više pogodaka od LRU algorima zbog tendencije da duže zadrže starije podatke. MRU algoritam je najkorisniji u situacijama gde je verovatnije da će starija informacija da traži više .

Pseudo-LRU

Pseudo-LRU (srp. pseudo najmanje koriščen):Koristi se kod [procesorski keš|procesorskog keša]sa velikom asocijativnošću (generalno ako je više od 4 nivoa), implemetaciona cena LRU algoritma postaje prepreka. Zbog toga u mnogim [procesoski keš|procesorskim keševima], se koristi pristup da gotovo uvek se odbacuje jedna od najmanje korišćenih informacija u kešu. Mnogi dizajneri procesora biraju PLRU algoritam kojem je potreban samo jedan bit po kešu da bi radio.Stepen promašaja je tipično lošiji kod PLRU algoritma, ali ima malo bolje kašnjenje i koristi manje struje nego LRU algoritam.

Random Replacement

Random Replacement (srp. slučajna zamena): na slučajan način bira kandidata i odbacuje ga kad dodje do potrebe za slobodnim prostorom. Kod ovog algoritma nema potrebe za čuvanjem istorije pristupa. Zbog svoje jednostavnosti se i koristi u ARM procesorima.

Segmented LRU

Segmented LRU (srp. segemntisan LRU algoritam): SLRU keš je podeljen u dva segmenta: uslovni segment i zaštićeni segment.Linije u svakom od segmenata su poređane po učestalosti pristupa, od najčešće do najređe pristupanoj.Kad dođe do promašaja, ti podaci se dodaju na kraj naskorijeg pristupa uslovnog segmenta. Pogodci su uklanjaju iz trenutne pozicije i dodaju se na kraj naskorijeg pristupa zaštićenog segmenta. Zaštićeni segment je konačan pa migracija linije iz uslovnog segmenta ka zaštićenom segmentu može dovesti do migracije LRU linije u zaštićenom segmentu poslednji korišćeni (МRU) крај uslovnog segmenta, čime ta linija dobija još jednu šansu da joj se pristupi pre zamene.Veličina zaštićenog segmenta je parametar SLRU algoritma koji varira u zavisnosti od obrazaca I/O opterećenja. Kad se linije odbacuju iz keša, uzimaju se linije sa LRU kraja uslovnog segmenta."

2-Way Set Associative

2-Way Set Associative se koristi za vrlo brze procesorske keševe gde je čak i PLRU prespor. Adressa novog podatka se koristi da bi se izračunala jedna od dve moguće pozicije u kešu gde je moguć upis.U principu LRU od dve se odbacuje.Linije keša koriste jedan bit po paru kao indikator koja je od njih najmanje korišćenja da bi ovo implementirale.

Direct-mapped cache

Direct-mapped cache se koristi za najbrže procesorske keševe gde je i prethodni algoritam prespor. Adressa novog podatka se koristi da bi se izračunala jedna moguća pozicija u kešu gde je moguć upis. Šta god je pre bilo na toj poziciji se odbacuje.

LFU

Least Frequently Used (srp. najmanje često koriščen).Algotitam LFU broji koliko često se informacija koristi. One koje se najmanje koriste prve se odbacuju.

Low Inter-reference Recency Set - LIRS

Low Inter-reference Recency Set je algoritam zamene strana sa boljim performansama od LRU algoritma i mnogih drugih algortimama zamene. To je postignuto ponovnom upotrebom distance kao metrike za dinamično ocenjivanje posečenih strana u cilju donosenja odluke o zameni stranice. Algoritam su razvili Song Jiang i Xiaodong Zhang.

Adaptive Replacement Cache - ARC

Adaptive Replacement Cache (srp. keš sa adaptivnom zamenom): konstatno balansira između LRU i LFU da bi dobio kombinovani rezultat. ARC algoritam je poboljšanje SLRU algoritma. To se postignuto upotrebom informacija o skoro izbačenim podacima iz keša da bi se dinamički određivala veličina zaštićenog i uslovnog segmenta u cilju bolje iskorišćenosti prostora u kešu.

Clock with Adaptive Replacement CAR

Clock with Adaptive Replacement algoritam kombinuje ARC i CLOCK algoritam.Perfomanse su uporedive sa ARC algoritmom, takođe one su bolje od LRU algoritma i CLOCK algoritma. Kao i ARC, CAR je samopodešavajuči i ne zahteva nikakve parametre od strane korisnika.

Multi Queue Caching Algorithm - MQ

Multi Queue Caching Algorithm: (by Zhou, Philbin, and Li). Stvari uzete u razmatranje:

• Podaci sa raličitom cenom: sačuvati podatke koje je skupo ponovo uzeti.
• Podaci koji zauzimaju više mesta: Ako u kešu ima podataka različite veličine, možda bi bilo bolje da se izbaci jedan veći podatak da ni stalo više manjih.
• Podaci koji istiću sa vremenom: Neki kešovi čuvaju podatke koji istiću sa vremenom (npr. DNS keš). Kompjuter može izbaciti podatke kojima je isteklo vreme . U zavisnosti od veličine keša možda nema potrebe ni za jednim drugim algoritmom keširanja.

Postoje algoritmi koji čuvaju koherenciju keša. Ovo se odnosi samo na one situacije gde više nezavisnih kešova se koristi za iste podatke.