Memoria cache a procesorului

Același subiect în detaliu: memoria cache .

Memoria cache CPU este cache utilizat de un computer CPU pentru a reduce media de memorie timpul de acces; este un tip de memorie mic, dar foarte rapid, care păstrează copii ale datelor care sunt accesate cel mai frecvent în memoria principală mai mare.

Caracteristici

Comparație între memoria RAM și memoria cache a procesorului

Diagrama din stânga prezintă două amintiri. Fiecare locație de memorie are date (o linie cache ), care variază între 8 și 512 octeți între diferite tipuri de cache. Dimensiunea cache-ului este de obicei mai mare decât cea a accesului normal, care variază de obicei între 1 și 16 octeți. Fiecare locație de memorie are un index, care este un identificator unic folosit pentru a se referi la acea locație specifică. Indexul unei locații din memoria principală se numește adresă de memorie. Fiecare locație cache are o etichetă care conține indicele de memorie principal al datelor încărcate acolo. În cache-urile de date, aceste valori se numesc blocuri de cache sau linii de cache. Atâta timp cât majoritatea acceselor la memorie sunt pentru date cache, latența medie a accesului la memorie va fi mai aproape de latența cache decât memoria principală, astfel încât performanța va fi mai bună.

Când procesorul trebuie să citească sau să scrie într-o anumită locație din memoria principală, verifică inițial dacă conținutul acestei locații este încărcat în cache. Acest lucru se face prin compararea adresei locației de memorie cu orice etichete din cache care ar putea conține date la adresa respectivă. Dacă procesorul constată că locația memoriei se află în cache, aceasta este denumită hit cache, altfel o pierdere cache. În cazul unui acces cache, procesorul citește imediat sau scrie datele pe linia cache. Raportul dintre accesările cache și numărul total de accesări se mai numește rata de accesări și este o măsură indirectă a eficacității algoritmului cache.

În cazul unei rate de cache, urmează (pentru majoritatea cache-urilor) crearea unei noi entități, care include eticheta solicitată de procesor și o copie a datelor din memoria principală. Un astfel de eșec este relativ lent, deoarece necesită transferul datelor din memoria principală, în unele cazuri după ce ați șters datele care nu mai sunt valabile.

Acesta este motivul pentru care o memorie cache foarte mare, chiar dacă este gestionată cu un algoritm eficient, poate fi contraproductivă din punct de vedere al performanței în anumite circumstanțe. De fapt, procesul de ștergere a datelor expirate și nevalide din cache și încărcarea datelor corecte în cache durează de obicei mai mult decât atunci când CPU citește datele direct din memoria principală fără a utiliza cache-ul. Cu alte cuvinte, un cache mare poate duce, în situații de calcul specifice, de exemplu, non-iterative, la un număr mai mare de rate de cache decât accesări de cache, cu o degradare semnificativă a performanței.

Câteva detalii operaționale

Pentru a face loc noilor date în cazul unei rate de cache , cache-ul trebuie, în general, să șteargă conținutul uneia dintre linii. Euristica pe care o folosește pentru a alege ce date să ștergeți se numește politică de înlocuire. Problema fundamentală cu orice politică de înlocuire este aceea de a prezice datele cache care vor fi mai puțin probabil să fie solicitate în viitor.

Prezicerea viitorului este dificilă, în special pentru cache-urile hardware care trebuie să exploateze reguli care pot fi implementate cu ușurință în circuite, deci există o serie de politici de înlocuire și niciuna dintre ele nu poate fi considerată perfectă. Unul dintre cele mai populare, LRU (din limba engleză Least Recent Used , care este folosit mai puțin recent ), înlocuiește, de fapt, datele accesate mai puțin recent.

Când datele sunt scrise în memoria cache, acestea trebuie în continuare scrise în memoria principală după ceva timp. Decizia momentului în care ar trebui să aibă loc această scriere este controlată de politica de scriere. Într - o memorie cache-scriere prin intermediul, fiecare scriere a rezultatelor cache într - o scriere simultan în memoria principală. Alternativ, un cache de scriere nu efectuează imediat această acțiune: dimpotrivă, cache-ul ține evidența liniilor care conțin date care urmează să fie actualizate prin setarea adecvată a ceea ce se numește bitul murdar . Datele sunt de fapt scrise în memorie numai atunci când trebuie șterse din cache pentru a face loc noilor informații. Din acest motiv, o căutare eșuată într-o memorie cache de scriere generează adesea două accesuri la memorie: unul pentru a citi noile date, celălalt pentru a scrie informațiile vechi (dacă este indicat de bitul murdar). Atât redactarea, cât și redactarea servesc la menținerea coerenței între nivelurile de memorie.

Există, de asemenea, unele politici intermediare. De exemplu, memoria cache ar putea fi scrisa, dar scrierile ar putea fi temporar în coadă, astfel încât să proceseze mai multe scrieri împreună, optimizând accesul la magistrală .

Datele din memoria principală, din care există o copie în cache, ar putea fi modificate de alte cauze (eveniment puțin probabil, de exemplu, într-un sistem multiprocesor ), prin urmare, datele din cache ar putea deveni învechite. Protocoalele de comunicație între sistemele de gestionare a cache-ului care mențin consistența datelor sunt denumite protocoale de consistență.

Timpul necesar pentru citirea datelor din memorie (latența de citire) este important, deoarece deseori un procesor își poate completa coada de operații în timp ce așteaptă sosirea datelor solicitate. Când un microprocesor ajunge la această stare, se numește blocaj de procesor. Pe măsură ce microprocesoarele se grăbesc, oprirea pentru pierderea memoriei cache irosește multă putere de calcul; CPU-urile moderne, de fapt, pot executa sute de instrucțiuni în același timp necesar pentru a încărca o singură bucată de date din memorie. Prin urmare, au fost studiate diverse tehnici pentru a „menține CPU ocupat” în această fază. Unele microprocesoare, cum ar fi Pentium Pro , încearcă să efectueze operațiile care urmează celei care așteaptă datele, dacă sunt independente de acestea (din acest motiv sunt denumite out-of-order în engleză). Pentium 4 folosește simultan multithreading (denumit HyperThreading în terminologia Intel ), care permite unui alt program să folosească CPU în timp ce un prim program așteaptă sosirea datelor din memoria principală.

Asociativitate

Ce locații de memorie pot fi încărcate în ce locații cache

Politica de înlocuire decide unde în cache poate locui o copie a unei anumite locații de memorie. Dacă politica de înlocuire este liberă să aleagă în ce linie cache să încarce datele, memoria cache se numește complet asociativă (sau chiar complet asociativă). Pe de altă parte, dacă orice date din memorie pot fi plasate doar într-o anumită linie cache, se numește mapare directă (sau chiar mapare directă). Majoritatea cache-urilor, cu toate acestea, implementează un compromis numit set asociativ (sau chiar parțial asociativ). De exemplu, memoria cache de date AMD Athlon de nivel 1 este asociativă cu două căi , adică o anumită locație de memorie poate fi stocată în cache în două locații distincte în memoria de date de nivel 1.

Dacă fiecare locație din memoria principală poate fi încărcată în două locații diferite, apare întrebarea: care dintre ele? Schema utilizată cel mai frecvent este prezentată în diagrama laterală: biții cei mai puțin semnificativi ai indexului de locație a memoriei sunt folosiți ca indici pentru cache și două linii de cache sunt asociate cu fiecare dintre acești indici. O bună proprietate a acestei scheme este că etichetele datelor încărcate în cache nu trebuie să includă acea parte a indexului deja codificată de linia cache aleasă. Deoarece etichetele sunt exprimate pe mai puțini biți, acestea ocupă mai puțină memorie și timpul de procesare a acestora este mai mic.

Au fost sugerate și alte scheme, cum ar fi cache-ul înclinat , unde indicele modului 0 este direct, ca mai sus, în timp ce indicele modului 1 este calculat printr-o funcție hash. O funcție hash bună are proprietatea care adresează conflictele cu maparea directă, care tind să nu se ciocnească atunci când este mapată cu funcția hash, deci un program este mai puțin probabil să sufere de un număr imprevizibil de mare de coliziuni datorită unei funcții hash. În special metoda patologică a acces. Dezavantajul este întârzierea suplimentară necesară pentru calcularea rezultatului funcției hash. În plus, atunci când devine necesară încărcarea unei linii noi și ștergerea uneia vechi, poate fi dificil să se determine care dintre liniile existente a fost folosită cel mai recent, deoarece noua linie intră în conflict cu „seturi” de linii diferite pentru fiecare ” cale "; de fapt, urmărirea LRU este calculată în mod normal pentru fiecare set de linii.

Asociativitatea este un compromis. Dacă există zece poziții, politica de înlocuire poate completa o nouă linie, dar atunci când căutați date trebuie verificate toate cele 10 poziții. Controlul pozițiilor multiple necesită mai multă putere, suprafață și timp. Pe de altă parte, cache-urile cu mai multă asociativitate suferă de mai puține rate de cache (vezi și mai jos). Regula generală este că dublarea asociativității are aproximativ același efect asupra ratei de accesare ca dublarea dimensiunii cache-ului, de la o direcție ( mapare directă ) la 4 direcții. Creșterile asociativității dincolo de 4 direcții au un efect mult mai redus asupra ratei de accesare și sunt utilizate în general din alte motive (a se vedea aliasing virtual, mai jos).

Unul dintre avantajele cache-ului direct mapat este acela că permite executarea speculativă rapidă și ușoară. Odată ce adresa a fost calculată, se știe ce linie cache ar putea conține datele. Acest lucru poate fi citit și procesorul poate continua să lucreze cu acele date înainte de a termina de verificat dacă eticheta corespunde efectiv adresei solicitate.

Ideea că procesorul utilizează datele din cache chiar înainte de verificarea corespondenței dintre etichetă și adresă poate fi aplicată și cache-urilor asociative. Un subset al etichetei, numit indiciu în engleză, poate fi utilizat pentru a alege temporar una dintre liniile cache asociate cu adresa solicitată. Aceste date pot fi utilizate de CPU în paralel, în timp ce eticheta este complet verificată. Această tehnică funcționează cel mai bine atunci când este utilizată în contextul traducerii adreselor, așa cum se explică mai jos.

Dor de cache

Pierderea memoriei cache se referă la o încercare nereușită de a citi sau scrie o bucată de date în memoria cache, ceea ce duce la o latență mult mai mare în accesarea memoriei principale. Pentru o eroare de citire din memoria cache a instrucțiunilor, procesorul trebuie să aștepte (să blocheze ) până când instrucțiunea este încărcată din memoria principală. Un eșec al cache-ului cauzat de încărcarea datelor poate fi mai puțin dureros, deoarece alte instrucțiuni care nu sunt legate de acesta pot fi executate în continuare, atâta timp cât operația care necesită încărcarea datelor poate fi efectuată. Cu toate acestea, datele sunt adesea utilizate imediat după instrucțiunea de încărcare. Ultimul caz de memorie cache , adică un eșec de scriere, este cel mai puțin îngrijorător, deoarece scrierea este de obicei tamponată. Procesorul poate continua în liniște până când bufferul este plin. (Nu există eșec la scrierea în memoria cache a instrucțiunilor, deoarece acestea sunt numai în citire.)

Pentru a minimiza rata de pierdere a memoriei cache , s-a făcut o mare parte din analiza comportamentului cache-ului pentru a găsi cea mai bună combinație de dimensiune, asociativitate, dimensiune bloc și așa mai departe. Secvențele de referință ale memoriei create de programele de referință sunt salvate ca urme de adresă . O analiză suplimentară simulează multe posibilități diferite de implementare a cache-ului pe baza acestor urme de adrese lungi. Înțelegerea modului în care mai multe variabile modifică rata de accesare a memoriei cache poate fi destul de confuză. O contribuție semnificativă a fost adusă de Mark Hill, care a separat diferitele defecțiuni ale cache-ului în trei categorii (cunoscute sub numele de „cele trei C” ):

Pierderile obligatorii sunt acele defecțiuni cauzate de prima referire la un anumit. Dimensiunea cache-ului și asociativitatea nu fac diferență față de numărul de ratări obligatorii . Pre-preluarea poate ajuta aici, la fel și dimensiunile mari ale blocurilor cache (care este un tip de pre-preluare).

Pierderile de capacitate sunt acele eșecuri pe care le va avea un cache de o anumită dimensiune, indiferent de asociativitate sau dimensiunea blocului. Curba frecvenței ratei capacității față de dimensiunea memoriei cache oferă o anumită măsură a locației temporare a unui anumit flux de referință.

Pierderile de conflict sunt acele eșecuri care ar fi putut fi evitate dacă memoria cache nu ar fi șters datele anterior. Erorile de conflict ar putea fi împărțite în continuare în erori de cartografiere , care sunt inevitabile, având în vedere o asociativitate specială, și erorile de înlocuire , care sunt cauzate de alegerea specială a regulii de înlocuire.

Rată de ratare vs dimensiunea cache-ului pe porțiunea întreagă a SPEC CPU2000

Graficul din dreapta rezumă performanța cache văzută de parametrii de referință ai porțiunii întregi a unui CPU CPU2000, luată de Hill și Cantin [1] . Aceste repere servesc la reprezentarea tipului de sarcină de lucru pe care o stație de lucru ar putea să o experimenteze într-o anumită zi. În acest grafic putem vedea diferitele efecte ale celor trei Cs .

În extrema dreaptă, atunci când dimensiunea cache-ului capătă o valoare „Inf” (care, cu alte cuvinte, tinde spre infinit), avem greșeli obligatorii . Dacă am dori să îmbunătățim caracteristicile SpecInt2000, creșterea dimensiunii cache peste 1 MB ar fi practic inutilă.

Rata de eșec a cache-ului complet asociativ reprezintă pe deplin rata ratată a capacității . În simulări, a fost aleasă o regulă de înlocuire LRU: aceasta arată că, pentru a minimiza frecvența ratelor de capacitate, ar fi necesară o regulă de înlocuire perfectă, ca și cum ar fi, de exemplu, un vizionist care să cerceteze în viitor pentru a găsi o locație cache care nu este va fi folosit.

Observați cum, în aproximarea noastră la frecvența ratărilor de capacitate , graficul are o scădere bruscă între 32KB și 64KB. Acest lucru indică faptul că etalonul are un set de lucru de aproximativ 64 KB. Un designer de cache care se uită la aceste criterii de referință ar fi puternic tentat să seteze dimensiunea cache-ului chiar peste 64 KB, mai degrabă decât chiar sub această valoare. De asemenea, trebuie remarcat faptul că, pe această simulare, niciun fel de asociativitate nu poate rula o memorie cache de 32 KB, precum și o memorie de 64 KB pe 4 căi, sau chiar o memorie directă de 128 KB.

În cele din urmă, rețineți că între 64 KB și 1 MB există o mare diferență între cache-ul mapat direct și cel complet asociativ. Această diferență este frecvența ratărilor conflictuale . Conform datelor din 2004, cache-urile de nivel doi montate direct pe cipul procesorului tind să rămână în acest interval, deoarece cache-urile mici sunt suficient de rapide pentru a fi cache-urile de primul nivel, în timp ce cele mai mari sunt prea scumpe pentru a fi montate ieftin pe cipul în sine ( Itanium 2 are un cache al treilea nivel de 9 MB, cel mai mare cache on-chip disponibil pe piață în 2004). Din punctul de vedere al frecvenței ratărilor conflictului , se pare că cache-ul de al doilea nivel atrage un mare beneficiu din asociativitatea ridicată.

Acest beneficiu a fost bine cunoscut la sfârșitul anilor 1980 și începutul anilor 1990 , când proiectanții CPU nu puteau încapea cache-uri mari pe cipuri și nu aveau suficientă lățime de bandă pentru a implementa o asociativitate ridicată pe cache-urile din afara cipului procesorului. S-au încercat diverse soluții: MIPS R8000 a folosit SRAM - uri dedicate scumpe, care includeau comparatoare de etichete și drivere mari, pentru a implementa un cache asociativ cu 4 căi de 4 MB. MIPS R10000 a folosit cipuri SRAM obișnuite pentru etichete. Accesarea etichetelor, în ambele direcții, a necesitat două cicluri: pentru a reduce latența, R10000, pentru fiecare acces, a încercat să prezică modul cache care ar fi cel corect.

Cache lovit

Hit-ul cache se referă în schimb la succesul procesorului în găsirea adresei locației de memorie printre diferitele etichete cache care o pot conține. Dacă are succes, procesorul poate citi ( Cache Read Hit ) sau scrie ( Cache Write Hit ) datele de pe linia cache.

În cazul unui hit citit , procesorul citește cuvântul direct din cache fără a implica memoria principală. În ceea ce privește accesul la scriere , vă rugăm să consultați analiza aprofundată a politicii cache-ului de scriere

Traducere adresă

Cele mai frecvent utilizate procesoare implementează un fel de memorie virtuală . În practică, fiecare program care rulează pe aparat vede propriul spațiu de memorie, care conține cod și date pentru programul în sine, într-un mod simplificat. Fiecare program pune totul în propriul spațiu de memorie, fără a se îngrijora de ceea ce fac celelalte programe în spațiile lor de memorie respective.

Memoria virtuală necesită procesorului să traducă adresele virtuale generate de program în adrese fizice din memoria principală. Porțiunea procesorului care efectuează această traducere este cunoscută sub numele de unitate de gestionare a memoriei (MMU). MMU poate accesa rapid tabelul de traducere prin Translation Lookaside Buffer (TLB), care este un cache de mapări pentru tabelul de pagini al sistemului de operare.

Traducerea adreselor are trei caracteristici importante:

Latență: În general, MMU face ca adresa fizică să fie disponibilă la câteva cicluri după ce adresa virtuală este calculată de generatorul de adrese.

Aliasing: mai multe adrese virtuale se pot referi la aceeași adresă fizică. Majoritatea procesoarelor se asigură că toate actualizările adresei fizice individuale sunt efectuate în ordine. Pentru a permite acest lucru, procesorul trebuie să se asigure că există o singură copie a fiecărei adrese fizice în cache în același timp.

Granularitate: spațiul de adrese virtuale este împărțit în pagini. De exemplu, un spațiu de adrese virtuale de 4 GB ar putea fi împărțit în 1048576 pagini 4Kb, fiecare dintre acestea putând fi referite independent. Pentru suport pentru pagini cu dimensiuni variabile, consultați intrarea în memorie virtuală .

O notă istorică: primele sisteme cu memorie virtuală au fost foarte lente, deoarece au necesitat un acces la tabelul de pagini (rezident în memorie) înainte de fiecare acces programat la memorie. Fără cache, aceasta reduce la jumătate viteza de accesare a memoriei aparatului. Din acest motiv, primul cache hardware folosit într-un computer nu a fost un cache de date sau instrucțiuni, ci un TLB.

Existența adreselor fizice și virtuale ridică întrebarea care dintre ele să fie utilizate pentru etichetele și indexurile cache. Motivația pentru utilizarea adreselor virtuale este viteza: o memorie cache de date cu indici și etichete virtuale exclude MMU de la încărcare și utilizarea datelor din memorie. Întârzierea cauzată de încărcarea datelor din RAM ( latența de încărcare ) este crucială pentru performanța procesorului: din acest motiv, majoritatea cache-urilor de nivel 1 sunt indexate cu adrese virtuale, permițând MMU să caute TLB în paralel cu recuperarea datelor din cache-ul RAM.

Adresarea virtuală nu este întotdeauna cea mai bună alegere: introduce, de exemplu, problema aliasurilor virtuale , adică memoria cache ar putea stoca valoarea aceleiași adrese fizice în mai multe locații. Costul gestionării pseudonimelor virtuale crește odată cu dimensiunea cache-ului și, ca rezultat, majoritatea cache-urilor de nivelul 2 și peste sunt indexate cu adrese fizice.

Cu toate acestea, utilizarea adreselor virtuale pentru etichete ( etichetarea virtuală ) nu este comună. Dacă căutarea în TLB s-a încheiat înainte de căutarea în memoria cache, atunci adresa fizică ar fi disponibilă la timp pentru compararea etichetelor și, prin urmare, nu ar fi necesară etichetarea virtuală. Prin urmare, cache-urile mari tind să fie etichetate fizic și doar cache-urile mici cu latență scăzută sunt practic etichetate. În procesoarele mai noi, etichetarea virtuală a fost înlocuită cu vhints , așa cum este descris mai jos.

Indexare virtuală și aliasuri virtuale

Modul tipic în care procesorul se asigură că aliasurile virtuale funcționează corect este de a le ordona astfel încât, în orice moment, să existe un singur alias virtual în cache.

De fiecare dată când se adaugă o nouă valoare în cache, procesorul caută alte aliasuri virtuale și le elimină. Acest lucru se face numai în caz de eșec al memoriei cache. Nu este necesară nicio lucrare specială în timpul unei accesări cache, ceea ce ajută la menținerea căii rapide în cache cât mai rapid posibil.

Cel mai simplu mod de a găsi aliasuri este să le mapezi pe toate în aceeași zonă cache. Acest lucru se întâmplă, de exemplu, dacă TLB are pagini 4KB, iar memoria cache este mapată direct la 4KB sau mai puțin.

Cache-urile moderne de nivel superior sunt mult mai mari decât 4KB, dar paginile de memorie virtuală au rămas de aceeași dimensiune. Dacă, de exemplu, memoria cache este de 16 KB și este practic indexată, fiecare adresă fizică poate fi adresată din 4 locații diferite din cache, pentru tot atâtea adrese virtuale. Dacă memoria cache eșuează, toate cele patru locații ar trebui verificate pentru a vedea dacă adresele lor fizice corespunzătoare se potrivesc cu adresa fizică a datei de conectare care nu reușesc.

Aceste controale sunt aceleași controale pe care le folosește un set de cache asociativ pentru a selecta o anumită potrivire. Deci, dacă un cache indexat practic de 16 KB, asociativ cu 4 căi, este utilizat cu pagini de memorie virtuală 4KB, nu este necesară nicio lucrare suplimentară pentru a elimina pseudonimele virtuale în caz de pierdere a memoriei cache, deoarece verificările au fost deja făcute. .

Să folosim din nou un AMD Athlon ca exemplu: are un cache de date de nivel superior de 64 KB, cu pagini 4KB, set asociativ în 2 direcții. Când cache-ul de date de nivel superior eșuează, 2 dintre cele 16 (= 64 KB / 4KB) aliasuri virtuale posibile au fost deja verificate și sunt necesare șapte cicluri suplimentare ale buclei de verificare a etichetelor pentru a finaliza eliminarea aliasurilor virtuale suplimentare.

Etichete și vhints virtuale

Etichetarea virtuală este, de asemenea, posibilă. Marele avantaj al etichetei virtuale este că, pentru cache-urile asociative, acestea permit potrivirea etichetelor înainte ca traducerea virtuală-fizică să se facă. In orice caz,

Verificările de coerență și eliminare prezintă o adresă fizică per acțiune. Hardware-ul trebuie să aibă o metodă de conversie a adresei fizice într-o adresă cache, în general prin stocarea etichetelor fizice, precum și a etichetelor virtuale. Pentru comparație, un cache etichetat fizic nu trebuie să păstreze etichete virtuale, ceea ce este mai simplu.

Când o referință virtual-fizică este ștearsă din TLB, informațiile cache cu acele adrese virtuale vor trebui golite într-un fel. Dacă informațiile cache sunt permise pe paginile care nu sunt mapate de TLB, atunci aceste informații vor trebui șterse atunci când drepturile de acces pe aceste pagini se modifică în tabelul de pagini.

Este posibil ca sistemul de operare să se asigure că mai multe aliasuri virtuale sunt rezidente simultan în cache. Sistemul de operare asigură acest lucru prin tensionarea colorării paginii, care este descrisă mai jos. Unele procesoare RISC recente (SPARC, RS / 6000) au adoptat această abordare. Nu a fost folosit recent, deoarece costul hardware-ului pentru descoperirea și eliminarea pseudonimelor virtuale a scăzut, în timp ce complexitatea și prețul performanței software-ului perfect pentru colorarea paginilor au crescut.

Ar putea fi util să distingem cele două funcții de etichetare într-un cache asociativ: acestea sunt utilizate pentru a determina ce mod din setul de informații să selecteze și sunt utilizate pentru a determina dacă cache-ul eșuează sau nu. A doua funcție trebuie să fie întotdeauna corectă, dar prima funcție este permisă să ghicească și să greșească răspunsul ocazional.

Unele procesoare (cum ar fi SPARC recent) au cache-uri cu etichete virtuale și fizice. Etichetele virtuale sunt utilizate pentru selectarea modului, iar etichetele fizice sunt utilizate pentru a determina centrul sau eșecul. Acest tip de cache favorizează avantajul latenței unei cache de etichete virtuale și interfața software simplă a unei cache de etichete fizice. Cu toate acestea, suportă costul adăugat al etichetelor duplicate. Chiar și în timpul proceselor de eșec, modurile alternative ale liniei cache trebuie să fie verificate pentru aliasuri virtuale și pentru orice potriviri eliminate.

Zona suplimentară (și o anumită latență) poate fi atenuată păstrând indicii virtuale cu orice informație cache în loc de etichete virtuale. Aceste sugestii sunt un subset sau hash al unei etichete virtuale și sunt utilizate pentru a selecta modul cache prin care să preluați o dată și o etichetă fizică. Cu o memorie cache virtual etichetată, poate exista o potrivire de indicii virtuale, dar o nepotrivire fizică a etichetei, în acest caz, informațiile din memoria cache cu potrivirea de indicii trebuie eliminate astfel încât să acceseze memoria cache după ce ați completat memoria cache la această adresă. au un singur meci de indiciu. Deoarece sugestiile au mai puțini biți decât etichetele virtuale pentru a le distinge între ele, un cache cu sugestii virtuale suferă de mai multe deficiențe de conflict decât un cache de etichete virtuale.

Poate că reducerea finală a indicilor virtuale poate fi găsită în Pentium 4 (nucleele Willamette și Northwood). În aceste procesoare, indiciul virtual este de fapt de doar 2 biți, iar memoria cache este asociativă în 4 direcții. De fapt, hardware-ul menține o permutare simplă de la adrese virtuale la adrese cache, astfel încât nu este nevoie de CAM pentru a selecta cel corect din cele patru moduri de recuperare.

Colorarea paginii

Memoriile cache indexate fizic de mari dimensiuni (de obicei cache-urile secundare) întâmpină o problemă: sistemul de operare, mai degrabă decât aplicațiile, controlează care pagini se ciocnesc între ele în cache. Differenze nell'allocazione delle pagine da un programma portano al prossimo livello di differenze nei percorsi di collisione della cache, i quali possono portare a differenze molto larghe nelle prestazioni dei programmi. Queste differenze possono far diventare molto difficile ottenere un consistente e ripetibile tempo di benchmark per i programmi in esecuzione, che porta ingegneri pagati e sconsolati a richiedere che gli autori del sistema operativo risolvano il problema.

Per capire il problema, consideriamo una CPU con 1MB di cache di livello-2 direct-mapped indicizzata fisicamente e 4KB di pagine di memoria virtuale. Pagine fisiche in sequenza si mappano in posizioni in sequenza nella cache fino a che dopo 256 pagine il percorso torna su se stesso. Possiamo etichettare ogni pagina fisica con un colore da 0-255 per denotare dove nella cache può andare. Posizioni all'interno di pagine fisiche con colori differenti non possono entrare in conflitto nella cache.

Un programmatore che voglia usare al massimo l'uso della cache potrebbe arrangiare i suoi accessi del programma cosicché solo 1MB di data necessiti di essere messo in cache per volta, tutto questo evitando fallimenti di capacità. Ma dovrebbe anche assicurarsi che gli accessi non abbiano fallimenti di conflitto. Un modo per pensare a questo problema è di suddividere le pagine virtuali che utilizza il programma ed assegnare a loro colori virtuali nello stesso modo come colori fisici erano assegnati a pagine fisiche precedentemente. Il programmatore può poi arrangiare gli accessi del suo codice in modo che due pagine con lo stesso colore virtuale non siano in uso nello stesso momento. C'è una distesa letteratura su queste ottimizzazioni (per esempio. Loop nest optimization ), proveniente soprattutto dalla comunità High Performance Computing (HPC).

Il concetto è che mentre tutte le pagine in uso in un determinato momento, potrebbero avere differenti colori virtuali, alcune potrebbero avere lo stesso colore fisico, Infatti, se il sistema operativo assegna pagine fisiche a pagine virtuali in modo casuale ed uniforme, è molto probabile che alcune pagine abbiano lo stesso colore fisico, e quindi posizioni da queste pagine coincidano nella cache (questo è il Birthday paradox ).

La soluzione sta nel fare in modo che il sistema operativo tenti di assegnare pagine fisiche colorate diversamente a differenti colori virtuali, una tecnica chiamata page coloring . Sebbene la mappatura attuale da colori virtuali a fisici sia irrilevante per le prestazioni del sistema, mappature dispari sono difficili da tracciare e hanno piccoli benefici, quindi la maggior parte degli approcci alla colorazione delle pagine tenta semplicemente di tenere pagine fisiche e virtuali colorate nello stesso modo.

Se il sistema operativo può garantire che ogni pagina fisica si riferisca ad un solo colore virtuale, allora non vi sono virtual alias, ed il processore può usare cache virtually indexed senza la necessità di controlli su extra virtual alias durante la gestione del fallimento. Alternativamente il sistema operativo può svuotare una pagina dalla cache quantunque cambi da un colore virtuale ad un altro. Come menzionato prima, questo approccio fu usato da qualche recente progettazione SPARC e RC/6000.

Gerarchia delle cache in un processore moderno

I processori moderni dispongono sul chip di cache multiple con cui interagire. Due motivi, in particolare, hanno portato allo sviluppo della attuale gerarchia delle cache.

Cache specializzate

Il primo motivo è che CPU con pipeline accedono alla memoria da molteplici punti nella pipeline: recupero delle istruzioni, traduzione indirizzi da virtuali a fisici, e recupero dei dati. Per un semplice esempio: Classic RISC Pipeline . La naturale implementazione è di utilizzare differenti cache fisiche per ognuno di questi punti, cosicché nessuna risorsa fisica debba essere programmata per servire due punti nella pipeline. Sebbene la pipeline finisca naturalmente con almeno tre cache separate (istruzioni, TLB, e data), ognuna è specializzata in un ruolo particolare.

Victim cache

Una victim cache è una cache utilizzata per mantenere blocchi rimossi dalla cache della CPU a causa di un conflict miss o capacity miss. La victim cache è situata tra la cache primaria e la memoria sottostante, e mantiene solamente i blocchi rimossi dopo un miss. Questa tecnica è utilizzata per ridurre la penalità in cui si incorre per un fallimento della cache, perché può accadere che i dati che sono nella victim cache vengano richiesti qualche tempo dopo, e allora invece di dichiarare un miss, e andare in memoria a recuperare questi dati, si controlla la victim cache e si utilizzano i dati che sono ancora dentro di essa.

La victim cache originale su un HP PA7200 fu una cache piccola, fully-associative. Processori posteriori, come gli AMD Athlon , Athlon XP e Athlon 64 utilizzano la cache secondaria molto grande come una victim cache, per evitare ripetizioni di immagazzinamenti del contesto sulla cache primaria.

Trace cache

Uno dei più estremi esempi di specializzazione della cache è quello della trace cache utilizzata nei microprocessori Pentium 4 . Una trace cache è un meccanismo per aumentare il fetch bandwidth di istruzioni immagazzinando tracce di istruzioni che sono già state immagazzinate. Il meccanismo fu per la prima volta proposta da Eric Rotenberg , Steve Bennett e Jim Smith nel loro articolo del 1996: " Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching. "

Una trace cache immagazzina le istruzioni anche dopo che esse siano state eseguite, o come vengono ritirate. Generalmente, le istruzioni vengono aggiunte alle trace cache in gruppi che rappresentano sia blocchi individuali di base che tracce di istruzioni dinamiche. Un blocco base consiste in un gruppo di istruzioni non-branch (Non suddivise) che finiscono con una ramificazione. Una traccia dinamica ("trace path" o "traccia del percorso") consistono nelle solo istruzioni di cui il risultato viene effettivamente utilizzato, ed elimina le istruzioni seguenti che prendono ramificazioni (Siccome non sono eseguite); una traccia dinamica può essere il concatenamento di multipli di blocchi base. Questo permette all'unità di recupero delle istruzioni di recuperare parecchi blocchi basici, senza la preoccupazioni riguardante la ramificazione nel flusso delle esecuzione.

Le linee di traccia vengono immagazzinate nella trace cache in base al program counter della prima istruzione nella traccia e un set di predizioni di ramificazioni. Questo permette l'immagazzinamento di differenti tracce di percorsi che iniziano con lo stesso indirizzo, ognuna delle quali rappresenta differenti risultati di ramificazione. Nello stage dell'immagazzinamento delle istruzioni di un' Instruction pipeline , il program counter corrente insieme ad un set di predizioni di ramificazione viene controllato nella trace cache per un hit. Se un hit avviene, una linea di trace viene fornita per recuperare quale non deve andare in una cache regolare o in memoria per queste istruzioni. la trace cache continua ad alimentare la fetch unit fino a che la linea di traccia finisce o fino a che vi sia una misprediction nella pipeline. Se c'è un fallimento, una nuova traccia inizia ad essere creata. Il vantaggio rispetto alle normali cache per il codice è che non vengono mantenute in cache tutte le istruzioni successive ad un branch che sia incondizionato o predetto come non seguito: il risultato è che non si formano "bolle" di codice non utilizzato che sprecano spazio di memoria della cache.

Le Trace cache vengono anche impiegate in processori quali l' Intel Pentium 4 per immagazzinare micro operazioni già decodificate, o traduzioni di complesse istruzioni x86, cosicché alla successiva richiesta della stessa istruzione, non debba essere decodificata.

L'idea che sta alla base della trace cache è che nei processori CISC che internamente utilizzano istruzioni RISC , come il Pentium 4, la decodifica delle istruzioni è un'operazione estremamente onerosa, e il suo risultato dovrebbe essere sfruttato al meglio. Utilizzare una trace cache in luogo di una normale cache ha proprio questo vantaggio: non dover decodificare un'istruzione già incontrata durante l'esecuzione di un programma.

Ultimamente la trace cache non gode di molti favori a causa di alcuni difetti. Il primo è che molte istruzioni RISC sono tradotte in una singola istruzione CISC in un solo ciclo di clock, e le istruzioni che necessitano di più cicli di clock per essere tradotte in più istruzioni di tipo RISC sono relativamente poche e poco frequenti, per cui il vantaggio effettivo della trace cache è limitato. A questo si aggiunge il fatto che, nel caso dell'architettura di Intel, le istruzioni di tipo CISC hanno lunghezza variabile in genere tra 1 e 6 byte (tra gli 8 ei 48 bit), mentre tutte le istruzioni RISC utilizzate internamente hanno lunghezza fissa di 118 bit. Quindi a parità di dimensioni una trace cache contiene molte meno istruzioni di una cache normale. Questi svantaggi hanno portato l'Intel a non utilizzare la trace cache nelle sue ultime architetture: l' Intel Core e l' Intel Core 2 .

Vedi il testo Smith, Rotenberg and Bennett s paper in Citeseer .

Cache multilivello

Il secondo motivo è il fondamentale compromesso tra la cache latency ed l'hit rate. Le cache più grandi sono più lente e hanno migliori hit rate. Per migliorare questo tradeoff , molti sistemi utilizzano livelli multipli di cache, con cache piccole e veloci che si appoggiano a cache più grandi e più lente. Siccome la differenza di latenza tra la memoria principale e le cache più veloci è diventata più grande, alcuni processori hanno cominciato ad utilizzare anche tre livelli di cache nel chip. Per esempio nel 2003, Itanium II iniziò ad essere fornito con una cache sul chip unificata di livello 3 di 6MB. L'IBM Power 4 series ha una cache di livello 3 a 256MB fuori dal chip, condivisa attraverso parecchi processori.

Le cache multilivello generalmente operano controllando dapprima le cache a livello 1; se avviene un hit, il processore procede ad alta velocità. Se la cache più piccola “fallisce”, allora viene controllata quella più grande e così via, fino a dover accedere alla memoria principale.

Le cache multi livello introducono un nuovo modello decisionale. Per esempio, in alcuni processori (come gli Intel Pentium 2 , 3 , e 4 , così come in molti RISC ), i dati nella cache L1 possono essere anche in quella L2. Queste cache vengono denominato inclusive. Altri processori (come l' AMD Athlon ) hanno cache exclusive in cui è garantito che i dati siano al massimo in una delle cache L1 o L2.

Il vantaggio delle cache exclusive è che memorizzano più dati. Questo vantaggio aumenta con cache più grandi (le implementazioni Intel x86 invece no). Un vantaggio delle cache inclusive è che quando device esterni o altri processori in un sistema multiprocessore desiderano rimuovere una linea di cache dal processore, devono far controllare al processore solo la cache L2. Nelle gerarchie di cache che non usano l'inclusione, le cache L1 devono essere controllate anch'esse. C'è una correlazione tra la associatività delle cache L1 e L2: se le cache L2 non hanno almeno tanti modi come tutte le L1 insieme, l'effettiva associatività delle cache L1 risulta confinata.

Un altro vantaggio delle cache inclusive è che le cache più grandi possono usare linee di cache più grandi, che riducono la dimensione delle etichette delle cache secondarie. Se la cache secondaria è di un ordine di grandezza maggiore di quella primaria, ei dati della cache sono di un ordine di grandezza più grande delle etichette della cache, queste etichette di dati salvati può essere confrontato con l'area incrementale necessaria ad immagazzinare i dati nella cache L1 ed L2.

Come menzionato prima, grandi computer hanno a volte un'altra cache tra quella L2 e la memoria principale chiamata cache L3. Questa cache è implementata generalmente su un chip separato dalla CPU, e come nel 2004 , ha un capacità dai 2MB ai 256MB. Queste cache costeranno ben oltre i $1000 da costruire, ed i loro benefici dipenderanno dai percorsi di accesso delle applicazioni. Workstation x86 di fascia alta e server sono ora disponibili con un'opzione per la cache L3.

Infine, dall'altro lato della gerarchia della memoria, Il Register file della CPU può essere considerato la più piccola, veloce cache nel sistema, con la speciale caratteristica che viene richiamata dal software—tipicamente da un compilatore, siccome alloca registri che devono mantenere valori recuperati dalla memoria principale.

Esempio: architettura AMD K8

Per illustrare sia la specializzazione che il multilivello delle cache, qui è la gerarchia della cache di un AMD Athlon 64 , la cui implementazione del core è conosciuta come architettura K8 ( dettagli ^{[ collegamento interrotto ]} ).

Esempio di gerarchia, la K8

La K8 ha 4 cache specializzate: una cache di istruzioni, una di istruzioni TLB , una cache di dati ed una di dati TLB. Ognuna di queste cache è specializzata:

La cache di istruzione mantiene copie di line di memoria da 64 bytes, e recupera 16 bytes per ogni ciclo. Ogni byte in questa cache è immagazzinato in 10 bit piuttosto che 8, con gli extra bit che segnano i limiti delle istruzioni (Questo è un esempio del precoding). La cache ha solamente una protezione di parità piuttosto che una ECC , perché la parità è più piccola, ed ogni dato danneggiato può essere sostituito da un dato fresco dalla memoria (che ha sempre una copia aggiornata delle istruzioni).

La TLB di istruzioni tiene copia delle informazioni nella page table (PTE). Ogni ciclo di recupero di istruzione ha il suo indirizzo virtuale tradotto attraverso questo TLB in uno fisico. Ogni informazione è sia da 4 che da 8 byte in memoria. Ogni TLB è suddivisa in due sezioni, una per mantenere il PTE che mappa 4KB, e una per tenere i PTE per mappare 4MB o 2MB. La suddivisione permette un circuito semplice per un confronto fully associative in ogni sezione. Il sistema operativo mappa sezioni differenti dello spazio di indirizzi virtuali con differenti dimensioni di PTE.

La TLB dei dati ha due differenti copie che mantengono le stesse informazioni. Le due copie permettono due accessi ai dati per ogni ciclo per tradurre indirizzi virtuali in fisici. Come la TLB di istruzioni, questa TLB è suddivisa in due tipi di informazioni.

La cache dei dati mantiene copie di memoria di linee da 64 bytes. È suddivisa in 8 banchi (ognuno immagazzina 8KB di dati), e può recuperare due data da 8-byte per ogni ciclo per tanto che questi dati siano in banchi diversi. Vi sono due copie delle etichette, perché ogni line da 64 byte è sparsa in tutti gli 8 banchi. Ogni copia di etichetta gestisce uno dei due accessi per ciclo.

La K8 ha anche cache a multilivello. Vi sono TLB di istruzioni e dati di secondo livello, che immagazzinano solo mappature di PTE da 4KB. Sia le cache di istruzioni che di dati e le varie TLB, possono essere riempite dalla grande cache unified di livello 2. Questa cache è esclusiva per entrambe le cache L1 di dati e istruzioni, il che significa che qualsiasi line a 8-byte può risiedere in una delle cache di istruzioni L1, cache di dati L1 o cache L2. È comunque possibile per una linea nella cache dei dati di avere un PTE che sta anche in una delle cache TLB—il sistema operativo è responsabile di tenere le TLB coerenti scaricandone porzioni quando la page table nella memoria vengono aggiornate.

La K8 memorizza informazioni che non vengono mai immagazzinate in memoria—prediction information. Queste cache non vengono visualizzate nel diagramma precedente. Siccome è solito per questa classe di CPU, la K8 ha un branch prediction abbastanza complesso, con tabelle che aiutano a predire quali percorsi vengono presi ed altre tabelle che predicono gli obbiettivi dei percorsi e salti. Alcune di queste informazioni vengono associate con delle istruzioni, sia nella cache di istruzioni L1 sia in quella unified L2.

La K8 utilizza un interessante meccanismo per immagazzinare le informazioni di predizione con le istruzioni nella cache secondaria. Le linee nella cache secondaria sono protette dalla corruzione dei dati involontaria (ad esempio un colpo di particelle alfa tramite l' ECC o tramite la parità , in dipendenza che queste linee siano state rimosse dalla cache dei dati o da quella delle istruzioni. Siccome il controllo di parità occupa meno bit di quello ECC, le linee dalla cache di istruzioni hanno pochi bit in avanzo. Questi bits vengono usati dal calcolo delle predizioni dei percorsi associati con quelli delle istruzioni. Il risultato finale è che il predittore di percorsi ha un grande tabella storica, quindi ha una migliore accuratezza.

Altre gerarchie

Altri processori hanno altri tipi di predittori. (ad esempio lo store-to-load bypass predictor nel DEC Alpha 21264), ed altri svariati predittori specializzati sono facilmente pensabili da essere integrati nei futuri processori.

Questi predittori sono cache nel senso che immagazzinano informazioni che sono costose da calcolare. Alcune delle terminologie utilizzate nel discutere i predittori sono le stesse di quelle per le cache (si parla di hit nel predittore di percorsi), ma i predittori non sono generalmente pesati come parte della gerarchia delle cache.

La K8 mantiene le istruzioni ei dati delle cache coerenti nell'hardware, il che significa che un immagazzinamento in un'istruzione appena dopo l'immagazzinamento dell'istruzione cambierà l'istruzione seguente. Altri processori, come quelli nella famiglia Alpha e MPS, sono basati sul software per mantenere le cache di istruzioni coerenti. Gli immagazzinamenti non sono garantiti di essere visti nel fiume di istruzioni a meno che un programma chiami un'opzione del sistema operativo per assicurarsi della coerenza. L'idea è quella di risparmiare la complessità dell'hardware sull'assunzione che il codice automodificante è raro.

La gerarchia di cache si allarga se consideriamo il software come l'hardware. Il register file nel core di un processore può essere considerata una cache molto piccola, veloce i quali hit, fallimenti, e riempimenti sono previsti dal compilatore prima del tempo. (vedi specialmente Loop nest optimization .) I register file a volte hanno anch'essi una gerarchia: La Cray-1 (circa del 1976) aveva 8 registri scalari e 8 registri di indirizzi che erano generalmente utilizzabili, aveva anche 64 registri scalari e 64 registri di indirizzi di tipo "B". I registri di tipo "B" potevano essere caricati più velocemente di quelli nella memoria principale, in quanto il Cray-1 non aveva una cache di dati.

Implementazione

Dato che le letture dalla cache sono operazioni piuttosto comuni che impiegano più di un solo ciclo, la ricorrenza da un caricamento di un'istruzione alla istruzione stessa tende ad essere il percorso più critico nella buona progettazione dei processori, cosicché i dati in questo percorso perdano il minor tempo possibile. Come risultato la cache L1 è il componente più sensibile alle latenze sul chip.

La cache più semplice è una cache virtually indexed direct-mapped. L'indirizzo virtuale è calcolato con un sommatore, la parte più significativa dell'indirizzo viene estratta ed utilizzata per indicizzare una SRAM, la quale ritorna i dati immagazzinati. Il data viene allineato a livello di byte in un byte shifter, e da lì è passato alla successiva operazione. Non c'è alcuna necessità di alcun controllo di etichetta nel loop interno—infatti, le etichette non necessitano nemmeno di essere lette. Più tardi nella pipeline, ma prima che l'istruzione sia effettivamente caricata, l'etichetta per dei dati caricati deve essere letta, e controllata con l'indirizzo virtuale per rassicurarsi che ci fosse stato un cache hit. In caso di fallimento, la cache viene aggiornata con la linea richiesta e la pipeline viene fatta ripartire.

Una cache associativa è molto più complicata, siccome alcuni elementi di dati devono essere letti per determinare quale punto della cache selezionare, una cache level-1 set-associative N-way solitamente legge tutte le possibili N etichette ed N dati in parallelo, dopo di che sceglie i dati associati con l'etichetta corrispondente. Le cache Level-2 a volte risparmiano potenza leggendo prima l'etichetta, cosicché solo un elemento di dato venga letto dalla SRAM.

Read path for a 2-way associative cache

Il diagramma a destra serve a chiarire il modo in cui i vari campi degli indirizzi vengono utilizzati. Il diagramma mostra le SRAM, indicizzazioni e multiplexing per una cache virtually tagged e virtually indexed 4KB, 2-way set-associative con 64 B linee, una lettura di larghezza a 32b e 32b di virtual address.

Siccome la cache è da 4KB e ha linee da 64B, ci sono giusto 64 linee nella cache, e ne leggiamo due per volta da un'etichetta SRAM la quale ha 32 righe, ognuna con un paio di etichette da 21 bit. Sebbene qualsiasi funzione di indirizzi virtuali bit 31 attraverso 6 può essere usata per indicizzare etichette e dati SRAM, è più semplice usare i bit meno significativi.

Similmente, siccome la cache è da 4KB e ha un percorso di lettura da 4B, e legge due modi per ogni indirizzo, i dati SRAM sono da 512 righe larghi 8 byte.

Una cache più moderna potrebbe essere da 16KB, 4-way set-associative, virtually indexed, virtually hinted, e physically tagged, con linee da 32B, letture da 32b e indirizzi fisici da 36 bit. La ricorrenza di lettura di percorsi per questi tipi di cache assomigliano molto al percorso di sopra. Invece di etichette, vengono letti vhints, e confrontati con un sottoinsieme di indirizzi virtuali. Più tardi nella pipeline, l'indirizzo virtuale viene tradotto in un indirizzo fisico dalla TLB, e la etichetta fisica viene letta (giusto una, siccome il vhint fornisce quale modo della cache da leggere). Finalmente l'indirizzo fisico è confrontato con l'indirizzo dell'etichetta per determinare se sia avvenuto un hit.

Alcune implementazioni SPARC hanno migliorato la velocità delle loro cache L1 di pochi ritardi collassando il sommatore dell'indirizzo virtuale nei decoder SRAM.

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su CPU cache

Collegamenti esterni

( EN ) Evaluating Associativity in CPU Caches — Hill and Smith — 1989 — Introduces capacity, conflict, and compulsory classification.
( EN ) Cache Performance for SPEC CPU2000 Benchmarks — Hill and Cantin — 2003 — This reference paper has been updated several times. It has thorough and lucidly presented simulation results for a reasonably wide set of benchmarks and cache organizations.
( EN ) Memory Hierarchy in Cache-Based Systems Archiviato il 15 settembre 2009 in Internet Archive ., by Ruud van der Pas, 2002, Sun Microsystems, is a nice introductory article to CPU memory caching.
( EN ) A Cache Primer Archiviato il 25 july 2008 Data nell'URL non combaciante: 25 luglio 2008 in Internet Archive . by Paul Genua, PE, 2004, Freescale Semiconductor, another introductory article.

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