Memorie cache

Acest articol sau secțiune referitoare la informatică este considerat a fi verificat . Motiv : vocea este prea specializată. Ar trebui simplificat pentru a nu-l face prea asemănător cu ceea ce se găsește într-un manual specializat în computer și pentru a îmbunătăți lizibilitatea acestuia pentru un utilizator non-tehnic. Alăturați-vă discuției și / sau corectați intrarea. Urmați sfaturile de proiectare de referință .

Acest articol sau secțiune referitoare la memoria computerelor nu menționează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citări din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

Acest articol sau secțiune despre subiectul informaticii nu este încă formatat conform standardelor . Comentariu : exces de îndrăzneț, exces de liste cu marcatori (malformatat), lipsa cursivelor pentru argou / termeni vorbitori de limba engleză (care ar trebui reduși) Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia . Urmați sfaturile de proiectare de referință .

Memoria cache (în limba engleză memoria cache , memoria cache sau memoria cache CPU ), în informatică , este o memorie rapidă (în comparație cu memoria principală ), relativ mică, nu este vizibilă de software și gestionată complet de hardware , care stochează date utilizate recent în memoria principală (MM - Main Memory) sau în memoria de lucru a sistemului.

Funcția memoriei cache este de a accelera accesele la memoria principală prin creșterea performanței sistemului. Mai mult, în sistemele multiprocesor cu memorie partajată, permite reducerea traficului magistralei de sistem și a memoriei principale, care este unul dintre blocajele majore ale acestor sisteme. Se face uz de rapid SRAM tehnologie, comparativ cu mai lent de memorie principală DRAM , conectat direct la procesor.

Caracteristici

Definiție

Cache-ul este o memorie care stochează date temporare „silențios” la cel mai înalt nivel de utilizare pentru reutilizare rapidă . ^{[4] [5] [6]}

Termenul „cache” provine din franceză și înseamnă „ascuns”.

Termenul „Memorie cache” sau „Memorie cache” sau pe scurt „cache” fără alte specificații, se referă, în general, la o memorie ascunsă care stochează un subset al conținutului memoriei principale și precis „Instrucțiunile” unui program și „ date " pentru a opera.

Operațiune

Logica funcțională a memoriei cache este următoarea:

1. în operațiile de citire a memoriei principale (MM), managerul cache verifică mai întâi dacă datele sunt stocate în cache;
2. în caz de rezultat pozitiv (Hit), datele sunt transferate direct și rapid din cache în procesor, fără a implica MM;
3. în caz contrar (Miss), datele sunt citite de MM.
   

   Schema de funcționare a cache-ului

Funcționarea memoriei cache se bazează în principal pe două principii ale localității :

• Localitate temporală: datele utilizate recent au o mare probabilitate de a fi utilizate din nou în curând. O memorie cache stochează doar un subset de date MM - datele cele mai utilizate - cele mai recent utilizate (MRU). Datele citite din MM sunt temporar stocate în cache. Dacă procesorul solicită aceleași date, acestea sunt furnizate de cache. Memorarea în cache este eficientă deoarece buclele scurte de instrucțiuni și rutine (programe mici) sunt structuri comune ale programului și, în general, se efectuează mai multe operații pe aceleași date și variabile.
• Localitate spațială: dacă se face referință la o dată, este foarte probabil ca datele adiacente să fie accesate în curând la rândul lor. Instrucțiunile și datele sunt transferate de la MM la cache în blocuri fixe (blocuri cache), cunoscute sub numele de linii cache. Dimensiunea liniei cache este în intervalul de 4-512 octeți ^[7] , astfel încât mai multe date care urmează să fie procesate (4/8 octeți) sunt stocate în fiecare intrare cache (adresa cache). După primul acces la MM, toate datele legate de linia cache sunt disponibile în cache-ul în sine. Multe programe sunt foarte secvențiale. Următoarea instrucțiune este de obicei la următoarea adresă de memorie. Datele sunt în general structurate, iar datele din aceste structuri sunt stocate în mod normal în locații de memorie adiacente (șiruri de date, tabele etc.). Liniile cache mari măresc localitatea spațială, dar crește și numărul de date invalidate în caz de înlocuire a liniilor (consultați Politica de înlocuire ).

Eficienţă

Eficiența cache-ului este măsurată în termeni de „Rată de accesare”. Rata de accesare reprezintă procentajul de accesări, adică datele găsite în cache, comparativ cu numărul total de accesări la cache. Opusul „Hit” se numește „Miss”. Eficiența cache-ului depinde de mai multe elemente, cum ar fi dimensiunea cache-ului, dimensiunea liniei cache-ului, tipul, arhitectura și aplicațiile. O cifră bună de performanță pentru aplicațiile comerciale poate fi în intervalul de succes de 80-95% ^[8] .

Structură de bază

Există trei structuri de bază de stocare în cache:

• Memorie cache complet asociativă (memoria cache complet asociativă)
• Direct Mapped Cache (cache cartografiat direct)
• Cache Set Associative (cache parțial asociativ)

Memorie cache complet asociativă

Memorie cache complet asociativă

Fiecare bloc de memorie poate fi stocat în orice locație cache. Se numește „complet asociativ”, deoarece fiecare dată cache este asociată cu adresa sa de memorie completă. Cache - ul este împărțit în două bănci: Directory (indicele de ghidare) și banca de date (date). Directorul este la rândul său împărțit în două câmpuri, bitul atributului de date (bitul atributului de date ) sau Starea (starea) și adresa ADD a datelor (adresa blocului de memorie). Biții atributului de date includ bitul Valid și pot include, de asemenea, mai mulți alți biți de stare, cum ar fi bitul modificat ( M ) (bitul de modificare), bitul partajat ( S ) (bitul de partajare) și altele (a se vedea sub Stare cache ). În plus față de acești biți, pot fi incluși și „biți de protecție”, cum ar fi supraveghere / utilizator și protecție la scriere - „ protecție la scriere ”. Adresa complet asociată a blocului de memorie este stocată în cache în memoria cache complet asociativă. Când se citesc date din cache, toate adresele stocate în „Director” sunt comparate simultan cu adresa blocului de memorie al datelor solicitate. Dacă se găsește o adresă cu date „valide” ( accesare ), datele corespunzătoare sunt citite din cache. În caz de ratare, blocul de date este citit de MM. Datele citite de MM sunt, de asemenea, memorate în cache, ceea ce va înlocui (suprascrie) o linie cache aleasă în conformitate cu politica de înlocuire . Memoria cache complet asociativă are o eficiență ridicată. Datele pot fi stocate oriunde în cache, dar sunt scumpe din punct de vedere al circuitelor. Necesită rute de acces simultan independent și un comparator pentru fiecare intrare (intrare) a cache-ului. Prin urmare, dimensiunea acestui cache este de obicei foarte mică și este utilizată doar pentru cazuri specifice (de exemplu, în TLB ). În mod normal, nu este folosit niciodată ca memorie cache , dar sunt folosite în schimb cache - uri direct-mapate și set-asociative .

Memorare cache directă

Cache direct mapat

În cache cartografiat direct - cartografiat direct Fiecare bloc de memorie poate fi stocat într-o singură intrare cache. Intrarea (adică locația cache) în care se stochează blocul este derivată direct din adresa de memorie (de aici și numele "Direct-Mapped" - mapat direct).

Adresarea cache

Dimensiunea cache-ului este mai mică decât MM, deci adresa de memorie trebuie redusă pentru a se potrivi spațiului cache. Toate datele de memorie trebuie să poată fi stocate într-un spațiu mai mic, dar evident nu toate în același timp. Mulți algoritmi, numiți codare hash (sau hash), sunt folosiți pentru a face acest lucru. Soluția obișnuită ^[9] pentru a obține adresa cache este utilizarea directă a unei părți a adresei de memorie, și precis câmpul numit Index (index), adică, excluzând decalajul , cei mai puțin semnificativi biți ai adresei ( cel mai puțin semnificativ bit) - LSB), vezi fig. Adresarea cache . Offset-ul ( offset de linie) este câmpul de adresă utilizat pentru adresarea internă a liniei cache la nivelul de octeți. De exemplu, având o adresă de memorie pe 32 de biți (4 GB spațiu) și o dimensiune cache de 4 MB cu o linie cache de 256 B, cei mai puțin semnificativi biți (8-21), Indexul , sunt utilizați pentru a selecta cache-ul adresa liniei. Această soluție de adresă liniară în memoria virtuală Demand-paging ( memorie virtuală ), (vezi și mai jos adresarea virtuală ), permite stocarea unei pagini complete de memorie ( pagina de memorie ) în cache. Toate datele care au același index , numite sinonime, sunt stocate în aceeași intrare, astfel încât un singur sinonim la un moment dat poate fi stocat în cache (conflict sinonim). Sinonimele diferă între ele pentru MSB (Cele mai semnificative biți - cei mai semnificativi biți ai adresei). Pentru a distinge diferitele sinonime, eticheta de adresă MSB (eticheta de adresă) este stocată în directorul cache (în exemplele anterioare de biți (22-31). Când se citesc date din cache, MSB din directorul cache-ului este comparat cu MSB-ul adresei de memorie a datelor care urmează să fie citite. În ceea ce privește memoria cache complet asociativă, în cazul unei lovituri, datele sunt citite din memoria cache, altfel în caz de lipsă, din memorie. două sinonime, în ceea ce privește adresa, este un multiplu al dimensiunii cache-ului. Conflictul de sinonime scade pe măsură ce crește dimensiunea cache-ului, deoarece distanța dintre sinonime crește. necesar Pentru a minimiza problema sinonimelor se utilizează setarea cache asociativă.

Set de cache asociativ

Set de cache asociativ

Setul cache asociativ (sau multi-via-direct-maped ) este o combinație a celor două abordări anterioare și este utilizat pentru a reduce conflictul dintre sinonime. Acest cache este compus dintr-un set de cache-uri Direct Mapped identice, adresate exact în același mod, astfel încât pentru fiecare intrare există un „set” (grup, moduri) de linii cache alternative pentru a stoca mai multe sinonime. Sinonimele pot fi stocate în orice set de intrări selectate, în funcție de algoritmul „ politică de înlocuire ” utilizat, în general LRU . În mod normal, numărul de seturi este cuprins între 2-8 / 16 sau mai mult, până la 48 ( AMD Athlon ^[10] ) și 128 ( POWER3 ^[11] ), în funcție de tipul de cache (Instrucțiuni / Date). În memoria cache asociativă, se utilizează un comparator de adrese pentru fiecare set. O memorie cache asociată direct poate fi văzută ca o memorie cache asociativă cu un singur set și o memorie cache complet asociativă cu linii n ca o memorie cache asociată n-way cu o singură intrare. În funcție de „ politica de înlocuire ” adoptată, Directorul poate conține sau nu biți de înlocuire pentru a selecta linia cache candidată pentru înlocuire.

Politica de înlocuire

Când sunt disponibile mai multe intrări pentru stocarea datelor, ca în cazul cache-ului complet asociativ și al setării asociative, intrarea care trebuie înlocuită este selectată pe baza „politicii de înlocuire” adoptată. Există politici diferite ^[12] .

Principalele sunt:

• LRU - (Cel mai recent folosit)
• FIFO - (First-In First-Out - First to Enter First to Exit)
• LFU - (Cel mai puțin frecvent utilizat - Mai puțin frecvent utilizat)
• Round-robin (cerc de păsări round-robin - selecție ciclică)
• Aleatoriu (aleatoriu)

- LRU

- Utilizat în mod obișnuit pentru setările cache asociative.

- Separat pentru fiecare set , fiecare intrare este asociată cu un „contor de vârstă” ( index de înlocuire ). Capacitatea maximă a acestui contor este egală cu numărul de seturi . Linia cache a unei intrări cu cea mai mare valoare este cea care va fi înlocuită cu o nouă linie cache. De fiecare dată când o linie cache este accesată, contorul său este setat la zero, în timp ce celelalte contoare ale celorlalte linii ale aceleiași intrări cu o valoare mai mică decât linia cache accesată sunt mărite cu 1. De exemplu, cu o setare cache cu 4 căi Asociativ și, prin urmare, doi biți pe contor, contoare având valorile 0-3-2-1 (setate de la 1 la 4), ordinea de înlocuire va fi a 4-a -1-a -2-a-3-a. Cea mai mare valoare (3) este cea mai veche și cea mai mică (0) cea mai recentă (sau ar putea fi și invers într-o implementare alternativă).

- dacă se accesează Setul 3 (valoarea 2), situația finală va fi: valoarea contoarelor 1-3- 0 -2, ordinea de înlocuire 3a -1a - 4a -2a. Setul 3 este mutat pe ultimul loc.

- În cazul înlocuirii unei linii cache, linia înlocuită va fi Set 2 și contoare vor deveni 2-0 -1-3: a 2-a-4-a 3-a -1-a comandă de înlocuire.

- FIFO

- Se utilizează în seturile cache asociate.

- Același algoritm ca LRU, dar cu diferența că contoare sunt actualizate numai atunci când o linie cache este înlocuită. Linia cache cu cea mai mare valoare este înlocuită, iar contorul său este setat la zero, în timp ce toate celelalte contoare sunt mărite cu 1.

- LFU

- Cel mai eficient algoritm, dar cel mai scump. În general nu este utilizat.

- Round-robin

- Utilizat în cache-uri asociative complete.

- Un indicator selectează linia cache care trebuie înlocuită. Acest indicator este mărit cu 1 la fiecare înlocuire a unei linii cache. Acest lucru se face ciclic. Este nevoie de un singur indicator.

- Simplu și ieftin de implementat.

- Aleatoriu

- Utilizat în cache-uri asociative complete.

- Round-robin actualizat la fiecare ceas / acces în loc de fiecare înlocuire.

- Simplu și ieftin de implementat.

Tipuri de cache

Există două tipuri de cache:

• Cache de instrucțiuni
• Memorie cache de date

Cache de instrucțiuni și cache de date

Există două tipuri de informații stocate în MM, instrucțiuni (numite și cod) și date (sub formă de operanzi sau stivă - consultați Stack cache )

• Memoriile cache unificate stochează ambele.
• În cache-uri separate, instrucțiunile și datele sunt stocate în cache-uri dedicate; aceste cache sunt denumite pe scurt „I-Cache” pentru cache-urile de instrucțiuni și „D-Cache” pentru cache-urile de date. Există trei avantaje ale cache-urilor separate:

1. Reducerea interferenței între două structuri de date diferite; cu cât instrucțiunile sunt mai secvențiale, cu atât datele sunt mai aleatorii. În plus, această abordare permite diferite tipuri de implementare. În general 2 - 4/8-way Setați cache-uri asociative pentru cache-ul de instrucțiuni, 4 - 16-way sau mai mult (128) pentru cache-ul de date ^[11] .

2. Permite implementarea arhitecturii „Harvard” ; acest tip de arhitectură mărește paralelismul de execuție al procesorului, deoarece permite accesul la instrucțiunile ulterioare (preluare, acces timpuriu) în paralel cu accesul și executarea datelor referitoare la instrucțiunile anterioare (căi de acces independente separate);

3. Nicio interferență, în sistemele multiprocesor, între activitatea Snoopy și activitatea procesorului pe I-Cache; Activitatea Snoopy se face, în general, numai în cache-ul D (consultați politica de scriere și interferența dintre Snoopy și activitatea procesorului ).

Majoritatea cache-urilor pot gestiona o singură solicitare la un moment dat. Dacă se face o cerere și apare o eroare , memoria cache trebuie să aștepte datele din memorie, iar în timp ce așteaptă aceasta, memoria cache rămâne „blocată”. Un cache fără blocare (sau fără blocare) are capacitatea de a lucra la alte solicitări în timp ce așteaptă date „ratate” din memorie.

Memorie cache inclusivă și exclusivă

Memoria cache poate fi inclusă sau exclusivă:

• Inclusiv înseamnă că conținutul cache-ului L1 este inclus și în cache-ul L2, adică L1 este un subset al lui L2 .

• Memoria cache L2 stochează o copie a L1 plus datele „ expulzate ” din L1 (date expulzate în cazul înlocuirii liniei).
• Memoria cache L2 inclusă implică faptul că L1 trebuie să fie scris în L2.
• Dimensiunea efectivă a cache-ului global al sistemului este egală cu dimensiunea L2 singur.

Aceeași relație între L3 și L2 inclusiv, dacă se folosește L3.

• Operațiuni

• Miss în L1 și Hit în L2

- Linia cache L2 este copiată în L1.

• Miss în L1 și în L2

- Datele sunt citite din memorie și stocate atât în ​​L1 cât și în L2, înlocuind aceeași linie înlocuită în L2 în L1, dacă L1 conține o copie, în caz contrar linia cache care trebuie înlocuită în L1 va fi aleasă în conformitate cu politica de înlocuire utilizată.

- Când o linie L2 este înlocuită, din cauza unui conflict ratat în L2, inclusiv orice copie a L1 trebuie oprită (evacuată) pentru a menține incluzivitatea.

• Exclusiv (sau neinclusiv ) înseamnă că datele pot fi stocate numai într-un cache .

• Memoria cache L2 conține numai liniile cache de copiere (scrise înapoi de la L1 la L2), care au fost evacuate din L1 din cauza conflictelor ratate (liniile victimei ). Acest tip de cache este, prin urmare, numit și „cache de victimă”

(Notă - Dimensiunea globală a memoriei cache este suma dimensiunilor ambelor cache).

Aceeași relație între L3 și L2 exclusive, dacă se folosește L3.

• Operațiuni

• Miss în L1 și Hit în L2

- Liniile cache ale L1 și L2 sunt schimbate între ele, adică linia cache a L1 este stocată în L2 și linia L2 în L1.

• Miss în L1 și în L2

- Datele citite din memorie sunt stocate direct în L1 și linia cache înlocuită de L1 ( datele victimei ) este transferată în L2 înlocuind o altă linie cache în conformitate cu politica de înlocuire utilizată.

• Inclusivitate vs Exclusivitate : Inclusivitatea este preferabilă în sistemele multiprocesor / multi-core bazate pe magistrală, adică bazate pe magistrală pentru consistența datelor, altfel verificarea consistenței trebuie făcută în toate cache-urile (vezi mai jos Interferența dintre Snoopy și Activitatea procesorului ). Inclusivitatea facilitează coerența cache-urilor. Dezavantajul cache-ului inclus este că cache-ul L2 conține date redundante, ceea ce înseamnă o reducere a dimensiunii cache-ului general. Acest lucru este adevărat numai dacă dimensiunile cache L1 și L2 sunt comparabile. Adesea mărimea L2 este un ordin de mărime în comparație cu L1, prin urmare reducerea ratei de lovire datorată reducerii dimensiunii globale poate fi foarte mică (câteva procente), luând în considerare, de asemenea, că în intervalul 80-95 % din hit-rate pe măsură ce mărimea crește, câștigul ratei de hit-uri tinde rapid să fie plat ^[8] . Aceleași considerații pot fi luate pentru cache L3 versus L2 (a se vedea de exemplu Shanghai (AMD) vs Nehalem-EP (Intel) ^[13] ).

Scrieți politica

Politica de scriere - sau politica de scriere - determină modul în care sunt tratate scrierile în memoria datelor cache. În general, numai D-Cache este afectat, deoarece în mod normal instrucțiunile nu se auto-modifică și, în caz de auto-modificare, software-ul forțează scrierea acestui cod (Instrucțiuni) numai în memorie fără a implica cache-ul (vezi de exemplu AMD64 Cod auto-modificat ^[14] )

Există două tipuri de politici:

- Scrie prin

- Rescriere (sau copiere )

Scrie prin

• Datele sunt scrise simultan atât în ​​cache, cât și în memorie sau în cache și apoi în memorie (de unde și numele)

Redactare (sau copiere) (rescrie, scrie sau copia)

• Datele sunt actualizate numai în cache. Este rescris în memorie numai atunci când este necesar, de exemplu în cazurile de „înlocuire” (suprascriere) a liniei cache sau când este solicitat de alte cache. Acest lucru reduce traficul de memorie și autobuz, deoarece următoarea actualizare a liniei cache se face numai în cache, fără a afecta memoria. În directorul cache, bitul „ D ” sau „ M ” ( D irty = murdar sau M odificat) este activat (setat) - (vezi mai jos statele cache ).

În cazul ratării în scris, există două soluții diferite:

Scrieri alocate (scriere cu alocare)

Scrie aloca pe dor (alocare de scriere pe dor) , de asemenea , numit Fetch-la-scriere (dobândește , pentru a scrie) sau RWITM (R EAD W i - lea I ntent T sau M odify - citește cu intenția de a modifica) sau citire pentru scriere - citire pentru scriere

• În cazul unei greșeli de scriere, linia cache este citită mai întâi din memoria principală sau dintr-o cache în caz de intervenție cache , apoi este actualizată (modificată) în cache cu noile date (scriere parțială linie: octet, jumătate cuvânt , cuvânt sau cuvânt dublu - 8, 16, 32 sau 64 biți, în funcție de paralelismul operațional intrinsec al procesorului)

Scrieți fără alocare (sau fără scriere - fără alocare)

• Datele sunt scrise direct în MM „ocolind” memoria cache

- Alocarea scrierii este în mod normal asociată cu scrierea înapoi . Scrierea fără alocare poate fi sau nu asociată cu scrierea .

Niveluri de cache

Mai multe cache pot fi utilizate pe un sistem. Cache-urile sunt organizate în niveluri ierarhice. Sunt posibile până la patru niveluri, L1-L4 sau mai mult ^[15] . Un cache mai mare are o rată de acces mai bună, dar un timp de latență mai mare. O memorie cache pe mai multe niveluri garantează accesul rapid cu o rată de acces mare. Cache-ul multi-nivel funcționează, în general, verificând mai întâi cel mai mic cache de cel mai mic nivel, nivelul 1 (L1). Dacă lovește, procesorul rulează rapid. Dacă cea mai mică memorie cache lipsește, se verifică următoarea memorie cache (L2) și așa mai departe până la cel mai înalt nivel. Tehnologia îmbunătățită permite suficient spațiu pentru a implementa un cache L1 mic în interiorul cipului procesorului. O memorie cache internă este mai rapidă decât una externă, dar are o rată de lovire mai mică datorită dimensiunii sale mai mici, de obicei în intervalul 8KB până la 64KB. Pentru a crește dimensiunea totală a cache-ului și, astfel, rata de accesare, se utilizează un cache L2 mai mare strâns cuplat la procesor. O dimensiune tipică a memoriei cache L2 este cuprinsă între 64KB și 8MB. Cache-ul L2 poate fi extern sau intern pentru cipul sau pachetul procesorului . În acest din urmă caz, prin urmare, se poate utiliza o memorie cache L3 externă și mai mare (4-256 MB). În sistemele multi-core, L3 poate fi implementat într-un MCM ( modul multi-chip ) (vezi de exemplu POWER5 IBM, AMD Bulldozer ). În mod normal, L1 este o memorie cache asociativă de instrucțiuni și seturi de date. Memoria cache L2 poate fi unificată sau separată, precum și o memorie cache asociată direct mapată sau setată. La fel și pentru memoria cache L3.

Ierarhia Cache pe mai multe niveluri

Funcția ierarhică a cache-urilor pe mai multe niveluri

L1 → În interiorul cipului procesorului. Acces rapid.

- Gama 8KB - 64KB ( POWER8 ^[7] )

L2 → Pentru a crește dimensiunea generală și pentru consistența datelor

- Snoopy pentru multiprocesorul bazat pe autobuz (bazat pe autobuz),

partajat pentru multi-core .

- Poate fi extern sau intern la cipul procesorului.

- Interval 64KB - 8MB (16MB IBM RS64 -IV) ^[7]

L3 → Pentru a mări dimensiunea totală. De asemenea, utilizat ca cache L2 Victim

(vezi de ex. POWER5 și AMD ) și pentru snoopy în sistemele SMP.

- Gama 4MB - 128MB ^{[7] [16]} . L3 este utilizat dacă L2 este intern chipului sau matriței

L4 → Cache de la distanță pentru cc-NUMA - Sisteme de clusterizare

- Gama> L3 (512 MB sau mai mult) în funcție de numărul de noduri

- uneori utilizat ca cache L3 Victim în procesoare grafice ( GPU-uri ) ^[17] .

Cache multi-bancă ( multi-bancă ) și multi-port ( multi-portată )

Arhitecturile procesorului suprascalar (procesoare suprascalare = unități de operare multiple) sunt capabile să execute instrucțiuni în paralel simultan (exploatând paralelismul intrinsec al fluxului / instrucțiunilor multithread - flux continuu / multi-ramificare). În acest tip de procesoare există mai multe unități funcționale de același tip cu circuite suplimentare pentru „trimiterea” instrucțiunilor către diferitele unități. În majoritatea acestor sisteme „suprascalare” acestea includ mai mult de o unitate aritmetico-logică (unitate pentru operații aritmetice și logice). De exemplu în IBM POWER3 ^[18] până la opt instrucțiuni, două virgulă mobilă (virgulă mobilă), două încărcare / stocare (citire / scriere = mișcare de date - în engleză „move”), trei punct fix - (punct fix), două ciclu unic, un ciclu multiplu și o „ramură” (instrucțiune de salt - instrucțiunile sunt executate secvențial până când se găsește o instrucțiune „sărit” care sare dintr-o nouă secvență) care poate fi executată în același ciclu. Instrucțiunile disponibile sunt trimise din uz ( din funcție ) din cozile de ieșire, permițând ca aceste instrucțiuni să fie executate din uz prin utilizarea tehnicii de redenumire a registrului (înlocuirea unui registru deja utilizat cu un registru diferit - nume de schimb) pentru sincronizare și reordonare a rezultatelor.

Executarea în paralel a instrucțiunilor necesită acces simultan la memoria cache L1 D. Conflictele apar atunci când două sau mai multe cereri accesează simultan aceeași bancă cache. Aceste conflicte pot fi parțial eliminate prin utilizarea cache-urilor multi-bancare și / sau multi-port ^{[19] [20] [21]}

Există mai multe soluții ^{[22] [23]} :

• Cache multi-bancar
• Cache cu mai multe porturi
• Copii multiple
• Multi-porturi virtuale
• Soluție hibridă

Cache multi-bancar

Memoria cache L1 este împărțită în mai multe bănci cu adrese independente. Există două abordări:

• Adresare liniară
• Memorie cache intercalată (cache intercalat)

Adresare liniară

Băncile sunt adresate în paralel printr-o bară transversală (conexiuni transversale directe). Adresa este liniară, adică următoarea adresă a ultimei adrese a unei bănci este prima adresă a următoarei bănci. Băncile sunt selectate în ordine prin utilizarea celor mai semnificativi biți (MSB) ai „Indexului” adresei (de exemplu, cu 8 bănci, cei trei biți 21-19 ai exemplului în adresarea cache ). Mai multe bănci pot accepta mai multe cereri pe ciclu atunci când nu se adresează aceleiași bănci. Abordarea multi-bancară poate fi eficientă pentru aplicațiile care au o localitate spațială slabă a datelor (date statistice independente), dar pentru aplicații cu o localitate spațială bună, cum ar fi în accesările consecutive, nu sunt permise accesuri simultane multiple din cauza conflictelor bancare . "(coliziune bancară)

Memorie cache intercalată (cache intercalată)

8-way Cache Interleaving

Liniile cache consecutive sunt stocate pe bănci consecutive. Adresarea liniilor cache este „întrețesută” (distribuită orizontal) între bănci așa cum se arată în fig. în lateral. Băncile sunt selectate de biții cei mai puțin semnificativi ai „Indexului” adresei (de exemplu, cu intercalare cu 8 căi, biții 10-8 din exemplul de mai sus în adresarea cache ). Comunemente il numero di banchi varia da due, quattro od otto (vedi ad es. IBM POWER3 ^[24] ), chiamati two-way , four-way o eight-way interleaving rispettivamente. La cache interleaving da vantaggi specialmente nelle operazioni su stringhe di dati multipli. Per esempio, avendo una cache two-way interleaving (indirizzo pari nel Banco 0 e dispari nel Banco 1) e due programmi (threads) che operano su due stringhe indipendenti, il primo programma può accedere al Banco 0 mentre il secondo al Banco 1. Nel successivo accesso, il primo programma può accedere al Banco 1 mentre il secondo al Banco 0, e così via alternativamente. In caso di "conflitto di banchi" (bank collision), cioè accesso simultaneo allo stesso banco, un programma all'inizio deve aspettare un ciclo, poi può iniziare. Anche negli accessi casuali simultanei multipli questo sistema offre vantaggi, dipendente dal numero di banchi. La probabilità di conflitto diminuiscono all'aumentare del numero di banchi. Esempio di interleaving: la cache L1 di POWER3 ^[25] con interleaving a 8-vie è in grado di servire due "load" (letture), una "store" (scrittura) e una rilettura (reload) di una linea di cache per ciclo.

Cache multi-porte ( multi-port cache , true multi-porting o ideal multi-porting )

Porte multiple permettono di fare accessi paralleli multipli alla cache nello stesso ciclo di clock, che operano in modo indipendente fra loro ^{[7] [26]} .

Le cache multi-porte permettono di ottenere la più alta frequenza di accesso per ciclo, ma sono complesse e perciò lente e costose. Inoltre comporta l'uso di strutture di celle non standard. Mentre una singola celle di memoria statiche richiede 6 transistor a effetto di campo (field-effect), per aver una porta doppia sono necessari 2 transistor in più. Perciò questa soluzione può essere usata per solo poche porte, normalmente due per le letture e una per le scritture (es. POWER4 IBM ).

Multiple copie ( mirroring o cloning )

Cache con "n" identiche copie (cloni) con indirizzamento simultaneo indipendente. Limitazioni: copie replicate senza benefici di spazio di memorizzazione. Inoltre le richieste di scrittura devono essere fatte simultaneamente su tutte le copie, cosicché nessun'altra richiesta può essere inviata in parallelo. Poiché circa il 30% di accessi alla memoria sono scritture ^[27] , questa soluzione ha dei severi limiti.

Multi-porte Virtuali (time division multiplexing - divisione di tempo distribuita)

La "time division multiplexing" è una tecnica che può essere anche riferita come "cache over-clocking" cioè clock con frequenza maggiorata. Funzionamento della cache con frequenza 2x (3x, 4x) della frequenza del processore in modo che la cache può essere acceduta due (tre, quattro) volte per ciclo (clock).

Soluzione ibrida

Combinazione della soluzione cache interleaving con multi-porte. I banchi multipli interleaving permettono accessi paralleli a basso costo mentre le porte multiple riducono i conflitti di banco.

Coerenza della cache ( cache coherency )

I processori possono condividere una cache comune. Le cache condivise generalmente sono usate per la coerenza dei dati nei sistemi multi-core (Multi-chip) e per la riduzione dei costi. Nei sistemi come il multiprocessore simmetrico (SMP) , il multi core e il cc-NUMA , dove viene usata una cache dedicata per ogni processore , core o nodo , si può verificare un problema di coerenza, o coerenza, dei dati quando uno stesso dato è memorizzato in più di una cache e si verifica che un dato viene modificato in una cache. Può essere risolto in due modi:

1. invalidando tutte le copie delle altre cache (broadcast-invalidate - diffusione invalidazione);
2. aggiornando tutte le copie delle altre cache (write-broadcasting - diffusione scrittura).

In entrambi i casi la memoria può essere aggiornata (write through) o non aggiornata (write-back); la coerenza dai dati generalmente riguarda solo i dati (come operandi) e non le istruzioni (vedi Self-Modifying Code ).

Gli schemi si possono classificare in base a:

• Schema Snoopy Vs Directory e Vs Shared caches;
• Protocollo Write through vs Write-back (basati sull'ownership o proprietà);
• Protocollo Update Vs Invalidation (aggiornamento Vs invalidazione);
• Intervention Vs non Intervention (intervento Vs non intervento);
• Protocollo dirty-sharing Vs non dirty-sharing (dati modificati condivisi Vs non condivisi - MOESI Vs MESI).

Tre approcci sono adottati per mantenere la coerenza dei dati:

1. Bus watching o Snooping : generalmente usato per i sistemi SMP o Sistema Multiprocessore Simmetrico / multi-core basati sul bus;
2. Directory-based - Message-passing : basati sulla directory e scambio di messaggi; possono essere usati in tutti i sistemi, ma tipicamente nei sistemi cc-NUMA e nei sistemi multi-core estesi;
3. Shared cache (cache condivisa): generalmente usata nei sistemi multi-core .

Bus watching o Snooping

SMP - Symmetric Multiprocessor System

Protocollo usato nei sistemi con bus, come ad esempio nei sistemi SMP. Sistema operante sotto un unico sistema operativo con due o più processori omogenei e con una memoria principale centralizzata condivisa. Ciascun processore ha una propria cache che agisce come ponte tra il processore e la memoria principale. La connessione è fatta usando un bus di sistema (system bus) o un crossbar (xbar, connessioni incrociate) ^[28] o un mix dei due precedenti sistemi, bus per gli indirizzi e crossbar per i dati (data crossbar) ^{[29] [30] [31]} .

Il limite maggiore di questi sistemi è il traffico e la larghezza di banda di memoria (quantità di dati al sec.). La banda può essere aumentata usando un largo canale dati, un crossbar dati, la memory interleaving e la transazioni di dati fuori ordine (out of order data transaction). Il traffico può essere ridotto usando una cache che agisce da filtro verso la memoria condivisa. La cache è quindi un elemento essenziale nei sistemi SMP con memoria condivisa (shared-memory). Nei sistemi multiprocessori con cache separate che condividono una memoria comune, uno stesso dato può essere memorizzato in più di una cache. Un problema di coerenza nei dati nasce quando un dato è modificato in una sola cache. I protocolli per mantenere la coerenza fra processori multipli sono chiamati cache-coherency protocols (protocolli di coerenza delle cache). Generalmente nei sistemi SMP la coerenza si basa sull'approccio chiamato Bus watching (sorveglianza del bus) o Snoopy. In un sistema basato sullo snoopy, tutte le cache controllano le transazioni del bus per intercettare i dati e verificare se ha una copia nella propria cache. Vari protocolli di coerenza sono usati per mantenere la coerenza dei dati tra cache ^[32] . Questi protocolli sono generalmente classificati solo in base agli stati della cache (da 3 a 5 e 7 o più) e le transazioni tra questi, ma questo potrebbe creare qualche confusione in quanto la definizione di un protocollo così fatta è incompleta perché mancante di importanti ed essenziali informazioni come le azioni che questi producono; queste azioni possono essere indotte dal processore o dal bus (esempio "intervention", "invalidation", "broadcasting", "updating", ecc.). Il tipo di azioni sono dipendenti dalle implementazioni adottate. Protocolli aventi gli stessi stati e le stesse regole di transazioni possono essere differenti, per es. il protocollo MESI con "shared intervention" (intervento su dati condivisi puliti (clean)) e MESI senza "intervention". Protocolli con stati differenti possono essere praticamente lo stesso protocollo, per esempio i protocolli 4-stati MESI Illinois e 5-stati MERSI (IBM) / MESIF-Intel sono solo un'implementazione diversa delle stesse funzionalità. I più comuni protocolli sono il protocollo 4-stati conosciuto con l'acronimo MESI e il 5-stati MOESI. Altri protocolli usano gli stessi stati - o un sottoinsieme di questi - ma con differenti implementazioni e spesso con una differente ma equivalente terminologia. Con il termine MESI o MOESI, o un sottoinsieme di questi, generalmente si fa riferimento a una classe di protocolli piuttosto che a uno specifico protocollo.

Stati della cache

• M =Modified (modificato) o D =Dirty (sporco/alterato) o DE =Dirty-Exclusive (sporco esclusivo) o EM =Exclusive Modified (esclusivo modificato)
  • modificato o sporco, cioè modificato solo in una cache - write-back in caso di rimpiazzo (replacement); il dato è memorizzato in una sola cache, ma il dato in memoria non è aggiornato (invalido);
• O =Owner (proprietario/responsabile) o SD =Shared Dirty (sporco condiviso) o M =Shared Modified (sporco modificato) o T =Tagged (etichettato/contrassegnato)
  • modificato, potenzialmente condiviso, proprietario - write-back in caso di rimpiazzo; il dato può essere memorizzato in più di una cache, ma il dato in memoria non è aggiornato (invalido). Solamente una cache è "owner" (proprietario), le altre cache sono marcate "shared" (condivise). In caso di una richiesta di lettura sul bus, il dato viene fornito dall'owner anziché dalla memoria.
• E = Exclusive o R = Reserved o VE = Valid-Exclusive o EC = Exclusive Clean o Me = Exclusive
  • esclusivo o riservato o valido esclusivo o esclusivo pulito; il dato è memorizzato solo in una cache e clean (pulito, cioè valido) in memoria.
• S = Shared (condiviso) o V = Valid (valido) o SC = Shared Clean (condiviso pulito)
  • Dato potenzialmente condiviso con altre cache. Il dato può essere clean o dirty. Il termine "clean" in SC è fuorviante perché può essere anche dirty (vedi Protocollo Dragon )
• I = Invalid
  • Linea di cache invalida. Se la linea di cache non è presente (tag non corrispondente) è equivalente a linea invalida, perciò dato invalido significa dato presente ma invalido oppure non presente in cache

Stati speciali

• F = Forward (in avanti) o R = Recent (recente)
  • stati addizionali del protocollo MESI . L'ultimo dato letto. È uno speciale stato "Valido" che è l'owner per dati condivisi non modificati , usato in alcuni protocolli estesi di MESI (MERSI o R-MESI IBM ^{[33] [34]} , MESIF - Intel ^{[35] [36]} ). Lo stato R/F è usato per permettere l' "Intervention" quando il dato è "Valido" ma condiviso con le altre cache. Questa cache è responsabile per l'intervention (shared intervention). Su una richiesta di lettura del bus, il dato viene fornito da questa cache invece che dalla memoria. MERSI e MESIF sono lo stesso protocollo solo con una differente terminologia (F al posto di R). Qualche volta R è riferito anche come "Shared Last " - ultimo condiviso (S _L ) ^{[26] [37]} . Lo stato R (Recent) è usato non solamente nel protocollo MERSI = R-MESI ma in diversi altri protocolli. Questo stato può essere usato in combinazione con altri stati. Per esempio RT-MESI , HR-MESI, HRT-MESI, HRT-ST-MESI ^{[38] [39]} . Tutti i protocolli che usano questo stato saranno riferiti come R-MESI type.
• H = Hover - H-MESI (stato addizionale del protocollo MESI) ^[40]
  • Lo stato Hover (H) (sospeso) permette a una cache di mantenere un indirizzo nella directory anche se il corrispondente valore della linea di cache è una copia invalida. Se il valore corrispondente appare sul bus (Tag dell'indirizzo coincidente) dovuto a una "Read" o "Write" valida, il dato della linea di cache è aggiornato con una copia valida e il suo stato è cambiato in S. Questo stato può essere usato in combinazione con altri stati, per es. HR-MESI, HT-MESI, HRT-MESI, HRT-ST-MESI ^{[38] [41] [42]}

Interferenze tra Snoopy e attività del processore

L'attività dello Snoopy richiede l'accesso alla Directory della cache e può essere in conflitto con gli accessi concorrenti del processore. Questa interferenza fa aumentare la latenza della cache.

Per ridurre o eliminare questa interferenze possono essere usate tre soluzioni:

• Cache multi-livello inclusive
• Cache istruzioni e dati separate
• Dual-port e dual-directory

1. Due o più livelli di cache "inclusive" riducono queste interferenze perché circa 85-90% ^[8] degli accessi del processore (per i dati) è fatto al livello più basso di cache.
2. Cache "Separate" Istruzioni e Dati riducono l'interferenza perché lo snoopy normalmente è fatto solamente sulla cache Dati (vedi Write Policy ), perciò i conflitti sulle Istruzioni vengono eliminati.
3. Lo snoopy spende la maggior parte del suo tempo a monitorare un traffico parassita. Una " dual-Port Directory " (directory con due porte) o " dual-cache " (cache con due porte - drectory+dati) o un " dual-directory " (doppia directory) ^[43] elimina quasi completamente le interferenze. Una porta/directory è usata per lo snoopy e l'altra per il processore (i conflitti avvengono solo quando lo snoopy e il processore fanno uso della stessa entry, ma questo evento e comparativamente raro).

Operazioni di coerenza Snoopy

L'attività dello Snoopy richiede l'accesso alla Directory della cache e può essere in conflitto con gli accessi concorrenti del processore. Questa interferenza fa aumentare la latenza della cache. Per ridurre o eliminare questa interferenze possono essere usate tre soluzioni:

• Cache multi-livello inclusive
• Cache Istruzioni e Dati separate
• Dual-Port e Dual-Directory

1. Due o più livelli di cache "inclusive" riducono queste interferenze perché circa 85-90% ^[8] degli accessi del processore (per i dati) è fatto al livello più basso di cache.
2. Cache "Separate" Istruzioni e Dati riducono l'interferenza perché lo snoopy normalmente è fatto solamente sulla cache Dati (vedi Write Policy ), perciò i conflitti sulle Istruzioni vengono eliminati.
3. Lo snoopy spende la maggior parte del suo tempo a monitorare un traffico parassita. Una " dual-Port Directory " (Directory con due porte) o " dual-Cache " (cache con due porte - Directory+Dati) o un " dual-Directory " (doppia Directory) ^[43] elimina quasi completamente le interferenze. Una porta/directory è usata per lo snoopy e l'altra per il processore (i conflitti avvengono solo quando lo snoopy e il processore fanno uso della stessa entry, ma questo evento e comparativamente raro).

Si distinguono tre operazioni: transazioni di bus, caratteristiche dei dati e operazioni di cache:

• Transazioni di bus : le principali operazioni sono:
  • Write Through : la linea di cache è aggiornata sia in cache che in MM o solo in MM (write no-allocate); semplice da implementare, alta occupazione di banda. Va bene per scritture singole.
  • Write-Back : il dato è scritto solo in cache. Il dato è scritto indietro in MM (Write-Back) solo quando sarà rimpiazzato (replacement) o quando richiesto dalle altre cache (vedi Write Policy ); soluzione intermedia: Write Through per la prima scrittura, Write-Back per le successive (protocolli Write-once e Protocollo Bull HN ISI ^[44] )
  • Write Allocate : in caso di miss il dato è letto dall'"owner" o dalla MM, poi il dato è scritto in cache (aggiornato - scrittura parziale) (vedi Write Policy )
  • Write no-Allocate : in caso di miss il dato è scritto in MM senza coinvolgere la cache, oppure, come nel protocollo Protocollo Bull HN ISI , è scritto nell '"owner" , cioè nella D o SD cache (owner updating - aggiornamento dell'Owner), se è presente, altrimenti in MM; Write-no-Allocate normalmente è associato al Write Through.
  • Cache Intervention (o brevemente "intervention " - intervento)
    • Shared Intervention: shared-clean intervention (intervento su dati non modificati); in caso Read Miss (mancanza di lettura) il dato viene fornito dall' "owner" - E o R / F o anche S invece che dalla MM (vedi protocolli Illinois , IBM R-MESI type and Intel MESIF ):
    • Dirty Intervention (intervento su dati modificati): in caso di Read Miss il dato è fornito dagli "owner" M (D) o O (SD) o E (R) (Non per E (R) nella proposta originale del protocollo MOESI ^[45] e in alcune altre implementazioni tipo-MOESI) invece che dalla MM (es. protocollo MOESI, RT-MESI, …)
    • L'"Intervento" è una soluzione migliore rispetto al "non-Intervento" perché le transazioni cache-to-cache (da cache a cache) sono molto più veloci rispetto all'accesso alla MM, e in più si riduce il traffico di memoria (aumento di banda). MESI esteso Illinois e R-MESI type / MESIF sono perciò molto più efficienti rispetto al protocollo MOESI (vedi MESI vs MOESI )
  • Invalidation : in caso di Write Hit con stato S (V) o O (SD) (shared) una transazione di bus è inviata per invalidare tutte le copie delle altre cache (Write-invalidate)
  • Write-broadcast (Write-update) : (scrittura distribuita), in caso di "Write Hit" con stato S (V) o O (SD) (shared) una scrittura di aggiornamento è inviata a tutte le altre cache per aggiornare le loro copie (es. Intel Nehalem ^[46] , Dragon protocol (Xerox), Firefly (DEC). L'operazione di aggiornamento delle altre cache è a volte chiamata anche Snarfing (arraffare, impadronirsi). Le cache monitorizzano (snoopy) il bus e se si ha hit la cache si impadronisce del dato che transita sul bus e aggiorna la propria cache. Anche l'aggiornamento dello stato H in ( H-MESI ) può essere definito come snarfing. Nel primo caso avviene solo in un'operazione scrittura distribuita, nel secondo caso sia in lettura che scrittura.
  • Intervention-broadcasting : (Intervento con aggiornamento distribuito): in caso di una transazione di intervento, una cache con stato H ( H-MESI ) aggiorna la sua copia invalida con il valore inviato sul bus e il suo stato è cambiato in S ^[41]
  • Write Invalidate vs broadcast: w rite Invalidate è migliore in caso di scritture multiple, tipicamente scritture parziali, fatte da un processore prima che la linea di cache sia letta da un altro processore. Write-broadcast (aggiornamento) è migliore quando si ha un produttore singolo a molti consumatori del dato, ma è peggiore quando una cache è aggiornata con un dato che non sarà più successivamente utilizzato (inutile aumento di traffico sul bus e aumento delle interferenze di cache ). L'invalidazione è la soluzione comune.
• Caratteristiche dei dati : ci sono tre caratteristiche dei dati di cache:
  • Validità : Qualsiasi linea di cache non invalida, cioè stati MOES / D-SD-RV
  • Esclusività : il dato è valido solo su una cache (dato non condiviso) in stato M (D) o E (R), con la MM non aggiornata (dirty) in caso di M (D) e aggiornata (clean) in caso di E (R);
  • Ownership - Proprietà ^[47] : la cache che è responsabile di fornire il dato richiesto in sostituzione della MM (Intervento). - Dipendente dal protocollo, la cache che deve fare l'intervento può essere S - E - M in MESI Illinois , o R / F - E - M in R-MESI type / MESIF o M (D) o O (SD) o anche E (R) (dipendente dall'implementazione) nel tipo MOESI, (es. AMD64 , ^[45] , Bull HN ISI ^[44] - vedi operazione di "Read Miss" sotto).
• Operazioni di cache : le operazioni delle cache sono:
  • Read Hit: il dato è letto dalla cache. Lo stato rimane inalterato; poiché questa è un'operazione ovvia, in seguito non sarà più considerata, anche nei diagrammi di transazione di stato
  • Read Miss : la richiesta di lettura dato è inviata sul bus; ci sono diverse situazioni:
    • Dato memorizzato solamente in MM : il dato è letto dalla MM; la cache è settata E (R) o S (V); E (R) se una speciale linea di bus ( Shared line ) è usata per indicare " nessun dato condiviso " (no data sharing). Usato in tutti i protocolli aventi lo stato E (R) eccetto per i protocolli Write-once e Bull HN ISI (vedi "Write Hit" sotto).
    • Dato memorizzato in MM e in una o più cache in stato S (V) oppure in R/F nel protocollo R-MESI type / MESIF : Ci sono tre situazioni:
      • Protocollo Illinois - una rete di priorità è usata per assegnare in modo arbitrario e temporaneo la "ownership" (proprietà) a una copia S . Il dato è fornito dalla cache selezionata. La cache richiedente è settata S ( shared intervention - intervento tra dati condivisi con MM clean);
      • Protocollo R-MESI type / MESIF con una cache in stato R / F - shared owner ("owner" delle cache condivise); il dato è fornito dalla cache R / F . La cache che fornisce il dato è cambiata in S e la cache richiedente è settata R / F (in read miss la "ownership" è sempre presa dalla cache richiedente) - shared intervention ;
      • In tutte gli altri casi il dato è fornito dalla MM e la cache richiedente è settata S (V).
    • Dato memorizzato in MM e in una sola cache in stato E (R): il dato è fornito dalla cache E (R) o dalla MM, in funzione del protocollo; fornito da E (R) in MESI esteso (es. Illinois , Pentium (R) II ^[48] ), R-MESI type / MESIF e in alcune implementazioni di MOESI (es. AMD64 ); la cache richiedente è settata S (V), o R / F nel protocollo R-MESI type / MESIF e la cache E (R) è cambiata in S (V) o in I nel protocollo MEI. In tutti gli altri casi il dato è fornito dalla MM

• Dato modificato in una o più cache con MM non aggiornata :

• Protocollo tipo MOESI - Dato memorizzato in M (D) o in O (SD) e le altre cache nello stato S (V): il dato è inviato alla cache richiedente dall' "owner" M (D) o O (SD). La cache richiedente è settata S (V) mentre M (D) è cambiato in O (SD); la MM rimane non è aggiornata.
• Protocollo tipo MESI o MEI - Dato memorizzato in M (D) e le altre cache nello stato S (V); ci sono due soluzioni:

1. il dato è inviato dalla cache M (D) alla cache richiedente e contemporaneamente in MM (per es. Illinois )
2. l'operazione è fatta in due passi: la transazione richiedente è temporaneamente sospesa. Si ha il "Copy Back" del dato M (D) in MM, poi la transazione in attesa prosegue leggendo il dato dalla MM (es. protocolli MESI e MSI Synapse )

Tutte le cache sono settate S (V)

• • Write Hit : il dato è scritto in cache; ci sono diverse situazioni:
    • Cache in stato S (V) o R/F o O (SD) (cache condivise)
      • Write invalidate
        • Copy back: il dato è scritto in cache e una transazione di invalida è inviata sul bus per invalidare le altre cache; la cache è settata M (D)
        • Write Through ( Write-once , Bull HN ISI ): il dato è scritto in cache e in MM invalidando tutte le altre cache. La cache è settata R (E)
      • Write broadcasting (es. Firefly , Dragon ); il dato è scritto in cache e una transazione di "broadcasting" è inviata sul bus per aggiornare tutte le altre cache aventi una copia; la cache è settata M (D) se la linea "shared line" non è attiva, altrimenti è settata O (SD). Tutte le altre cache sono settate S (V)
    • Cache con stato E (R) o M (D) (esclusività): la scrittura può essere fatta localmente senza nessun'altra azione. Lo stato è settato (o rimane) M (D)
  • Write Miss
    • Write Allocate
      • Operazione di Read with Intent to Modified operation ( RWITM ): Come per un'operazione di Read più un comando di invalida, successivamente la cache è scritta (aggiornata); la cache richiedente è settata M (D) e tutte le altre cache sono invalidate
      • Write broadcasting (es. Firefly , Dragon ): come per una Read Miss; se la "shared line" non è attiva il dato è scritto in cache e settato M (D), altrimenti come per una Write Hit - Write broadcasting
    • Write-no-Allocate : il dato è inviato alla MM, oppure come nel protocollo Bull HN ISI , solamente alle cache D (M) o SD (O) se presenti, bypassando la cache.

Vari protocolli di coerenza della cache (esempi)

Lo stesso argomento in dettaglio: Protocolli di coerenza della cache (esempi) .

                                                                                Protocolli

• SI                                                                       Write Through
• MSI                                                                    Synapse ^[32]
• MEI                                                                    IBM PowerPC 750 ^[49] , MPC7400 ^[41]
• MES                                                                   Firefly ^[32]
• MESI                                                                  Pentium II ^[48] , PowerPC, Intel Harpertown (Xeon 5400)
• MOSI                                                                 Berkeley ^[32]
• MOESI                                                              AMD64 ^[50] , AMD Opteron ^[28] , MOESI ^[45] , T-MESI IBM ^[42]

                                                                                Terminologia usata

• Illinois                                                                 D-VE-SI                      (= MESI esteso) ^{[32] [51]}
• Write-once o Write-first                                      DRVI                         (= MESI) ^{[32] [52] [53]}
• Berkeley                                                             D-SD-VI                      (= MOSI) ^[32]
• Synapse                                                             DVI                            (= MSI) ^[32]
• Firefly                                                                 D-VE-S                        (= MES) DEC ^[32]
• Dragon                                                               D-SD (SM?)-SC-VE (= MOES) Xerox ^[32]
• Bull HN ISI                                                         D-SD-RVI                  (= MOESI) ^[44]
• Protocollo MERSI (IBM) / MESIF (Intel)             R=Recent - IBM PowerPC G4 , MPC7400 ^{[33] [41]}

                                                                                F=Forward - Intel ^[35] , Intel Nehalem ^{[13] [46] [54]}

• RT-MESI                                                           T=Tagged - IBM ^[42]
• HRT-ST-MESI                                                   H=Hover, R=Recent,T=Tagged, ST=Shared-Tagged - IBM ^{[38] [42]}
• Protocollo POWER4 IBM                                 T-Mu-Me-MSS _L -I (L2 sette stati) ^[26]

                                                                                Mu =Unsolicited Modified - non Sollecitato Modificato Esclusivo - ( M ) ^[55]

                                                                                M =Modified Exclusive - Modificato Esclusivo

                                                                                T =Tagged - Modificato Owner non Esclusivo ( O )

                                                                                Me =Valido Esclusivo - ( E )

                                                                                S =Shared

                                                                                S _L =Shared Last - sourced local" - ( Shared Owner Locale )

                                                                                I =Invalido - ( I )

Directory-based - Message-passing

È noto che i sistemi SMP hanno una limitata scalabilità. La memoria multi-banco e il crossbar dati ^[29] permettono accessi paralleli alla memoria. L'uso di grandi cache riduce il traffico sul bus di sistema ma non le write invalidate (scrittura con invalidazione) o write-broadcast (scrittura con distribuzione). La maggiore limitazione è che l'indirizzo di memoria deve essere monitorato (snoopy) usando un unico bus. Per superare questa limitazione, viene adottata una nuova architettura chiamata " cc-NUMA ".

Il sistema cc-NUMA è un insieme di sistemi SMP chiamati " Nodi " connessi via una rete di connessione che può essere un link (collegamento) formato da un singolo o doppio anello bidirezionale o multi-anello, connessioni punto-punto ^{[28] [35]} o un mix di queste (vedi ad es. sistemi IBM Power Systems ^{[26] [56]} ), intercessione via bus (es. NUMAq ^[57] ), crossbar , segmented bus (bus segmentato - NUMA Bull HN ISI ex Honeywell ^[58] ),Mesh router , ecc..

Esempi di interconnessione:

Double-reverse ring

Segmented Bus

Crossbar

   La caratteristica principale del sistema cc-NUMA è di avere un' unica memoria globale condivisa e distribuita in ciascun nodo
   direttamente acceduta da tutti i processori di tutti i nodi

cc-NUMA System

In un sistema NUMA l'accesso di un processore a una memoria remota di un nodo remoto è più lento rispetto all'accesso alla propria memoria locale. Per questa ragione questo sistema è chiamato NUMA ( N on U niform M emory A ccess - accesso della memoria non uniforme).

L'architettura NUMA è anche chiamata Distributed Shared Memory (DSM) - memoria condivisa distribuita ^[59] .

Normalmente ciascun nodo è un sistema SMP , dove un processore può essere un singolo processore o un multi-core, o un mix dei due, o qualsiasi altro tipo di architettura. La fig. a lato è solo un esempio.

La differenza del tempo di accesso fra una memoria locale e una remota può anche essere di un ordine di grandezza, in dipendenza del tipo di connessione (più veloce nel segmented bus, crossbar e interconnessione punto-punto, più lenta con la connessione ad anelli seriali).

Cache Remota

Terminologia:

(da un punto di vista di un nodo)

• Memoria locale            - memoria del nodo
• Memoria remota           - memoria degli altri nodi remoti
• Dati locali                     - dati memorizzati nella memoria locale
• Dati remoti                   - dati memorizzati nelle memorie remote
• Cache remota              - cache del nodo che memorizza dati letti dalle memorie remote
• Cache locali (L1-L3)    - cache del nodo che memorizzano dati locali e remoti

Per ridurre le differenze di accesso tra dati locali e remoti, viene utilizzata una cache remota ( Remote cache ). Questa cache memorizza i dati letti dalle altre memorie remote . Normalmente questa cache è inclusiva-condivisa ( shared inclusive ) con protocollo MESI. Le cache L1-L3 possono essere tipo MESI esteso (es. R-MESI , RT-MESI , ecc.). Ogni dato remoto memorizzato nelle cache L1-L3 è anche memorizzato in questa cache (per l'inclusività). Questa cache è il 4º livello di cache del nodo per i soli dati remoti ( cache delle memorie remote ), mentre le cache L1-L3 memorizzano sia dati locali che remoti (cache del nodo relativo alla memoria globale). Da un punto di vista interno di un nodo la remote cache può essere vista come un'estensione della memoria locale (dati remoti memorizzati localmente).

Poiché la funzione di questa cache è di ridurre il tempo di accesso remoto almeno come il tempo di accesso della propria memoria locale, può essere usata una tecnologia ibrida - SRAM per la directory, DRAM per la cache dei dati ^[60] . Questa soluzione permette di implementare cache sufficientemente grandi come richiesto da questi sistemi.

La Cache remota può memorizzare sia le istruzioni (codice) che i dati (come operandi), ma normalmente solo i dati sono memorizzati. L'accesso ai dati privati, come il codice ei dati di stack, spesso possono essere elaborati localmente copiando il codice (replicazione del codice) da un altro nodo (aumento dell'efficienza). ^[61]

Coerenza delle Cache in cc-NUMA

cc-NUMA Memory Directory

La coerenza delle cache nei sistemi cc-NUMA (Cache Coherency-NUMA) è ottenuta usando il protocollo noto col nome di Directory-based - Message-passing . Questo approccio è stato proposto per la prima volta da Censier e Feaultrier ^[62] e descritto anche in " The Directory-Based Cache Coherency Protocol for DASH Multiprocessor " ^[63] .

Poiché normalmente non tutti i nodi accedono nello stesso tempo agli stessi dati, il controllo di coerenza può essere molto più efficiente se fatto in modo selettivo sui soli nodi interessati.

Nei sistemi cc-NUMA la coerenza della cache a livello di sistema (inter-nodo) è perciò fatta mediante un protocollo directory-based (basato su una directory), usando una directory associata a ciascuna memoria locale (local memory directory) che tiene traccia dello stato globale di tutti i blocchi della propria memoria locale e un indicatore (" indicator bit ") per indicare quale nodo ha il blocco memorizzato nella propria cache remota. La coerenza all'interno del nodo invece è basata sullo schema bus-snoopy.

Ciascuna entry (linea di ingresso) della directory ha N-1 bit indicatori di nodo e tre stati globali associati a ciascun blocco di memoria che sono una copia degli stati di tutte le cache remote.

• Invalid ( I ) o Uncached ( U ) - nessun nodo ha il blocco nella cache remote. Il blocco è solo nella home, cioè nella memoria locale proprietaria del dato
• Shared-Remote ( S ) - copie valide esistono negli altri nodi
• Exclusive-Remote ( E ) o Dirty-Remote - il blocco è memorizzato nella cache remota di un solo nodo. Nel protocollo MESI il blocco nel nodo remoto può essere Clean-Exclusive o Dirty. Il cambiamento da Clean-Exclusive a Dirty è fatto localmente senza informare la "home directory", cioè la directory della memoria locale proprietaria del blocco. Nel protocollo MSI il blocco nel nodo remoto può essere solo nello stato Dirty anche se non modificato ^{[63] [64]} .

   * La cache remota memorizza i dati letti dalle memorie remote degli altri nodi.
   * La directory della memoria locale tiene traccia dei dati e del loro stato, letti dalla propria memoria locale,
     che sono memorizzati nelle cache remote degli altri nodi ^[65] .

• Attenzione - non va confusa la directory della memoria locale con la directory della cache remota. La prima contiene informazioni sui dati locali, la seconda sui dati remoti

Ci sono quattro possibili situazioni per un nodo:

• Lettura della memoria locale
• Scrittura della memoria locale
• Lettura della memoria remota
• Scrittura della memoria remota

Lettura della memoria locale

cc-NUMA Local Memory Read and Invalidate

• Una transazione di lettura di memoria locale di uno stesso nodo è monitorata e gestita nello stesso modo come in un normale sistema SMP.
• L3 miss
  • In caso di L1-L3 miss, la transazione è monitorata sul System Bus del proprio nodo da tutte le altre cache L3 e dalla "directory della memoria locale", in questo caso per verificare se il dato da leggere è presente nelle altre cache remote e in quali nodi. La directory della memoria locale è vista e gestita come una directory di un'extra cache e più precisamente come una "shared directory" (directory condivisa) di tutte le cache remote di tutti i nodi remoti. L'unica differenza rispetto alle cache L3 (formata da directory+dati) è che il campo dati e il "Tag" della cache non sono memorizzati nello stesso nodo della directory, ma distribuito sugli altri nodi. La comunicazione tra la directory della memoria locale e le cache remote è fatta tramite una connessione "Message-passing" (inviando un messaggio), punto-punto o distribuito usando il vettore "Indicator bit" (il campo dei bit indicatori dei nodi).
  • In caso di stato E (esclusivo) nella directory della memoria locale, un messaggio è inviato all'unica cache remota del nodo dove il dato è memorizzato in attesa della risposta perché la cache potrebbe essere "Dirty".
    • Se il dato è Dirty , il dato è inviato indietro alla "home" e gestita come se provenisse da una cache locale con l'eccezione che lo "Shared-Dirty" non è permesso tra nodi nel protocollo tipo MOESI. Potrebbe essere permesso solo con protocollo tipo T-Mesi con l' "owner" solo nella "home" (migrazione del "Dirty-Owner" nella home) ma normalmente il "Dirty-intervention" e il "Shared-clean intervention" tra nodi non è usato (vedi ad es. Protocollo POWER4 IBM )
    • Lo stato della cache remota e lo stato delle cache L1-L3 associate sono settate "Shared" e lo stato della directory della memoria locale è cambiato in S
  • Se il dato è memorizzato in una cache L3 "owner" locale, il dato è fornito da questa cache (che può essere "shared-clean owner" o "dirty-owner")
  • altrimenti dalla memoria locale

Scrittura della memoria locale

• Hit Shared in L3
  • Se c'è hit S in L3 una transazione di "Invalida" è inviata sul bus del proprio nodo per invalidare tutte le altre copie. Se nella directory della memoria locale ci sono alcuni nodi con lo stato S , una transazione di invalida è inviata, tramite l'indicatore di nodo della home directory, a ciascun nodo avente una copia
• Hit Esclusiva in L3
  • La scrittura è fatta localmente in L1-L3 (per l'inclusività) come normalmente. Le cache sono settate (or rimangono) "Dirty"
• Miss
  • Come con una " lettura della memoria locale miss " con un comando di invalida ( RWITM ), poi come con una "write hit-esclusiva"

Lettura della memoria remota

cc-NUMA Remote Memory Read

• Miss
  • Una transazione di lettura di memoria locale (per un dato remoto) è monitorata da tutte le cache L3 e dalla cache remota del proprio nodo.
  • Se c'è una cache L3 "owner", il data è fornito da questa cache
  • altrimenti se "hit" nella cache remota del nodo, il dato è fornito da questa cache
  • altrimenti una richiesta di lettura remota è inviata sul nodo "home" del dato. La "home" gestisce questa richiesta nello stesso modo come per una richiesta interna. L'unica differenza è che il dato è inviato invece al nodo richiedente. La cache richiedente è settata "Shared"
    • In caso di dato "Dirty" in un altro nodo differente dalla "home", la "home" richiede il dato a questo nodo, come descritto nella operazione di "lettura della memoria locale miss" nel caso di stato E nella directory dalla memoria locale, poi il dato è inviato al nodo richiedente. Esempio: il nodo "A" richiede il dato alla "home" "B". "B" richiede il dato al nodo "C" che ha il dato "Dirty". Il nodo "C" invia il dato alla "home" nodo "B" (copy back), "B" lo rispedisce al nodo "A". I nodi "A" e "C" sono settati "Shared" come pure la directory dell memoria locale.
    • Ci sono altre possibili varianti: per es. il nodo "C" manda il dato al nodo "B" (home) e simultaneamente al nodo richiedente "A" (vedi DASH ^[63] e Intel QuickPath" Interconnect ^[35] ).

Scrittura della memoria remota

• Hit "Exclusive" in L3
  • Il dato è processato localmente come in normale "scrittura hit-esclusiva locale"
• Hit "Shared" in L3
  • Una transazione di invalida è mandata alla "home" del dato e resta in attesa per il consenso di scrittura. La "home" rinvia la transazione di invalidazione a tutti i nodi aventi il dato e poi invia il consenso di scrittura al nodo richiedente. Due scritture simultanee su differenti nodi sono così sincronizzate.
• Miss
  • Come in una "Lettura remota miss" con un comando di invalida ( RWITM ), poi come in una "scrittura hit-esclusiva locale"

Shared cache

Tipicamente usato nei sistemi Multi-core per la coerenza e per riduzione dei costi (in termini di spazio).

Sistemi multi-core

Il multi-core ("multipli processori integrati"), denominato anche chip multiprocessors , multicore chips , e many-core chips , è uno speciale genere di multiprocessore dove tutti i processori sono sullo stesso chip MCM ( Multi-Chip Module ) ^{[66] [67]}

L2 Shared Cache

L3 Shared Cache

I processori Multi-core sono dei sistemi MIMD : core differenti eseguono differenti threads ( Multithread /Multiple Istruzioni - esecuzione parallela sullo stesso contesto di piccole sequenze di istruzioni programmate), operando su differenti parti di memoria (Multiple Data).

Una soluzione comune di implementazione dei sistemi Multi-core è l'uso di cache multi-livello condivise e inclusive ( multi-level inclusive shared cache ) per mantenere la coerenza dei dati.

L' Inclusività forza i dati ad essere coerenti. Dati memorizzati in L1 sono memorizzati anche in L2 (e in L3 se usata). Qualsiasi cambiamento in L1 deve essere riportato anche nella cache L2 e così anche in L3. Se L2 è aggiornata o invalidata anche tutte le cache L1 devono essere invalidate o aggiornate (stessa relazione tra L2-L3).

La coerenza delle cache è mantenuta mediante l'uso di un controllore centralizzato della cache condivisa. La cache condivisa può essere la L2, o L3 se L2 è una cache privata.

Il protocollo di coerenza si basa protocollo tipo point-to-point message-passing simile a quello descritto nel sistema cc-NUMA . La differenza sta solamente nella directory, che nel sistema cc-NUMA è relativo alla memoria e non alla cache condivisa.

cc-NUMA Multi-Core

Ci sono due generi di implementazione. Messaggio distribuito (message broadcasting) a tutte le cache L1 oppure solo alle specifiche cache L1 che hanno il dato memorizzato. Nel primo caso il protocollo di coerenza è di tipo snoopy. La cache condivisa agisce come ponte in sostituzione del bus di sistema, rinviando le transazioni a tutte le cache L1 per lo snooping, solo però quando è necessario, cioè quando un dato non è esclusivo nella cache condivisa. Nel secondo caso, nella directory della cache condivisa c'è un "indicator bit" per ciascuna cache L1 per indicare quale L1 può avere il dato (Intel Nehalem ^[46] ).

cc-NUMA in sistemi multi-core

Sistemi Multi-core possono essere connessi assieme per formare un sistema NUMA. La coerenza è garantita tramite message-passing tra le L3 shared-cache dei vari nodi (vedi ad es.Intel Nehalem ^[46] , AMD Opteron ^{[28] [35] [68]} , MCM Interconnections POWER5 IBM ^{[7] [56] [69]} , ecc.)

Indirizzamento virtuale, fisico e pseudo virtuale

MMU

L' MMU (Memory Management Unit) è l'unità di gestione degli accessi di MM. Le funzioni principali sono:

• Traduzione degli indirizzi da virtuali in fisici
• Gestione dei miss del TLB
• Controllo dei permessi di accesso alla linea di cache e alla memoria:

1. - Supervisor/User

2. - protezione delle scritture

TLB

La memoria virtuale è lo spazio visto da un processo. Generalmente questo spazio è molto più grande della memoria fisica. Questo spazio è segmentato in pagine di dimensione prefissata. La page table (tabella delle pagine), generalmente caricata in memoria, tiene traccia di dove le pagine virtuali vengono caricate nella memoria fisica. Il TLB ( Translation Lookaside Buffer - memoria di traduzione a lato) o Page Table cache o page-translation caches - cache di traduzione delle pagine) è una cache della Page Table , cioè solamente un sottoinsieme del suo contenuto è memorizzato nel TLB. Il TLB, come per la cache di memoria può essere "separato" Istruzioni (ITLB) e Dati (DTLB) o "unificato" , come pure essere Direct Mapped o Set Associative o Fully Associative. Generalmente l'organizzazione segue l'organizzazione della cache associata, ma può essere organizzata in modo indipendente da questa (vedi TLB ). Come per la cache, per aumentarne l'efficienza può essere usato anche un secondo livello di TLB aggiungendo un L2 TLB (es. Intel Nehalem ^[46] ).

Virtual - Physical - Pseudo Virtual addressing

La cache può essere indirizzata in modo fisico o virtuale. Ci sono pro e contro per entrambe le implementazioni, ma generalmente l'indirizzamento fisico è quello normalmente usato.

Indirizzamento virtuale

In fig. sotto un esempio di indirizzo virtuale con 4 GB di spazio virtuale, 4 MB cache, 4 KB di dimensione di pagina e 256 B di dimensione della linea di cache.

Virtual Space Address Structure

Virtual Addressing

Lo spazio virtuale o logico è diviso in pagine. L' MSB + PA formano l'indirizzo di pagina dello spazio virtuale VPA (Virtual Page Address). Anche la cache è divisa in pagine.

La cache memorizza un sottoinsieme delle pagine dello spazio virtuale. È indirizzata dall' Index che è formato da PA + PA Offset dove il PA (Page Address) è l'indirizzo di pagina della cache e il PA Offset è l'indirizzo della linea di cache all'interno della pagina, mentre l' Offset è l'indirizzo interno, a livello di byte, della linea di cache.

Nel indirizzamento virtuale o logico una cache è direttamente indirizzata dall'indirizzo virtuale Index senza dover prima convertire l'indirizzo virtuale in fisico. Anche i TAG sono virtuali ( logical MSB ). Questo tipo di indirizzamento è denominato anche Virtual Index - Virtual TAG (VIVT).

In un ambiente multiprocessing differenti indirizzi logici di contesti (context) o processi diversi possono riferirsi ad uno stesso indirizzo fisico, e lo stesso indirizzo logico di un processo può mappare differenti indirizzi fisici causando un problema di coerenza, mentre al contrario all'interno dello stesso contesto, lo stesso indirizzo logico è sempre relativo allo stesso indirizzo fisico.

Ci sono tre possibili soluzioni:

1. Flushing (letteralmente sciacquatura = invalidazione) della cache ad ogni context switch (cambiamento di contesto),
2. Aggiungere in cache un ID (ASID - Address Space IDentifier) o un Context Number (CTX) o Process Number (identificatore dello spazio indirizzi, numero di contesto o numero di processo), per distinguere i vari processi/contesti ^[70] .
3. Aggiungere in cache il corrispondente indirizzo fisico che deve essere confrontato con l'indirizzo fisico ottenuto dal TLB (acceduto in parallelo - "look aside" - visto a lato), per verificare la corretta associazione virtuale-fisica dell'indirizzo (indirizzamento Virtual Index - Physical TAG - VIPT).

Problema di coerenza

Poiché differenti indirizzi logici di differenti contesti possono riferisci allo stesso indirizzo fisico (dati condivisi), più di una posizione di memoria potrebbe memorizzare lo stesso dato, causando un problema di coerenza in caso di scrittura. Solamente una posizione di memoria sarebbe aggiornata.

Ci sono due soluzioni principali ^[71]

1. Prevenzione dei sinonimi (synonym prevention)

   - Tramite il software prevenire od evitate i sinonimi

2. Rilevamento dinamico dei sinonimi (dynamic synonym detection)

   - Supporto hardware per aiutare il software di tutti o del principale "task" (programma) di mantenimento della coerenza in presenza di sinonimi

In ogni caso la cache deve sempre essere invalidata quando la mappatura virtuale-fisica viene cambiata, per es. nel caso di rimpiazzo della pagina - page replacement .

Indirizzamento fisico

Physical Addressing

Nell'indirizzamento fisico, per prima cosa viene indirizzato il TLB (*) usando l'indirizzo virtuale L-MSB + LPA , poi l'indirizzo fisico ( PPA ) ottenuto dal TLB più PPA Offset è usato per indirizzare la cache. Solamente la parte dell'indirizzo virtuale che differisce dall'indirizzo fisico è convertita, cioè "L.MSB" e "LPA".

Il TLB è una cache della Page Table cache ed è gestita come una normale cache con in aggiunta che il CTX associato all'indirizzo logico è confrontato con il CTX memorizzato nel TLB perché cambiando contesto cambia l'associazione LPA-PPA (vedi indirizzamento virtuale ).

Questa soluzione (indirizzamento Physical Index - Physical TAG - PIPT) è molto più semplice ed evita qualsiasi problema di ambiguità, ma è più lenta perché prima è richiesto l'accesso al TLB .

(*) - All'inizio la dimensione della cache era piccola ed uguale alla dimensione della pagina, perciò "index" (l'indice) virtuale e fisico erano coincidenti e il TLB era acceduto in parallelo (a lato - look aside, da cui il nome) solamente per verificare gli MSB, come nell' indirizzamento virtuale .

Indirizzamento pseudo-virtuale

• Soluzione usata nei sistemi Honeywell Bull Italia ^[72] - F. Zulian - US Patent N. 5.165.028
• Questa soluzione offre tutti i vantaggi di entrambe le precedenti soluzioni.

   Questo approccio si basa sul principio della località spaziale

Pseudo Virtual Addressing

Facendo riferimento alla fig. Virtual Space Address Structure , l'indirizzo virtuale/logico "Index" è diviso in due parti: Logical Page Address (LPA - indirizzo di pagina logica o numero di pagina) e LPA Offset (l'indirizzo della linea di cache all'interno della pagina). L' Offset è l'indirizzo interno (a livello di byte) della linea di cache.

Virtual-Physical-Pseudo Virtual Cache Access Time.svg

Il Virtual e il Physical Page Offset coincidono (come pure, ovviamente, l' Offset ). L'indirizzo virtuale e l'indirizzo fisico differiscono per l' L.MSB e per l' LPA. Il TLB converte l' L.MSB logico e la Logical Page Address (LPA), rispettivamente in P.MSB fisico e in Physical Page Address (PPA = indirizzo fisico di pagina). Nell'indirizzamento fisico, il PPA + LPA Offset formano l' Index fisico che è usato per indirizzare la cache.

Località spaziale significa che se un accesso è fatto in una pagina ci sono moltissime probabilità che il prossimo accesso (relativo allo stesso tipo) sia fatto nella stessa pagina .

Separatamente per le Istruzioni e per i Dati ei dati di Stack (se la cache Stack è usata), la probabilità che il successivo accesso sia fatto nella stessa pagina del precedente accesso è molto alta dovuta a una località spaziale molto ampia (4 KB o più rispetto, per esempio, a una molto più piccola dimensione di una linea di cache).

Il precedente indirizzo logico/virtuale di pagina (LPA) con il suo Context Number (CTX) e il corrispondente indirizzo fisico di pagina (PPA) sono memorizzati in un dedicato registro.

Nel successivo accesso, il nuovo indirizzo logico di pagina e confrontato (assieme al CTX) con l'indirizzo memorizzato precedentemente nel registro LPA. Se coincidono (hit), viene usato il corrispondente registro dell'indirizzo fisico di pagina PPA per indirizzare direttamente la cache, senza la necessità di accedere al TLB così come avviene nel caso di indirizzamento virtuale (da cui il nome Pseudo Virtual addressing- indirizzo Pseudo Virtuale).

In caso di miss, il PPA è fornito dal TLB, come nel caso di indirizzamento fisico senza alcuna penalità rispetto a quest'ultimo.

Questo approccio è efficiente se un set di registri "LPA-PPA" è riservato ciascun per tipo di funzione: uno per le istruzione, due per gli operandi (le istruzioni possono avere sino a due indirizzi di operandi) ed eventualmente uno per i dati di stack. In aggiunta per aumentare l'efficienza nei sistemi multithreading , possono essere usati un gruppo di dedicati registri "LPA-PPA" per ogni thread.

Nota - Questi registri possono essere visti come una cache L1 del TLB con una sola entry, separata per ogni tipo di dato (istruzioni, dato1, dato2, stack) e per ogni thread, cioè una cache L1 TLB fatta a registri e perciò velocissima.

Con questa soluzione, praticamente senza costi aggiuntivi, nella quasi totalità dei casi, e in particolare per le istruzioni e per stringhe di dati sequenziali, l'indirizzamento è fatto in modo fisico senza però la necessità di aspettare la traslazione dell'indirizzo da virtuale a fisico, esattamente come avviene nel caso dell'indirizzamento virtuale, e senza anche la necessita, rispetto a quest'ultimo, di invalidare ( flush ) la cache in caso page replacement (sostituzione della pagina), eliminando qualsiasi problema di coerenza.

Note

Bibliografia

• ( EN ) Jim Handy, The Cache Memory Book . Academic Press, Inc., 1998. ISBN 0-12-322980-4

Voci correlate

• Cache
• ccNUMA
• Memoria (informatica)

Collegamenti esterni

• ( EN ) Memoria cache , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.

Portale Informatica : accedi alle voci di Wikipedia che trattano di informatica