Un cache este un buffer intermediar cu acces rapid care conține informații care sunt cel mai probabil să fie solicitate. Accesarea datelor din cache este mai rapidă decât recuperarea datelor originale din memoria operațională (RAM) și mai rapidă decât memoria externă (hard disk sau solid-state drive), reducând astfel timpul mediu de acces și crescând performanța generală a sistemului informatic.

O serie de modele de unități centrale de procesare (CPU) au propriul cache pentru a minimiza accesul la memoria cu acces aleatoriu (RAM), care este mai lentă decât registrele. Memoria cache poate oferi beneficii semnificative de performanță atunci când viteza de ceas a RAM este semnificativ mai mică decât viteza de ceas a procesorului. Viteza de ceas pentru memoria cache nu este de obicei cu mult mai mică decât viteza procesorului.

Niveluri de cache

Cache-ul CPU este împărțit în mai multe niveluri. Într-un procesor de uz general de astăzi, numărul de niveluri poate fi de până la 3. Cache-ul de nivel N+1 este de obicei mai mare ca dimensiune și mai lent ca viteză de acces și transfer de date decât cache-ul de nivel N.

Cea mai rapidă memorie este cache-ul de prim nivel - L1-cache. De fapt, este o parte integrantă a procesorului, deoarece este situat pe același cip și face parte din blocurile funcționale. La procesoarele moderne, memoria cache L1 este de obicei împărțită în două cache, cache-ul de instrucțiuni și cache-ul de date (arhitectura Harvard). Majoritatea procesoarelor fără cache L1 nu pot funcționa. Cache-ul L1 funcționează la frecvența procesorului și, în general, poate fi accesat la fiecare ciclu de ceas. Este adesea posibilă efectuarea simultană a mai multor operații de citire/scriere. Latența de acces este de obicei de 2-4 cicluri de ceas de bază. Volumul este de obicei mic - nu mai mult de 384 KB.

Al doilea cel mai rapid este L2-cache - un cache de al doilea nivel, situat de obicei pe cip, ca L1. La procesoarele mai vechi, un set de cipuri pe placa de bază. Volumul cache L2 de la 128 KB la 1-12 MB. În procesoarele moderne cu mai multe nuclee, cache-ul de al doilea nivel, situat pe același cip, este o memorie separată - cu o dimensiune totală a cache-ului de nM MB, fiecare nucleu are nM/nC MB, unde nC este numărul de nuclee de procesor. De obicei, latența cache-ului L2 situat pe cipul central este de la 8 la 20 de cicluri de ceas de bază.

Cache-ul de al treilea nivel este cel mai puțin rapid, dar poate fi foarte impresionant ca dimensiune - mai mult de 24 MB. Cache-ul L3 este mai lent decât cache-urile anterioare, dar totuși semnificativ mai rapid decât RAM. În sistemele multiprocesor este de uz comun și este destinat sincronizării datelor din diferite L2.

Uneori există și un cache de nivel 4, de obicei este situat într-un cip separat. Utilizarea cache-ului de nivel 4 este justificată numai pentru servere și mainframe de înaltă performanță.

Problema sincronizării între diferite cache-uri (atât unul cât și mai multe procesoare) este rezolvată prin coerența cache-ului. Există trei opțiuni pentru schimbul de informații între cache-uri de diferite niveluri sau, după cum se spune, arhitecturi cache: inclusive, exclusive și neexclusive.

Cât de important este memoria cache L3 pentru procesoarele AMD?

Într-adevăr, este logic să echipați procesoarele cu mai multe nuclee cu memorie dedicată care va fi partajată de toate nucleele disponibile. În acest rol, un cache rapid de nivel al treilea (L3) poate accelera în mod semnificativ accesul la datele care sunt solicitate cel mai des. Atunci nucleele, dacă este posibil, nu vor trebui să acceseze memoria principală lentă (RAM).

Cel puțin în teorie. Recent, AMD a anunțat procesorul Athlon II X4, care este un model Phenom II X4 fără cache L3, sugerând că nu este atât de necesar. Am decis să comparăm direct două procesoare (cu și fără cache L3) pentru a testa modul în care cache-ul afectează performanța.

Click pe poza pentru marire.

Cum funcționează memoria cache?

Înainte de a ne aprofunda în teste, este important să înțelegem câteva elemente de bază. Principiul cum funcționează memoria cache este destul de simplu. Cache-ul tamponează datele cât mai aproape de nucleele de procesare ale procesorului pentru a reduce cererile CPU la o memorie mai îndepărtată și mai lentă. Pe platformele desktop moderne, ierarhia cache-ului include până la trei niveluri care preced accesul la RAM. Mai mult, cache-urile celui de-al doilea și, în special, al treilea nivel servesc nu numai la stocarea datelor. Scopul lor este de a preveni supraîncărcarea magistralei procesorului atunci când nucleele trebuie să facă schimb de informații.

Lovituri și rateuri

Eficacitatea arhitecturilor cache este măsurată prin rata de accesare. Solicitările de date care pot fi satisfăcute de cache sunt considerate accesări. Dacă acest cache nu conține datele necesare, atunci cererea este transmisă mai departe de-a lungul conductei de memorie și se contorizează o pierdere. Desigur, greșelile duc la mai mult timp necesar pentru a obține informații. Ca rezultat, „bule” (inactiv) și întârzieri apar în conducta de calcul. Hiturile, dimpotrivă, vă permit să mențineți performanța maximă.

Intrare în cache, exclusivitate, coerență

Politicile de înlocuire dictează modul în care spațiul este eliberat în cache pentru noile intrări. Deoarece datele scrise în cache trebuie să apară în cele din urmă în memoria principală, sistemele pot face acest lucru în același timp cu scrierea în cache (scriere prin scriere) sau pot marca zonele de date ca „murdare” (rescriere) și pot scrie în memorie.când este evacuat din cache.

Datele din mai multe niveluri de cache pot fi stocate exclusiv, adică fără redundanță. Atunci nu veți găsi aceleași linii de date în două ierarhii de cache diferite. Sau cache-urile pot funcționa inclusiv, adică nivelurile inferioare de cache sunt garantate să conțină date prezente în nivelurile de cache superioare (mai aproape de nucleul procesorului). AMD Phenom utilizează un cache L3 exclusiv, în timp ce Intel urmează o strategie de cache inclusivă. Protocoalele de coerență asigură integritatea și prospețimea datelor în diferite nuclee, niveluri de cache și chiar procesoare.

Mărimea cache-ului

Un cache mai mare poate stoca mai multe date, dar tinde să crească latența. În plus, un cache mare consumă un număr considerabil de tranzistori de procesor, așa că este important să găsim un echilibru între bugetul tranzistorului, dimensiunea matriței, consumul de energie și performanță/latență.

Asociativitatea

Intrările din RAM pot fi mapate direct în cache, adică există o singură poziție cache pentru o copie a datelor din RAM, sau pot fi asociative în n moduri, adică există n locații posibile în cache în care acest lucru datele pot fi stocate. Grade mai înalte de asociativitate (până la cache-uri complet asociative) oferă o flexibilitate mai mare de stocare în cache, deoarece datele existente în cache nu trebuie rescrise. Cu alte cuvinte, un grad n ridicat de asociativitate garantează o rată de hit mai mare, dar crește și latența, deoarece este nevoie de mai mult timp pentru a verifica toate acele asocieri pentru un hit. În mod obișnuit, cel mai înalt grad de asociere este rezonabil pentru ultimul nivel de stocare în cache, deoarece capacitatea maximă este disponibilă acolo, iar căutarea datelor în afara acestui cache va duce la accesarea procesorului RAM lentă.

Iată câteva exemple: Core i5 și i7 folosesc 32 KB de cache L1 cu asociativitate cu 8 căi pentru date și 32 KB de cache L1 cu asociativitate în 4 căi pentru instrucțiuni. Este de înțeles că Intel dorește ca instrucțiunile să fie disponibile mai rapid și cache-ul de date L1 să aibă o rată de accesare maximă. Cache-ul L2 de pe procesoarele Intel are asociativitate cu 8 căi, iar memoria cache Intel L3 este și mai inteligentă, deoarece implementează asociativitate cu 16 căi pentru a maximiza accesările.

Cu toate acestea, AMD urmează o strategie diferită cu procesoarele Phenom II X4, care utilizează un cache L1 asociativ cu două căi pentru a reduce latența. Pentru a compensa eventualele erori, capacitatea cache-ului a fost dublată: 64 KB pentru date și 64 KB pentru instrucțiuni. Cache-ul L2 are asociativitate cu 8 căi, ca și designul Intel, dar memoria cache L3 de la AMD funcționează cu asociativitate cu 48 de căi. Dar decizia de a alege o arhitectură cache în detrimentul unei alte nu poate fi evaluată fără a lua în considerare întreaga arhitectură a CPU. Este destul de firesc ca rezultatele testelor să aibă o semnificație practică, iar scopul nostru a fost tocmai un test practic al întregii structuri complexe de stocare în cache pe mai multe niveluri.

Fiecare procesor modern are un cache dedicat care stochează instrucțiunile și datele procesorului, gata de utilizare aproape instantaneu. Acest nivel este denumit în mod obișnuit cache de nivel 1 sau L1 și a fost introdus pentru prima dată în procesoarele 486DX. Recent, procesoarele AMD au devenit standard cu 64 KB cache L1 per nucleu (pentru date și instrucțiuni), iar procesoarele Intel folosesc 32 KB cache L1 per nucleu (și pentru date și instrucțiuni)

Cache-ul L1 a apărut pentru prima dată pe procesoarele 486DX, după care a devenit o caracteristică integrală a tuturor procesoarelor moderne.

Cache-ul de nivel al doilea (L2) a apărut pe toate procesoarele după lansarea Pentium III, deși primele implementări ale acestuia pe ambalaj au fost în procesorul Pentium Pro (dar nu pe cip). Procesoarele moderne sunt echipate cu până la 6 MB de cache L2 pe cip. De regulă, acest volum este împărțit între două nuclee pe un procesor Intel Core 2 Duo, de exemplu. Configurațiile tipice L2 oferă 512 KB sau 1 MB de cache per nucleu. Procesoarele cu un cache L2 mai mic tind să fie la un nivel de preț mai scăzut. Mai jos este o diagramă a implementărilor timpurii ale cache-ului L2.

Pentium Pro avea memoria cache L2 în ambalajul procesorului. În generațiile ulterioare de Pentium III și Athlon, memoria cache L2 a fost implementată prin cipuri SRAM separate, ceea ce era foarte comun la acea vreme (1998, 1999).

Anunțarea ulterioară a unei tehnologii de proces de până la 180 nm a permis producătorilor să integreze în sfârșit cache-ul L2 pe matrița procesorului.

Primele procesoare dual-core au folosit pur și simplu modele existente care includeau două matrițe per pachet. AMD a introdus un procesor dual-core pe un cip monolitic, a adăugat un controler de memorie și un comutator, iar Intel a asamblat pur și simplu două cipuri single-core într-un singur pachet pentru primul său procesor dual-core.

Pentru prima dată, memoria cache L2 a început să fie partajată între două nuclee de calcul pe procesoarele Core 2 Duo. AMD a mers mai departe și a creat primul său Phenom quad-core de la zero, iar Intel a folosit din nou o pereche de matrițe, de data aceasta două matrițe dual-core Core 2, pentru primul său procesor quad-core pentru a reduce costurile.

Cel de-al treilea nivel cache există încă din primele zile ale procesorului Alpha 21165 (96 KB, procesoare introduse în 1995) sau IBM Power 4 (256 KB, 2001). Cu toate acestea, în arhitecturile bazate pe x86, memoria cache L3 a apărut pentru prima dată cu modelele Intel Itanium 2, Pentium 4 Extreme (Gallatin, ambele procesoare în 2003) și Xeon MP (2006).

Implementările timpurii pur și simplu au oferit un alt nivel în ierarhia cache-ului, deși arhitecturile moderne folosesc memoria cache L3 ca un tampon mare, partajat pentru transferul de date între nuclee în procesoarele multi-core. Acest lucru este subliniat de gradul n ridicat de asociativitate. Este mai bine să cauți date puțin mai mult în cache decât să ajungi la o situație în care mai multe nuclee folosesc acces foarte lent la memoria RAM principală. AMD a introdus pentru prima dată memoria cache L3 pe un procesor desktop cu linia Phenom deja menționată. Phenom X4 de 65 nm conținea 2 MB de cache L3 partajat, iar Phenom II X4 modern de 45 nm are deja 6 MB de cache L3 partajat. Procesoarele Intel Core i7 și i5 folosesc 8 MB de cache L3.

Procesoarele moderne quad-core au cache L1 și L2 dedicate pentru fiecare nucleu, precum și un cache L3 mare partajat de toate nucleele. Cache-ul L3 partajat permite, de asemenea, schimbul de date pe care nucleele pot lucra în paralel.

Cât de important este memoria cache L3 pentru procesoarele AMD?

Cel puțin în teorie. AMD a anunțat recent procesorul Athlon II X4, care este un model al Phenom II X4 fără cache L3, sugerând că nu este atât de necesar. Am decis să comparăm direct două procesoare (cu și fără cache L3) pentru a testa modul în care cache-ul afectează performanța.

Cum funcționează memoria cache?

Lovituri și rateuri

Intrare în cache, exclusivitate, coerență

Mărimea cache-ului

Asociativitatea

Aproape toți dezvoltatorii știu că memoria cache a procesorului este o memorie mică, dar rapidă, care stochează date din zonele de memorie vizitate recent - definiția este scurtă și destul de precisă. Cu toate acestea, cunoașterea detaliilor plictisitoare despre mecanismele de cache este necesară pentru a înțelege factorii care afectează performanța codului.

În acest articol vom analiza o serie de exemple care ilustrează diferite caracteristici ale cache-urilor și impactul acestora asupra performanței. Exemplele vor fi în C#; alegerea limbajului și a platformei nu afectează foarte mult evaluarea performanței și concluziile finale. Desigur, în limite rezonabile, dacă alegeți o limbă în care citirea unei valori dintr-o matrice este echivalentă cu accesarea unui tabel hash, nu veți obține niciun rezultat interpretabil. Notele traducătorului sunt cu caractere cursive.

Habracut - - -

Exemplul 1: Acces la memorie și performanță

Cu cât crezi că este mai rapid al doilea ciclu decât primul?

int arr = int nou;
// mai întâi
pentru (int i = 0; i< arr.Length; i++) arr[i] *= 3;
// al doilea
pentru (int i = 0; i< arr.Length; i += 16) arr[i] *= 3;

Prima buclă înmulțește toate valorile din matrice cu 3, a doua buclă înmulțește doar la fiecare șaisprezecea valoare. Al doilea ciclu se încheie doar 6% lucrează primul ciclu, dar pe mașinile moderne ambele cicluri sunt executate în timp aproximativ egal: 80 msȘi 78 ms respectiv (pe aparatul meu).

Soluția este simplă - acces la memorie. Viteza acestor bucle este determinată în primul rând de viteza subsistemului de memorie și nu de viteza de multiplicare a întregului. După cum vom vedea în exemplul următor, numărul de accesări la RAM este același atât în primul cât și în cel de-al doilea caz.

Exemplul 2: Impactul liniilor cache

Să cercetăm mai profund și să încercăm alte valori de pas, nu doar 1 și 16:

pentru (int i = 0; i< arr.Length; i += K /* шаг */ ) arr[i] *= 3;

Iată timpii de rulare ai acestei bucle pentru diferite valori de pas K:

Vă rugăm să rețineți că, cu valori de trepte de la 1 la 16, timpul de funcționare rămâne practic neschimbat. Dar cu valori mai mari de 16, timpul de rulare scade cu aproximativ jumătate de fiecare dată când dublăm pasul. Acest lucru nu înseamnă că bucla începe cumva în mod magic să ruleze mai repede, doar că și numărul de iterații scade. Punctul cheie este același timp de funcționare cu valori de pas de la 1 la 16.

Motivul pentru aceasta este că procesoarele moderne nu accesează memoria câte un octet, ci mai degrabă în blocuri mici numite linii cache. De obicei, dimensiunea șirului este de 64 de octeți. Când citiți orice valoare din memorie, cel puțin o linie de cache intră în cache. Accesul ulterior la orice valoare din acest rând este foarte rapid.

Deoarece 16 valori int ocupă 64 de octeți, buclele cu pași de la 1 la 16 accesează același număr de linii cache, sau mai precis, toate liniile cache ale matricei. La pasul 32, accesul are loc la fiecare a doua linie, la pasul 64, la fiecare a patra.

Înțelegerea acestui lucru este foarte importantă pentru unele tehnici de optimizare. Numărul de accesări la acesta depinde de locația datelor în memorie. De exemplu, datele nealiniate pot necesita două accesări la memoria principală în loc de una. După cum am aflat mai sus, viteza de operare va fi de două ori mai mică.

Exemplul 3: dimensiunile cache de nivel 1 și 2 (L1 și L2)

Procesoarele moderne au de obicei două sau trei niveluri de cache, numite de obicei L1, L2 și L3. Pentru a afla dimensiunile cache-urilor la diferite niveluri, puteți utiliza utilitarul CoreInfo sau funcția Windows API GetLogicalProcessorInfo. Ambele metode oferă, de asemenea, informații despre dimensiunea liniei de cache pentru fiecare nivel.

Pe aparatul meu, CoreInfo raportează 32 KB cache de date L1, 32 KB cache de instrucțiuni L1 și 4 MB cache de date L2. Fiecare nucleu are propriile sale cache L1 personale, cache-urile L2 sunt partajate de fiecare pereche de nuclee:

Harta procesor logic către cache: *--- Cache de date 0, Nivel 1, 32 KB, Assoc 8, LineSize 64 *--- Cache de instrucțiuni 0, Nivel 1, 32 KB, Assoc 8, LineSize 64 -*-- Cache de date 1, Level 1, 32 KB, Assoc 8, LineSize 64 -*-- Cache de instrucțiuni 1, Level 1, 32 KB, Assoc 8, LineSize 64 **-- Unified Cache 0, Level 2, 4 MB, Assoc 16, LineSize 64 --*- Cache de date 2, Nivel 1, 32 KB, Assoc 8, LineSize 64 --*- Cache de instrucțiuni 2, Nivel 1, 32 KB, Assoc 8, LineSize 64 ---* Cache de date 3, Nivel 1, 32 KB, Assoc 8, LineSize 64 ---* Instruction Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64 --** Unified Cache 1, Level 2, 4 MB, Assoc 16, LineSize 64
Să verificăm aceste informații experimental. Pentru a face acest lucru, să trecem prin matricea noastră, incrementând fiecare a 16-a valoare - o modalitate ușoară de a schimba datele din fiecare linie de cache. Când ajungem la sfârșit, ne întoarcem la început. Să verificăm diferitele dimensiuni ale matricei; ar trebui să vedem o scădere a performanței atunci când matricea nu se mai încadrează în cache-urile de diferite niveluri.

Codul este:

int pași = 64 * 1024 * 1024; // numărul de iterații
int lengthMod = arr.Length - 1; // dimensiunea matricei -- puterea a doi
pentru (int i = 0; i< steps; i++)
{
// x & lengthMod = x % arr.Length, deoarece puteri de doi
arr[(i * 16) & lengthMod]++;
}

Rezultatele testului:

Pe aparatul meu, există scăderi vizibile ale performanței după 32 KB și 4 MB - acestea sunt dimensiunile cache-urilor L1 și L2.

Exemplul 4: Paralelismul instrucțiunilor

Acum să ne uităm la altceva. În opinia dumneavoastră, care dintre aceste două bucle se va executa mai repede?

int pași = 256 * 1024 * 1024;
int a = int nou ;
// mai întâi
pentru (int i = 0; i< steps; i++) { a++; a++; }
// al doilea
pentru (int i = 0; i< steps; i++) { a++; a++; }

Se pare că a doua buclă rulează aproape de două ori mai repede, cel puțin pe toate mașinile pe care le-am testat. De ce? Deoarece comenzile din bucle au dependențe diferite de date. Primele comenzi au următorul lanț de dependențe:

În al doilea ciclu dependențele sunt:

Părțile funcționale ale procesoarelor moderne sunt capabile să efectueze un anumit număr de anumite operații simultan, de obicei nu un număr foarte mare. De exemplu, este posibil accesul paralel la datele din memoria cache L1 la două adrese și este posibilă și executarea simultană a două instrucțiuni aritmetice simple. În primul ciclu, procesorul nu poate folosi aceste capacități, dar poate în al doilea.

Exemplul 5: Asociativitatea cache

Una dintre întrebările cheie la care trebuie să se răspundă atunci când se proiectează un cache este dacă datele dintr-o anumită regiune de memorie pot fi stocate în orice celule cache sau numai în unele dintre ele. Trei solutii posibile:

Cache de cartografiere directă,Datele fiecărei linii cache din RAM sunt stocate într-o singură locație cache predefinită. Cel mai simplu mod de a calcula maparea este: row_index_in_memory % number_of_cache_cells. Două linii mapate la aceeași celulă nu pot fi în cache în același timp.
Cache-ul asociativ parțial cu N intrări, fiecare linie poate fi stocată în N locații cache diferite. De exemplu, într-un cache cu 16 intrări, o linie poate fi stocată într-una dintre cele 16 celule care alcătuiesc grupul. De obicei, rândurile cu biți egali de indici mai puțin semnificativi împart un grup.
Cache complet asociativ, orice linie poate fi stocată în orice locație cache. Soluția este echivalentă cu un tabel hash în comportamentul său.

Cache-urile mapate direct sunt predispuse la dispute, de exemplu, atunci când două rânduri concurează pentru aceeași celulă, se scot reciproc din cache, eficiența este foarte scăzută. Pe de altă parte, cache-urile complet asociative, deși lipsite de acest dezavantaj, sunt foarte complexe și costisitoare de implementat. Cache-urile parțial asociative reprezintă un compromis tipic între complexitatea și eficiența implementării.

De exemplu, pe computerul meu, memoria cache L2 de 4 MB este o cache asociată parțială cu 16 intrări. Întreaga RAM este împărțită în seturi de linii conform celor mai puțin semnificative biți ai indicilor lor, liniile din fiecare set concurează pentru un grup de 16 celule cache L2.

Deoarece memoria cache L2 are 65.536 de celule (4 * 2 20 / 64) și fiecare grup este format din 16 celule, avem un total de 4.096 de grupuri. Astfel, cei 12 biți inferiori ai indexului de rând determină grupului căruia îi aparține acest rând (2 12 = 4.096). Ca rezultat, rândurile cu adrese care sunt multipli de 262.144 (4.096 * 64) împart același grup de 16 celule și concurează pentru spațiul din acesta.

Pentru ca efectele asociativității să aibă efect, trebuie să accesăm constant un număr mare de rânduri din același grup, de exemplu, folosind următorul cod:

public static long UpdateEveryKthByte (byte arr, int K)
{
const int rep = 1024 * 1024; // numărul de iterații
Cronometru sw = Cronometru.StartNew();
int p = 0;
pentru (int i = 0; i< rep; i++)
{
arr[p]++;
P += K; dacă (p >= arr.Lungime) p = 0;
}
Sw.Stop();
return sw.ElapsedMilliseconds;
}

Metoda incrementează fiecare K-lea element al tabloului. Când ajungem la capăt, începem din nou. După un număr destul de mare de iterații (2 20), ne oprim. Am făcut rulări pentru diferite dimensiuni de matrice și valori ale pașilor K. Rezultate (albastru - timp de rulare lung, alb - scurt):

Zonele albastre corespund acelor cazuri în care, cu modificări constante ale datelor, memoria cache nu este capabilă să găzduiască toate datele necesare simultan. O culoare albastră strălucitoare indică un timp de funcționare de aproximativ 80 ms, aproape alb - 10 ms.

Să ne ocupăm de zonele albastre:

De ce apar linii verticale? Liniile verticale corespund valorilor pasului la care sunt accesate prea multe rânduri (mai mult de 16) dintr-un grup. Pentru aceste valori, memoria cache cu 16 intrări a mașinii mele nu poate găzdui toate datele necesare.
Unele dintre valorile stride proaste sunt puteri de doi: 256 și 512. De exemplu, luați în considerare stride 512 și o matrice de 8 MB. Cu acest pas, există 32 de secțiuni în matrice (8 * 2 20 / 262 144), care concurează între ele pentru celule din 512 grupuri de cache (262 144 / 512). Există 32 de secțiuni, dar există doar 16 celule în cache pentru fiecare grup, așa că nu există suficient spațiu pentru toată lumea.
Alte valori ale pașilor care nu sunt puteri de doi sunt pur și simplu ghinioniste, ceea ce provoacă un număr mare de accesări la aceleași grupuri de cache și, de asemenea, duce la apariția liniilor albastre verticale în figură. În acest moment, iubitorii de teoria numerelor sunt invitați să gândească.
De ce se rup liniile verticale la limita de 4 MB? Când dimensiunea matricei este de 4 MB sau mai puțin, memoria cache cu 16 intrări se comportă ca un cache complet asociativ, adică poate găzdui toate datele din matrice fără conflicte. Nu există mai mult de 16 zone care luptă pentru un grup de cache (262.144 * 16 = 4 * 2 20 = 4 MB).
De ce există un triunghi albastru mare în stânga sus? Pentru că, cu un pas mic și o matrice mare, memoria cache nu este capabilă să încapă toate datele necesare. Gradul de asociativitate a cache-ului joacă un rol secundar aici; limitarea este legată de dimensiunea cache-ului L2.
De exemplu, cu o dimensiune a matricei de 16 MB și un pas de 128, accesăm fiecare 128 de octeți, modificând astfel fiecare a doua linie de cache a matricei. Pentru a stoca fiecare a doua linie în cache, aveți nevoie de 8 MB de cache, dar pe aparatul meu am doar 4 MB.
Chiar dacă memoria cache ar fi complet asociativă, nu ar permite stocarea a 8 MB de date în el. Rețineți că în exemplul deja discutat cu un pas de 512 și o dimensiune a matricei de 8 MB, avem nevoie doar de 1 MB de cache pentru a stoca toate datele necesare, dar acest lucru este imposibil din cauza asociativității insuficiente a cache-ului.
De ce partea stângă a triunghiului câștigă treptat în intensitate? Intensitatea maximă apare la o valoare a pasului de 64 de octeți, care este egală cu dimensiunea liniei de cache. După cum am văzut în primul și al doilea exemplu, accesul secvenţial la același rând nu costă aproape nimic. Să zicem, cu un pas de 16 octeți, avem patru accesări la memorie la prețul unuia.
Deoarece numărul de iterații este același în testul nostru pentru orice valoare a pasului, un pas mai ieftin are ca rezultat un timp de rulare mai mic.

Efectele descoperite persistă la valori mari ale parametrilor:

Asociativitatea cache-ului este un lucru interesant care se poate manifesta în anumite condiții. Spre deosebire de celelalte probleme discutate în acest articol, nu este atât de gravă. Cu siguranță nu este ceva care necesită o atenție constantă atunci când scrieți programe.

Exemplul 6: Partiționarea cache falsă

Pe mașinile cu mai multe nuclee, este posibil să întâmpinați o altă problemă - coerența cache-ului. Miezurile procesorului au cache-uri parțial sau complet separate. Pe mașina mea, cache-urile L1 sunt separate (ca de obicei) și există, de asemenea, două cache-uri L2 partajate de fiecare pereche de nuclee. Detaliile pot varia, dar, în general, procesoarele moderne multi-core au cache-uri ierarhice pe mai multe niveluri. Mai mult, cele mai rapide, dar și cele mai mici cache aparțin nucleelor individuale.

Când un nucleu modifică o valoare din memoria cache, alte nuclee nu mai pot folosi valoarea veche. Valoarea din cache-urile altor nuclee trebuie actualizată. Mai mult, trebuie actualizat întreaga linie cache, deoarece cache-urile operează pe date la nivel de rând.

Să demonstrăm această problemă cu următorul cod:

private static int s_counter = new int ;
private void UpdateCounter (poziție int)
{
pentru (int j = 0; j< 100000000; j++)
{
s_counter = s_counter + 3;
}
}

Dacă pe mașina mea cu patru nuclee apelez această metodă cu parametrii 0, 1, 2, 3 simultan din patru fire, atunci timpul de rulare va fi 4,3 secunde. Dar dacă apelez la metoda cu parametrii 16, 32, 48, 64, atunci timpul de rulare va fi doar 0,28 secunde.

De ce? În primul caz, este posibil ca toate cele patru valori procesate de fire de execuție la un moment dat să ajungă într-o singură linie de cache. De fiecare dată când un nucleu incrementează o valoare, acesta marchează celulele cache care conțin acea valoare în alte nuclee ca nevalide. După această operație, toate celelalte nuclee vor trebui să memoreze din nou linia în cache. Acest lucru face ca mecanismul de stocare să fie inoperabil, distrugând performanța.

Exemplul 7: Complexitatea hardware

Chiar și acum, când principiile funcționării cache-ului nu sunt un secret pentru tine, hardware-ul tot îți va oferi surprize. Procesoarele diferă unele de altele prin metode de optimizare, euristică și alte subtilități de implementare.

Cache-ul L1 al unor procesoare poate accesa două celule în paralel dacă aparțin unor grupuri diferite, dar dacă aparțin aceluiași grup, doar secvențial. Din câte știu eu, unii pot accesa chiar și diferite sferturi ale aceleiași celule în paralel.

Procesoarele vă pot surprinde cu optimizări inteligente. De exemplu, codul din exemplul anterior despre partajarea falsă a memoriei cache nu funcționează pe computerul meu de acasă așa cum a fost prevăzut - în cele mai simple cazuri, procesorul poate optimiza munca și poate reduce efectele negative. Dacă modifici puțin codul, totul cade la locul său.

Iată un alt exemplu de ciudatenii hardware ciudate:

private static int A, B, C, D, E, F, G;
private static void Ciudație ()
{
pentru (int i = 0; i< 200000000; i++)
{
<какой-то код>
}
}

Dacă în schimb<какой-то код>Înlocuiți trei opțiuni diferite, puteți obține următoarele rezultate:

Creșterea câmpurilor A, B, C, D durează mai mult decât creșterea câmpurilor A, C, E, G. Ce este și mai ciudat este că creșterea câmpurilor A și C durează mai mult decât câmpurile A, C Și E, G. Nu știu exact care sunt motivele pentru aceasta, dar poate sunt legate de băncile de memorie ( da, da, cu băncile obișnuite de memorie de economii de trei litri și nu ceea ce credeai). Dacă aveți vreo părere despre această chestiune, vă rugăm să vorbiți în comentarii.

Pe mașina mea, cele de mai sus nu sunt respectate, totuși, uneori există rezultate anormal de proaste - cel mai probabil, programatorul de sarcini își face propriile „ajustări”.

Lecția care trebuie învățată din acest exemplu este că este foarte dificil să preziceți complet comportamentul hardware-ului. Da, Poate sa preziceți multe, dar trebuie să vă confirmați constant predicțiile prin măsurători și teste.

Concluzie

Sper că tot ceea ce s-a discutat mai sus v-a ajutat să înțelegeți designul cache-urilor procesorului. Acum puteți pune aceste cunoștințe în practică pentru a vă optimiza codul.

Cipurile din majoritatea computerelor desktop moderne au patru nuclee, dar producătorii de cipuri au anunțat deja planuri de a trece la șase nuclee, iar procesoarele cu 16 nuclee nu sunt încă neobișnuite pentru serverele high-end astăzi.

Cu cât sunt mai multe nuclee, cu atât mai mare este problema distribuirii memoriei între toate nucleele în timp ce lucrează împreună în același timp. Odată cu creșterea numărului de nuclee, este din ce în ce mai benefic să se minimizeze timpul pierdut la gestionarea nucleelor la procesarea datelor - deoarece viteza de schimb de date este în urmă față de viteza procesorului și de procesarea datelor în memorie. Puteți accesa fizic memoria cache rapidă a altcuiva sau puteți accesa propriul dvs. lent, dar economisiți timp de transfer de date. Sarcina este complicată de faptul că cantitatea de memorie solicitată de programe nu corespunde în mod clar cu cantitatea de memorie cache a fiecărui tip.

Din punct de vedere fizic, doar o cantitate foarte limitată de memorie poate fi plasată cât mai aproape de procesor - cache-ul L1 al procesorului, al cărui volum este extrem de nesemnificativ. Daniel Sanchez, Po-An Tsai și Nathan Beckmann, cercetători de la Laboratorul de Informatică și Inteligență Artificială al Institutului de Tehnologie din Massachusetts, au învățat un computer să configureze diferite tipuri de memorie pentru o ierarhie flexibilă a programelor în timp real. Noul sistem, numit Jenga, analizează nevoile volumetrice și frecvența accesului programului la memorie și redistribuie puterea fiecăruia dintre cele 3 tipuri de cache a procesorului în combinații care asigură o eficiență sporită și economii de energie.

Pentru început, cercetătorii au testat creșterea performanței la combinarea memoriei statice și dinamice atunci când lucrează la programe pentru un procesor cu un singur nucleu și au obținut o ierarhie primară - când este mai bine să folosești ce combinație. Din 2 tipuri de memorie sau dintr-una. Au fost evaluați doi parametri: întârzierea semnalului (latența) și consumul de energie în timpul funcționării fiecărui program. Aproximativ 40% dintre programe au început să funcționeze mai rău cu o combinație de tipuri de memorie, restul - mai bine. După ce au înregistrat programele care „apreciază” performanța mixtă și cărora le place dimensiunea memoriei, cercetătorii și-au construit sistemul Jenga.

Au testat practic 4 tipuri de programe pe un computer virtual cu 36 de nuclee. Programe testate:

omnet - Objective Modular Network Testbed, bibliotecă de simulare C și platformă de instrumente de simulare a rețelei (albastru în imagine)
mcf - Cadrul de conținut meta (culoare roșie)
astar - software de afișare în realitate virtuală (verde)
bzip2 - arhivator (culoare violet)

Imaginea arată unde și cum au fost procesate datele fiecărui program. Literele indică unde rulează fiecare aplicație (una pe cadran), culorile indică unde se află datele acesteia, iar umbrirea indică al doilea nivel al ierarhiei virtuale atunci când este prezentă.

Niveluri de cache

Cache-ul CPU este împărțit în mai multe niveluri. Pentru procesoare universale - până la 3. Cea mai rapidă memorie este memoria cache de prim nivel - cache L1, deoarece se află pe același cip cu procesorul. Constă dintr-un cache de instrucțiuni și un cache de date. Unele procesoare fără cache L1 nu pot funcționa. Cache-ul L1 funcționează la frecvența procesorului și poate fi accesat la fiecare ciclu de ceas. Este adesea posibilă efectuarea simultană a mai multor operații de citire/scriere. Volumul este de obicei mic - nu mai mult de 128 KB.

Cache-ul de al doilea nivel, L2, interacționează cu memoria cache L1. Este al doilea cel mai rapid. De obicei, este situat fie pe cip, cum ar fi L1, fie în imediata apropiere a nucleului, cum ar fi într-un cartuş de procesor. La procesoarele mai vechi, un set de cipuri pe placa de bază. Volumul cache L2 de la 128 KB la 12 MB. În procesoarele moderne cu mai multe nuclee, cache-ul de al doilea nivel, situat pe același cip, este o memorie separată - cu o dimensiune totală a memoriei cache de 8 MB, fiecare nucleu reprezintă 2 MB. De obicei, latența cache-ului L2 situat pe cipul central este de la 8 la 20 de cicluri de ceas de bază. În sarcinile care implică numeroase accesări la o zonă limitată de memorie, de exemplu, un DBMS, utilizarea completă a acestuia crește productivitatea de zece ori.

Cache-ul L3 este de obicei chiar mai mare, deși oarecum mai lent decât cache-ul L2 (datorită faptului că magistrala dintre L2 și L3 este mai îngustă decât magistrala dintre L1 și L2). L3 este de obicei situat separat de nucleul procesorului, dar poate fi mare - peste 32 MB. Cache-ul L3 este mai lent decât cache-urile anterioare, dar totuși mai rapid decât RAM. În sistemele multiprocesor este de uz comun. Utilizarea unui cache de nivel al treilea este justificată într-o gamă foarte restrânsă de sarcini și poate nu numai să nu ofere o creștere a performanței, ci, dimpotrivă, să conducă la o scădere generală a performanței sistemului.

Dezactivarea nivelului al doilea și al treilea este cea mai utilă în problemele matematice când cantitatea de date este mai mică decât dimensiunea memoriei cache. În acest caz, puteți încărca toate datele în memoria cache L1 simultan și apoi le puteți procesa.

Jenga reconfigurează periodic ierarhiile virtuale la nivel de sistem de operare pentru a minimiza schimbul de date, ținând cont de limitările resurselor și de comportamentul aplicației. Fiecare reconfigurare constă din patru pași.

Jenga distribuie datele nu numai în funcție de programele care sunt expediate - cele care iubesc memoria mare cu o singură viteză sau cele care iubesc viteza cache-urilor mixte, ci și în funcție de proximitatea fizică a celulelor de memorie față de datele procesate. Indiferent de ce tip de cache necesită programul implicit sau prin ierarhie. Principalul lucru este de a minimiza întârzierea semnalului și consumul de energie. În funcție de câte tipuri de memorie îi „place” programului, Jenga modelează latența fiecărei ierarhii virtuale cu unul sau două niveluri. Ierarhiile cu două niveluri formează o suprafață, ierarhiile cu un singur nivel formează o curbă. Jenga proiectează apoi întârzierea minimă în dimensiunile lui VL1, rezultând două curbe. În cele din urmă, Jenga folosește aceste curbe pentru a selecta cea mai bună ierarhie (adică dimensiunea VL1).

Folosirea Jenga a avut un efect vizibil. Cipul virtual cu 36 de nuclee a început să funcționeze cu 30% mai rapid și a folosit cu 85% mai puțină energie. Desigur, deocamdată Jenga este doar o simulare a unui computer care funcționează și va trece ceva timp până când veți vedea exemple reale ale acestui cache și chiar înainte ca producătorii de cipuri să o adopte dacă le place tehnologia.

Configurația unei mașini nucleare convenționale 36

Procesoare. 36 de nuclee, x86-64 ISA, 2,4 GHz, OOO asemănător Silvermont: 8B-wide
ifetch; bpred cu 2 niveluri cu BHSR de 512 × 10 biți + PHT 1024 × 2 biți, decodare/emitere/redenumire/commitere în 2 căi, IQ și ROB cu 32 de intrări, LQ cu 10 intrări, SQ cu 16 intrări; 371 pJ/instrucțiune, 163 mW/nucleu putere statică
Cache L1. 32 KB, cache de date și instrucțiuni asociate cu 8 căi,
latență de 3 cicluri; 15/33 pJ per lovitură/rătăcire
Serviciul Prefetchers. Prefetcher-uri de flux cu 16 intrări, modelate după și validate
Nehalem
Cache L2. 128 KB privat per-core, 8-way set-asociativ, inclusiv, latență de 6 cicluri; 46/93 pJ per lovitură/rătăcire
Mod coerent. Bănci de directoare cu latență cu 16 căi, 6 cicluri pentru Jenga; directoare L3 în cache pentru alții
NoC global. 6×6 mesh, flits și legături pe 128 de biți, rutare X-Y, routere cu conducte în 2 cicluri, legături cu 1 ciclu; 63/71 pJ per router/link flit traversal, 12/4mW router/link putere statică
Memoria statică blochează SRAM. 18 MB, o bancă de 512 KB per tile, zcache cu 4 căi cu 52 de candidați, latență de bancă de 9 cicluri, partiționare Vantage; 240/500 pJ per lovitură/rătăcire, 28 mW/bancă putere statică
DRAM multistrat stivuit. 1152MB, un seif de 128MB la 4 plăci, aliaj cu MAP-I DDR3-3200 (1600MHz), magistrală de 128 de biți, 16 ranguri, 8 bănci/rang, 2 KB buffer de rând; 4,4/6,2 nJ per lovitură/rătăcire, putere statică de 88 mW/seif
Memoria principala. 4 canale DDR3-1600, magistrală pe 64 de biți, 2 rânduri/canal, 8 bănci/rang, 8 KB buffer de rând; 20 nJ/acces, putere statică de 4W
Timpurile DRAM. tCAS=8, tRCD=8, tRTP=4, tRAS=24, tRP=8, tRRD=4, tWTR=4, tWR=8, tFAW=18 (toate cronometrele în tCK; DRAM-ul stivuit are jumătate din tCK ca memorie principală )