Алгоритми кеширања

У информатици, алгоритми кеширања (који се често називају и алогритмима замене или политикама замене) су алгоритми који у рачунарском програму или у хадверски одржаваној структури служе за управљање са информацијама сладиштеним у кешу на рачунару. Када је тај кеш пун, алгоритам мора да одлучи које информације да избаци из кеша да би направио места за нове.

Просечно време референцирања меморије

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

wхере

$T$ = Просечно време референцирања меморије

$m$ = степен промашивања = 1 - (степен погодака)

$T_{m}$ = Време приступа главној меморији када је дошло до промашаја (или у случају кеша у више нивоа , просечно време референцирања меморије за следећи кеш нижег нивоа)

$T_{h}$= кашњење: време реферанцирања кеша кад је дошло до погодка

$E$ = различити секундарни ефекти, као што су чекање у реду код мултипроцесорских система

Две главне одлике кеша су: Кашњење и степен погодака.

Поред ових одлика кеша постоји и одређен број секундарних фактора који могу да утичу на перформансе кеша.

"Степен погодака" кеша представља колико често се тражена информација заиста налази у кешу.

Ефикасне политике замене прате коришчење информација у циљу побољшања степена погодака (за дату величину кеша).

Кашњење кеша представља колико дуго након захтева за траженом информацијом је кеш може вратити (под условом да је у питању погодак).

Брже стратегије замене типично прате које се информације мање користе, или као у случају директно пресликаног кеша, никакве информације не прате да би смањили време потребно да би се да информација ажурирала.

Свака стратегија замене је компромис између степен погодака и кашњења.

Мерења "степена погодака" се обично врше помоћу референтних тестова.

Стварни степен погодака варира у зависноти од апликација где се употребљава . На пример, видео и аудио репродукавање у реалном времену често имају степен погодака близу 0, јер сваки бит података у току се чита први пут (што је обавезни промашај), користи, и након тога се никад не уписује или чита.

Још горе, многи алгоритми кеширања (посебно ЛРУ) дозволе да ток податаке да напуни кеш, избацујући на тај начин из кеша информацију који ће се користити поново ускоро (загађење кеша).

Примери

Беладијев Алгоритам

Најефикаснији алгоритам кеширања би био онај који увек одбацује информације које неће бити потребне најдуже време у будућности. Овај оптимални резултат је познат као Беладијев оптимални алгоритам или видовњачки алгоритам. Пошто је генерално немогуће предвидети кад ће у будућности информација бити потребна, ово је генерално није применљиво. Практични минимум се може добити само након експреиментисања и потребно га је упоредити са заиста изабраним алгортимом кеширања.

LRU

Least Recently Used (срп. најмање коришћена ): одбацује најмање коришћене информације прво. Алгоритам захтева да се прати шта је било коришћено и кад , што може бити скупо ако неко жели да се осигура да се одбацује заиста најмање коришћене информација.Генерална имплементација подразумева чување "битова старости" за линије кеша и праћење Least Recently Used линије кеша у засновану на тим битовима. У таквој имплеметацији кад год се нека линија кеша искорити старост осталих линија се промени.

MRU

Most Recently Used (срп. најчешче коришћена): прво одбацује, за разлику од LRU, најчешче коришћене информације. У закључцима који су изнети на 11-тој ВЛДБ конференцији, Chou и Dewitt су приметили да "Када се фајл стално скенира у секвенцијалној петљи обрасцу приступа, MRU је најбољи алгоритам кеширања." Касније су други истраживачи на 22-гој ВЛДБ конференцији дошли до сазнања обрасци случајног приступа и поновљења скенирања над великим скуповима података (обрасци цилкичног приступа).MRU алгоритам кеширања има више погодака од LRU алгорима због тенденције да дуже задрже старије податке. MRU алгоритам је најкориснији у ситуацијама где је вероватније да ће старија информација да тражи више .

Псеудо-LRU

Псеудо-LRU (срп. псеудо најмање коришчен):Користи се код [процесорски кеш|процесорског кеша]са великом асоцијативношћу (генерално ако је више од 4 нивоа), имплеметациона цена LRU алгоритма постаје препрека. Због тога у многим [процесоски кеш|процесорским кешевима], се користи приступ да готово увек се одбацује једна од најмање коришћених информација у кешу. Многи дизајнери процесора бирају ПLRU алгоритам којем је потребан само један бит по кешу да би радио.Степен промашаја је типично лошији код ПLRU алгоритма, али има мало боље кашњење и користи мање струје него LRU алгоритам.

Random Replacement

Random Replacement (срп. случајна замена): на случајан начин бира кандидата и одбацује га кад додје до потребе за слободним простором. Код овог алгоритма нема потребе за чувањем историје приступа. Због своје једноставности се и користи у ARM процесорима.

Segmented LRU

Segmented LRU (срп. сегемнтисан ЛРУ алгоритам): SLRU кеш је подељен у два сегмента: условни сегмент и заштићени сегмент.Линије у сваком од сегмената су поређане по учесталости приступа, од најчешће до најређе приступаној.Кад дође до промашаја, ти подаци се додају на крај наскоријег приступа условног сегмента. Погодци су уклањају из тренутне позиције и додају се на крај наскоријег приступа заштићеног сегмента. Заштићени сегмент је коначан па миграција линије из условног сегмента ка заштићеном сегменту може довести до миграције LRU линије у заштићеном сегменту последњи коришћени (МRU) крај условног сегмента, чиме та линија добија још једну шансу да јој се приступи пре замене.Величина заштићеног сегмента је параметар СЛРУ алгоритма који варира у зависности од образаца I/О оптерећења. Кад се линије одбацују из кеша, узимају се линије са LRU краја условног сегмента."

2-Way Set Associative

2-Way Set Associative се користи за врло брзе процесорске кешеве где је чак и PLRU преспор. Адресса новог податка се користи да би се израчунала једна од две могуће позиције у кешу где је могућ упис.У принципу LRU од две се одбацује.Линије кеша користе један бит по пару као индикатор која је од њих најмање коришћења да би ово имплементирале.

Direct-mapped cache

Direct-mapped cache се користи за најбрже процесорске кешеве где је и претходни алгоритам преспор. Адресса новог податка се користи да би се израчунала једна могућа позиција у кешу где је могућ упис. Шта год је пре било на тој позицији се одбацује.

LFU

Least Frequently Used (срп. најмање често коришчен).Алготитам LFU броји колико често се информација користи. Оне које се најмање користе прве се одбацују.

Low Inter-reference Recency Set - LIRS

Low Inter-reference Recency Set је алгоритам замене страна са бољим перформансама од LRU алгоритма и многих других алгортимама замене. То је постигнуто поновном употребом дистанце као метрике за динамично оцењивање посечених страна у циљу доносења одлуке о замени странице. Алгоритам су развили Song Jiang и Xiaodong Zhang.

Adaptive Replacement Cache - ARC

Adaptive Replacement Cache (срп. кеш са адаптивном заменом): констатно балансира између LRU и LFU да би добио комбиновани резултат. ARC алгоритам је побољшање SLRU алгоритма. То се постигнуто употребом информација о скоро избаченим подацима из кеша да би се динамички одређивала величина заштићеног и условног сегмента у циљу боље искоришћености простора у кешу.

Clock with Adaptive Replacement CAR

Clock with Adaptive Replacement алгоритам комбинује ARC и CLOCK алгоритам.Перфомансе су упоредиве са ARC алгоритмом, такође оне су боље од LRU алгоритма и CLOCK алгоритма. Као и ARC, CAR је самоподешавајучи и не захтева никакве параметре од стране корисника.

Multi Queue Caching Algorithm - MQ

Multi Queue Caching Algorithm: (by Zhou, Philbin, and Li). Ствари узете у разматрање:

• Подаци са раличитом ценом: сачувати податке које је скупо поново узети.
• Подаци који заузимају више места: Ако у кешу има података различите величине, можда би било боље да се избаци један већи податак да ни стало више мањих.
• Подаци који истићу са временом: Неки кешови чувају податке који истићу са временом (нпр. DNS кеш). Компјутер може избацити податке којима је истекло време . У зависности од величине кеша можда нема потребе ни за једним другим алгоритмом кеширања.

Постоје алгоритми који чувају кохеренцију кеша. Ово се односи само на оне ситуације где више независних кешова се користи за исте податке.