Cache-ul procesorului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 septembrie 2020; verificările necesită 15 modificări .

Un cache al microprocesorului  este o memorie cache (memorie super-secundară) utilizată de un microprocesor de computer pentru a reduce timpul mediu de acces la memoria computerului . Este unul dintre nivelurile superioare ale ierarhiei memoriei [1] . Cache-ul folosește o memorie mică, foarte rapidă (de obicei de tip SRAM ) care stochează copii ale datelor accesate frecvent din memoria principală. Dacă majoritatea solicitărilor de memorie sunt procesate de cache, latența medie de acces la memorie se va apropia de latența cache.

Când un procesor trebuie să acceseze memorie pentru a citi sau scrie date, mai întâi verifică dacă este disponibilă o copie în cache. Dacă verificarea reușește, procesorul efectuează operația folosind memoria cache, care este mult mai rapidă decât folosind memoria principală mai lentă. Pentru mai multe despre latența memoriei, consultați Latența SDRAM : tCAS, tRCD, tRP, tRAS.

Datele dintre cache și memorie sunt transferate în blocuri de dimensiuni fixe, numite și linii cache sau blocuri cache . 

Majoritatea microprocesoarelor moderne pentru computere și servere au cel puțin trei cache independente: un cache de instrucțiuni pentru a accelera încărcarea codului mașină , un cache de date pentru a accelera citirea și scrierea datelor și un buffer asociativ de traducere (TLB) pentru a accelera traducerea. de adrese virtuale (logice) în cele fizice, cum ar fi pentru instrucțiuni, precum și pentru date. Cache-ul de date este adesea implementat ca cache stratificat (L1, L2, L3, L4).

Creșterea dimensiunii cache-ului poate avea un efect pozitiv asupra performanței aproape tuturor aplicațiilor [2] , deși în unele cazuri efectul este neglijabil [3] . Lucrarea memoriei cache este de obicei transparentă pentru programator, cu toate acestea, pentru utilizarea eficientă a acesteia, în unele cazuri, se folosesc tehnici algoritmice speciale care schimbă ordinea de ocolire a datelor din RAM sau măresc localitatea acestora (de exemplu, cu multiplicarea matricei bloc ) [4] .

Cum funcționează

Această secțiune descrie un cache de date tipic și unele tipuri de cache de instrucțiuni; bufferul de asociere de traducere (TLB) poate fi mai complex, dar memoria cache a instrucțiunilor poate fi mai simplă. Diagrama din dreapta arată memoria principală și memoria cache. Fiecare rând este un grup de celule de memorie care conţin date organizate în linii cache . Dimensiunea fiecărei linii de cache poate varia de la procesor la procesor, dar pentru majoritatea procesoarelor x86 este de 64 de octeți. Dimensiunea liniei de cache este de obicei mai mare decât dimensiunea datelor care pot fi accesate de la o singură instrucțiune de mașină (dimensiunile tipice sunt de la 1 la 16 octeți). Fiecare grup de date din memorie cu o dimensiune de 1 linie cache are un număr de serie. Pentru memoria principală, acest număr este adresa de memorie cu cei mai puțin semnificativi biți eliminați. În memoria cache a fiecărei linii de cache, eticheta este atribuită suplimentar , care este adresa datelor duplicate în această linie de cache din memoria principală.

Când procesorul accesează memorie, mai întâi verifică dacă memoria cache stochează datele solicitate din memorie. Pentru a face acest lucru, adresa de solicitare este comparată cu valorile tuturor etichetelor cache în care aceste date pot fi stocate. Cazul unei potriviri cu eticheta oricărei linii de cache se numește cache hit ( English  cache hit ), cazul opus se numește cache miss ( English  cache miss ). O lovitură de cache permite procesorului să citească sau să scrie imediat date în linia cache cu eticheta potrivită. Raportul dintre numărul de accesări cache și numărul total de solicitări de memorie se numește rata de accesare  , este o măsură a eficienței cache-ului pentru algoritmul sau programul selectat.

În caz de pierdere, în cache este alocată o nouă intrare, în eticheta căreia este scrisă adresa solicitării curente, iar în linia cache-ului propriu-zis - date din memorie după citirea acesteia sau date care urmează să fie scrise în memorie. Missurile de citire întârzie execuția deoarece necesită ca datele să fie solicitate în memoria principală mai lentă. Erorile de scriere pot să nu provoace latență, deoarece datele care sunt scrise pot fi stocate imediat în cache, iar scrierea lor în memoria principală se poate face în fundal. Cache-urile de instrucțiuni funcționează aproape în același mod ca algoritmul de cache de date de mai sus, dar se fac numai cereri de citire pentru instrucțiuni. Cache-urile de instrucțiuni și de date pot fi separate pentru a crește performanța (un principiu folosit în arhitectura Harvard ) sau combinate pentru a simplifica implementarea hardware.

Pentru a adăuga date în cache după o pierdere a memoriei cache, poate fi necesar să eliminați datele scrise anterior .  Pentru a selecta o linie de cache de înlocuit, se utilizează o euristică numită politică de înlocuire . Problema principală a algoritmului este de a prezice ce rând nu este cel mai probabil necesar pentru operațiunile ulterioare. Predicțiile calitative sunt complexe, iar cache-urile hardware folosesc reguli simple, cum ar fi LRU . Marcarea anumitor zone de memorie ca necacheabile îmbunătățește performanța , împiedicând stocarea în cache a datelor utilizate rar . Pierderile pentru o astfel de memorie nu creează copii ale datelor din cache.   

Când scrieți date în memoria cache, trebuie să existe un anumit moment de timp când acestea vor fi scrise în memoria principală. Acest timp este controlat de politica de scriere .  Pentru cache - urile de scriere , orice scriere în cache are ca rezultat o scriere imediată în memorie. Un alt tip de cache, write-back eng. write-back (uneori numit și copy-back ), amână scrierea pentru o dată ulterioară. În astfel de cache-uri, este monitorizată starea liniilor de cache care nu au fost încă golite în memorie (marcate cu bitul „dirty” ) . dirty ). Scrierea în memorie este efectuată atunci când o astfel de linie este evacuată din cache. Astfel, o pierdere a memoriei cache folosind o politică de rescriere poate necesita două accesări la memorie, una pentru a reseta starea rândului vechi și alta pentru a citi noile date.     

Există și politici mixte. Memoria  cache poate fi scrisă , dar pentru a reduce numărul de tranzacții pe magistrală, scrierile pot fi puse temporar în coadă și îmbinate unele cu altele.

Datele din memoria principală pot fi modificate nu numai de procesor, ci și de periferice folosind acces direct la memorie sau de alte procesoare dintr-un sistem multiprocesor. Modificarea datelor face ca copia din cache să devină învechită ( starea învechită ). Într-o altă implementare, atunci când un procesor modifică datele din memoria cache, copiile acestor date din memoria cache ale altor procesoare vor fi marcate ca învechite. Pentru a menține actualizat conținutul mai multor cache, se folosește un protocol special de coerență .

Structura intrării în cache

Structura tipică de intrare în cache

Bloc de date etichetă un pic de relevanță

Blocul de date (linia cache) conține o copie directă a datelor din memoria principală. Bitul proaspăt înseamnă că această intrare conține o copie actualizată (cea mai recentă).

Structura adresei

etichetă index părtinire

Adresa de memorie este împărțită (de la biți înalți la biți mici) în Tag, index și offset . Lungimea câmpului index este de biți și corespunde rândului (liniei) cache-ului folosit pentru scriere. Lungimea offset este .

Asociativitate

Asociativitatea este un compromis. Verificarea mai multor înregistrări necesită mai multă energie, suprafață de cip și, eventual, timp. Dacă ar exista 10 locuri în care algoritmul de evacuare ar putea mapa o locație de memorie, atunci verificarea acelei locații de cache ar necesita analiza a 10 intrări în cache. Pe de altă parte, cache-urile cu asociativitate ridicată sunt supuse la mai puține erori (vezi „eșecuri conflictuale” de mai jos) și procesorul petrece mai puțin timp citind din memoria principală lentă. Există o observație empirică că dublarea asociativității (de la maparea directă la 2 canale sau de la 2 la 4 canale) are aproximativ același impact asupra ratei de accesare ca și dublarea dimensiunii cache-ului. Creșterea asociativității pe 4 canale are un efect redus asupra reducerii ratei de ratare și se face de obicei din alte motive, cum ar fi intersecțiile de adrese virtuale.

În ordinea înrăutățirii (creșterea duratei verificării loviturilor) și îmbunătățirea (scăderea numărului de rateuri):

  1. direct mapped cache - cel  mai bun timp de accesare și, în consecință, cea mai bună opțiune pentru cache-urile mari;
  2. Cache multi- asociativ cu 2 canale  memoria cache asociată setului cu două căi ;
  3. Cache asociativă bidirecțională ( André Seznec  )
  4. 4-way set asociative cache ( ing.  4-way set asociative cache );
  5. cache complet asociativ  cache complet asociativ  - cel mai bun (cel mai mic) procent de rateuri (rata de ratare) și cea mai bună opțiune pentru costuri extrem de mari atunci când lipsesc (penalizare ratată).
Cache pseudo-asociativ

Tipuri de rateuri

Lectură ratată din memoria cache a instrucțiunilor. De obicei dă o întârziere foarte mare, deoarece procesorul nu poate continua să execute programul (cel puțin firul de execuție curent) și trebuie să rămână inactiv în timp ce așteaptă ca instrucțiunea să fie încărcată din memorie.

Citirea ratată din memoria cache a datelor. De obicei oferă o latență mai mică, deoarece instrucțiunile care nu depind de datele solicitate pot continua să se execute în timp ce cererea este procesată în memoria principală. După ce primiți date din memorie, puteți continua să executați instrucțiuni dependente.

Eroare de scriere în memoria cache a datelor. De obicei oferă cea mai mică latență, deoarece scrierea poate fi pusă în coadă și instrucțiunile ulterioare sunt practic nelimitate în capacități. Procesorul își poate continua lucrul, cu excepția cazului de greșeală de scriere cu o coadă plină.

Categorii Miss ( Trei C )

  • Greșeli obligatorii - rateuri cauzate de prima mențiune a adresei solicitate. Dimensiunile cache-urilor și asociativitatea lor nu afectează numărul acestor rateuri. Preîncărcarea, atât software-ul, cât și hardware-ul, poate ajuta, la fel ca și creșterea dimensiunii liniei de cache (ca formă de preîncărcare hardware). Asemenea rateuri sunt uneori denumite „rătăciri reci”.
  • Rasări de capacitate - rateuri cauzate exclusiv de dimensiunea finită a memoriei cache, care apar indiferent de gradul de asociativitate sau de dimensiunea liniei de cache. Un grafic al unor astfel de rateuri în raport cu dimensiunea memoriei cache poate oferi o anumită măsură a localității temporale a unui set de solicitări de memorie. Este de remarcat faptul că nu există un concept de cache plin, cache gol sau cache aproape plin, deoarece cache-urile procesorului au linii de cache într-o stare ocupată aproape tot timpul și, prin urmare, aproape fiecare stabilire a unei noi linii. va necesita ștergerea unuia deja ocupat.
  • Conflict miss - rateuri cauzate de un conflict. Acestea pot fi evitate dacă memoria cache nu a evacuat intrarea mai devreme. Poate fi împărțit în continuare în erori cauzate de mapare (o anumită valoare de asociativitate) și greșeli de înlocuire care sunt cauzate de un anumit algoritm pentru selectarea înregistrărilor de înlocuit.

Traducerea adresei

Majoritatea procesoarelor de uz general implementează o anumită formă de memorie virtuală . Pe scurt, fiecare program care rulează pe o mașină își vede propriul spațiu de adrese simplificat care conține doar codul și datele acelui program. Orice program folosește propriul spațiu de adrese virtuale, indiferent de locația sa în memoria fizică.

Prezența memoriei virtuale necesită ca procesorul să traducă adresele virtuale (matematice) utilizate de program în adrese fizice corespunzătoare locației reale din RAM. Partea procesorului care face această conversie se numește unitatea de gestionare a memoriei (MMU). Pentru a accelera traducerile, la MMU a fost adăugată o memorie cache de mapări utilizate recent (corespondențe ale adreselor virtuale și fizice) numită Translation Lookaside Buffer (TLB).

Trei caracteristici ale procesului de traducere a adreselor sunt importante pentru o descriere ulterioară:

  • Întârziere: Adresa fizică va fi primită de la MMU doar ceva timp mai târziu, până la câteva cicluri, după ce adresa virtuală de la generatorul de adrese este furnizată la intrarea MMU.
  • Efect de suprapunere: mai multe adrese virtuale pot corespunde unei adrese fizice. Majoritatea procesoarelor garantează că toate scrierile la o adresă fizică vor fi făcute în ordinea specificată de program. Această proprietate necesită verificarea faptului că o singură copie a datelor de la adresa fizică se află în prezent în cache.
  • Unitate de cartografiere: Spațiul de adrese virtuale este paginat - blocuri de memorie de dimensiune fixă ​​începând de la adrese care sunt multipli de dimensiunea lor. De exemplu, 4 GB de spațiu de adrese pot fi împărțiți în 1.048.576 pagini de 4 KB, fiecare dintre acestea putând fi mapată în mod independent la pagini fizice. Procesoarele moderne acceptă adesea mai multe dimensiuni de pagină simultan, cum ar fi 4 KB și 2 MB pentru x86-64, iar unele procesoare AMD moderne acceptă și 1 GB.

De asemenea, este important de remarcat faptul că primele sisteme de memorie virtuală au fost foarte lente, deoarece necesitau ca tabelul de pagini (stocat în RAM principal) să fie verificat înainte de a avea acces la memoria programului. Fără utilizarea memoriei cache pentru mapări, astfel de sisteme reduc viteza de lucru cu memoria de aproximativ 2 ori. Prin urmare, utilizarea TLB este foarte importantă și uneori adăugarea lui la procesoare a precedat apariția cache-urilor convenționale de date și instrucțiuni.

În ceea ce privește adresarea virtuală, cache-urile de date și instrucțiuni pot fi împărțite în 4 tipuri. Adresele din cache sunt folosite în două scopuri diferite: indexare și etichetare.

  • Indexat fizic, etichetat fizic (PIPT) - indexat fizic și etichetat fizic. Astfel de cache-uri sunt simple și evită problemele de aliasing, dar sunt lente, deoarece este necesară o solicitare pentru o adresă fizică în TLB înainte de a accesa memoria cache. Această solicitare poate cauza o pierdere TLB și o accesare suplimentară în memoria principală înainte ca datele să fie verificate în cache.
  • Virtually indexed , virtually tagged (VIVT) - virtual indexat și virtual etichetat. Atât etichetarea, cât și indexarea folosesc o adresă virtuală. Din acest motiv, verificările pentru prezența datelor în cache sunt mai rapide, fără a necesita un apel către MMU. Cu toate acestea, apare o problemă de suprapunere atunci când mai multe adrese virtuale se mapează la aceeași adresă fizică. În acest caz, datele vor fi stocate în cache de două ori, ceea ce complică foarte mult menținerea coerenței. O altă problemă o reprezintă omonimele, situațiile în care aceeași adresă virtuală (de exemplu, în procese diferite) este mapată la adrese fizice diferite. Devine imposibil să distingem astfel de mapări doar după indexul virtual. Soluții posibile: spălarea memoriei cache la comutarea între sarcini (comutație de context), necesitatea neintersecției spațiilor de adrese de proces, etichetarea adreselor virtuale cu un ID de spațiu de adrese (ASID) sau utilizarea etichetelor fizice. Există, de asemenea, o problemă la schimbarea mapării adreselor virtuale cu cele fizice, ceea ce necesită resetarea liniilor de cache pentru care s-a schimbat maparea.
  • Indexat virtual , etichetat fizic (VIPT) - indexat virtual și etichetat fizic. Indexul folosește o adresă virtuală, în timp ce eticheta folosește o adresă fizică. Avantajul față de primul tip este o latență mai mică, deoarece puteți căuta linia cache în același timp cu traducerea adresei TLB, dar compararea etichetelor este întârziată până când se obține adresa fizică. Avantajul față de al doilea tip este detectarea omonimelor, deoarece eticheta conține o adresă fizică. Acest tip necesită mai mulți biți pentru etichetă, deoarece biții index utilizează un tip de adresare diferit.
  • Indexate fizic, etichetate virtual  - cache-urile indexate fizic și etichetate virtual sunt considerate inutile și marginale și sunt de interes pur academic [5] .

Viteza acestor acțiuni (încărcarea latenței din memorie) este critică pentru performanța procesorului și, prin urmare, majoritatea cache-urilor L1 moderne sunt practic indexate, ceea ce permite cel puțin MMU să interogheze TLB în același timp cu solicitarea datelor din cache.

Etichetarea virtuală și mecanismul vhints

Dar indexarea virtuală nu este cea mai bună alegere pentru alte niveluri de cache. Costul detectării intersecțiilor de adrese virtuale (aliasing) crește odată cu dimensiunea memoriei cache și, ca urmare, majoritatea implementărilor L2 și a nivelurilor de cache ulterioare utilizează indexarea adreselor fizice.

Pentru o perioadă destul de lungă, cache-urile au folosit atât adrese fizice, cât și adrese virtuale pentru etichete, deși etichetarea virtuală este foarte rară astăzi. Dacă solicitarea TLB se termină înainte de cererea de cache, adresa fizică va fi disponibilă pentru comparare cu eticheta până în momentul în care este necesară și, prin urmare, nu este necesară nicio etichetare virtuală. Cache-urile mari sunt mai des etichetate cu adrese fizice și numai cache-urile mici și rapide folosesc adrese virtuale pentru etichete. În procesoarele moderne de uz general, etichetarea virtuală a fost înlocuită de mecanismul vhints, descris mai jos.

Indexare virtuală și intersecții de adrese virtuale Problema omonimelor și sinonimelor Colorarea paginii

Ierarhia cache-urilor în microprocesoarele moderne

Cele mai multe procesoare moderne conțin mai multe cache-uri care interacționează.

Cache-uri specializate

CPU-urile superscalare accesează memoria din mai multe etape ale conductei : citirea unei instrucțiuni (aducerea instrucțiunilor), traducerea adreselor virtuale în adrese fizice, citirea datelor (preluarea datelor). Soluția evidentă este să folosiți cache-uri fizice diferite pentru fiecare dintre aceste cazuri, astfel încât să nu existe nicio dispută pentru accesul la una dintre resursele fizice din diferitele etape ale conductei. Astfel, a avea o conductă are ca rezultat cel puțin trei cache separate: un cache de instrucțiuni, un cache de traducere TLB și un cache de date, fiecare specializat pentru o activitate diferită.

Procesoarele pipeline care utilizează cache-uri separate pentru date și instrucțiuni (astfel de procesoare sunt acum omniprezente) sunt numite procesoare cu arhitectură Harvard . Inițial, acest termen a fost folosit pentru calculatoarele în care instrucțiunile și datele sunt complet separate și stocate în diferite dispozitive de memorie. Cu toate acestea, o astfel de separare completă nu s-a dovedit populară, iar majoritatea computerelor moderne au un singur dispozitiv de memorie principală, așa că pot fi considerate mașini cu arhitectură von Neumann .

Cache-uri pe mai multe niveluri

Una dintre probleme este problema fundamentală a echilibrării latenței cache-ului și ratei de accesare. Cache-urile mai mari au o rată de accesare mai mare, dar și o latență mai mare. Pentru a reduce tensiunea dintre cele două, majoritatea computerelor folosesc mai multe niveluri de cache atunci când cache-urile mici și rapide sunt urmate de cache-uri mari mai lente (în prezent, până la 3 niveluri în ierarhia cache).

În cazuri izolate, sunt implementate 4 niveluri de cache [6] [7] .

Cache-urile stratificate funcționează de obicei în secvență de la cache-urile mai mici la cele mai mari. Mai întâi se verifică cel mai mic și mai rapid cache al primului nivel (L1), în cazul unei lovituri, procesorul continuă să funcționeze la viteză mare. Dacă memoria cache mai mică lipsește, următorul cache de nivel al doilea (L2) ceva mai mare și mai lent este verificat și așa mai departe, până când există o solicitare către memoria RAM principală.

Pe măsură ce diferența de întârziere dintre RAM și cea mai rapidă memorie cache crește, unele procesoare cresc numărul de niveluri de cache (în unele, până la 3 niveluri pe un cip). De exemplu, procesorul Alpha 21164 din 1995 avea un cache L3 pe cip de 96 kB; IBM POWER4 în 2001 avea până la patru cache L3 de 32 MB [8] pe matrițe separate, partajate de mai multe nuclee; Itanium 2 în 2003 avea 6 MB cache L3 pe cip; Cod Xeon MP „Tulsa” în 2006 - 16 MB L3 cache pe cip, partajat de 2 nuclee; Phenom II în 2008 - până la 6 MB cache L3 universal; Intel Core i7 în 2008 - 8 MB de cache L3 pe cip, care este inclusiv și partajat între toate nucleele. Utilitatea unui cache L3 depinde de natura accesărilor la memorie ale programului.

În cele din urmă, pe cealaltă parte a ierarhiei memoriei se află fișierul de registru al microprocesorului însuși, care poate fi considerat cache-ul cel mai mic și mai rapid din sistem cu proprietăți speciale (de exemplu, programarea statică de către compilator la alocarea registrelor atunci când alocă). date din RAM într-un registru). Consultați optimizarea cuibului de bucle pentru detalii . Fișierele de registru pot fi, de asemenea, ierarhice: Cray-1 (în 1976) avea 8 registre cu adrese „A” și 8 registre scalare „S” de uz general . Mașina conținea, de asemenea, un set de 64 de registre de adresă „B” și 64 de registre scalare „T”, care a durat mai mult pentru a fi accesate, dar totuși semnificativ mai rapid decât RAM-ul principal. Aceste registre au fost introduse din cauza lipsei unui cache de date în mașină (deși a existat un cache de instrucțiuni în mașină)

  • Datele solicitate sunt citite din memoria cache a primului nivel ( Limba engleză  L1 ).
  • Datele solicitate sunt citite din memoria cache L2 . 
  • În absența datelor solicitate în cache, se efectuează citirea din RAM.
Exclusivitate (exclusivitate) și incluziune

Cache-urile pe mai multe niveluri necesită soluții arhitecturale noi.

De exemplu, un procesor poate solicita ca toate datele stocate în memoria cache L1 să fie stocate și în memoria cache L2. Astfel de perechi de cache sunt numite strict inclusive .  Alte procesoare (de exemplu, AMD Athlon) pot să nu aibă o astfel de cerință, atunci cache-urile se numesc exclusive (exclusive)  - datele pot fi fie în cache L1, fie L2, dar nu pot fi niciodată în ambele în același timp.

Până acum, alte procesoare (cum ar fi Pentium II, Pentium III și Pentium 4) nu necesită ca datele din primul nivel să fie plasate și în cache de al doilea nivel, totuși, ele continuă să facă acest lucru. Nu există un nume universal acceptat pentru această politică intermediară, deși termenul în principal inclusiv este adesea folosit . 

Avantajul cache-urilor exclusive este că stochează mai multe date. Acest beneficiu este mai mare atunci când memoria cache L1 exclusivă este comparabilă ca dimensiune cu memoria cache L2 și mai mic atunci când memoria cache L2 este de multe ori mai mare decât memoria cache L1. Când L1 ratează și L2 accesează la o lovitură, linia cache a loviturilor din L2 este schimbată cu linia din L1.

Cache pentru victime

Victim cache sau Victim buffer [9] ) (literalmente Victim cache) este un mic cache specializat care stochează acele linii de cache care au fost eliminate recent din memoria cache a microprocesorului principal când au fost înlocuite. Acest cache este situat între memoria cache principală și limba engleză.  cale de reumplere . De obicei, memoria cache a victimei este complet asociativă și servește la reducerea numărului de erori de conflict. Multe programe utilizate în mod obișnuit nu necesită mapare asociativă completă pentru toate încercările de acces la memorie. Statistic, doar o mică parte a acceselor la memorie va necesita un grad ridicat de asociativitate. Pentru astfel de solicitări este folosit cache-ul victimei, care oferă asociativitate ridicată pentru astfel de solicitări rare. A fost propus de Norman Jouppi (DEC) în 1990 [10] . Dimensiunea unui astfel de cache poate varia de la 4 la 16 linii de cache [11] .

Cache de urmărire

Unul dintre cele mai extreme cazuri de specializare a cache-ului este trace cache- ul folosit la procesoarele Intel Pentium 4 .  Cache-ul de urmărire este un mecanism pentru creșterea debitului de încărcare a instrucțiunilor și pentru reducerea disipării căldurii (în cazul Pentium 4) prin stocarea urmelor de instrucțiuni decodificate. Astfel, acest cache a eliminat munca decodorului la re-executarea codului executat recent.

Una dintre cele mai vechi publicații despre trace cache a fost o lucrare din 1996 a unei echipe de autori ( Eric Rotenberg , Steve Bennett și Jim Smith ) intitulată „Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching”. (Trace Cache: A Low-Latency Approach for High Throughput Loading Instructions).

Cache-ul de urmărire stochează instrucțiunile decodificate fie după ce au fost decodate, fie după ce s-au terminat de executat. În general, instrucțiunile sunt adăugate în memoria cache de urmărire în grupuri care sunt fie blocuri de bază, fie urme dinamice. O urmărire dinamică (cale de execuție) constă numai din instrucțiuni ale căror rezultate au fost semnificative (utilizate ulterior) și elimină instrucțiunile care se află în ramuri neexecutive, în plus, o urmă dinamică poate fi o unire a mai multor blocuri de bază. Această caracteristică permite încărcătorul de instrucțiuni din procesor să încarce mai multe blocuri de bază simultan, fără a fi nevoit să-și facă griji cu privire la prezența ramurilor în firul de execuție.

Liniile de urmărire sunt stocate în memoria cache de urmărire la adrese corespunzătoare contorului de instrucțiuni al primei instrucțiuni de mașină din urmă, la care a fost adăugat un set de caracteristici de predicție a ramurilor. Această adresare vă permite să stocați diferite urme de execuție care încep la aceeași adresă, dar reprezintă situații diferite ca urmare a predicției de ramificație. La etapa de preluare a instrucțiunii a conductei de instrucțiuni, atât contorul de instrucțiuni curent (contorul de program), cât și starea predictorului de ramificație sunt utilizate pentru a verifica dacă urmele sunt în cache. Dacă apare o lovitură, linia de urmărire este alimentată direct în conductă, fără a fi nevoie să interogăți memoria cache normală (L2) sau RAM principală. Cache-ul de urmărire alimentează instrucțiunile mașinii la intrarea conductei până când linia de urmărire se epuizează sau până când apare o eroare de predicție în conductă. În cazul unei erori, memoria cache de urmărire începe să construiască următoarea linie de urmărire prin încărcarea codului mașinii din memoria cache sau din memorie.

Cache-uri de urme similare au fost folosite în Pentium 4 pentru a stoca micro-opțiuni decodate și microcod care implementează instrucțiuni x86 complexe. Lucrarea lui Smith, Rotenberg și Bennett Vezi Citeseer pentru textul integral .

Implementări

Istorie

În primele zile ale tehnologiei cu microprocesor, accesul la memorie era doar puțin mai lent decât accesul la registrul procesorului. Dar începând cu anii 1980 [12] , decalajul de performanță dintre procesoare și memorie s-a extins. Microprocesoarele s-au îmbunătățit mai repede decât memoria, mai ales în ceea ce privește frecvența de funcționare, astfel memoria a devenit obstacolul în obținerea performanței depline a sistemului. Deși din punct de vedere tehnic a fost posibil să existe o memorie principală la fel de rapidă ca procesorul, a fost aleasă o cale mai economică: să folosești o cantitate în exces de memorie de viteză redusă, dar să introduci un cache mic, dar rapid, în sistem pentru a atenua decalajul de performanță. Drept urmare, am obținut cantități de memorie cu un ordin de mărime mai mari, la aproximativ același preț și cu o ușoară pierdere a performanței generale.

Citirea datelor din memoria cache pentru procesoarele moderne durează de obicei mai mult de un ciclu de ceas. Timpul de execuție al programelor este sensibil la întârzierile citirii din memoria cache a datelor de la primul nivel. O mulțime de eforturi ale dezvoltatorilor, precum și puterea și zona cristalului atunci când creează un procesor, sunt dedicate accelerării funcționării cache-urilor.

Cel mai simplu cache este un cache cu hartă directă indexată virtual. Adresa virtuală este calculată folosind un acumulator, partea corespunzătoare a adresei este alocată și utilizată pentru indexarea SRAM-ului care va returna datele descărcate. Datele pot fi aliniate pe octeți într-un schimbător de octeți și apoi trecute la următoarea operație. Cu această citire, nu este necesară verificarea etichetei, de fapt, nici măcar nu este nevoie să citiți eticheta. Mai târziu, înainte de finalizarea executării instrucțiunii de citire, eticheta va trebui citită și comparată cu adresa virtuală pentru a verifica dacă a avut loc o accesare în cache. Dacă a existat o pierdere, ar fi necesară o citire din memorie sau o cache mai lentă, cu o actualizare suplimentară a memoriei cache în cauză și o repornire a conductei.

O memorie cache asociativă este mai complexă deoarece trebuie citită o anumită variație a etichetei pentru a determina ce parte a memoriei cache să fie selectată. Cache-ul asociativ de set N-căi de prim nivel citește de obicei toate N etichete posibile simultan și N date în paralel, apoi compară etichetele cu adresa și selectează datele asociate cu eticheta potrivită. Cache-urile de nivel 2, pentru a economisi energie, citesc mai întâi etichetele și abia apoi citesc un element de date din datele SRAM.

Diagrama din dreapta ar trebui să arate cum sunt utilizate diferitele părți ale adresei. Bitul 31 al adresei este bitul cel mai semnificativ (cel mai semnificativ), bitul 0 este bitul cel mai puțin semnificativ (cel mai puțin semnificativ). Diagrama prezintă două SRAM-uri, indexare și multiplexare pentru o memorie cache de 4 kB, asociată cu set în 2 căi, indexată virtuală și etichetată virtuală, cu blocuri de 64 de octeți, lățime de citire de 32 de biți și adresă virtuală de 32 de biți.

Deoarece memoria cache este de 4KB și liniile sunt de 64 de octeți, stochează 64 de linii și putem număra de două ori din eticheta SRAM, care conține 32 de coloane, fiecare conținând o pereche de etichete de 21 de biți. Deși orice funcție de adresare virtuală a biților de la 31 la 6 poate fi utilizată pentru a indexa eticheta și datele SRAM, biții mai puțin semnificativi sunt cei mai ușor de utilizat. De asemenea, deoarece memoria cache este de 4 KB și are o cale de citire de patru octeți și două căi de citire per acces, datele SRAM au o lățime de 512 rânduri de 8 octeți.

Un cache mai modern ar fi probabil 16K, 4-way, set-asociativ, virtual indexat, virtual lovit și etichetat fizic (tag), cu linii de 32 de biți, lățime magistrală de citire de 32 de biți și adresare fizică de 36 de biți. Recurența căii de citire pentru un astfel de cache arată foarte asemănătoare cu cele discutate mai sus. Se citesc hit-urile virtuale în loc de etichete ? ( în engleză  vhits ) și din nou subsetul este potrivit cu adresa virtuală. Mai târziu, în pipeline, adresa virtuală este tradusă în adresa fizică a TLB, iar eticheta fizică este citită (doar una, deoarece hit-ul virtual furnizează calea de citire a cache-ului). În cele din urmă, adresa fizică este comparată cu eticheta fizică pentru a determina dacă a avut loc o lovitură.

Unele procesoare SPARC aveau cache-uri L1 accelerate de mai multe întârzieri de poartă prin  utilizarea decodoarelor SRAM în loc de un agregator de adrese virtuale. Consultați ro:Decodor cu adresă suma pentru detalii .

În X86

Când microprocesoarele x86 au atins frecvențe de 20 megaherți sau mai mult (începând cu Intel 80386 ), a fost adăugată o cantitate mică de memorie cache rapidă pentru a crește performanța. Acest lucru a fost necesar din cauza faptului că DRAM -ul folosit ca RAM de sistem a avut întârzieri semnificative (până la 120 ns) și a necesitat cicluri de actualizare. Cache-ul a fost construit în jurul SRAM -ului mai scump, dar mult mai rapid , care la acea vreme avea latențe de 15-20ns. Cache-urile timpurii erau externe procesorului și erau adesea localizate pe placa de bază ca 8 sau 9 cipuri în pachete DIP , aranjate în socluri pentru a permite cache-ului să crească sau să se micșoreze. Unele versiuni ale procesorului I386 au suportat de la 16 la 64 KB de cache extern [13] .

Odată cu lansarea procesorului Intel 80486, 8 kB de memorie cache au fost integrate direct pe matrița microprocesorului. Această memorie cache a fost numită L1 (nivelul unu, ing.  nivel 1 ) pentru a o deosebi de memoria cache mai lentă a plăcii de bază numită L2 (al doilea nivel, ing.  nivel 2 ). Acestea din urmă erau mult mai mari, până la 256 kB.

În viitor, cazurile de separare a memoriei cache au fost făcute numai pe baza considerațiilor politicii de marketing, de exemplu, în microprocesorul Celeron , construit pe nucleul Pentium II .

Microprocesorul Pentium folosește un cache separat, instrucțiuni și date [14] . Address Translation Buffer (TLB) traduce o adresă din RAM în adresa corespunzătoare din cache. Cache-ul de date Pentium folosește metoda write-back ,  care vă permite să modificați datele din cache fără acces suplimentar la RAM (datele sunt scrise în RAM doar atunci când sunt eliminate din cache) și protocolul MESI (Modified, Exclusive, Shared, Invalid) , care asigură coerența datelor în memoria cache a procesorului și în RAM atunci când se lucrează într-un sistem multiprocesor.

Fiecare dintre cache-urile, datele și instrucțiunile separate ale microprocesorului Pentium MMX are o dimensiune de 16 kB și conține două porturi, câte unul pentru fiecare conductă de execuție. Cache-ul de date are un buffer de traducere a adresei (TLB).

Următoarea implementare a cache-urilor în x86 a apărut în Pentium Pro , în care cache-ul de nivel al doilea (combinat pentru date și comenzi, 256-512 kB în dimensiune) este plasat în același pachet cu procesorul și cache-ul de prim nivel, Dimensiunea de 8 kB, separat pentru date și comenzi și a crescut frecvența la frecvența de bază. Mai târziu, cache-ul de al doilea nivel a început să fie localizat pe același cip cu procesorul.

Dual Independent Bus este o  nouă arhitectură cache care utilizează diferite magistrale pentru a conecta nucleul procesorului la memoria RAM principală. Cache-ul L1 este cu porturi duale, non-blocante și acceptă o operație de încărcare și o operație de scriere pe ceas. Funcționează la frecvența de ceas a procesorului. 64 de biți sunt transferați pe ciclu.

În microprocesorul Pentium II , memoria cache de primul nivel a fost mărită - 16 KB pentru date și 16 KB pentru instrucțiuni. Pentru al doilea nivel cache se folosește BSRAM, situat pe aceeași placă cu procesorul din cartuşul SEC pentru instalare în Slot 1 .

Odată cu popularitatea tot mai mare a procesoarelor multi-core, cache-urile de nivel al treilea, numite L3, au început să fie adăugate la cip. Acest nivel de cache poate fi partajat între mai multe nuclee și permite o comunicare eficientă între nuclee. Volumul său este de obicei mai mare decât dimensiunea totală a memoriei cache a tuturor nucleelor ​​conectate la acesta și poate ajunge la 16 MB.

Cache-ul plăcii de bază a rămas popular până în epoca Pentium MMX și a căzut în neutilizare odată cu introducerea SDRAM -ului și diferența tot mai mare dintre frecvența magistralei procesorului și frecvența de bază a procesorului: memoria cache de pe placa de bază a devenit doar puțin mai rapidă decât RAM-ul principal.

Exemplu de cache (nucleu procesor K8)

Este prezentată schema cache-urilor nucleului microprocesorului AMD K8, care arată atât cache-urile specializate, cât și natura lor pe mai multe niveluri.

Nucleul folosește patru cache specializate diferite: cache de instrucțiuni, TLB de instrucțiuni, TLB de date și cache de date:

  • Cache-ul de instrucțiuni este format din blocuri de 64 de octeți, care sunt o copie a memoriei principale și poate încărca până la 16 octeți pe ceas. Fiecare octet din acest cache este stocat pe 10 biți în loc de 8, iar limitele instrucțiunilor sunt marcate în biții suplimentari (adică, cache-ul efectuează o pre-decodificare parțială). Numai paritatea este folosită pentru a verifica integritatea datelor, nu ECC, deoarece bitul de paritate ocupă mai puțin spațiu, iar în cazul unei erori, datele corupte pot fi actualizate cu versiunea corectă din memorie.
  • Instrucțiunea TLB conține copii ale intrărilor din tabelul de pagini. Pentru fiecare solicitare de citire a comenzilor, este necesară traducerea adreselor matematice în adrese fizice. Înregistrările de traducere sunt de 4 și 8 octeți, iar TLB este împărțit în 2 părți, respectiv una pentru mapările de 4 kB și cealaltă pentru mapările de 2 și 4 MB (pagini mari). O astfel de partiție simplifică schemele de căutare complet asociative în fiecare dintre părți. Sistemele de operare și aplicațiile pot utiliza mapări de dimensiuni diferite pentru porțiuni din spațiul de adrese virtuale.
  • TLB de date este dual și ambele buffer-uri conțin același set de înregistrări. Dualitatea lor face posibilă efectuarea fiecărui ciclu de traducere pentru două solicitări de date simultan. La fel ca instrucțiunea TLB, acest buffer este împărțit între două tipuri de înregistrări.
  • Cache-ul de date conține copii de 64 de octeți ale bucăților de memorie. Este împărțit în 8 bănci (bănci), fiecare conținând 8 kiloocteți de date. Cache-ul permite două cereri pentru date de 8 octeți în fiecare ciclu, cu condiția ca cererile să fie procesate de bănci diferite. Structurile etichetelor din cache sunt duplicate, deoarece fiecare bloc de 64 de octeți este distribuit pe toate cele 8 bănci. Dacă se fac 2 solicitări într-un ciclu, acestea funcționează cu propria lor copie a informațiilor etichetei.

Acest nucleu folosește, de asemenea, cache-uri pe mai multe niveluri: TLB-uri de instrucțiuni și date pe două niveluri (doar înregistrările de mapări de 4 KB sunt stocate la al doilea nivel) și un cache de nivel al doilea (L2), unificat pentru a funcționa atât cu date, cât și cu instrucțiuni. cache-urile de nivel 1 și pentru diferite TLB-uri. Cache-ul L2 este exclusiv pentru datele L1 și instrucțiunile L1, adică fiecare bucată de 8 octeți stocată în cache poate fi fie în instrucțiuni L1, fie în date L1, fie în L2. Singura excepție sunt octeții care alcătuiesc înregistrările PTE, care pot fi în TLB și în memoria cache de date în același timp în timpul procesării mapării virtuale de către sistemul de operare. Într-un astfel de caz, sistemul de operare este responsabil pentru resetarea promptă a TLB după actualizarea intrărilor de traducere.

DEC Alpha

În microprocesorul DEC Alpha 21164 (lansat în noiembrie 1995 la 333 MHz), memoria cache de primul nivel poate suporta un număr (până la 21) de erori necontrolate. Există un  fișier de adresă greșită (MAF ) cu șase elemente , fiecare element conținând o adresă și un registru pentru a se încărca în caz de eroare (dacă adresele greșite aparțin aceleiași linii de cache, acestea sunt tratate ca un element în MAF).

Pe lângă memoria cache L1 de scriere separată, cipul procesorului conține un cache L2 de scriere inversă parțial asociativă și un controler cache L3 care funcționează atât în ​​mod sincron, cât și în mod asincron.

Modelul DEC Alpha 21164PC din martie 1997 are un cache L2 extern; dimensiunea cache a instrucțiunilor a crescut la 16 KB.

Microprocesorul DEC Alpha 21264 nu are un cache de al doilea nivel (al cărui controler, totuși, se află pe un cip), dar cache-ul de prim nivel este mărit la 128 kB (64 kB fiecare pentru cache de instrucțiuni și, respectiv, cache de date). ).

PA-RISC

Hewlett-Packard PA-8000 pentru calculul științific și de inginerie conține un  buffer de reordonare a adreselor ( ARB ) care ține evidența tuturor comenzilor de încărcare / stocare, ceea ce reduce latența abordării datelor externe și a cache-ului de instrucțiuni, care în acest procesor poate fi ridicat. la 4 MB. Cu toate acestea, chiar și controlul eficient al cache-ului extern folosind linii de control de mare viteză și preluare a datelor și comenzilor din memoria principală în cache nu a compensat viteza scăzută și costul ridicat.

Aceste neajunsuri au fost eliminate în PA-8500, în care, datorită tehnologiei de proces de 0,25 microni, a fost posibil să se adauge 512 kB de cache de instrucțiuni și 1 MB de cache de date la cip.

PowerPC

Construit pe arhitectura Harvard, PowerPC 620 conține două cache-uri încorporate, fiecare cu o capacitate de 32 kB, care au propriile unități de gestionare a memoriei ( MMU ) și funcționează independent unul de celălalt .  Comenzile și adresele de ramuri sunt stocate în cache-ul BTAC (cache -ul de adrese țintă- branch ) . 

Interfața magistrală a procesorului include o implementare completă a suportului cache L2 (până la 128 MB, rulând la frecvența procesorului sau de două ori/patru ori mai puțin) și nu necesită cicluri suplimentare pentru a controla funcționarea cache-ului extern. Este implementată o combinație de trecere și scriere inversă, precum și suport pentru protocolul MESI.

MIPS

Cache-ul L1 folosit în RA-10000 are propriile sale caracteristici - fiecare comandă din cache este echipată cu o etichetă suplimentară de patru biți, care este utilizată în continuarea decodării și clasificării comenzii.

Evoluții actuale

Note

  1. ↑ Korneev V. V., Kiselev A. V. 1.2.3 Metode structurale pentru reducerea timpului de acces la memorie // Microprocesoare moderne. - M . : „Cunoașterea”, 1998. - S. 75-76. — 240 s. - 5000 de exemplare.  - ISBN 5-98251-050-6 .
  2. ↑ Dependența performanței procesorului de dimensiunea cache-ului L2 . Consultat la 20 octombrie 2011. Arhivat din original pe 22 octombrie 2011.
  3. ↑ AMD Athlon II X4 sau Phenom II: Impactul cache-ului L3 asupra performanței . Data accesului: 12 ianuarie 2015. Arhivat din original pe 15 iulie 2014.
  4. ↑ Intel 64 și IA-32 Architectures Software Developer's Manual. Volumul 1: Arhitectura de bază. Număr comandă 253665-021.
  5. ↑ Înțelegerea stocării în cache . Jurnalul Linux. Preluat la 2 mai 2010. Arhivat din original la 27 aprilie 2012.
  6. ↑ https://www.theregister.co.uk/2004/05/06/hp_mx2_itaniummodule/ Arhivat 10 august 2017 la Wayback Machine „HP a împachetat mx2 cu 32 MB de cache L4”
  7. ↑ https://www.theregister.co.uk/2010/07/23/ibm_z196_mainframe_processor/ Arhivat la 10 august 2017 la Wayback Machine „Memorie cache L4, pe care majoritatea serverelor nu o au. (IBM a adăugat niște cache L4 la chipset-urile sale EXA pentru procesoarele Xeon de la Intel cu câțiva ani în urmă). Acest cache L4 este necesar dintr-un motiv cheie"
  8. ↑ Revizuirea procesorului IBM POWER4. Ixbtlabs Arhivat 13 iulie 2011 la Wayback Machine „O caracteristică importantă a cache-ului L3 este capacitatea de a combina cache-uri separate ale cipurilor POWER4 de până la 4 (128 MBytes), ceea ce permite utilizarea intercalării adreselor pentru a accelera accesul.”
  9. ↑ Un studiu detaliat al arhitecturii AMD64 Arhivat la 27 ianuarie 2012 la Wayback Machine // ixbt.com , „The Cache Subsystem. Căutarea și analiza modificărilor»
  10. ↑ NPJouppi. „Îmbunătățirea performanței cache-ului cu mapare directă prin adăugarea unui cache complet asociativ și a unor buffer-uri de preluare preliminară.” — 17th Annual International Symposium on Computer Architecture, 1990. Proceedings., DOI:10.1109/ISCA.1990.134547
  11. ↑ Victim Cache Simulator . Consultat la 12 ianuarie 2012. Arhivat din original pe 2 mai 2010.
  12. ↑ Decalajul de performanță procesor-memorie (link descendent) . acm.org. Consultat la 8 noiembrie 2007. Arhivat din original pe 27 aprilie 2012. 
  13. ↑ Guk M. 4. Memory caching // Pentium II, Pentium Pro și doar procesoare Pentium. - M . : Piter, 1999. - S. 126-143. — 288 p. - 7000 de exemplare.  - ISBN 5-8046-0043-5 .
  14. ↑ Korneev V. V., Kiselev A. V. 2.2.1.2 Cache-uri separate pentru instrucțiuni și date // Microprocesoare moderne. - M . : „Cunoașterea”, 1998. - S. 75-76. — 240 s. - 5000 de exemplare.  - ISBN 5-98251-050-6 .

Vezi și

Link -uri