Кеш централне процесорске јединице

С Википедије, слободне енциклопедије

Кеш централне процесорске јединице је кеш који користи CPU (енгл. central processing unit - централна процесорска јединица) рачунара да би се смањило просечно време приступа меморији. Ако је кеш мањи, бржа је меморија, која чува копије података из често коришћених главних меморијских локација. Све док су већина приступа меморији кеширане меморијске локације, просечна латентнција приступа меморији ће бити ближа латенцији кеша него латенцији главне меморије.

Прегледи[уреди | уреди извор]

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

Већина модерних десктопа и серверских CPUs имају најмање три независна кеша: инструкцију кеша ради брзине доношења извршних инструкција, податке кеша ради брзине доношења података и складиштења, и translation lookaside buffer (TLB) који се користи ради виртуелног-у-физички адресни превод и за извршне инструкције и податаке. Кеш подаци се обично организују као хијерархије кеша вишег-нивоа (L1, L2, итд, види кешеви вишег нивоа).

Кеш улази[уреди | уреди извор]

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

Када процесор треба да чита или исписује локацију у главној меморији, он прво проверава одговарајући улаз у кешу. Кешеви проверавају садржај захтеване меморијске локације у свакој од линија кеша, која може да садржи ту адресу. Ако процесор утврди да је меморијска локација у кешу, јавља се кеш погодак. Међутим, ако процесор не пронађе меморијску локацију у кешу, јавља се промашај кеша. У случају:

  • кеш погодка, процесор одмах чита или исписује податке у кеш линији
  • кеш промашаја, кеш додељује нови улаз, и копира у подацима из главне меморије; затим, захтев се испуњава из садржаја кеша.

Кеш перформансе[уреди | уреди извор]

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

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

Политика замене[уреди | уреди извор]

Да би се направило места за нови улаз на кеш промашај, кеш мора да избаци један од постојећих улаза. Хеуристички, да користи избор улаза да би извршио избацивање, а што се зове политика замене. Основни проблем са било којом политиком замене је да мора да се предвиди за који постојећи улаз кеша је најмање вероватно да ће се користити у будућности. Предвиђање будућности је тешко, тако да не постоји савршен начин да се изабере између различитих расположивих политика замене.

Једна популарна политика замене, најмање скоро коришћена, ЛРУ (LRU - Least Recently Used), замењује најмање недавно приступни улаз.

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

  • Кеш улази такође могу бити искључени или закључани у зависности од контекста.

Политика исписа[уреди | уреди извор]

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

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

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

Подаци у главној меморији кеша могу да се промене од стране других субјеката (нпр. периферије користе директан приступ меморији или процесор са више-језгара), у ком случају копија у кешу може да постане застарела или устајала. Алтернативно, када CPU у процесору са више-језгара ажурира податке у кешу, копије података у кешу, које ће се повезати са другим језгрима, постаће устајале. Комуникациони протоколи између кеш менаџера, који одржавају доследност података, су познати као кеш кохерентни протоколи.

CPU застоји[уреди | уреди извор]

Време потребно да се донесе једна кеш линија из меморије (читај латенције) је битно јер ће CPU остати без ствари које треба да уради док чека на кеш линију. Када CPU достигне ово стање, то се зове застој.

Како CPUs постају бржи, застој услед кеш промашаја се помера ка већим могућностима рачунања; модерни CPUs могу да извршавају стотине упутства за време потребно да се донесе једна кеш линија из главне меморије. Различите технике се употребљавају да би се CPU одржао радно активним за то време.

  • CPUs ван функције (оut-of-order) (Pentium Pro и касније Intel дизаин, на пример) покушавају да изврше независне инструкције после инструкције која се чека за кеш промашене податаке.
  • Још једна технологија, која се користи од стране многих процесора, је симултани мултитрединг (simultaneous multithreading - SMT), или - у Intel терминологији – хипертрединг (hyper-threading - HT), који омогућавају да алтернативна нит користи CPU језгро, док прва нит чека да подаци дођу из главне меморије.

Кеш улазна структура[уреди | уреди извор]

Кеш улазни ред обично је следеће структуре:

таг блок података застава бита(flag bits)

Блок подаци (кеш линија) садрже стварне податке учитане из главне меморије. Таг садржи (део од) адресу стварних података преузетих из главне меморије. Flag битови су дискутовани у даљем тексту.

Величина кеша је количина података главне меморије коју он може да држи. Ова величина се може израчунати као број бајтова који се налазе у сваком блоку података пута број блокова смештених у кешу. (Број тага и flag битова је ирелевантан за овај обрачун, мада то не утиче на физичко подручје кеша).

Ефективна меморијска адреса је подељена (MSB до LSB) na таг, индекс и блок офсет:[1][2]

таг индекс блок офсет

Индекс описује који је кеш ред (која кеш линија) унутар кога ће се ставити подаци. Дужина индекса је бита. Блок офсет специфицира жељене податке у сачуваним подацима блока у кеш реду. Типична ефективна адреса је у бајтовима, па дужина блок офсета је бита. Таг садржи најзначајније адресе битова, које се проверавају у односу на тренутни ред (ред је преузет од стране индекса) да се види да ли је то онај што нам треба или други, небитна меморијска локација где се догодио исти индексни бит који желимо. Ознака дужина у битовима је:.

Неки аутори блок офсет једноставно зову "офсет",[3] или "премештање“.[4][5]

Пример[уреди | уреди извор]

Оригинални Pentium 4 има четворосмерни скуп удружених L1 кеш података величине 8 KB са 64-бајт кеш блокова. Дакле, постоји 8 KB/64= 128 кеш блокова. То подразумева 128/4 = 32 скупа (а самим тим и 2 ^ 5 = 32 различита индекса). Постоји 64 = 2 ^ 6 могућих одступања. Пошто је адреса CPU од 32 бита, то значи 32 = 21 + 5 + 6, а самим тим подразумева 21 бита таг поља. Оригинални Pentium 4 је такође имао на осам-начина удружени скуп L2 интегрисаног кеша величине 256 KB са 128 бајт кеш блокова. То подразумева 32 = 17 + 8 + 7, а самим тим и 17 бита таг поља.[3]

Застава (flag) битови[уреди | уреди извор]

Кеш инструкција захтева само један flag бит по уласку у ред кеша: важећи бит. Важећи бит означава да ли је или није кеш блок оптерећен валидним подацима.

При укључењу рачунара, хардвер поставља све важеће битове у свим кешевима на "неважеће“. У другим приликама, неки системи такође постављају важећи бит на "неважећи", као када мулти-мастер bus-snooping хардвер у кешу једног процесора слуша пренос адреса из неког другог процесора, и схвата да су одређени блокови података у локалном кешу сада устајали и требало би да буду означени као неважећи.

Кеш податак обично захтева два flag бита по уласку у кеш ред: важећи бит и такође прљав бит. Прљав бит показује да ли је блок био непромењен пошто је био прочитан из главне меморије - "чист" - односно да ли је процесор написао податке у том блоку (а нову вредност није још направио у главној меморији) - "прљав“.

Асоцијативност[уреди | уреди извор]

Which memory locations can be cached by which cache locations

Политика замене одлучује где ће у кешу ићи копија одређеног улаза главне меморије. Ако је политика замене слободна да изабере било који улаз у кешу да одржи копију, кеш се зове потпуно асоцијативни (повезан). Са друге стране, ако сваки улаз у главној меморији може да иде на само једно место у кешу, кеш је директно мапиран. Многи кешеви испуњавају компромис у коме сваки улаз у главној меморији може да иде у било које од Н-места у кешу, а описани су као Н-начина асоцијативног скупа. На пример, кеш подаци нивоа-1 у AMD Athlon су двосмерни асоцијативни скуп, што значи да било која одређена локација у главној меморији може да се сачува у једној од две локације у кеш подацима нивоа-1.

Асоцијативност је компромис. Ако постоји десет места на којима политика замене може имати мапиране меморијске локације, а затим проверу да ли је локација у кешу, морају се претражити десет кеш улаза. Провера више места тражи више енергије, чип зона, и потенцијално време. С друге стране, кешеви са више асоцијативности трпе мање промашаје (погледати промашаје сукоба, доле), тако да процесор троши мање времена за читање из споре главне меморије. Правило палца је да удвостручење асоцијативности, од директно мапираних у двосмер, или од два пута до четири пута, има отприлике исти ефекат на брзину поготка као удвостручење величине кеша. Асоцијативност повећана преко четири пута има много мање утицаја на брзину поготка,[6] и углавном се извршава из других разлога (види виртуелно изобличење, доле).

У циљу лошијег, али једноставно боље него сложеног:

  • директни мапирани кеш - најбољи (најбржи) погодак времена, и тако најбољи компромис за "велике" кешове
  • двосмерни скуп асоцијативног кеша
  • двосмерни искривљени асоцијативни кеш – 1993. године, ово је најбољи компромис за кеш чије су величине биле у опсегу 4-8 KB[7]
  • четворосмерни скуп асоцијативног кеша
  • потпуно асоцијативни кеш - најбоље (најниже) промашене брзине, па је најбољи компромис када је казна за промашај веома висока.

Директно-мапирани кеш[уреди | уреди извор]

Овде свака локација у главној меморији може да иде само на један улаз у кешу. Овде нема политике замене као такве, јер не постоји избор у којем ће кеш улазни садржаји да се избаце. То значи да, ако се две локације пресликавају у исти улаз, оне могу стално да куцају једна другој. Мада једноставније, директно мапирани кеш мора да буде много већи него асоцијативни да би дао упоредиве перформансе, и више је непредвидив. Нека "к" буде број блока у кешу, "y" да буде блок број меморије, и "n" да буде број блокова у кешу, тада се мапирање врши помоћу једначине k = y mod n.

Двосмерни скуп асоцијативног кеша[уреди | уреди извор]

Ако свака локација у главној меморији може бити сачувана у једном од две локације у кешу, једно логично питање је: која је од те две? Најједноставнија и најчешће коришћена шема, што је приказано на десној слици изнад, је да се користе најмање значајни битови меморијског локацијског индекса као индекса за кеш меморију, као и да постоје два улаза за сваки индекс. Једна од предности овог програма је да тагови, који се чувају у кешу, не морају да укључе тај део главне меморијске адресе, која је присутна у меморијском кеш индексу. Пошто кеш тагови имају мање битова, они узимају мању површину на чипу микропроцесора и могу да се читају и брже пореде. Такође LRU је посебно једноставан, јер само један бит треба да се сачува за сваки пар.

Разматрање извршења[уреди | уреди извор]

Једна од предности директног мапираног кеша је у томе што омогућава једноставно и брзо размишљање. Када је адреса израчуната, познат је један кеш индекс који може имати копију те локације у меморији. Тај кеш улаз може да се чита, а процесор може да настави да ради са тим подацима пре него што заврши проверу да таг заправо одговара траженој адреси.

Идеја да процесор користи кеширане податке, пре него што се таг комплетира може да се примени на асоцијативни кеш. Подскуп таг, зове се наговештај, и може да се користи за избор само једног од могућих кеш улаза који мапирају у траженој адреси. Улаз који се селектује наговештавањем може тада да се користи паралелно са провереним пуним тагом. Техника наговештаја најбоље делује када се користи у контексту адресе превода, као што је објашњено у наставку.

Двосмерни искривљени асоцијативни кеш[уреди | уреди извор]

Предложене су и друге шеме, као што је искривљни кеш,[8] где је индекс за пут 0 директан, као горе, али индекс за пут 1 се формира са hash функцијом. Добра hash функција има својство да адресе које се сукобљавају са директним мапирањем, не теже сукобу када се мапира са hash функцијом, па је мање вероватно да ће програм бити оптерећен са неочекивано великим бројем промашених сукоба, што потиче од патолошког приступа обрасцу. Лоша страна са рачунањем hash функцијом је екстра кашњење.[9] Поред тога, када дође време да се учита нова линија и избаци стара линија, може да се деси да она тешко може да одреди која постојећа линија је најмање недавно коришћена, јер се нове линије сукобљавају са подацима различитих индекса у сваком путу; LRU трагање за неискривљене кешеве се обично ради на по-скуп базама Ипак, искривљени-асоцијативни кеш има велике предности у односу на конвенционалне скуп-асоцијативне.[10]

Псеудо асоцијативни кеш[уреди | уреди извор]

Прави скуп-асоцијативни кеш истовремено тестира све могуће начине, користећи нешто као садржајно адресабилну меморију. Псеудо-асоцијативни кеш тестира сваки могући начин, један по један. Примери псеудо-асоцијативног кеша су hash-rehash кеш и колона-асоцијативни кеш.

У уобичајеном случају проналажења поготка, у првом начину тестирања, псеудо-асоцијативни кеш је брз као и директно-мапирајући кеш, и има много мањи сукоб брзине промашаја него директно-мапирани кеш, ближи промашају брзине потпуно асоцијативног кеша.[9]

Кеш промашај[уреди | уреди извор]

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

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

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

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

У циљу смањења кеш промашене брзине, велики део анализа је урађен у вези кеш понашања, у покушају да се пронађе најбоља комбинација величине, асоцијативности, величине блока, и тако даље. Секвенце меморијских референци које обављају benchmark (мера вредности, стандард односно важни (главни) показатељ који се користи за компаративне сврхе) програми се чувају као адресни трагови. Сходно томе, анализе симулирају већи број различитих могућих кеш дизајна на овим дугим адресним траговима. Осећај о томе како многе променљиве утичу на кеш брзину поготка може бити прилично збуњујућ. Значајан допринос овој анализи дао је Марк Хил, који је одвојио промашаје у три категорије (познате као три ЗС):

  • Обавезни промашаји су они промашаји изазвани од стране прве референце у локацији у меморији. Величина кеша и асоцијативност не праве разлику у броју обавезних промашаја. Претходно доношење може овде да помогне, као што може већа величина кеш блока (облик претходно доношења). Обавезни промашаји се понекад називају и хладни промашаји.
  • Капацитет промашаја су они пропусти који се јављају без обзира на асоцијативност или величину блока, и искључиво се јављају због коначних величина кешева. Крива капацитета брзине промашаја у односу на величину кеша даје неку меру временског локалитета. Треба имати на уму да не постоји користан појам кеша "пун" или "празан", или "блиски капацитет": CPU кешеви готово увек имају скоро сваку линију испуњену са копијом неког реда у главној меморији, а скоро свака додела нових линија захтева избацивање старе линије.
  • Промашаји сукоба су они промашаји који су се могли избећи, да кеш није раније избацио улаз. Конфликт промашаји могу даље да се деле на мапиране промашаје, који неизбежно дају посебну количину асоцијативности, и замену промашаја, који потичу од нарочитог избора жртве политике замене.
Miss rate versus cache size on the Integer portion of SPEC CPU2000

Графикон са десне стране резимира учинак кеша који се види на целобројном делу SPEC CPU2000 benchmark дат од стране Хила и Кантина.[11] Ови benchmarks су са циљем да представе врсту посла да би се инжењерска рачунарска радна станица могла видети било ког дана. Читалац треба да има има у виду да је веома тешко пронаћи benchmarks, који увек морају корисно да заступају многе програме, и увек ће бити важни програми са врло различитим понашањем.

Могу да се виде различити ефекти три Cs у овом графикону.

На крајњем десном делу графикона, са величином кеша са ознаком "инф", налазе се обавезни промашаји. Ако се жели побољшање перформанси једне машине на SpecInt2000, повећавање величине кеша преко 1 MB, суштински је бескорисно. То је увид дат помоћу обавезних промашаја.

Потпуно асоцијативни кеш брзине промашаја је већином представник капацитета брзине промашаја. Разлика је у томе што представљени подаци јесу из симулација које претпостављају LRU политике замене. Приказ капацитета промашене брзине захтева савршену политику замене, тј. пророчанство које гледа у будућност да се пронађе улаз кеша, који у ствари неће бити погодак.

Треба имати на уму да приближавање капацитету промашене брзине пада стрмо између 32 KB и 64 KB. Ово указује да benchmark има радни скуп од грубо 64 KB. CPU кеш дизајнер, који испитује овај benchmark, имаће јак подстицај у скупу кеша величине 64 KB, пре него 32 KB. Треба имати на уму, за овај benchmark, да никаква количина асоцијативности не може направити 32 KB кеш да извршава исто што и 64 KB 4-пута, или чак директно мапирани 128 KB кеш.

Коначно, треба имати на уму да између 64 KB и 1 MB постоји велика разлика између директно мапираних и потпуно асоцијативног кеша. Ова разлика је сукоб промашене брзине. Увид у сукобе промашених брзина показује да секундарни кеш користи много из високе асоцијативности.

Ова погодност је добро позната у касним 1980-им и раним 1990.им годинама, када CPU дизајнери нису могли да склопе велике кешеве на-чипу, и нису могли да добију довољно пропусног опсега за било кеш меморијске податаке било кеш таг меморије за примену високе асоцијативности у ван-чип кешевима. Очајно хаковање су покушали: MIPS R8000 који је користио скуп ван-чип посвећен таг SRAMs, који је био намењен таг компараторима и великим драјверима на меч линијама, како би се спровео 4 MB четворосмерни асоцијативни кеш. MIPS R10000 користи обичне SRAM чипове за таг. Таг приступ за оба пута узима два циклуса. За смањење латенције, R10000 претпоставља на који начин би кеш погодио на сваком приступу.

Адресне промене[уреди | уреди извор]

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

Виртуелна меморија захтева да процесор преводи виртуелне адресе које генеришу програм у физичкој адреси у главној меморији. Део процесора који ради овај превод је познат као меморијска управљачка јединица (memory management unit - MMU). Брз пут кроз MMU може да обави те преводе који су ускладиштени у преводу бафера TLB (translation lookaside buffer), који је кеш мапира из оперативне системске стране табеле, сегментног стола или оба.

За потребе ове дискусије, постоје три важне одлике адресног превода:

  • Латенција: физичка адреса је доступна неки пут из MMU, можда неколико циклуса, пошто је виртуелна адреса доступна из адресног генератора.
  • Псеудоним (Aliasing): више виртуелних адреса могу да се мапирају на једну физичку адресу. Већина процесора гарантује да ће се све исправке у тој једној физичкој адреси десити у програмском реду. Да би се ово гарантовало, процесор мора да осигура да се само једна копија физичке адресе налази у кешу у било ком тренутку.
  • Гранулација: виртуелни адресни простор је подељен на странице. На пример, 4 GB виртуелни адресни простор може бити исечен на 1048576 страница величине 4 KB, од којих сваки може самостално да се мапира.[NB 1] Може бити више подржаних величина страница; види виртуелну меморију за израду.

Историјска напомена: неки рани виртуелни меморијски системи су били веома спори, јер су захтевали приступ страници табеле (држана у главној меморији) пре сваког програмираног приступа главној меморији. Без кешева, ово ефективно смањује упола брзину машине. Први кеш хардвер који се користио у рачунарском систему није заправо податак или кеш инструкција, већ TLB.

Кеш се може поделити на 4 врсте, на основу тога да ли индекс или таг одговарају физичким или виртуелним адресама:

  • Физички индексирани, физички тагирани (PIPT) кешеви користе физичку адресу и за индекс и за таг. Иако је ово једноставно и избегава проблеме са псеудонимом, такође је споро, како се физичка адреса мора погледати (што би могло укључити TLB промашај и приступ главној меморији) пре него што се адреса може погледати у кешу.
  • Виртуелно индексирани, виртуелно тагирани (VIVT) кешеви користе виртуелну адресу и за индекс и за таг. Ова кеширана шема може да доведе до много брже претраге, јер MMU не треба прво консултовање одређивања физичке адресе за дату виртуелну адресу. Међутим, VIVT пати од псеудоним проблема, где неколико различитих виртуелних адреса могу да се односе на исту физичку адресу. Резултат је да ће таква адреса бити кеширана одвојено, што указује на исту меморију, која узрокује проблеме кохерентности. Други проблем је хомоним, где исте виртуелне адресе мапирају у неколико различитих физичких адреса. Није могуће направити разлику између ових мапирања, гледајући само у виртуални индекс, мада потенцијална решења укључују: испирање кеша након контекста прекидача, приморавајући адресне просторе да буду не-преклапајући, тагирање виртуелне адресе са адресним простором ID (ASID), или коришћење физичких тагова. Поред тога, постоји проблем који може мењати виртуелно-на-физичко мапирање, што би захтевало испирање кеш линије, како VAs више неће важити.
  • Виртуално индексирани, физички тагирани (VIPT) кешови користе виртуелну адресу за индекс и физичку адресу у тагу. Предност над PIPT је мања латенција, како се кеш линија може гледати паралелно са TLB преводом, међутим таг не може да се пореди док није доступна физичка адреса. Предност над VIVT је, да будући да таг има физичку адресу, и кеш може детектовати хомониме. VIPT захтева више таг бита, како индекс битови више не представљају исту адресу.
  • Физички индексирани, виртуални таг (PIVT) кешеви су само теоретски, јер у суштини би били бескорисни.[14]

Брзина овог рецидива (оптерећење латенције) је од кључног значаја за CPU перформансе, па тако већина модерних кешева нивоа-1 су виртуално индексирани, што барем дозвољава MMU-овом TLB проналажењу да се одвија паралелно са преузимањем података из кеш RAMa.

Али виртуелно индексирање није најбољи избор за све нивое кеша. Трошкови који се односе на виртуелни псеудоним расту са кеш меморије, а као резултат тога већина кешева нивоа-2 и већег су физички индексирани.

Кешеви историјски користе и виртуелне и физичке адресе за кеш таг, иако је сада виртуелно тагирање необично. Ако се TLB проналажење може завршити пре проналажења кеш RAМа, онда је физичка адреса доступна на време за таг поређење, и нема потребе за виртуелним тагирањем. Велики кешеви, онда, имају тенденцију да буду физички тагирани, а само мали, веома ниске латенције кешеви су виртуално тагирани. У недавним опште наменским CPUs, виртуелно таг означавање замењено је са vhints, као што је описано у наставку.

Проблеми хомонима и синонима[уреди | уреди извор]

Кеш који се ослања на виртуелно индексирање и тагирање постаје недоследно након што се иста виртуелна адреса преслика у различите физичке адресе (хомоним). Ово се може решити коришћењем физичке адресе за тагирање или чувањем адресног простора ID у кеш линији. Међутим, други од ова два приступа не помаже у решењу синоним проблема, где неколико кеш линија завршава чување података за исту физичку адресу. Писање у таквој локацији може ажурирати само једну локацију у кешу, остављајући друге са недоследним подацима. Овај проблем се може решити помоћу не-преклапајућег меморијског распореда за различите адресне просторе или иначе кеш (или њехов део) мора да буде испран када се мења мапирање.[тражи се извор]

Виртуални таг и hint[уреди | уреди извор]

Велика предност виртуалних тагова је да, за асоцијативне кешеве, они дозвољавају да таг настави меч пре него се изврши виртуелни физички превод. Међутим,

  • повезаност проби и избацивања представљају физичку адресу за акцију. Хардвер мора да има нека средства за претварање физичке адресе у кеш индекс, генерално гледано, помоћу физичких тагова, као и виртуелних тагова. За поређење, физички тагирани кеш не мора да држи виртуелне тагове, што је једноставније.
  • Када се виртуелно физичко мапирање брише из TLB, кеш улази са тим виртуелним адресама ће морати некако да се истерају. Алтернативно, ако се кеш улази дозвољени на страницама не мапирају помоћу TLB, онда ће ти улази морати да се истерају, када се на прави начин приступи тим страницама промене на страници табеле.

Такође, могуће је за обезбеђење оперативног система да се ниједан од виртуалних псеудонима истовремено налази у кешу. Оперативни систем даје ову гаранцију за спровођење обојења странице, што је описано у наставку. Неки рани RISC процесори (SPARC, RS/6000) узимају овај приступ. Он се није недавно користио, када су пали трошкови хардвера и избацивање виртуелног псеудонима и повећани су сложеност софтвера и казнене перформансе савршеног бојења странице.

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

Неки процесори (нпр. рани SPARCs) имају кешеве са виртуалним и физичким таговима. Виртуелни тагови се користе за начин селекције, а физички тагови се користе за одређивање погодка или промошаја. Ова врста кеша ужива предност латенције виртуално тагираног кеша, као и једноставан софтверски интерфеј физички тагираног кеша. Ово доноси додатне трошкове дуплирања тага. Такође, у току обраде промашаја, алтернативни начини кеш индексираних линија треба да буду истражени за виртуалне псеудониме и било које прилагодљиво избацивање.

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

Можда крајња редукција виртуалних hints се може наћи у Pentium 4 (Willamette и Northwood језгрима). У овим процесорима виртуелни hint је ефективно 2 бита, а кеш је на 4-начина асоцијативни скуп. Ефективно, хардвер одржава једноставну пермутацију из виртуелне адресе у кеш индексу, тако да ниједан CAM (content-addressable memory - садржајне-адресиране меморије) није потребан у избору једног правог од четири учитаних начина.

Бојење стране[уреди | уреди извор]

Велики физички индексирани кеш (обично секундарни кеш) покрећу проблем: оперативни систем, а не апликација управља страницама које се сударају једна са другом у кешу. Разлике у додели странице из једног програма, који се креће у следећи, доводи до разлике у обрасцима кеш судара, што може довести до веома великих разлика у програмском извођењу. Ове разлике могу да учине да он веома тешко добије конзистентно и поновљиво време за benchmark ток.

Да би се разумео проблем, треба да се замисли CPU са 1 MB физички индексираним директно мапираним кешом нивоа-2 и 4 KB виртуално меморијском страницом. Секвенцијалне физичке странице праве мапу у секвенцијалним локацијама у кешу све док се после 256 страна образац обавије около. Може да се обележи свака физичка страница са бојом од 0-255 за означавање где у кешу она може да иде. Места унутар физичких страница са различитим бојама не могу да се сукобе у кешу.

Програмер, који покушава да направи максималну корист од кеша, може да организује свој програмски приступ обрасцима, тако да само 1 MB података треба да буде кеширан у сваком тренутку, чиме се избегава капацитетни промашај. Али он такође треба да осигура да приступ обрасцима неће имати сукоб промашаја. Један од начина да се размишља о овом проблему јесте да се поделе виртуелне странице које програм користи и њима доделе виртуелне боје на исти начин као што су раније физичке боје биле додељиване физичким страницама. Програмер онда може да организује приступ обрасцима његовог кода, тако да не постоје две странице са истом виртуелном бојом у употреби у исто време. Постоји широка литература о таквим оптимизацијама (нпр. Loop nest optimization), која у великој мери долази из заједнице High Performance Computing (HPC).

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

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

Ако оперативни систем може да гарантује да свака физичка страница мапује (пресликава) у само једној виртуелној боји, онда нема виртуалних псеудонима, а процесор може да користи виртуално индексирани кеш, без потребе за додатним пробама виртуалних псеудонима током руковања промашајем. Алтернативно, O/S може да испразни страницу из кеша кад год се она мења од једне до друге виртуелне боје. Као што је већ поменуто, овај приступ је коришћен нешто раније за SPARC и RS/6000 дизаин.

Кеш хијерархија на модерним процесорима[уреди | уреди извор]

Memory hierarchy of an AMD Bulldozer server.

Модерни процесори имају више интерактивних кешева на чипу.

Рад партикуларних кеш меморија може бити потпуно одређен:[3]

  • Величином кеша
  • Величином кеш блока
  • Бројем блокова у скупу
  • Политиком замењивања кеша
  • Политиком уписивања у кеш (write-through или write-back)

Иако су сви кеш блокови у одређеном кешу исте величине и имају исту асоцијативност, типични кешеви „нижих-нивоа“ ("lower-level" cashs) (као L1 кеш) су мање величине, имају мање блокове, и мањи број блокова у скупу, док су кешеви „виших-нивоа“ ("higher-level" cashs) (као L3 кеш) већи, имају веће блокове и више блокова у скупу.

Специјализовани кешеви[уреди | уреди извор]

Доводна линија CPUs приступне моморије из више тачака у доводној линији: доношење упутства, превођење виртуелних у физичке адресе и доношење података (види classic RISC pipeline). Природни дизаин користи више кешева за сваку од ових ставки, тако да ни један физички ресурс не би морао да буде планиран да обавља две стари у доводној линији. Тако да се доводна линија природно завршава са најмање три раздвојена кеша (инструкција, TLB и податак), од којих је сваки специјализован са одређену улогу.

Жртвени кеш[уреди | уреди извор]

Жртвени кеш је кеш који се користи да чува избачене блокове од CPU кеша након замене. Жртвени кеш лежи између главног кеша и његових путева допуне, а чува само блокове који су избачени из главног кеша. Жртвени кеш је обично потпуно асоцијативан, и покушава да смањи број конфликтних промашаја. Већина често коришћених програма не захтева асоцијативно мапирање за све приступе. У ствари, само мали део меморијског приступа програма захтева високу асоцијативност. Жртвени кеш експлоатише ово својство тако што омогућава високу асоцајативност само овим приступима. Увео га је у употребу Norman Jouppi 1990.[15]

Интелова Crystal Well[16] варијанта Haswell процесора, опремљена са Интеловим Iris Pro GT3e интегрисаном графиком и 128MB eDRAM-а, увела је кеш нивоа-4 на чипу, који се користи као жртвени кеш за процесорски кеш новоа-3.[17]

Траг кеш[уреди | уреди извор]

Један од екстемнијих примера специјализације кеша је траг кеш који се јавља у микропроцесору Intel Pentiumа 4. Траг кеш је механизам за поваћавање протока за донос инструкција и смањења потрошње енергије (у случају Pentium 4) складиштењем трага инструкција које су већ биле преузете и декодиране.

Најранији запис за широку академску публику везан је за: Eric Rotenberg, Steve Bennett, и Jim Smith у њеиховом чланку "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching."[18]

Рана публикација је била дата у US patent 5381533, Alex Peleg and Uri Weiser of Intel Corp., "Dynamic flow instruction cache memory organized around trace segments independent of virtual address line" , Alex Peleg и Uri Weiser из Intel Corp. „Динамичан ток инструкција кеш меморије је организован око тока сегманта независног од виртуалне адресе линије“, наставак поднесене пријаве 1993. године, која је касније напуштена.

Траг кеш чува инструкције, или након што су биле декодоване, или јер су повучене. Генерално, инструкције се у групама додају траг кешу, представљајућу или базични блок или динамични траг инструкција. Динамични траг („пут трага“) садржи само инструкције чији се резултат користи, а елиминише инструкције након узетих грана (пошто се оне неизвршавају); динамични траг може бити састављен од више базичних блокова. Ово омогућава да упутства донесу јединици процесора неколико базичних блокова, без бриге на гране у извршењу тока.[19]

Траг линије се чува у траг кешу базираном на програмском бројачу прве инструкције у трагу и скупу предвиђених грана. Ово омогућава да се различити траг путеви чувају на истој адреси, од којих свака репрезентује другу грану на излазу. У инструкцијском стању доношења доводне линије, тренутни програмски бројач заједно са скупом грана предвиђања се проверава у траг кешу ради поготка. Ако постоји погодак, за преузимање се испоручује траг линија, која не мора да иде до регуларног кеша или до мемораије за те инструкције. Траг кеш наставља да храни донету јединицу све док се траг пут не заврши или док не дође до непредвиђених догађаја у доводној линији. Ако је промашај, нови траг почиње да се гради.

Pentium 4 траг кеш складишти микрооперације добијене декодирањем x86 инструкција, и такође омогућава функционисање микрооперација кеша. Имајући ово, следећи пут када је инструкција потребна, она не мора поново да се декодује у микрооператоре.

Микрооперациони (uop) кеш[уреди | уреди извор]

Микрооперациони кеш (uop Cache, UC) је специјализован кеш који чува микрооперације декодованих инструкција, које је примио директно од инструкцијског декодера или од инструкцијског кеша. Када се инструкција мора декодовати, uop кеш се проварава за његову декодовану форму која се поново користи ако је кеширана; ако није доступна, инструкција се декодује па тек онда кешира.

Један од најранијих радова који описује uop кеш као алтернативу са предњег краја за Intel P6 pпроцесор фамилију, је чланак из 2001. године "Micro-Operation Cache: A Power Aware Frontend for Variable Instruction Length ISA"[20]. Касније, Intel је укључио uop кеш у Sandy Bridge процесоре и у успешне микроархитектуре као Ivy Bridge и Haswell.[21]

Доношење завршено предекодираних инструкција елиминише потребу да се у више наврата декодира дужина променљиве комплексним инструкцијама у простије фиксиране-дужине микрооперације, а поједностављује процесе предвиђања, привлачења, ротирања и сврставања привучених инструкција. Uop кеш ефектно растерећује донос и хардвер за декодовање, тако смањује потрошњу енергије и побољшава снабдевање са предње стране декодованим микрооперацијама. Uop кеш такође повећава перфомансе зато што константније испоручује декодоване микрооперације на крај и елиминише разна уска грла у CPU's донешењу и логици декодовања.[20][21]

Uop кеш има доста сличности са траг кешом, иако је uop кеш много једноставнији и обезбеђује бољу потрошњу енергије. Главни недостатак траг кеша, води до његове потрошње енергије, односи се на хардверску сложеност потребну за њенгово хеуристичко одлучивање о кеширању и поновним коришћењем динамичко креираних трагова инструкције.[19]

Кешеви са више нивоа[уреди | уреди извор]

Други проблем је фундаментални компромис између кеш кашњења и брзине поготка. Већи кешеви имају бољу брзину погађања али веће кашњење. Да би се постигао компромис, многи рачунари користе кеш у више нивоа, са малим брзим кешом који је потпомогнут већим, споријим кешом.

Кешеви вишег нивоа оперишу тако што прво проверавају најмањи кеш нивоа-1 (L1); ако је погодак, процесор наставља великом брзином. Ако је мали кеш промашај, следећи већи кеш (L2) се проверава, и тако даље, пре него што се провери спољашња меморија.

Пошто латенција (кашњење) између главне меморије и брзе кеш меморије постаје све веће, неки процесори су почели да користе чак три нивоа кеша на чипу. На пример, Alpha 21164 (1995) је имао 1 до 64 MB ван-чипа L3 кеш; IBM POWER4 (2001) имао је ван-чипа L3 кеш од 32 MB по процесору, подељен између неколико процесора; Itanium 2(2003) имао је 6 MB уједињени L3 кеш на-чипу; Itanium 2 (2003) MX 2 Module обухвата два Itanium2 процесора са дељеним 64 MB L4 кеш меморијом на мулти-чип модулу који је пински компатибилан са Madison процесором; Intel-ов XeonMP производ под кодним називом "Tulsa" (2006) има 16 MB на-чипу L3 кеша који учествује између два процесорска језгра; AMD Phenom II (2008) има до 6 MB на-чипу уједињену L3 кеш меморију; и Intel Core i7 (2008) има 8 MB на-чипу уједињену L3 кеш меморију која је инклузивна, коју деле сва језгра. Корист од L3 кеша зависи од приступа апликацији за обрасце.

Коначно, на другом крају меморијске хијерархије, CPU регистрски фајл се може сматрати најмањим, најбржи кешом у систему, са посебним карактеристикама које су планиране у софтверу – обично помоћу компајлера, јер он додељује регистру да чува вредност преузету из главне меморије. (Посебно види петље оптимизације гнезда.) Регистарски фајлови понекад имају хијерархију: Cray-1 (око 1976) је имао осам адреса "A" и осам скаларних података "S" регистра који су генерално били употребљиви. Ту је био и скуп од 64 адреса "B" и 64 скаларних података "T" регистра којима је требало више времена за приступ, али су били бржи од главне меморије. "B" и "T" регисри су обезбеђени зато што Cray-1 није имао кеш податке. (Cray-1 је, међутим, имао кеш инструкције.)

Чипови са више језгара[уреди | уреди извор]

Када узмемо у разматрање чип са више језгара, поставља се питање да ли кешеви треба да буду подељени или локални за свако језгро. Имплементација дељеног кеша несумњиво уводи више жичаног вода и већу комплексност. Али тада, када имамо један кеш по чипу, радије него по језгру, значајно смањујемо потребни простор, и зато се може добити већи кеш. Обично се налази да је подељен L1 кеш непожељан пошто се повећава латенција, па тако ће свако језгро радити моного спорије него јендо-језгрени чип. Али тада, за највиши ниво (последњи који се зове пре приступања меморији), из више разлога пожељно је да се има глобални кеш. На нпример, осмо-језгарни чип са три новоа може да има L1 кеш за свако језгро, и L3 дељени кеш са свим језгарима, и са L2 средњим кешом, нпр. један за сваки пар језгара.

Подељени наспрам уједињених[уреди | уреди извор]

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

Ексклузивни наспрам инглузивног[уреди | уреди извор]

Кеш са више нивоа уводи нова дизајнерска решења. На пример, у неким процесорима, сви подаци у L1 кешу морају такође бити негде у L2 кешу. Ови кешеви се зову строго инклузивни. Други процесори (као AMD Athlon) имају ексклузивни кеш – гарантује се да су подаци у највише једном кешу L1 или L2, никада у оба. Неки други процесори (као Intel Pentium II, III и 4) не захтевају да подаци у L1 кешу буду и у L2 кешу, иако се то често може учинити. Не постоји јединствено прихваћено име за ову средњу политику.

Предност ексклузивног кеша је да складишти више података. Ова предност је већа када је ексклузивни L1 кеш упоредив са L2 кешом, а умањује се ако је L2 кеш неколико пута већи од L1 кеша. Када су L1 промашај и L2 погодак на приступу, погођена кеш линија у L2 кешу се мења са линијом у L1 кешу. Овај процес размењивања задаје мало више посла од обичног копирања из L2 у L1, а то је оно шта инклузивни кеш ради.

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

Још једна мана инклузивног кеша је та да већи кеш користи веће кеш линије, који смањују величину тага на секундарном кешу. (Ексклузивни кеш захтева да оба кеша имају кеш линије исте величине, тако да би се линије могле заменити приликом L1 промашаја и L2 поготка). Ако је секундарни кеш за ред величине веће од примарног, а кеш подаци за један ред величине већи од кеш тага, овај сачувана област тага може бити упоређиван у инкременталној области која је потребна да складишти L1 кеш податке у L2.

Пример: К8[уреди | уреди извор]

Да би илустовали специјализовани кеш у више нивоа, овде је приказана кеш хијерархија К8 језгара у AMD Athlon 64CPU.[22]

Пример К8 кеш хијерархије

К8 има 4 специјализована кеша: инструкциони кеш, инструкциони TLB, TLB за податке, и кеш за податке. Сваки од ових кешева је специјализован:

  • Инструкциони кеш чува копије 64 бајтне линије меморије, и преузима 16 бајта сваког циклуса. Сваки бајт у овом кешу се чува у десет бита пре него 8, са екстра битовима који обележавају границе инстрикција (пример предешифровања). Кеш има само равноправну заштиту пре него ECC, зато што је заштита равноправности мања и сви оштећени подаци се могу заменити новим подацима денешеним из меморије (која увек има актуелне копије инструкција).
  • Инструкциони TLB чува копије улаза табела странице (PTEs). Сваки циклус доношења инструкција има своју виртуелну адресу која се преводи кроз TLB у физичку адресу. Сваки улаз је са или 4 или 8 бајта у меморији. Пошто К8 има променљиву величину стране, сваки од TLB-ова се дели на два дела, један чува PTEs које мапира 4КВ, а друга чува PTEs која мапира стране од 4МВ или 2МВ. Дељење омогућава потпуно једноставну асоцијативност сваког равноправног кола у сваком делу. Оперативни систем мапира различите делове виртуелне адресе са различитом величином PTEs.
  • TLB за податке има две копије које чувају идентичне улазе. Две копије дозвољавају два приступа подацима по циклусу ради превођења витуелне адресе у физичку. Као инструкциони TLB, овај TLB за податке је такође подељен на два типа улаза.
  • Кеш за податке чува копије 64 бајтних линија меморије. Он је подељен на 8 делова (од којих сваки чува 8КВ) и може донети податке од 8 бајта сваког циклуса, све док су ти подаци у различитим деловима. Постоје две копије тага, зато што је свака линија од 64 бајта раширена међу 8 делова. Свака копија тага ради са једним од два приступа по циклусу.

К8 такође има кешеве са више нивоа. Постоји други ниво инструкција и података TLB, које складиште само PTEs који мапирају 4КВ. Оба кеша за инструкције и податаке, и разни TLB, могу да се попуне из великог L2 кеша. Овај кеш је ексклузиван за L1 инструкцију и за кеш податке, што значи да било која 8 бајтна линија може бити само у једном од L1 инструкцијског кеша, L1 кеша података или L2 кеша. То је, међутим могуће за линију у кеш подацима да имају PTE, који је такође у једном од TLB – оперативни систем је одговоран за чување TLB-а кохерентним избацивањем његових делова када се обнови табела странице у меморији.

К8 такође кешира информације које се никада не чувају у меморији - предвиђање информација. Ови кешеви нису приказани у горњем дијаграму. Као што је уобичајено за ову класу процесора, К8 има прилично сложено предвиђање гранања, са табелама које помажу у предвиђању да ли су те гране преузете и друге табеле која предвиђају циљеве грана и скокове. Неке од ових информација су повезане са инструкцијама, инструкцијским кешом нивоа-1 и јединственим секундарним кешом.

К8 користи занимљив трик за складиштење предвиђених информација са упутствима у секундарној кеш меморији. Линије у секундарној кеш меморији су заштићене од случајних корупција података (нпр. штрајк алфа честица) од стране ECC или равноправности, у зависности од тога да ли су те линије избачене из података или из кешева основних инструкција. Пошто равноправност кода узима мање битова него ECC код, линије из инструкцијског кеша имају неколико резервних битова. Ови битови се користе за кеширање превиђеног гранања информација у вези са овим инструкцијама. Чист резултат је то да предвиђач гранања има већу ефективну табелу историје, па има и бољу прецизност.

Више хијерархије[уреди | уреди извор]

Други процесори имају и друге врсте предсказивача (нпр чување-у-оптерећеном бајпас предсказивачу у DEC Alpha 21264) и разне специјализоване предсказиваче који ће вероватно напредовати у будућим процесорима.

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

К8 чува инструкције и податке у кешевима кохерентним у хардверу, што значи да ће чување у инструкцији, која пажљиво прати сачувану инструкцију, мењати ту следбену инструкцију. Други процесори, попут оних из Alpha и MIPS породице, ослањали су се на софтвер, да би инструкције кеша остале кохернтне. Чување не гарантује да ће се појавити у инструкцијском току све док програм позива оперативни систем да обезбеди кохерентност објекта.

Имплементација[уреди | уреди извор]

Кеш читања су најчешће процесорске операције које трају више од једног циклуса. Програм за време извршења има тенденцију да буде веома осетљив на латенцију кеш поготка новоа-1. Много напора при дизајну, а често и енергија и силикон, су потребни да би кеш био што је могугће бржи.

Најједноставнији кеш је практично индексиран директно-мапиран кеш. Виртуелна адреса се израчунава помоћу сабирача, релелевантни делови екстраховане адресе се користе за индексирање SRAM, који враћа учитане податке. Податак је бајтовски поравнат у бајт померачу, а одатле је премошћен са следећом операцијом. Нема потребе за било какву таг проверу у унутрашњој петљи - у ствари, тагови се не морају ни читати. Касније у припреми, али пре него што се учитана инструкција повуче, таг за учитане податке мора да се прочита, и проверава у односу на виртуелну адресу, како би се уверили да је кеш погодак. На промашај, кеш се ажурира са траженом кеш линијом и „доводна линија“ се рестартује.

Асоцијативни кеш је компликованији, јер се неки облици тага морају прочитати да би се одредио који улазак кеша треба изабрати. Н-пут скупа-асоцијативног кеша нивоа-1 обично чита све Н могуће тгагове и Н податке у паралели, и тада изабира податке који су прикладно удружени са тагом. Кешеви нивоа-2 неки пут уштеде енергију читајући прво тагове, тако да се само један елемент података чита из података SRAM.

Прочитај део за асоцијативни кеш на 2 начина

Дијаграм десно је превиђен да разјасни начин како се користе различита поља адреса. Адресни бит 31 је најзначајнији, бит 0 је најмање значајан. Дијаграм приказује SRAM, индексирање, и вишеструкост за 4КВ, 2-начина асицијативног скупа, вируелно индексирање и виртуелни тагирани кеш са 64 бајт (В) линије, 32-битну ширину читања и 32-битну виртуелну адресу.

Пошто је кеш 4КВ и има 64 В линје, постоји само 64 линије у кешу, а ми читамо две истовремено из Tag SRAM који има 32 реда, сваки са паром од 21 бит тага. Иако свака функција виртуелних адресних битова 31 кроз 6, може да се користи за индексирање тага и података SRAM, најједноставније је да се користе најмање важни битови.

Слично, пошто је кеш 4 КВ и има 4В читајућих путања и чита два пута за сваки приступ, Data SRAM је са 512 реда са по 8 бајтова ширине.

Модернији кеш може да буде 16 КВ, 4-пута асоцијативни скуп, виртуално индексиран, виртуално наговештен, и физички тагован, са 32 В линије, 32 битне ширине читања и са 36 битне физичке адресе. Враћање пута читања за такав кеш изгледа врло слично горњем путу. Уместо тага, чита се vhints, и усмерава се против подскупа виртуалне адресе. Касније у доводној линији, виртуална адреса се преводи у физичку адресу помоћу TLB, и чита се физички таг (само један, како vhint снабдева који пут кеша је за читање). Коначно физичка адреса се пореди у физичком тагу да се утврди да ли је дошло до погодка.

Неки SPARC дизајни побољшали су брзину својих L1 кешева за нека врата кашњења рушењем виртуелних адреса сабирача у SRAM декодерима. Погледајте Укупни адресирани декодер.

Историја[уреди | уреди извор]

Рана историја кеш технологије је уско повезана са проналаском и коришћењем виртуелне меморије. Због оскудице и цене полу-проводничких меморија, рани главни оквири рачунара 1960. године користили су сложену хијерархију физичке меморије, мапиране на равну вируелну меморију, коју користе програми. Технологија меоморије обухвата полу-проводнике, магнетна језгра, добош и диск. Програми виде и користе виртуелну меморију и биће равни и кеширање ће се користити за доношење података и инструкција у најбржој меморији испред процесорског приступа. Обимне студије су урађене ди би се опимизовала величина диска. Опимална величина зависи од коришћења програмског језика, Најмање кеша је требало за Algol док су Фортран и Кобол користили највише кеша.

У раним данима технилогије микрорачунара, приступ меморији је био мало спорији у односу на приступ регистрима. Али од 1980. године[23] разлике у перфомансама између процесора и меморије су расле. Микропроцесори су напредовали много брже него меморија, поготово у фреквенци рада, па су тако меморијске перформансе постале уско грло. Иако је технички могуће да имамо све главне меморије брзе као процесор, узет је више економски одржив пут: коришћење доста меморија мале брзине, али и увођење и мало брже кеш меморије да би се смањио јаз измећу перфоманси. Ово је за ред величине дало веће капацитете - за исту цену - са само мало лошијим заједничким перфомансама.

Прва TLB имплементација[уреди | уреди извор]

Прво документовано коришћење TLB-а били су на GE 645[24] и IBM 360/67,[25]; оба су користили асоцијативну меморију као TLB.

Први кеш података[уреди | уреди извор]

Прва документована употреба кеша за податке је била на IBM System/360 Model 85.[26]

У x86 микропроцесору[уреди | уреди извор]

Када је микропроцесор x86 достигао радни такт од 20 MHz и преко у 386, мала количина брзе кеш меморије је почела да се појављује у системима ради повећања перфоманси. Ово је било зато што се DRAM користио за главну меморију а имао је значајно кашњење, до 120 ns, као и циклус освежавања. Кеш је био изграђен од скупљег, али знатно бржег, SRAM, који је тада имао кашњење око 10 ns. Рани кешеви су били спољни у процесору и обично су се налазили на матичној плочи у виду осам или девет DIP уређаја, пласираних у подножју (sockets) да омогуће кешу да буде додатна опрема или карактеристика надоградње.

Неке верзије Intel 386 процесора су могле да подрже од 16 до 64KB спољњег кеша.

Са 486 процесором, кеш од 8KB је директно интегрисан у процесор. Овај кеш је назван ниво-1 или L1 кеш, да би се разликовао од споријег на матичној плочи или ниво-2 (L2) кеш. Ови кешеви на матичној плочи су били много већи, најчешће 256 KB. Популарност кешева на матичној плочи се наставила кроз еру Pentium MMX, али је направљен од застарелог уведеног SDRAM и расла је неједнакост између магистрале такта и такта на процесору, који је узроковао да кешеви на матичној плочи буду само мало бржи од главне меморије.

Следећи развој у кеш имплементацији у x86 микропроцесорима почиње са Pentium Pro, који је донео секундаране кеш меморије на истом пакету као микропроцесор, који ради на истој фреквенији као микропроцесор. Кешеви на матичној плочи уживају у продуженој популарности захваљујући AMD K6-2 и AMD K6-III процесорима, који су још увек користили древни Сокет 7, који је раније користио Intel са кешевима на матичној плочи. K6-III је је укључивао 256 KB на чипу кеша L2 и искористио је предност кеша на матичној плочи као ниво-3, назван L3 (производиле су се матичне плоче са кеш меморијом до 2 MB). Када је Сокет 7 застарео, кеш меморије на матичним плочама су нестале са x86 система.

Кеш меморије од три нивоа су се поново почели користити увеђењем процесора са више језгара, где је L3 кеш био додат на процесорски чип. Постало је уобичајено да укупна величина кеша буде постепено већа у новијим генерацијама процесора, а од скора (од 2011. године) није неуобичајено наћи на нивоу-3 неколико десетина мегабајта.[27] Овај тренд изгледа да ће бити настављен и у будућности.

Intel је представио ниво-4 кеш на-чипу у Haswell микроархитектури. Crystal Well [16] Haswell процесори, опремељени са GT3e варијантом Intel's интегрисане Iris Pro графике, ефикасно имају 128MB уграђен DRAM (eDRAM) на истом чипу. Овај L4 кеш је динамички дељен између на-чипу GPU и CPU, и служи као жртвени кеш за L3 кеш процесора.[17]

Тренутна истраживања[уреди | уреди извор]

Ранији дизајни кеша су се у потпуности фокусирали на директини трошак за кеш меморију и RAM и просечне брзине извршавања. Новији кеш дизајни такође разматрају енергетску ефикасност, толеранцију грешака и друге циљеве.[28]

Постоји неколика алата на располагању за рачунарске архитектуре да помогну у истраживању компромиса између: времена циклуса кеша, енергије и простора. Ови алати укључују и отворени-изворни CACTI кеш симулатор [29] и отворени-изворни SimpleScalar симулатор инструкцијског скупа.

Мулти-портован кеш (више-портован кеш)[уреди | уреди извор]

Мулти-портован кеш је кеш који може извршити више од једног захтева у исто време. Приликом приступа традиционалном кешу обично се користи једна меморијска адреса, док је код мулти-портованог кеша могуће тражити N адреса инстовремено – где је N број портова који су повезани преко процесора и кеша. Предност овога је да доводна линија процесора може приступити меморији из различитих фаза у својој доводној линији. Још једна предност је у томе што омогућава концепт супер скаларних процесора кроз различите нивое кеша.

Види још[уреди | уреди извор]

Напомене[уреди | уреди извор]

  1. ^ The very first paging machine, the Ferranti Atlas[12][13] had no page tables in main memory; there was an associative memory with one entry for every 512 word page frame of core.

Референце[уреди | уреди извор]

  1. ^ Hennessy & Patterson 2012, стр. 120
  2. ^ Patterson & Hennessy 2008, стр. 484
  3. ^ а б в Gene Cooperman. "Cache Basics", 2003. [1]
  4. ^ Ben Dugan. "Concerning Caches". 2002. [2]
  5. ^ Cragon 1996, стр. 209
  6. ^ IEEE Xplore - Phased set associative cache design for reduced power consumption. Ieeexplore.ieee.org (2009-08-11). Приступљено 2013-07-30.
  7. ^ André Seznec (1993). „A Case for Two-Way Skewed-Associative Caches”. ACM Sigarch Computer Architecture News. 21 (2): 169—178. doi:10.1145/173682.165152. Приступљено 13. 12. 2007. 
  8. ^ André Seznec. „A Case for Two-Way Skewed-Associative Caches”. Приступљено 13. 12. 2007. 
  9. ^ а б * "Advanced Caching Techniques" Архивирано на сајту Wayback Machine (7. септембар 2012) by C. Kozyrakis
  10. ^ * Micro-Architecture "Skewed-associative caches have ... major advantages over conventional set-associative caches."
  11. ^ „Cache performance of SPEC CPU2000”. Cs.wisc.edu. Приступљено 2. 5. 2010. 
  12. ^ Sumner, F. H.; Haley, G.; Chenh, E. C. Y. (1962). „The Central Control Unit of the 'Atlas' Computer”. Information Processing 1962. IFIP Congress Proceedings. Proceedings of IFIP Congress 62. Spartan. 
  13. ^ Kilburn, T.; Payne, R. B.; Howarth, D. J. (1961). „The Atlas Supervisor”. Computers - Key to Total Systems Control. Conferences Proceedings. 20 Proceedings of the Eastern Joint Computer Conference Washington, D.C. Macmillan. стр. 279—294. 
  14. ^ „Understanding Caching”. Linux Journal. Приступљено 2. 5. 2010. 
  15. ^ Jouppi, N.P. (1990). „Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers”. [1990] Proceedings. The 17th Annual International Symposium on Computer Architecture. стр. 364–373. ISBN 0-8186-2047-1. S2CID 6157765. doi:10.1109/ISCA.1990.134547. 
  16. ^ а б „Products (Formerly Crystal Well)”. Intel. Приступљено 15. 9. 2013. 
  17. ^ а б „Intel Iris Pro 5200 Graphics Review: Core i7-4950HQ Tested”. AnandTech. Приступљено 16. 9. 2013. 
  18. ^ Rotenberg, E.; Bennett, S.; Smith, J.E. (1996). Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching. стр. 24—34. ISBN 0-8186-7641-8. S2CID 221908866. doi:10.1109/MICRO.1996.566447. 
  19. ^ а б Gu, Leon; Dipti Motiani (2003). „Trace Cache” (PDF). Приступљено 6. 10. 2013. 
  20. ^ а б Solomon, Baruch; Mendelson, Avi; Orenstein, Doron; Almog, Yoav; Ronny Ronen (2001). „Micro-Operation Cache: A Power Aware Frontend for Variable Instruction Length ISA” (PDF). ISLPED'01: Proceedings of the 2001 International Symposium on Low Power Electronics and Design (IEEE Cat. No.01TH8581). Intel. стр. 4—9. ISBN 1-58113-371-5. S2CID 10934861. doi:10.1109/LPE.2001.945363. Приступљено 6. 10. 2013. 
  21. ^ а б Anand Lal Shimpi (5. 10. 2012). „Intel's Haswell Architecture Analyzed”. AnandTech. Приступљено 20. 10. 2013. 
  22. ^ „AMD K8”. Sandpile.org. Архивирано из оригинала 15. 5. 2007. г. Приступљено 2. 6. 2007. 
  23. ^ „The Processor-Memory performance gap”. acm.org. Архивирано из оригинала 27. 4. 2012. г. Приступљено 8. 11. 2007. 
  24. ^ GE (јануар 1968). GE-645 System Manual (PDF). Архивирано из оригинала (PDF) 14. 03. 2012. г. Приступљено 04. 11. 2013. 
  25. ^ IBM (фебруар 1972). IBM System/360 Model 67 Functional Characteristics (PDF). Third Edition. GA27-2719-2. Архивирано из оригинала (PDF) 14. 03. 2012. г. Приступљено 04. 11. 2013. 
  26. ^ IBM (јун 1968). IBM System/360 Model 85 Functional Characteristics (PDF). SECOND EDITION. A22-6916-1. Архивирано из оригинала (PDF) 07. 09. 2011. г. Приступљено 04. 11. 2013. 
  27. ^ „Intel® Xeon® Processor E7 Family”. Intel. Приступљено 10. 10. 2013. 
  28. ^ "Chip Design Thwarts Sneak Attack on Data" by Sally Adee 2009 discusses "A novel cache architecture with enhanced performance and security" [3] [4] Архивирано на сајту Wayback Machine (6. март 2012) by Zhenghong Wang and Ruby B. Lee: (abstract) "Caches ideally should have low miss rates and short access times, and should be power efficient at the same time. Such design goals are often contradictory in practice."
  29. ^ „CACTI”. Hpl.hp.com. Архивирано из оригинала 21. 11. 2009. г. Приступљено 2. 5. 2010. 

Литература[уреди | уреди извор]