Memorie ierarhicăEdit

Memoria ierarhică este o optimizare hardware care preia beneficiile localității spațiale și temporale și care poate fi utilizată pe mai multe niveluri ale ierarhiei memoriei. Paginarea beneficiază în mod evident de localitatea temporală și spațială. O memorie cache este un exemplu simplu de exploatare a localității temporale, deoarece este o zonă de memorie special concepută, mai rapidă, dar mai mică, utilizată în general pentru a păstra datele recent referite și datele din apropierea datelor recent referite, ceea ce poate duce la potențiale creșteri ale performanțelor.

Elementele de date dintr-o memorie cache nu corespund neapărat elementelor de date care sunt apropiate din punct de vedere spațial în memoria principală; cu toate acestea, elementele de date sunt aduse în memoria cache o linie de memorie cache la un moment dat. Acest lucru înseamnă că localitatea spațială este din nou importantă: dacă se face referire la un element, câteva elemente vecine vor fi, de asemenea, aduse în memoria cache. În cele din urmă, localitatea temporală joacă un rol la cel mai mic nivel, deoarece rezultatele care sunt referite foarte aproape una de cealaltă pot fi păstrate în registrele mașinii. Unele limbaje de programare (cum ar fi C) permit programatorului să sugereze ca anumite variabile să fie păstrate în registre.

Localitatea datelor este o caracteristică tipică de referință în memorie a programelor obișnuite (deși există multe modele neregulate de acces la memorie). Ea face ca dispunerea ierarhică a memoriei să fie profitabilă. În calculatoare, memoria este împărțită într-o ierarhie pentru a accelera accesul la date. Nivelurile inferioare ale ierarhiei de memorie au tendința de a fi mai lente, dar mai mari. Astfel, un program va obține performanțe mai mari dacă utilizează memoria în timp ce aceasta se află în memoria cache în nivelurile superioare ale ierarhiei de memorie și evită să aducă alte date în nivelurile superioare ale ierarhiei care vor înlocui date care vor fi utilizate la scurt timp în viitor. Acesta este un ideal și, uneori, nu poate fi atins.

Hierarhie de memorie tipică (timpii de acces și dimensiunile cache-ului sunt aproximări ale valorilor tipice utilizate începând cu 2013 în scopul discuției; valorile reale și numărul real de niveluri în ierarhie variază):

• Registrele CPU (8-256 de registre) – acces imediat, cu viteza nucleului cel mai interior al procesorului
• L1 Memoria cache a CPU (32 KiB până la 512 KiB) – acces rapid, cu viteza magistralei de memorie cea mai interioară deținută exclusiv de fiecare nucleu
• L2 Memoria cache a CPU (128 KiB până la 24 MiB) – acces ușor mai lent, cu viteza magistralei de memorie partajată între gemeni de nuclee
• L3 CPU caches (2 MiB până la 32 MiB) – acces și mai lent, cu viteza magistralei de memorie partajată între și mai multe nuclee ale aceluiași procesor
• Memoria fizică principală (RAM) (256 MiB până la 64 GiB) – acces lent, a cărui viteză este limitată de distanțele spațiale și de interfețele hardware generale dintre procesor și modulele de memorie de pe placa de bază
• Disc (memorie virtuală, sistem de fișiere) (de la 1 GiB la 256 TiB) – foarte lent, din cauza canalului de date mai îngust (în lățime de bit), mult mai lung din punct de vedere fizic, dintre placa principală a calculatorului și dispozitivele de disc, și din cauza protocolului software străin necesar pe lângă interfața hardware lentă
• Memorie la distanță (alte calculatoare sau cloud) (practic nelimitată) – viteza variază de la foarte lentă la extrem de lentă

Mașinile moderne au tendința de a citi blocuri de memorie inferioară în următorul nivel al ierarhiei de memorie. Dacă acest lucru deplasează memoria utilizată, sistemul de operare încearcă să prezică ce date vor fi accesate cel mai puțin (sau cel mai târziu) și să le mute în josul ierarhiei de memorie. Algoritmii de predicție tind să fie simpli pentru a reduce complexitatea hardware, deși devin ceva mai complicați.

Înmulțirea matricelorEdit

Un exemplu comun este multiplicarea matricelor:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Schimbând ordinea de buclă pentru j și k, creșterea vitezei în cazul înmulțirii matricelor mari devine spectaculoasă, cel puțin pentru limbajele care pun elemente de matrice contiguă în ultima dimensiune. Acest lucru nu va schimba rezultatul matematic, dar îmbunătățește eficiența. În acest caz, „mare” înseamnă, aproximativ, mai mult de 100.000 de elemente în fiecare matrice, sau suficientă memorie adresabilă astfel încât matricile să nu încapă în memoria cache L1 și L2.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

Motivul acestei creșteri de viteză este că, în primul caz, citirile din A sunt în memoria cache (deoarece indexul k este ultima dimensiune contiguă), dar B nu este, astfel încât există o penalizare de ratare a memoriei cache pentru B. C este irelevant, deoarece poate fi scos din bucla interioară – variabila buclei este k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

În cel de-al doilea caz, citirile și scrierile din C sunt ambele în memoria cache, citirile din B sunt în memoria cache, iar citirea din A poate fi scoasă din bucla interioară.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Așa, al doilea exemplu nu are nicio penalizare de ratare a memoriei cache în bucla interioară, în timp ce primul exemplu are o penalizare a memoriei cache.

Pe un procesor din anul 2014, al doilea caz este de aproximativ cinci ori mai rapid decât primul caz, atunci când este scris în C și compilat cu gcc -O3. (O examinare atentă a codului dezasamblat arată că, în primul caz, GCC utilizează instrucțiuni SIMD, iar în al doilea caz nu o face, dar penalizarea cache-ului este mult mai rea decât câștigul SIMD.)

Localitatea temporală poate fi, de asemenea, îmbunătățită în exemplul de mai sus prin utilizarea unei tehnici numite blocking. Matricea mai mare poate fi împărțită în submatrici de dimensiuni egale, astfel încât blocurile mai mici să poată fi referite (înmulțite) de mai multe ori în timp ce se află în memorie.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

Localitatea temporală a soluției de mai sus este asigurată deoarece un bloc poate fi utilizat de mai multe ori înainte de a trece mai departe, astfel încât acesta este mutat în și din memorie mai rar. Localitatea spațială este îmbunătățită deoarece elementele cu adrese de memorie consecutive tind să fie trase împreună în sus în ierarhia de memorie.

.