Memorii cache

Memorii cache

Aceasta prezentare  incearca sa prezinte intr-o maniera sintetica unul dintre cele mai fecunde concepte ale tehnologiei computerelor, anume acela de memorie cache. Cache-urile au un rol esential, anume acela de 'acoperire a gap-urilor tehnologice' intre diversele componente ale sistemului ierarhizat de memorii.

Cache: a safe place for hiding or storing things. (Webster's New World Dictionary of the American Language, Third College Edition - 1988)

Memoria cache este o memorie situata din punct de vedere logic intre CPU (Central Processing Unit - unitate centrala) si memoria principala (uzual DRAM - Dynamic Random Access Memory), mai mica, mai rapida si mai scumpa (per byte) 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. Asadar, 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. Oricum, data accesata din MP se va introduce si in cache.

Memoriile cache sunt implementate in tehnologii de inalta performanta, avand deci un timp de acces foarte redus (cca. 2 - 7 ns la ora actuala, 1999). In prezent presiunea asupra acestor memorii este foarte ridicata, rolul lor fiind acela de a apropia performanta microprocesoarelor (care creste cu cca. 50 - 60 % pe an) cu aceea a memoriilor DRAM, a caror latenta scade cu doar cca. 7 % pe an. In general, pentru a accesa o locatie DRAM, un procesor "pierde" 10 - 30 de impulsuri de tact (~ timp acces DRAM / T_CLK, T_CLK = perioada ceasului microprocesorului), in schimb accesarea cache-ului se face in doar 1 - 3 impulsuri de tact. Cu alte cuvinte, 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.

Se defineste ca 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 esenta, utilitatea cache-ului deriva din urmatorul fapt: la o citire cu miss (din MP), data adusa din MP este introdusa si in cache, in speranta ca la o urmatoare citire a aceleiasi date, aceasta se va gasi in cache (hit). 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. Asadar, transferul din cache in MP se face tot la nivel de bloc si nu de cuvant. Astfel, se optimizeaza traficul intre cache si MP pe baza a 2 principii care vor fi discutate in continuare.

In esenta, 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 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 (pe baza acestui principiu statistic se aduce din MP in cache un intreg bloc si nu doar strict cuvantul dorit de catre CPU). O bucla de program - structura esentiala in orice program - exemplifica foarte clar aceste principii si justifica eficienta conceptului de cache.

O combinare a celor 2 principii anterior expuse conduce la celebra "regula 90/10" care spune ca cca. 90 % din timpul de rulare al unui program se executa doar cca. 10 % din codul acestuia. Personal, cred ca mai putin. Pe baza acestor principii empirice se situeaza intreg esafodajul conceptului de cache; eficienta sa deosebita nu poate fi explicata prin considerente analitice pentru simplul fapt ca este practic imposibil a descrie analitic notiunea de program. In fond, ce este un program? Care este distributia instructiunilor sau a primitivelor structurale intr-un program? Poate fi aceasta descrisa concret, pe baza unor modele deterministe sau aleatoare? Dificultatea unor raspunsuri exacte la aceste intrebari - data in fond de imposibilitatea punerii in ecuatie a mintii umane, cea care creeaza infinita diversitate de "programe" - face ca cea mai buna explicatie asupra eficientei memoriilor cache sa stea in cele 2 principii empirice anterior schitate, caracterizand intrinsec notiunea de program.

Din punct de vedere arhitectural, exista 3 tipuri distincte de memorii cache in conformitate cu gradul de asociativitate: cu mapare directa, semiasociative si total asociative.

La cache-urile cu mapare directa, ideea principala consta in faptul ca un bloc din MP poate fi gasit in cache (hit) intr-un bloc unic determinat. In acest caz 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. Astfel, de exemplu, blocurile 12, 20, 28, 36, 42 etc. nu pot coexista in cache la un moment dat intrucat toate se mapeaza pe blocul 4 din cache. Prin urmare, o bucla de program care ar accesa alternativ blocurile 20 si 28 din MP ar genera o rata de hit egala cu zero.

La cache-urile semiasociative exista mai multe seturi, fiecare set avand mai multe blocuri componente. Aici, regula de mapare precizeaza strict doar setul in care se poate afla blocul dorit, astfel:

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

In principiu blocul dorit se poate mapa oriunde in setul respectiv. Mai precis, la un miss in cache, inainte de incarcarea noului bloc din MP, trebuie evacuat un anumit bloc din setul respectiv. In principiu exista implementate doua tipuri de algoritmi de evacuare: "pseudorandom" (cvasialeator) si LRU ("Least Recently Used"). Algoritmul LRU evacueaza blocul din cache cel mai demult neaccesat, in baza principiului de localitate temporala (aflat oarecum in contradictie cu o probabilistica markoviana care ar sugera sa fie pastrat!). Daca un set din cache-ul semiasociativ contine N blocuri atunci cache-ul se mai numeste "tip N-way set associative".

Este evident ca intr-un astfel de cache rata de interferenta se reduce odata cu cresterea gradului de asociativitate (N "mare"). Aici, de exemplu, blocurile 12, 20, 28 si 36 pot coexista in setul 0. Prin reducerea posibilelor interferente ale blocurilor, cresterea gradului de asociativitate determina imbunatatirea ratei de hit si deci a performantei globale. Pe de alta parte insa, asociativitatea impune cautarea dupa continut (se cauta deci intr-un set daca exista memorat blocul respectiv) ceea ce conduce la complicatii structurale si deci la cresterea timpului de acces la cache si implicit la diminuarea performantei globale. Optimizarea gradului de asociativitate, a capacitatii cache, a lungimii blocului din cache etc., nu se poate face decat prin laborioase simulari software, variind toti acesti parametrii in vederea minimizarii ratei globale de procesare a instructiunilor [instr./cicli].

In fine, memoriile cache total 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 (practic) total interferentele blocurilor la aceeasi locatie cache si constituie o metrica superioara utila in evaluarea ratei de hit pentru celelalte tipuri de cache-uri (prin comparatie).

Cele 3 scheme urmatoare prezinta implementari realizate pentru tipurile de cache anterior discutate.

Cache "2-way set associative"

Cache "full associative"

Cache direct mapat

S-a considerat - pentru exemplificare - un bloc compus din 4 cuvinte. Bitul V este un bit de validare a blocului, V = 1 fiind o conditie necesara a obtinerii hitului. Bitul este util indeosebi in Sistemele multiprocesor in vederea mentinerii coerentei memoriilor cache locale datorita redundantei informationale. Mai precis, aici apare necesitatea citirii din cache-ul propriu a ultimei copii modificate a datei respective. Cand un procesor modifica o copie locala a unei date, toate blocurile care contin acea data din cadrul celorlalte procesoare, trebuie invalidate prin resetarea V = 0. Necesitatea invalidarii blocurilor (V = 0) apare chiar si in sistemele uniprocesor. Imediat dupa resetarea sistemului, uzual, procesorul executa un program incarcator rezident in memoria EPROM. Cum imediat dupa initializarea sistemului continutul cache-ului e practic aleator, 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. Practic 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.

In acest sens, din punct de vedere 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:

1.     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.

2.     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. Nu detaliem aici problemele de coerenta intrucat acestea se refera cu deosebire la problematica sistemelor multiprocesor si deci depasesc cadrul acestei prezentari.

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

Asadar, 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).

Explicatia la cauzele miss-urilor in cache-uri, conform literaturii acestui domeniu, sunt de 3 tipuri:

datorita faptului ca in fond primul acces la un bloc genereaza intotdeauna miss (compulsory); sunt inevitabile.

datorita capacitatii fatalmente limitate a cache-ului care nu poate contine la un moment dat toate blocurile din MP, ceea ce implica evacuari / incarcari (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.

Primul care a pus in lumina conceptul de memorie cache a fost prof. Maurice Wilkes (Univ. Cambridge, Anglia) - un pionier al calculatoarelor care a inventat in 1951 si tehnica microprogramarii unitatilor de comanda aferente procesoarelor - intr-un articol publicat in 1965 ("Slave memories and dynamic storage allocation", IEEE Trans. Electronic Computers, April, 1965). Prima implementare a unui cache (cu mapare directa) apartine probabil lui Scarrott, in cadrul unui sistem experimental construit tot la Universitatea din Cambridge. 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, compilatoare etc.