7/21/2019 LAB_AC11

1/9

Memoria cache

Viteza MICROPROCESORUL este superioara vitezei memoriilor, astfel ca dupa initiereaunui ciclu de acces la memorie, MICROPROCESORUL trebuie sa ramna inactiva un timp,asteptnd raspunsul acesteia.Memoriile rapide sunt realizabile din punct de vedere tehnologic, dar costul lor este ridicat. Suntcunoscute nsa tehnici pentru combinarea unei memorii rapide de dimensiuni mici cu o memorie

mai lenta de dimensiuni mai mari, pentru a se obtine aproximativ viteza memoriei rapide sicapacitatea mare a memoriei lente, la un pret moderat. Memoria rapida de dimensiune mica senumeste memorie cache (din limba franceza: cacher - a ascunde, in engleza Cache : a safe placefor hiding or storing thing).

Principiul memoriei cache.

Principiul memoriei cache este ilustrat n Figura. Exista o memorie principala de dimensiuni relativmari, dar mai lenta, si o memorie cache mai redusa, dar mai rapida. Memoria cache contine o copiea unor parti din memoria principala. Atunci cnd MICROPROCESORUL ncearca citirea unuicuvnt din memorie, se testeaza daca respectivul cuvnt se afla n memoria cache. n cazafirmativ, cuvntul este furnizat unitatii centrale. n caz contrar, se ncarca n memoria cache un

bloc al memoriei pr incipale, constnd dintr-un numar fix de cuvinte, iar apoi cuvntul este returnatunitatii centrale.Se cunoaste ca programele nu fac acces la memorie n mod complet aleator. Daca se face oreferire la o anumita adresa, este probabil ca urmatoarea referire la memorie va fi n vecinatateaacestei adrese. n spatiul adreselor de memorie, cteva regiuni au o probabilitate ridicata de a fiaccesate, cteva au o probabilitate moderata, iar celelalte au o probabilitate foarte mica de a fiaccesate n viitorul apropiat.O regiune care are o probabilitate nalta este cea corespunzatoare contorului de program actual,deoarece este probabil sa se execute urmatoarea instructiune din secventa de instructiuni. Alteregiuni care au o probabilitate mare de a fi accesate sunt cele care contin datele active, procedurile

si punctul de ntoarcere dintr-o procedura. Daca programul este scris ntr-un limbaj structurat peblocuri, ca de exemplu Pascal, zona de stiva pentru variabile locale si parametri este o alta zona cuprobabilitate ridicata de acces.Observatia ca referintele la memorie efectuate ntr-un interval scurt de timp utilizeaza o mica

portiune a memoriei reprezinta principiul localitatii, si formeaza baza sistemelor de memorie cache.Atunci cnd este adresat un cuvnt, acesta este transferat din memoria lenta n memoria cache,astfel nct la urmatoarea utilizare va putea fi accesat n mod rapid.Mai jos se prezinta structura unui sistem de memorie format din memoria principala si o memoriecache.

7/21/2019 LAB_AC11

2/9

Structura unui sistem de memorie.

Memoria principala consta din 2n cuvinte adresabile, fiecare cuvnt avnd o adresa unica den biti. Se considera ca aceasta memorie este formata dintr-un numar de blocuri de lungime fixa deK cuvinte fiecare. Exista deci 2n/K blocuri. Memoria cache consta din blocuri de cte K cuvintefiecare, un asemenea bloc fiind numit linie. Exista L linii n memoria cache, numarul de linii fiindmult mai mic dect numarul blocurilor din memoria principala (L

7/21/2019 LAB_AC11

3/9

n acest sens, din punct de vedere al acceselor de scriere a unui procesor, exista 2posibilitati:

a) Strategia Write Through (WT), prin care informatia este scrisa de catre procesor attn blocul aferent din cache ct si n blocul corespunzator din memoria principala.

b) Strategia Write - Back (WB), prin care informatia este scrisa numai n cache,blocul modificat fiind transferat n MP numai la evacuarea din cache.

n vederea mentinerii coerentei cache-urilor cu precadere n sistemele multimicroprocesor exista

2 posibilitati n functie de ce se ntmpla la o scriere (vezi pentru detalii capitolul dedicatsistemelor multimicroprocesor):a) Write invalidate prin care CPU care scrie determina ca toate copiile din celelaltememorii cache sa fie invalidate nainte ca el sa si modifice blocul din cache-ul propriu.

b) Write Broadcast CPU care scrie pune data de scris pe busul comun spre a fi actualizatetoate copiile din celelalte cache-uri.Ambele strategii de mentinere a coerentei pot fi asociate cu oricare dintre protocoalele

de scriere (WT, WB) dar de cele mai multe ori se prefera WB cu invalidare. Nu detaliem aiciproblemele de coerenta ntruct acestea se refera cu deosebire la problematica sistemelormultiprocesor si deci depasesc cadrul acestei prezentari. Apar posibile 4 procese distincte ntr-uncache ca n tabelul urmator:

Tip acces Hit / Miss Actiune n cacheCitire Miss Evacuare bloc + ncarcare bloc nouCitire Hit (comparare tag-uri)Scriere Miss Evacuare bloc + ncarcare bloc nou + scriere data n

blocScriere Hit Scriere data n blocul din cache (WB)

Tipuri de acces n cache

Asadar, memoriile cache mbunatatesc performanta ndeosebi pe citirile cu hit iar n cazulutilizarii scrierii tip Write Back si pe scrierile cu hit.

mbunatatirea accesului la memorie pe citirile CPU este normala avnd n vedere caacestea sunt mult mai frecvente dect scrierile (orice instructiune implica cel putin o citiredin memorie pentru aducerea sa; statistic, cca. 75 % din accesele la memorie sunt citiri).Explicatia la cauzele miss-urilor n cache-uri, conform literaturii acestui domeniu, sunt de3 tipuri:

datorita faptului ca n fond primul acces la un bloc genereaza ntotdeauna miss(compulsory ); sunt inevitabile. datorita capacitatii fatalmente limitate a cache-ului care nu poate contine la un momentdat toate blocurile din MP, ceea ce implica evacuari / ncarcari (capacity). datorita interferentelor (conflictelor) unor blocuri din MP pe acelasi bloc din cache(conflict); acestea se reduc odata cu cresterea capacitatii si a gradului de asociativitate.

Victim CACHE

Pentru a reduce rata de miss a cache -urilor mapate direct (fara sa se afecteze nsa timpulde hit sau penalitatea n caz de miss), cercetatorul Norman Jouppi (DEC) a propusconceptul de victim cache. Aceasta reprezinta o memorie mica complet asociativa, plasata ntre

primul nivel de cache mapat direct si memoria principala. Blocurile nlocuite din cache-ulprincipal datorita unui miss sunt temporar memorate n victim cache. Daca sunt referite din nounainte de a fi nlocuite din victim cache, ele pot fi extrase direct din victim cache cu o

penalitate mai mica dect cea a memoriei principale. Deoarece victim cache-ul este completasociativ, multe blocuri care ar genera conflict n cache -ul principal mapat direct, ar putearezida n victim cache fara sa dea nastere la conflicte. Decizia de a plasa un bloc n cache-ul

principal sau n victim cache (n caz de miss) este facuta cu ajutorul unei informatii de stare asociate

7/21/2019 LAB_AC11

4/9

blocurilor din cache. Bitii de stare contin informatii despre istoria blocului. Aceasta idee a fostpropusa de McFarling, care foloseste informatia de stare pentru a exclude blocurile sigure dincache-ul mapat direct, reducnd nlocuirile ciclice implicate de acelasi bloc. Aceasta schema,numita excludere dinamica, reduce miss-urile de conflict n multe cazuri. O predictie gresitaimplica un acces n nivelul urmator al ierarhiei de memorie contrabalansnd eventualecstiguri n performanta. Schema este mai putin eficace cu blocuri mari, de capacitati tipicecache-urilor microprocesoarelor curente.

Pentru a reduce numarul de interschimbari dintre cache-ul principal si victim cache, Stiliadis siVarma au introdus un nou concept numit selective victim cache(SVC).

Ierarhia de memorie pentru scema cu Selective Victim Cache

Cu SVC, blocurile aduse din memoria principala sunt plasate selectiv fie n cache-ul principal cumapare directa fie n selective victim cache, folosind un algoritm de predictie euristic bazat

pe istoria folosirii sale. Blocurile care sunt mai putin probabil sa fie accesate n viitor sunt plasaten SVC si nu n cache-ul princ ipal. Predictia este de asemenea folosita n cazul unui miss ncache-ul principal pentru a determina daca este necesara o schimbare a blocurilorconflictuale. Algoritmul obiectiv este de a plasa blocurile, care sunt mai probabil a fi referite dinnou, n cache-ul principal si altele n victim cache.La referirea unui cache mapat direct, victim cache-ul este adresat n paralel; daca rezultamiss n cache-ul principal, dar hit n victim cache, instructiunea (n cazul ICache-ului) esteextrasa din victim cache. Penalitatea pentru miss n cache-ul principal, n acest caz este multmai redusa dect costul unui acces n nivelul urmator de memorie. Algoritmul de victim cachencearca sa izoleze blocurile conflictuale si sa le memoreze doar unul n cache-ul principalrestul n victim cache. Daca numarul blocurilor conflictuale este suficient de mic sa se

potriveasca n victim cache, att rata de miss n nivelul urmator de memorie ct s i timpul mediude acces va fi mbunatatit datorita penalitatii reduse implicate de prezenta blocurilor n victim

cache.Cache-ul mapat direct creste cu un bloc pentru a implementa conceptul de selectivevictim cache. Acest bloc aditional se numeste bloc tranzitoriu, si este necesar pentru douamotive. Primul ar fi acela ca, blocul tranzitoriu este folosit de algoritmul de predictie pentru referirisecventiale ntr-un acelasi bloc. Hardware-ul este capabil sa determine accese secventiale,folosind semnalul Acces Secvential activat de CPU, cnd referirea curenta se face nacelasi bloc ca si cel anterior. Semnalul este folosit de catre cache pentru a evita actualizarea

bitilor de stare folositi de algoritmul de predictie la referinte repetate n acelasi bloc tranzitoriu.Al doilea motiv consta n faptul ca, atunci cnd are loc un hit n victim cache si algoritmul de

predictie decide sa nu se interschimbe blocurile, blocul corespondent este copiat din victim

7/21/2019 LAB_AC11

5/9

cache n blocul tranzitoriu. Astfel, blocul tranzitoriu serveste ca buffer, accesele secventialela acel bloc fiind satisfacute direct din acest buffer la timpul de acces al cache -ului principal.Similar, la un miss n urmatorul nivel de memorie, algoritmul de predictieva decide sa plaseze blocul sosit n victim cache si n blocul tranzitoriu. ntruct un al doilea sau unal n-lea acces consecutiv n acelasi bloc n cache -ul principal poate fi servit din blocultranzitoriu, acestuia i este adaugat un bit de stare pentru a adresa cache -ul principal. Acest bit destare urmareste starea datei din blocul tranzitoriu. Cnd starea este normala , adresa sosita pe

bus este decodificata pentru a accesa cache-ul principal n mod obisnuit; cnd starea este speciala ,accesul se face n blocul tranzitoriu. Figura urmatoare arata tranzitiile dintre cele doua stari. Mai josse prezinta acest algoritm sub forma de masina secventiala de stare.

Masina secventiala de stare si tranzitiile ei

Initial starea masinii este resetata n stare normala. Daca avem un miss n cache -ul mapatdirect, acesta este servit fie de victim cache fie de nivelul urmator de memorie. n fiecaredin cazuri, algoritmul de predictie este folosit pentru a determina care bloc urmeaza a fi memoratn cache-ul principal. Daca algoritmul de predictie plaseaza blocul accesat n cache -ul

principal, starea masinii ramne n stare normala. Altfel, blocul este copiat n blocul tranzitoriu diacest cache si masina tranziteaza n starea speciala.Referirea secventiala a aceluiasi bloc pastreaza semnalul Acces Secvential activat iar masina nstarea speciala . Datele se extrag din blocul tranzitoriu. Primul acces nesecvential reseteazastarea masinii n stare normala, distingndu-se trei cazuri distincte, pe care le vom discuta mai

jos.Algoritmul Selective Victim Cache

1. Hit n cache-ul principal: daca cuvntul este gasit n cache-ul principal, el este extras pentruCPU. Nu este nici o diferenta fata de cazul cache- ului mapat direct. Singura operatiesuplimentara este o posibila actualizare a bitilor de stare folositi de schema de predictie.Actualizarea se poate face n paralel cu operatia de fetch si nu introduce ntrzierisuplimentare.2. Miss n cache-ul principal, hit n victim cache: n acest caz, cuvntul este extras din victimcache n cache -ul mapat direct si naintat CPU. Un algoritm de predictie este invocat pentru adetermina daca va avea loc o interschimbare ntre blocul referit si blocul conflictual din cache-ul principal. Daca algoritmul decide ca blocul din victim cache este mai probabil sa fie

referit din nou dect blocul conflictual din cache -ul principal se realizeaza interschimbarea;altfel blocul din victim cache este copiat n blocul tranzitoriu al cache-ului principal iarmasina secventiala de stare trece n starea speciala. Data poate fi naintata CPU.n ambele cazuri blocul din victim cache este marcat drept cel mai recent folosit din lista LRU. n

plus, bitii de predictie sunt actualizati pentru a reflecta istoria acceselor.3. Miss att n cache-ul principal ct si n victim cache: daca cuvntul nu este gasit nici n cache-ul principal nici n victim cache, el trebuie extras din nivelul urmator al ierarhiei de memorie.Aceasta nseamna ca fie blocul corespondent din cache-ul principal este gol, fie noul bloc esten conflict cu un alt bloc memorat n cache (mai probabil). n primul caz, noul bloc este adus ncache-ul principal iar victim cache -ul nu este afectat. n cel de-al doilea caz, trebuie aplicat

7/21/2019 LAB_AC11

6/9

algoritmul de predictie pentru a determina care din blocuri este mai probabil sa fie referitpe viitor. Daca blocul care soseste din memoria centrala are o probabilitate mai mare dect bloculconflictual din cache -ul principal, ultimul este mutat n victim cache si noul bloc i ia locul ncache; altfel, blocul sosit este directionat spre victim cache si copiat n blocul tranzitoriu alcache- ului mapat direct, de unde poate fi accesat mai iute de catre CPU.Masina secventiala de stare trece n starea speciala iar bitii de predictie sunt actualizati.

Algoritmul de PredictieScopul algoritmului de predictie este de determina care din cele doua blocuri conflictuale estemai probabil sa fie referit pe viitor. Blocul considerat cu o probabilitate mai mare de accesn viitor este plasat n cache- ul principal, celalalt fiind plasat n victim cache. Astfel, daca

blocul din victim cache este pe viitor nlocuit datorita capacitatii reduse a victim cache- ului,impactul ar fi mai putin sever dect alegerea opusa (interschimbarea permanenta a blocurilordin cazul schemei cu victim cache obisnuit).Algoritmul de predictie se bazeaza pe algoritmul de excludere dinamica propus deMcFarling . Algoritmul foloseste doi biti de stare asociati fiecarui bloc, numiti hit bit sistickybit. Hit bit este asociat logic cu blocul din nivelul 1 (L1 - level one) al cache -ului care se afla penivelul 2(L2) sau n memoria centrala. Hit bit egal cu 1 logic indica, faptul ca a avut cel putin un

acces cu hit la blocul respectiv de cnd el a parasit cache-ul principal (cache-ul de pe nivelulL1). Hit bit egal cu 0 nseamna ca blocul corespunzator nu a fost deloc accesat de cnd a fostnlocuit din cache-ul principal. ntr-o implementare ideala, bitii de hit sunt mentinuti nnivelul L2 de cache sau n memoria principala si adusi n nivelul L1 de cache cu bloculcorespondent. Daca blocul este nlocuit din cache-ul principal (L1 cache), starea bitului de hittrebuie actualizata n L2 cache sau n memoria centrala. Cnd un bloc, sa-l numim , a fost adus ncache-ul principal, bitul sau sticky este setat. Fiecare secventa cu hit la blocul remprospateaza bitul sticky la valoarea 1. La referirea unui bloc conflictual, fie acesta ,daca algoritmul de predictie decide ca blocul sa nu fie nlocuit din cache-ul

7/21/2019 LAB_AC11

7/9

principal atunci bitul sticky este resetat. Daca un acces ulterior n cache-ul principal intra n conflict cublocul care are bitul sticky resetat, atunci blocul va fi nlocuit din cache-ul principal. De aceea, stickybit de valoare 1 pentru blocul semnifica faptul ca nu a avut loc nici o referire la un blocconflictual cu , de la ultima referire a acestuia.Este usor de nteles rolul blocului tranzitoriu n algoritmul de predictie. Daca algoritmultrateaza toate fetch-urile n acelasi fel, accesele secventiale n acelasi bloc vor seta ntotdeauna

bitul sticky. Algoritmul de predictie va fi incapabil sa determine daca blocul a fost referitrepetat n interiorul unei bucle, sau daca mai mult dect un cuvnt din acelasi bloc a fost extras dincache fara o referinta intervenita la un alt bloc.n algoritmul Selective Victim Cache prezentat n figura anterioara, sebdisting trei cazuri: n primul caz,un hit n cache-ul principal seteaza bitii de stare hit si sticky. n al doilea caz, blocul accesat, fie acesta, se considera rezident n victim cache. Acesta implica un conflict ntre blocul si cel din cache-ulprincipal, notat . n acest caz, algoritmul de predictie este aplicat pentru a determina daca va avea loco interschimbare. Daca bitul sticky alblui este 0, semnificnd faptul ca blocul nu a fost accesat de laconflictul anterior la acest bloc, noul bloc primeste o prioritate superioara lui , determinndo interschimbare.De asemenea, daca bitul hit al lui este setat pe 1, acestuia i este data o prioritate mai mare

dect lui , si ele sunt interschimbate. Daca bitul sticky al lui este 1 si bitul hit al lui este 0,accesul este satisfacut din victim cache si nu are loc nici o interschimbare (se considera cablocul nu este suficient de valoros pt. a fi adus n cache-ul principal). Bitul sticky aferentlui este resetat astfel nct o secventa urmatoare care implica conflict la acest bloc va determinamutarea lui din cache-ul principal.

7/21/2019 LAB_AC11

8/9

Algoritmul de Selective Victim Cachen final, cazul 3 al algoritmului prezinta secventa de actiuni care au loc n cazul unor accese cu missatt n cache-ul principal ct si n victim cache. Secventa este similara cu cea de la cazul 2, cu exceptia

faptului ca, destinatia blocului sosit se alege fie cache-ul principal fie victim cache-ul. nsituatia cu victim cache simplu, blocul conflictual din cache -ul principal era mutat n victimcache nainte sa fie nlocuit. n cazul de fata cnd blocul sosit este plasat n victim cache, el este deasemenea plasat si n blocul tranzitoriu pentru a servi eventualele viitoare referinte secventiale.Operatiile algoritmului de Selective Victim Cache pot fi ilustrate printr-o secventa deinstructiuni repetate (m)n implicnd trei blocuri conflictuale , si . Notatia (m)nreprezinta executia unei secvente compusa din doua bucle de program imbricate, bucla interioaraconstnd n m referinte la blocul , urmate de accesul la blocurile si n bucla exterioara,care se executa de n ori. Primul acces l aduce pe n cache-ul principal si att bitul hit ct si cel

7/21/2019 LAB_AC11

9/9

sticky sunt setati dupa cel mult doua referiri ale acestuia. Cnd este referit, bitul sau hit este initial0. De aceea el nu-l nlocuieste pe n cache-ul principal si este memorat n victim cache.Conflictul generat determina resetarea bitului sticky al lui . Cnd este referit, bitul sau hit este 0,dar bitul sticky al lui este tot 0. Deci, l nlocuieste pe . Blocul este transferat n victimcache si bitul sau hit ramne 1 datorita referintei sale anterioare. n ciclul urmator cnd estereferit din nou, el este mutat napoi n cache-ul principal datorita bitului sau de hit, ramas setat. Astfel,

daca victim cache-ul este suficient de mare pentru a ncape att si , sau si , doar treireferinte ar fi servite de catre al doilea nivel de cache. Numarul total de interschimbari nu va depasi2n. n cazul unei scheme simple de predictie fara victim cache, numarul total de referiri cu missar fi 2n, n cazul n care schema poate rezolva doar conflicte ntre doua blocuri. Un victim cachesimplu, fara predictie ar fi capabil sa reduca numarul de accese cu miss la cel de-al doilea nivel decache la 3, dar ar necesita 3n interschimbari n timpul executiei buclei exterioare, cu influenteevident defavorabile asupra timpului global de procesare. Aceasta arata avantajul Selective VictimCache-ului superioara altor scheme care trateaza conflicte implicnd mai mult de doua blocuri.De retinut ca, penalitatea pentru o predictie gresita n aceasta schema este limitata la accesul nvictim cache si o posibila interschimbare, presupunnd ca victim cache-ul este suficient de marepentru a retine blocurile conflictuale ntre accese.