thumb|Schéma použitia vyrovnávacej pamäte procesora
Rýchla vyrovnávacia pamäť procesora je rýchla vyrovnávacia pamäť (skratka: RVP; angl. cache) používaná procesorom počítača na zníženie priemernej doby prístupu do hlavnej pamäte. Vyrovnávacia pamäť je menšia a rýchlejšia pamäť, ktorá ukladá kópie najčastejšie používaných dát hlavnej pamäte. V prípade, že sa častejšie využívajú kópie dát z vyrovnávacej pamäte procesora ako z hlavnej pamäte, je priemerná latencia pamäťového prístupu bližšia latencii vyrovnávajúcej pamäte ako latencii hlavnej pamäte.
Diagram napravo zobrazuje dve pamäte – hlavnú pamäť a rýchlu vyrovnávaciu pamäť. V oboch má každé pamäťové miesto priradenú hodnotu (riadok rýchlej vyrovnávacej pamäte, angl. cache line), ktorej veľkosť sa pohybuje podľa rôznych konštrukčných návrhov od 8 do 512 bajtov. Veľkosť riadku RVP je zvyčajne väčšia ako veľkosť bežného prístupu, ktorý sa pohybuje od 1 do 16 bajtov. Každé pamäťové miesto v oboch pamätiach má index – jedinečné číslo určené na označenie tohto miesta. Index pamäťového miesta v hlavnej pamäti sa nazýva adresa. Každé miesto v rýchlej vyrovnávacej pamäti má navyše štítok, ktorý obsahuje index hodnoty hlavnej pamäte, ktorá bola uložená v RVP. V rýchlej vyrovnávacej pamäti procesora sú tieto záznamy nazývané riadkami alebo blokmi RVP.
Keď chce procesor čítať alebo zapisovať na pamäťové miesto v hlavnej pamäti, najprv skontroluje, či je dané pamäťové miesto v cache. To sa dosiahne porovnaním adresy pamäťového miesta so všetkými štítkami v cache, ktoré môžu danú adresu obsahovať. Ak procesor nájde dané pamäťové miesto v cache, hovoríme tomu cache hit, inak hovoríme o cache miss. Po zistení, že sa požadované dáta nachádzajú vo vyrovnávacej pamäti je ešte potrebné overiť ich platnosť, ktorú udáva tzv. valid bit. V prípade cache hitu procesor okamžite prečíta, alebo zapíše údaje do cache line. Pomer prístupov, ktorých výsledkom bol cache hit ku cache miss, nazývame hit rate a je meradlom efektívnosti cache.
V prípade cache miss, väčšina druhov cache alokuje nový záznam, ktorý obsahuje práve zmeškaný tag a kópiu dát z pamäte. Potom je možné sa odkázať na nový záznam ako v prípade cache hit. Cache miss je pomalý, pretože je potrebné preniesť dáta z hlavnej pamäte. Tento prenos spôsobuje zdržanie preto, že hlavná pamäť je omnoho pomalšia ako cache pamäť.
Niektoré detaily fungovania Aby sa vytvorilo miesto pre nový záznam v prípade cache miss, cache musí vo všeobecnosti "vyhodiť" jeden z existujúcich záznamov. Heuristika, ktorú na to používa na toto vyhodenie, sa nazýva politika nahrádzania (angl. replacement policy). Fundamentálny problém každej politiky nahrádzania je predpovedať, ktorý existujúci záznam v cache bude v budúcnosti použitý s najmenšou pravdepodobnosťou. Predpovedanie budúcnosti je náročné, obzvlášť pre hardvérové cache, ktoré musia byť implementované obvodmi, takže existuje množstvo politík nahrádzania a žiaden dokonalý spôsob, ako medzi nimi vybrať. Jedna z populárnych politík nahrádzania, LRU (Least Recently Used), nahrádza najdlhšie nepoužitý záznam.
Keď sa dáta zapíšu do cache, je tiež potrebné ich niekedy zapísať do hlavnej pamäte. Časovanie tohto zápisu sa riadi tzv. politikou zapisovania (write policy). Vo write-through cache spôsobí každý zápis do cache zápis do hlavnej pamäte. Vo write-back cache sa zápisy nezrkadlia v pamäti okamžite. Namiesto toho sa cache sleduje, ktorých miesta sa prepísali (tieto miesta sa označia ako špinavé - príznak dirty bit). Dáta z týchto miest sa zapíšu do hlavnej pamäte, keď sa dáta vyhadzujú z cache. Z tohto dôvodu cache miss vo write-back cache často bude vyžadovať dva prístupy do pamäte.
Sú aj kompromisné politiky. Cache môže byť write-through, ale zápisy sa môžu v zápisovom fronte držať dočasne, zvyčajne tak, aby sa viacnásobné zápisy vykonali súčasne (čo môže zlepšiť využitie zbernice).
Dáta v hlavnej pamäti, ktoré sú cacheované môžu byť časom nahradené inými entitami, čo znamená, že dáta v cache "vychladli" (angl. out-of-date alebo stale). A zasa keď CPU aktualizuje dáta v cache, kópie týchto dát v iných cache vychladnú. Komunikačné protokoly medzi správcami cache, ktoré slúžia na udržiavanie konzistencie dát sa nazývajú koherenčné protokoly.
Záleží aj na čase, ktorý je potrebný na prinesenie dáta z pamäte (latencia čítania), pretože CPU často počas čakania na dáta nebude mať čo robiť. Tento stav CPU sa nazýva stall. Ako sa novšie CPU neustále zrýchľujú, stalls z dôvodu cache miss predstavujú stále väčšie straty výpočtového potenciálu; moderné CPU sú schopné vykonať stovky inštrukcií v čase, ktorý je potrebný na prinesenie jediného dáta z pamäte. Na zamestnanie CPU v tomto čase boli vyvinuté rozličné techniky. CPU s Out-of-order (napr. Pentium Pro a novšie návrhy od Intelu) sa pokúšajú vykonávať nezávislé inštrukcie nasledujúce po inštrukcii, ktorá čaká na cache miss dáta. Pentium 4 používa simultánny multithreading (v terminológii Intelu Hyper Threading), aby dovolil druhému programu používať CPU kým prvý čaká na dáta z hlavnej pamäte..
Asociativita Takže politika nahrádzania rozhoduje, kde do cache sa uloží kópia určitého záznamu z hlavnej pamäte. Ak necháme voľbu, do ktorého záznamu cache sa kópia uloží, na politike nahrádzania, nazývame takúto cache plne asociatívna (fully associative). Opačným extrémom je, keď každý záznam z hlavnej pamäte môže ísť iba na jediné miesto v cache—cache sa mapuje priamo (direct mapped). Mnohé cache implementujú kompromis a označujú sa ako množinovo asociatívne (set associative). Napríklad dátová cache prvej úrovne (L1) v AMD Athlon je dvojcestne množinovo asociatívna (2-way set associative), čo znamená, že každý záznam z hlavnej pamäte môže byť cacheovaný v ktoromkoľvek z dvoch miest v dátovej cache prvej úrovne.
Ak každá z adries v hlavnej pamäti môže byť cacheovaná na dvoch adresách v cache, logickou otázkou je na ktorých dvoch? Najjednoduchšia a najbežnejšia schéma, zobrazená na diagrame vpravo hore, je použiť najnižšie bity indexu adresy hlavnej pamäte ako index do cache pamäte a mať dvojcestné záznamy pre každý index. Dobrou vlastnosťou tejto schémy je, že štítky uložené v cache nemusia obsahovať časť adresy hlavnej pamäte, ktorá je špecifikovaná indexom cache. Keďže štítky cache majú menej bitov, zaberajú menej miesta a je možné ich rýchlejšie čítať a porovnávať.
Boli navrhnuté aj iné schémy ako skewed cache, kde je index pre cestu 0 priamy, ale index pre cestu 1 je daný hash funkciou. Dobrá hash funkcia má vlastnosť, že adresy, ktoré sú v konflikte s priamym mapovaním nie s v konflikte s hash funkciou, a tak je menej pravdepodobné, že program bude trpieť neočakávaným množstvom konfliktných cache misses z dôvodu patologického prístupového vzoru.
Asociativita je obetovaním niečoho na úkor niečoho iného. Ak je desať miest, kde politika nahrádzania môže umiestniť nový záznam, potom ak sa kontroluje, či záznam je v cache, je potrebné skontrolovať všetkých desať miest. Kontrola viacerých miesť stojí výpočtový výkon, pamäťové miesto a strojový čas. Na druhej strane cache s väčšou asociativitou trpia menej cache missess (pozri konfliktné cache missess dolu). Základným pravidlom je, že zdvojenie asociativity má približne rovnaký efekt na hit rate ako zdvojenie kapacity cache, od jednocestnej (priamo mapovanej) po štvorcestnú. Zvýšenie asociativity nad štvorcestnú má omnoho menší dopad na hit rate a vo všeobecnosti sa robí z iných dôvodov (pozri virtual aliasing dolu).
Jednou z výhod priamo mapovanej cache je, že umožňuje jednoduché a rýchle špekulácie. Keď sa raz vypočíta adresa, cache index, ktorý mohol byť kópiou údaju je známy. Je možné tento záznam cache prečítať a procesor môže pokračovať v práci s údajom predtým, než sa skončí kontrola, či sa štítok v skutočnosti zhoduje s požadovanou adresou.
Princíp, že procesor môže používať cacheované dáta predtým ako sa skončí kontrola zhodnosti štítku, je možné aplikovať aj na asociatívne cache. Podmnožinu štítku zvanú pomôcka (hint), je možné použiť paralelne s kontrolou celého štítku. Technika pomôcky funguje najlepšie, keď sa používa v kontexte prekladu adresy tak, ako je vysvetlené nižšie.
Povinné, kapacitné a konfliktné cache misses Bolo vykonané množstvo analýz správania cache za účelom nájdenia najlepšej veľkosti, asociativity, veľkosti bloku atď. Sekvencie pamäťových referencií produkovaných benchmarkovými programami sa ukladajú ako address traces. Následné analýzy simulujú množstvo rôznych možných návrhov cache na týchto dlhých address traces. Zisťovanie toho, do akej miery toto množstvo premenných ovplyvňuje hit rate môže byť veľmi mätúce. Jedným z významných prispievateľov tejto analýzy je Mark Hill, ktorý rozdelil cache misses do troch kategórií:
Povinné cache misses sú tie, ktoré sú spôsobené referenciou na údaj. Veľkosť cache a asociativita neovplyvnia množstvo povinných cache misses. Prefetching ako aj veľkosť blokov (čo je forma prefetchingu) môžu pomôcť.
Kapacitné cache misses sú tie, ktorými bude trpieť cache danej veľkosti nezávisle od asociativity či veľkosti bloku. Krivka kapacitnej miss rate verzus veľkosť cache dáva určitú predstavu o lokalite určitého referenčného toku.
Konfliktné cache misses sú tie, ktorým sa dalo vyhnúť, keby nebola cache vyhodila záznam skôr. Konfliktné cache misses sa dajú ďalej rozdeliť na mapping misses, ktoré sú pri danej asociativite nevyhnutné, a replacement misses, ktoré sú spôsobené danými príležitostnými nákladmi politiky nahrádzania.
thumb|Miss rate verzus veľkosť cache na celočíselnej časti SPEC CPU2000
Graf vpravo sumarizuje výkon cache na celočíselnej časti benchmarkov SPEC CPU2000, ako ich namerali Hill a Cantin . Tieto benchmarky majú reprezentovať druh záťaže, ktorý môže mať pracovná stanica v danom dni. Na tomto grafe môžeme vidieť rozličné vplyvy troch druhov cache misses.
Ďalej napravo pri veľkosti cache označenej ako "Inf", máme povinné cache misses. Ak chceme zlepšiť výkon stroja pri SpecInt2000, zväčšenie veľkosti cache nad 1MB je zbytočné. Taký pohľad nám dávajú povinné cache misses.
Miss rate plne asociatívnej cache je tu takmer reprezentatívnym príkladom kapacitnej miss rate. Rozdiel je, že prezentované údaje sú zo simulácií používajúcich politiku nahrádzania LRU. Zobrazenie kapacitnej miss rate by vyžadovalo dokonalú politiku nahrádzania, t. j. predvídanie budúcnosti a nájdenie záznamu cache, ktorý nebude potrebný.
Všimnite si, že naša aproximácia kapacitnej miss rate strmo klesá medzi 32 KB a 64KB. To indikuje, že benchmark používa pracovnú vzorku s veľkosťou približne 64KB. Návrhár cache CPU skúmajúci tento benchmark bude mať silné nutkanie nastaviť veľkosť cache skôr nad 64KB ako pod túto veľkosť. Všimnite si, že pri tomto benchmarku nemôže žiadna zmena asociativity pomôcť 32KB cache k rovnako dobrým výsledkom ako má štvorcestná 64KB cache či priamo mapovaná 128KB cache.
Nakoniec si všimnite, že medzi 64KB a 1MB je veľký rozdiel medzi priamo mapovanými a plne asociatívnymi cache. Tento rozdiel je konfliktná miss rate. V roku 2004 sú sekundárne cache v rámci čipu v tomto rozsahu, pretože menšie cache sú dostatočne rýchle na to, aby boli primárnymi cache a väčšie cache sú príliš veľké na to, aby ich bolo možné ekonomicky produkovať na čipe (Itanium 2 má 9MB level-3 cache na čipe, najväčšiu aká sa predáva v roku 2004). Poučenie z pohľadu na konfliktné miss rates je, že sekundárnym cache veľmi prospieva asociativita.