- sluzi k skrateniu pristupovej doby do hlavnej pamate
- pristupova doba do cache je podstatne nizsia ako pre hlavnu pamat
- jej kapacita je podstatne nizsia, nez kapacita hlavnej pamate
- prvy pristup k datam je dan pristupovou dobou hlavnej pamate, ale kazdy dalsi pristup k tym istym datam, je dan pristupovou dobou skrytej pamate
- je transparentna - z funkcneho hladiska procesor nevie o cache
- obsahuje kopie dat hlavnej pamate a jej podmnozinou
- je umiestnena medzi pamat a procesor, aby odstranovala rozdiely sposobene vybavovacou dobou hlavnej pamate
Cache mozme delit podla toho, ako je mapovana na priamo mapovanu, plne asociativnu a s obmedzenym stupnom asociativity.
Priamo mapovana cache (Direct Mapped)
V tomto pripade je kazda pamatova adresa priradena jednemu bloku cache. Ak su pozadovane data v cache, tak su urcite na jednom jedinom mieste. Mapovat miesta v cache mozme napriklad pomocou modula. cache index = (adresa bloku v pamati) % pocet blokov cache => 7 % 4 = 3
Priamo mapovana cache moze vyzerat asi tak ako na obrazku nizsie. Vsimnite is V tagu, co je bit platnosti a tagu Tag, ktory je klucom k danemu "riadku". Na obrazku je cache, ktora je rozdelena do blokov a kazdy blok ma viacero elementov. To znamena, ze ked najdeme riadok (blok), tak musime este najst ten spravny element a to robime pomocou offsetu. Znazornena cache je 64KB s velkostou bloku 16B (128b).
Pamatova adresa je teda rozdelena na tri casti,
- Tag (kluc) pre overenie bloku. Sluzi k odliseniu vsetkych pamatovych adries, ktore su mapovane do rovnakeho miesta v cache.
- Index pre vyber bloku. Specifikuje priamo radok v cache (priamo adresuje index)
- Offset, ktory specifikuje ziadany element v bloku
V pripade, ze dojde k vypadku (miss), tak musime nahradit data. Nahradzujeme cely blok a teda hovorime o block replacement-e.
Do priamo mapovanej cache mozme zapisovat 2-ma sposobmi
- Write through
Jedna sa o sucasny zapis slova do pamatoveho bloku cache a na dane miesto v pamati. Zapis do cache a do pamate je vykonavany vzdy. Je to jednoduchy, ale pomaly sposob udrziavania zhodneho obsahu cache a pamate. Navyse zatazuje komunikaciu s pamatou a vyzaduje vyrovnavaci zapisovaci buffer. - Write back (copy back)
Tento sposob obnovuje obsah len v cache a na danom mieste v pamati ponechava povodny obsah. Zapis do pamati sa vykonava len v pripade, ze dany blok, ktory je oznaceny dirty bitom je odstranovany. Dirty bit je pridany kazdemu bloku cache. Indikuje potrebu zapisu obsahu z cache do hlavnej pamate. OS musi pred I/O operaciami aktualizovat obsah pamate obsahom cache. Tento sposob je sice rychly, ale implementacne zlozitejsi, ako write through.
Aky velky by mal byt blok cache? Odpoved by bola, ze optimalne :). Totiz, ak vyuzijeme priestorovu lokalitu, tak pouzijeme vacsie bloky. Vacsi blok potom obsahuje viac slov v blizkosti pozadovaneho slova a tak je pri sebe viac po sebe iducich instrukcii, alebo dat pola apod. To je vyhodou. Bohuzial, nevyhodou je, ze sice vacsi blok sposobuje menej vypadkov, ale vacsiu miss penalty (cas na ziskanie dat z nizsej urovne pamate + cas na prenesenie dat do vyssej urovne + cas na dorucenie dat procesoru ). K nacitaniu vacsieho bloku z nizsej urovne potrebujeme viac casu, ako na nacitanie mensieho bloku. Cim su bloky vacsie, tak rastie aj miss rate, pretoze cim vacsie bloky, tym je menej blokov v cache. Predstavme si, ze by sme mali len jeden velky blok o velkosti 16B (slovo). V takom pripade nam netreba index, pretoze nie je potreba rozlisovat bloky. Mali by sme len jeden vstup do cache, pretoze nemame co ine adresovat. Polozku pouzijeme a musime ju nahradit novou, ale nahradena polozka moze byt znovu ziadana a tak musime opat nahradzovat. To nam extremne zvysuje miss rate. Takto by sme sa lahko mohli dostat k nocnej more navrharov cache - tzv. ping pong efektu.
Pre vyjadrenie doby pristupu do pamate sa pouziva vypocet priemeru, AMAT (average memory access time).
AMAT = HT + MP x MR
Teda, priemerna doba pristupu do pamate je sucet doby pre najdenie a ziskanie polozky z cache a sucinu miss penalty (cas na ziskanie dat z nizsej urovne pamate + cas na prenesenie dat do vyssej urovne + cas na dorucenie dat procesoru) a pomeru neuspesnych hladani v cache.
Moze sa stat, ze v cache nenajdeme to, co hladame, aj napriek tomu, ze by to tam malo byt. Doslo teda k jednemu z dvoch druhov vypadkov
- Studeny vypadok (Compulsory misses)
Tento druh vypadku sa vyskytuej po starte pocitaca, kedy cache neobsahuje ziadne data. Studene vypadky sa potom vyskytuju az do naplnenia cache. - Konfliktny vypadok (Conflict misses)
Tento druh vypadkov sa vyskytuje z dvoch dovodov. Bud je na jedno miesto v pamati mapovanych viac rozdielnych adries, alebo je viac blokov mapovanych na rovnake miesto v cache (maju rovnaky index). Konfliktne vypadky sa riesia zvacsenim velkosti, alebo tak, ze pre ten isty index budeme mat viacnasobne umiestnenie bloku.
Plne asociativna cache
V pripade tejto cache neexistuju vypadky, pretoze kazdy blok moze byt umiestneny kdekolvek v cache. Hlada sa teda podla kluca v celej cache. Index nepotrebujeme .. Vyhodou takejto cache je, ze nemame konfliktne vypadky (z definicie). Na druhej strane, pribudli nam kapacitne vypadky a velke mnozstvo komparatorov (pre kazdy blok). Ak by sme mali 64KB cache s 32 bitovou adresou a velkostou bloku 32B, tak by sme na kluc potrebovali 27 bitov a to by znamenalo 2K x 27-bit komparatorov. A to uz je trochu vela :). Kapacitne vypadky su vypadky sposobene obmedzenou kapacitou plne asociativnej cache. Zmensenie kapacitnych vypadkov dosiahneme zvacsenim velkosti cache. Tento typ vypadku je zakladnym typom vypadkov pre plne asociativne cache.
Dalsim z typov cache je cache s obmedzenym stupnom asociativity, N-Way associative cache. Tentokrat nemame len bloky a elementy v blokoch, ale pribudli nam sety a v nich su bloky. Kazdy set teda ukazuje na niekolko blokov a kazdy set je plne asociativny. Na set ukazuje index a potom porovnavame kluc s klucom bloku. Na obrazku je 4-way associative cache. Takze, vo vysledku to vyzera tak, ze N priamo mapovanych cache pracuje vedla seba. Kazdy blok ma svoj bit platnosti a data. Blok do setu umiestnujeme napriklad podla vzorca cislo setu = cislo bloku % pocet setov.
Takto organizovana cache ma svoje vyhody. Uz 2-way as. cache vyluci mnozstvo konfliktnych vypadkov. Vacsi stupen as. znamena vacsiu hit rate, az do isteho stupna. HW nie je o vela zlozitejsi a vyzaduje len n komparatorov naviac, kde n je stupen asociativity.
Direct mapped cache je 1-way associative a plne asociativna cache s n blokmi je vlastne n-asociative cache.
Ked sme rozoberali adresovatelne pamate, tak sme hovorili o LRU algoritme, ako o jednom zo sposobov vyberu adresoveho miesta, ktore sa ma na nahradit. A kedze cache je vlastne implementaciou CAM (content accessed memory), tak sa nam tu bude diat vlastne to iste :). Priamo mapovana cache priamo specifikuje blok, ktory sa ma vymenit, pomocou valid bitu. V cache s obm. st. as. je set adresovan indexom a v sete sa nachadzaju bloky, ktore maju svoj bit platnosti a mozu byt vymenene. V plne asociativnej cachi mozme blok hodit kamkolvek, ale taktiez, bloky maju svoj bit platnosti a podla toho ich vymenime. Co ak ale nemam neplatny bit platnosti. V takom pripade musime urcit pravidlo, ktore urci, ktory blok sa nahradi. To moze byt
- LRU
- Random
- FIFO
- Pseudo LRU
Dalsim problemom, ktory riesime pri cache pamatiach je redukcia Miss Rate. Vieme, ze
- zvacsenim velkosti bloku
- zvacsenim stupna asociativity
a dalsie moznosti su
- vacsia cache
je ale limitovana cenou a technologiou. Hit time L1 cache je uz teraz mensi ako 1 CPU takt. - zvacsenim miesta pre bloky
to ale nemusi platit vzdy. zvacsovanie bloku pomaha len do istych velkosti. Zvacsovanim velkosti bloku sa nam totiz znizuje pocet blokov, pretoze uz nevyuzivame casovu lokalitu (bloky uz mozme umiestnit snad kamkolvek) - zvysovanim stupna asociativity
- pouzitim L2 cache
- victim cache
tu vlastne vyuzivame maleho HT DM cache a nejakej malej pamate odstranenych blokov. Cachujeme teda "obete" odstranene bloky - HW prefetchingom
napriklad Alpha 21064 nacita 2 bloky v pripade vypadku. Blok je navyse umiestneny do pamate - tzv. stream buffer. Ak dojde k vypadku, tak je skotrolovany aj stream buffer. Prefetching vyzaduje rozsirenu sirku prenosu z nizsich urovne pamate - Prostrednictvom pseudoasociativity
Znovu vyuzijeme HT DM cache s nizkou hodnotou konfl. vypadkov. cache s obmedz. stupnom asociativity n =2 => najprv sa prezrie jedna polka cache a potom druha - Write Buffer
Spomenieme si na FIFO. Write buffer je umiesteneny medzi cache a pamat. Procesor zapisuje data do cache a do bufferu. Obsah buffer je potom zapisany do pamate nizsej urovne. - Prostrenictvom zapisovacej pamate
Znamena to, ze pridame este jednu cache L2, do systemu a ta sluzi ako write back cache. Riesi problem preplnenia bufferu.
 |
| Write buffer riesenie |
 |
| Riesenie pomocou zapisovacej pamate |
Takze,
- Hit time redukujeme
- zmensenim velkosti cache (zvacsi miss rate)
- pouzitim priamo mapovanej cache (zvacsi miss rate)
- miss rate redukujeme
- zvacsenim cache, co moze ale zvysit hit time
- zvysenim stupna asociativity, co ale moze zvacsit hit time
- zvacsenim velkosti bloku (zvacsenie miss penalty)
- miss penalty redukujeme
- tak, ze redukujeme cas prenosu medzi komponentami (alebo celkovo)
- L2 cache
