Arhitectura sistemului ierarhizat de memorie

1. MEMORII CACHE

Cache: a safe place for hiding or storing things. (Webster's New World Dictionary of the American Language)

Memoria cache este o memorie situata din punct de vedere logic intre CPU si memoria principala (uzual DRAM), mai mica, mai rapida si mai scumpa (per byte - de tip SRAM) decat aceasta si gestionata - in general prin hardware - astfel incat sa existe o cat mai mare probabilitate statistica de gasire a datei accesate de catre CPU, in cache.

Cache-ul este adresat de catre CPU in paralel cu memoria principala (MP): daca data dorita a fi accesata se gaseste in cache, accesul la MP se aborteaza, daca nu, se acceseaza MP cu penalizarile de timp impuse de latenta mai mare a acesteia, relativ ridicata in comparatie cu frecventa de tact a CPU. data accesata din MP se va introduce si in cache.

Timpul de acces DRAM - 15 50 de impulsuri de tact (T_CLK = perioada ceasului microprocesorului), in schimb accesarea cache-ului se face in doar 1 - 3 T_CLK T memoria cache reduce timpul mediu de acces al CPU la MP, ceea ce este foarte util.

Se defineste un acces al CPU cu hit in cache, un acces care gaseste o copie in cache a datei accesate. Un acces cu miss in cache este unul care nu gaseste o copie in cache a datei accesate de catre CPU si care, prin urmare, adreseaza MP cu toate penalizarile de timp care deriva din accesarea acesteia.

Parametru de performanta al unei memorii cache rata de hit, ca fiind raportul statistic intre numarul acceselor cu hit in cache respectiv numarul total al acceselor CPU la memorie. Masurat pe benchmark-uri (programe de test) reprezentative, la ora actuala sunt frecvente rate de hit de peste 90 %. Rata de miss (RM) este complementara ratei de hit (RH), astfel ca: RH [%] + RM [%] = 100 %. In realitate, in cazul unei citiri cu miss in cache se aduce din MP nu doar data (cuvantul) dorita de catre CPU ci un intreg bloc (4 - 16 cuvinte) care evident contine data respectiva. O citire cu miss presupune aducerea blocului din MP dar inainte de aceasta se impune evacuarea in MP a unui bloc din cache. Transferul din cache in MP se face tot la nivel de bloc si nu de cuvant T Optimizarea traficului dintre cache si MP.

Eficienta memoriilor cache se bazeaza pe 2 principii de natura statistica si care caracterizeaza intrinsec notiunea de program: principiile de localitate temporala si spatiala. Conform principiului de localitate (vecinatate) temporala, exista o mare probabilitate ca o data (instructiune) accesata acum de catre CPU sa fie accesata din nou, in viitorul imediat. Conform principiului de localitate spatiala, exista o mare probabilitate ca o data situata in imediata vecinatate a unei date accesate curent de catre CPU, sa fie si ea accesata in viitorul apropiat. Ex: bucle de program, structuri regulate de date - tablouri, matrici.

O combinare a celor 2 principii conduce la celebra "regula 90/10": "cca. 90% din timpul de rulare al unui program se executa doar 10% din codul acestuia".

D.p.d.v. arhitectural, exista 3 tipuri distincte de memorii cache in conformitate cu gradul de asociativitate: cu mapare directa, semiasociative si total asociative.

Figura 1. Scheme de mapare in cache

La cache-urile cu mapare directa - un bloc din MP poate fi gasit in cache (hit) intr-un bloc unic determinat. Regula de mapare a unui bloc din MP in cache este:

(Adresa bloc MP) modulo (Nr. blocuri din cache)

Strictetea regulii de mapare conduce la o simplitate constructiva a acestor memorii dar si la fenomenul de interferenta al blocurilor din MP in cache. Exemplu, blocurile 12, 20, 28, 36 determina interferente in cache. Accesarea alternativa, in mod repetat a doua blocuri din MP conflictuale in cache, determina o rata de hit egala cu 0.

La cache-urile semiasociative exista mai multe seturi, fiecare set avand mai multe blocuri componente. Blocul dorit se poate mapa oriunde in setul respectiv. Regula de mapare precizeaza strict doar setul in care se poate afla blocul dorit:

(Adresa bloc MP) modulo (Nr. seturi din cache)

Mai precis, la un miss in cache, inainte de incarcarea noului bloc din MP, trebuie evacuat un anumit bloc din setul respectiv. Exista implementate doua-trei tipuri de algoritmi de evacuare: pseudorandom (cvasialeator), FIFO si LRU ("Least Recently Used"). Algoritmul LRU evacueaza blocul din cache cel mai demult neaccesat, in baza principiului de localitate temporala.

Daca un set din cache-ul semiasociativ contine N blocuri atunci cache-ul se mai numeste "tip N-way set associative". Intr-un astfel de cache rata de interferenta se reduce odata cu cresterea gradului de asociativitate (N ). Exemplu, blocurile 12, 20, 28 si 36 pot coexista in setul 0.

(N T interferentele blocurilor T performanta globala (IR)

(N T complexitatea structurala T Timpul de acces la cache T performanta globala (IR)

Optimizarea gradului de asociativitate, a capacitatii cache, a lungimii blocului din cache se face prin laborioase simulari software, variind toti acesti parametrii in vederea maximizarii ratei globale de procesare a instructiunilor [instr./cicli].

Memoriile cache complet asociative, implementeaza practic un singur set permitand maparea blocului practic oriunde in cache. Ele nu se implementeaza deocamdata in siliciu datorita complexitatii deosebite si a timpului prohibit de cautare. Reduc insa total interferentele blocurilor la aceeasi locatie cache.

Cache direct mapat

Figura  Implementarea unui cache cu mapare directa

Cache semiasociativ pe 2 cai

Figura 3. Implementarea unui cache semiasociativ (2-way)

Cache complet associativ

Figura 4. Implementarea unui cache complet asociativ

Blocul este compus din 4 cuvinte. Bitul V este un bit de validare a blocului, V=1 fiind o conditie necesara a obtinerii hitului. Pentru a evita false hituri la citirea programului incarcator din EPROM, se initializeaza bitii V cu zero. La prima incarcare a unei date (instructiuni) in cache, bitul V aferent se va seta pe '1', validand astfel hitul.

Bitul D (Dirty) este pus pe '0' la incarcarea initiala a blocului in cache. La prima scriere a acelui bloc, bitul se pune deci pe '1'. Evacuarea propriu-zisa a blocului se face doar daca bitul D=1. Prin acest bit se minimizeaza evacuarile de blocuri in MP, pe baza principiului ca un bloc trebuie evacuat numai daca a fost scris in cache.

D.p.d.v. al acceselor de scriere a unui procesor, exista 2 posibilitati:

a)  Strategia "Write Through" (WT), prin care informatia este scrisa de catre procesor atat in blocul aferent din cache cat si in blocul corespunzator din memoria principala.

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

In vederea mentinerii coerentei cache-urilor cu precadere in sistemele multimicroprocesor - exista 2 posibilitati in functie de ce se intampla la o scriere:

a)  Write invalidate - prin care CPU care scrie determina ca toate copiile din celelalte memorii cache sa fie invalidate inainte 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 actualizate toate 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.

Apar posibile 4 procese distincte intr-un cache ca in tabelul urmator:

Tabelul 1.Tipuri de acces in cache

Memoriile cache imbunatatesc performanta indeosebi pe citirile cu hit iar in cazul utilizarii scrierii tip "Write Back" si pe scrierile cu hit. Imbunatatirea accesului la memorie pe citirile CPU este normala avand in vedere ca acestea sunt mult mai frecvente decat scrierile (orice instructiune implica cel putin o citire din memorie pentru aducerea sa; statistic, cca. 75 % din accesele la memorie sunt citiri).

Conceptul de memorie cache a fost introdus de prof. Maurice Wilkes (Univ. Cambridge, Anglia) - un pionier al calculatoarelor. Primul sistem comercial care utiliza cache-urile a fost IBM 360/85 (1968). Conceptul de cache s-a dovedit a fi foarte fecund nu numai in hardware dar si in software prin aplicatii dintre cele mai diverse in sistemele de operare (memoria virtuala), retele de calculatoare, baze de date.

Dintre metodele de imbunatatire a performantei cache-urilor se disting:

1.   Reducerea ratei de miss in cache

2.   Reducerea penalitatii in caz de miss in cache

3.   Reducerea timpului de executie in caz de hit in cache.

Cu privire la accesele cu miss in cache exista trei tipuri de miss:

<   Compulsory - sau de start rece. Apar la primul acces al unui anumit bloc in cache.

<   De capacitate - apar in situatia in care cache-ul nu poate retine toate blocurile necesare iar cele care sunt evacuate la un moment dat vor fi necesare ulterior.

<   De conflict - sau de interferenta. Apar daca strategia de plasare a blocurilor in cache este mapata direct sau semi-asociativa, situatie in care mai multe blocuri din memoria principala pot interfera (accesa) acelasi bloc din cache.

Dintre metodele de reducere a ratei de miss in cache amintim:

Cresterea dimensiunii blocurilor

Cresterea gradului de asociativitate

Utilizarea conceptului de victim cache respectiv selective victim cache (impreuna cu solutia anterioara determina reducerea miss-urilor de conflict).

Utilizarea mecanismelor de prefetch asupra instructiunilor (buffer de prefetch) si datelor (data write buffer)

Folosirea tehnicilor de optimizare gen (merging array, loop interchange, loop fusion)