Studiul memoriei cache Obiectivul lucrării
Yüklə 57,18 Kb.
|
|
Studiul memoriei cache 1. Obiectivul lucrării Lucrarea de faţă îşi propune să prezinte o serie de aspecte teoretice şi practice referitoare la modul de funcţionare al memoriei cache. Aplicaţia constă dintr-un program de simulare realizat în mediul de dezvoltare .NET. 2. Introducere teoretică Datorită vitezei foarte mari cu care lucrează microprocesoarele, implicit şi fluxul de date şi informaţii cerute de acestea va fi foarte intens. Dar, deoarece unele componente din lanţul de transmisie a datelor sunt mai lente, în speţă memoria de lucru RAM (prin necesitatea de a fi reîmprospătată) şi magistralele calculatorului (lente din principiu), acest flux de date cerut de procesor este mai puţin rapid decât ar fi necesar (de exemplu, memoria RAM asigură un timp de acces de 60–120 ns, ceea ce este foarte mult faţă de nivelul de câteva nanosecunde, timp cu care lucrează de obicei procesoarele pentru un anumit proces). Ca atare, între posibilităţile de prelucrare a datelor de către microprocesor şi capacitatea RAM-ului şi a magistralelor de a pune la dispoziţia microprocesorului aceste date a apărut un decalaj foarte mare. Aceasta a dus în procesul de lucru al unui microprocesor la introducerea stărilor de pauză (wait states), astfel încât, prin execuţia a unuia, a două sau chiar a patru cicluri de aşteptare, datele solicitate să aibă timp să ajungă la procesor. Practic, se întâmplă următorul lucru: microprocesorul lucrează fie cu datele necesare calculelor, fie cu comenzi. Cum datele şi informaţiile necesare sunt cuprinse în memoria de lucru, microprocesorul citeşte memoria RAM, preluând anumite date, şi realizează calculele şi procesele cerute. Cum memoria este mult mai lentă în livrarea datelor faţă de viteza cu care le poate prelucra microprocesorul, în funcţionarea procesorului se introduc ciclurile de aşteptare despre care s-a vorbit anterior; cât timp aceste cicluri se execută, se permite datelor solicitate de procesor să fie localizate şi „extrase” din RAM, depuse pe magistrala de date şi „transportate” către microprocesor. În final, dacă se va înmulţi timpul cât durează un ciclu de aşteptare cu milioanele de operaţii pe secundă ale unui microprocesor, va rezulta o pierdere de timp substanţială. Deci era nevoie de o memorie de lucru ceva „mai aproape de microprocesor” şi mult mai rapidă (ideal fără să necesite operaţii de reîmprospătare). De aceea, între microprocesor şi memoria de lucru a mai fost introdusă o componentă şi anume memoria cache, realizată din celule de tip SRAM rapide, cu rol de memorie tampon. Memoriile rapide sunt realizabile din punct de vedere tehnologic, dar costul lor este ridicat. Sunt cunoscute însă tehnici pentru combinarea unei memorii rapide de dimensiuni mici cu o memorie mai lentă de dimensiuni mai mari, pentru a se obţine aproximativ viteza memoriei rapide şi capacitatea memoriei lente, la un preţ moderat. Dimensiunea memoriei cache trebuie să fie suficient de mică, astfel încât costul mediu pe bit al întregului sistem de memorie să fie apropiat de cel al memoriei principale, şi suficient de mare, astfel încât timpul mediu de acces al întregului sistem de memorie să fie apropiat de cel al memoriei cache. O dimensiune relativ redusă, între 64 KB şi 512 KB, satisface de obicei aceste cerinţe. Principiul de funcţionare al memoriei cache este sintetizat în figura 1.
O caracteristică de bază a memoriei cache este funcţia de mapare (de translatare), care atribuie locaţii din memoria cache blocurilor din memoria principală. Se pot utiliza trei tehnici:
Se consideră o memorie cache de 1024 (1 K) octeţi. Datele se transferă între memoria principală şi memoria cache în blocuri de câte 8 octeţi. Înseamnă că memoria cache are 128 de linii de câte 8 octeţi fiecare. Memoria principală constă din 64 Kocteţi, fiecare octet fiind direct adresabil printr-o adresă de 16 biţi. Se poate considera că memoria principală constă din 8 Kblocuri de câte 8 octeţi fiecare. Deoarece există un număr mai mic de linii ale memoriei cache faţă de numărul blocurilor memoriei principale, este necesar un algoritm pentru plasarea blocurilor memoriei principale în liniile memoriei cache. În plus, este necesar un mijloc de a determina care bloc al memoriei principale ocupă la un moment dat o linie a memoriei cache. 2.1.1. Memoria cache cu mapare directă În cazul tehnicii celei mai simple, numită mapare directă, fiecare bloc al memoriei principale poate ocupa o singură linie posibilă a memoriei cache, aşa cum este reprezentat în figura 3. 
Fig. 3. Memorie cache cu mapare directă. Maparea este: C = A mod L, (1) unde: C = numărul liniei din memoria cache; A = adresa din memoria principală; L = numărul de linii din memoria cache. Pentru exemplul considerat, L = 128 şi C = A mod128. Funcţia de mapare poate fi implementată simplu, utilizând adresa de 16 biţi. Cei 3 biţi mai puţin semnificativi (offset) identifică un cuvânt (octet) unic în cadrul unui bloc al memoriei principale. Restul de 13 biţi specifică unul din cele 213 = 8 Kblocuri ale memoriei principale. Câmpul de 7 biţi, numit linie (index), indică numărul blocului, modulo128. Astfel, blocurile 0, 128, 256, …, 8064 vor fi amplasate în linia 0; blocurile 1, 129, …, 8065 vor fi amplasate în linia 1, şi aşa mai departe, până la blocurile 127, 255, …, 8191, care vor fi amplasate în linia 127. Câmpul de 6 biţi, numit marcaj sau etichetă (tag), are rolul de a identifica în mod unic blocul din linie. Astfel, blocurile 0, 128, 256, …, 8064 au numerele de marcaje 0, 1, 2, …, respectiv 63. Considerând din nou figura 2, o operaţie de citire are loc astfel. Memoriei cache i se prezintă o adresă de 16 biţi. Numărul liniei de 7 biţi este utilizat ca un index în memoria cache pentru accesul la o anumită linie. Dacă marcajul de 6 biţi este egal cu marcajul liniei respective, atunci numărul de 3 biţi al cuvântului este utilizat pentru a selecta unul din cei 8 octeţi ai liniei respective. În caz contrar, marcajul şi numărul liniei (în total 13 biţi) se utilizează pentru a încărca un bloc din memoria principală. 2.1.2. Memoria cache cu mapare asociativă
Maparea directă este o tehnică care se poate implementa simplu. Principalul dezavantaj al acesteia este că există o locaţie fixă în memoria cache pentru oricare bloc dat. Deci, dacă un program face referire în mod repetat la cuvinte din două blocuri diferite care se mapează în aceeaşi linie, blocurile vor fi interschimbate în mod continuu în memoria cache şi rata de succes va fi redusă. O metodă care elimină dezavantajul mapării directe este maparea asociativă, reprezentată în figura 4. 
Fig. 4. Memorie cache cu mapare asociativă. În acest caz, adresa memoriei principale constă dintr-un marcaj de 13 biţi şi un număr al cuvântului de 3 biţi. Un bloc din memoria principală se poate încărca în oricare linie, iar marcajul său de 13 biţi se memorează împreună cu blocul. Pentru a determina dacă un bloc se află în memoria cache, sunt necesare circuite pentru a compara simultan marcajul său cu marcajele fiecărei linii. În cazul mapării asociative, există o flexibilitate în privinţa înlocuirii unui bloc atunci când un nou bloc este încărcat în memoria cache. Algoritmii de înlocuire a blocurilor din memoria cache, prezentaţi în continuare, au rolul de a creşte eficienţa. Principalul dezavantaj al acestei metode îl reprezintă circuitele complexe necesare pentru a examina marcajele tuturor liniilor din memoria cache. 2.1.3. Memoria cache cu mapare asociativă pe seturi Maparea asociativă pe seturi reprezintă un compromis care reţine avantajele mapării directe şi a celei asociative. În acest caz, memoria cache este împărţită în I seturi, iar fiecare din acestea conţine J linii, aşa cum rezultă din figura 5. Rezultă:
K = A mod I, (3) unde K este numărul setului. Cu această metodă, blocul conţinând adresa A poate fi mapat în oricare din liniile setului I. De observat că în cazul extrem în care I = L, J = 1, maparea asociativă pe seturi se reduce la maparea directă, iar atunci când I = 1, J = L, se obţine maparea asociativă. 
Fig. 5. Memorie cache cu mapare asociativă pe seturi. Utilizarea a două linii pe set este cea mai utilizată organizare asociativă pe seturi, care îmbunătăţeşte semnificativ rata de succes faţă de maparea directă. 2.2. Reînnoirea conţinutului memoriilor cache În ceea ce priveşte reînnoirea conţinutului memoriilor cache, pentru ştergerea datelor curente şi aducerea altora noi se aplică o politică de înlocuire (replacement policy) a blocurilor din memoria cache, care are numeroase variante: politica aleatoare (random), politica circulară (round robin), politica celui mai rar folosit (least frequently used), politica primul intrat – primul ieşit (first in, first out), politica celui mai demult folosit (least recently used), politica setului de lucru (working set), politica optimă (optimal), politica ceasului, politica celei de-a doua şanse (second chance) etc. În practică, sunt aplicate cu preponderenţă patru metode:
Metoda cea mai folosită este LRU. Cipul de memorie cache numit TAG RAM va juca rol de contor static al frecvenţei de apelare a datelor din memoria cache, determinându-se datele care vor fi rescrise. Modul de lucru general al microprocesoarelor cu memoria cache este următorul: programul va căuta datele, prin intermediul controlerului de cache, în cache-ul intern (L1). Dacă datele solicitate nu se află la acest nivel (cache miss), va merge mai departe cu căutarea în cache-ul extern (L2) şi apoi, în cazul negăsirii acestora nici aici, în memoria principală RAM. Probabilitatea ca procesorul să găsească datele necesare într-unul din cele două niveluri cache (cache hit) este însă destul de mare. Totodată, magistrala memoriei care, în lipsa memoriei cache, ar fi fost solicitată pentru operaţii cu RAM-ul, este disponibilizată pentru alte procese.
Memoria cache este conectată cu microprocesorul şi RAM-ul în sistem serial sau paralel. 1. Conectarea serială (look through), reprezentată în figura 6, presupune ca dialogul microprocesor–RAM să se desfăşoare prin intermediul memoriei cache. Acest sistem are dezavantajul că cererile procesorului sunt întârziate de intermediarul cache, dar are avantajul că magistrala memoriei nu este ocupată la fiecare cerere a procesorului. Dacă datele solicitate se află în cache (cache hit), interogarea RAM-ului nu se mai efectuează, iar magistrala memoriei rămâne liberă. 2. Conectarea paralelă (look aside), reprezentată în figura 7, presupune ca microprocesorul să se adreseze, în paralel, atât memoriei cache cât şi memoriei RAM. În cazul în care ecoul din partea memoriei cache este pozitiv, adresarea către RAM este abandonată. De aici rezultă, faţă de metoda anterioară, avantajul vitezei, evitându-se căutarea secvenţială: întâi în cache, apoi în RAM. Dezavantajul apare prin faptul că magistrala memoriei este tot timpul folosită şi astfel nu mai este disponibilă – în momentele de „scanare“ a memoriei – altor accesări din partea perifericelor. Mai ales în modul multitasking, acest lucru se reflectă în întârzieri semnificative ale vitezei de execuţie a diferitelor task-uri. Fig. 7. Organigrama conectării paralele (look aside). 2.4. Depunerea în memorie a rezultatelor În ce priveşte modul în care microprocesorul va depune în memorie rezultatele operaţiilor sale, se folosesc trei metode. 1. Metoda Write Through, reprezentată în figura 8, este cea în care se utilizează traseul invers al citirii datelor, acestea fiind depuse mai întâi în memoria cache internă, apoi în memoria cache externă şi, în final, în memoria RAM. Fig. 8. Schema metodei Write Through. Nu este nevoie de salvarea paginii de memorie cache, iar translatarea blocurilor se efectuează numai pentru accese de citire. La scriere, chiar şi pentru o pagină negăsită (page fault), se scrie în memoria cache şi în memoria principală sau numai în memoria principală). Pentru simplitatea şi claritatea codului, dar mai ales pentru eficienţa implementării, se alege ca tehnică de mapare maparea asociativă. Există o tabelă asociativă TA (bazată pe o memorie cu căutare asociativă, după conţinut), asociată memoriei cache, care păstrează pentru fiecare bloc de memorie cache o etichetă reprezentând adresa blocului din memoria principală (ABLP) stocat în blocul de memorie cache. Astfel, la fiecare acces la memorie, se va căuta în TA adresa cerută şi, dacă există o etichetă cu valoarea ABLP, se va furniza adresa blocului de memorie cache care rezultă din poziţia etichetei respective în TA. Dacă nu există, atunci se va înlocui un bloc din memoria cache, conform unui algoritm de înlocuire. În cazul de faţă este vorba de algoritmul LRU (Least Recently Used). Căutarea unui bloc în TA se poate face eficient în hardware, având în vedere că se pot realiza în paralel comparările care sunt independente. 2. Metoda Write Back, reprezentată în figura 9, este cea în care scrierea se face în memoria cache în cazul în care adresa de memorie la care se face scrierea există şi ea în cache (de fapt, dacă blocul de date de la acea adresă se află încărcat în cache). În cazul în care blocul de date localizat de acea adresă nu mai există în cache, scrierea se face direct în memoria RAM. 
Fig. 9. Schema metodei Write Back. Se scrie şi se citeşte doar în/din memoria cache, iar în caz de pagină negăsită (page fault) se realizează salvarea paginii de memorie cache care se înlocuieşte în memoria principală (de unde a fost adusă), apoi pagina de memorie principală cerută de procesor va fi scrisă în locul paginii de memorie cache salvate. Dacă nu se cunoaşte faptul că pagina de memorie cache care se înlocuieşte cu noua pagină a fost sau nu modificată, atunci se salvează întotdeauna pagina de memorie cache. Dacă se foloseşte un bit de modificare (dirty), care este setat la prima scriere a paginii de memorie cache, atunci se testează acest bit şi pagina de memorie cache este salvată în memoria principală numai dacă pagina a fost modificată. Transferarea blocurilor de memorie se realizează ori de cate ori apare un nou acces de pagină de memorie cache negasită (cache fault page). 3. Metoda Posted Write este cea prin care din memoria cache este rezervată o anumită porţiune care va juca un rol de buffer, în care vor fi memorate blocuri de date până când magistrala memoriei devine disponibilă, moment în care buffer-ul îşi transferă conţinutul în RAM.
2.5. Eficienţa şi localizarea datelor în memoria cacheO memorie cache este utilă numai dacă anumite informaţii sunt folosite frecvent şi mult timp. Atunci acele informaţii merită să fie păstrate în memoria cache. Din fericire, s-a constatat experimental că acest lucru este foarte adesea adevărat. Această observaţie poate fi formulată în mai multe moduri, unul dintre acestea fiind principiul localizării (locality principle). Există două feluri de localizare:
Acestea sunt doar observaţii, dar se potrivesc destul de bine programelor de calculator, aşa cum funcţionează acestea în calculatoarele actuale. Validitatea observaţiilor permite folosirea de memorii cache. Acesta nu înseamnă că nu există programe care folosesc prost memoriile cache; dimpotrivă, se poate scrie destul de uşor un astfel de program (este o metodă eficientă de a încetini calculatorul). Programele obişnuite însă nu se comportă astfel. Eficienţa unei memorii cache se măsoară în procentajul de găsiri ale datelor, H (hit rate): din 100 de accese, câte date sunt găsite în memoria cache? Opusul acestei valori este miss rate, M (procentajul de ratări). Procentajele acestea se măsoară rulând numeroase programe şi făcând media. Relaţia în ele este: H = 1 – M. (4) Dacă timpul de citire din memoria cache este TH (hit time), iar timpul pierdut până se ratează este TM (miss time), atunci se poate măsura timpul mediu de acces la memoria cache cu următoarea formulă: T = TH H + TM M. (5) Se observă că timpul unei ratări (TM) nu este neapărat egal cu timpul de citire din memoria lentă, Tl, deoarece, în cazul unei ratări, întâi trebuie constatat dacă datele sunt în memoria cache, iar, dacă nu sunt, se accesează memoria lentă. Memoria cache va fi eficientă dacă T < Tl. Parametrul H depinde de mărimea memoriei cache: pentru o memorie cache de mărimea memoriei lente (caz limită), toate datele pot fi ţinute în memoria rapidă şi se va obţine H = 1. Pentru o memorie cache de mărime 0, H = 0, pentru că niciodată datele nu se găsesc în această memorie. Relaţia între mărimea memoriei cache, a memoriei lente şi parametrul H nu este o dreaptă, ci creşte rapid la început, aşa cum se observă în figura 10. Din cauza aceasta, o memorie cache relativ redusă ca mărime are o importanţă mare ca eficienţă. 
Fig. 10. Performanţa memoriei cache. Eficienţa depinde şi de raportul dintre TH şi TM. În anumite cazuri, TM este de ordinul a 10.000 TH, deci chiar un parametru H de valoare redusă poate să însemne mult. 3. Descrierea aplicaţiei Aplicaţia realizată în mediul de dezvoltare .NET, prin implementarea unor algoritmi, a fost realizată în scopul simulării memoriei cache. Utilizatorul poate introduce anumite valori pe baza cărora aplicaţia generează anumite rezultate. Fiecare modul al aplicaţiei studiază un anumit aspect al memoriei cache. Simularea memoriei cache înseamnă, de fapt, înţelegerea funcţionării sale prin exemple. Aceste exemple sunt realizate de utilizator prin condiţionarea parametrilor de intrare. Aplicaţia începe cu meniul principal, în care se pot observa 5 componente de tip explorer bar, pentru fiecare din acestea existând câte două componente de tip link label. Acestea au rolul de a trimite utilizatorul acolo unde doreşte, la partea de noţiuni teoretice sau la partea practică (aplicaţie), în cadrul căreia poate urmări evoluţia şi funcţionarea memoriei cache. În funcţie de modulul aplicaţiei pe care doreşte să îl aprofundeze, utilizatorului îi va fi încărcată fereastra corespunzătoare modulului respectiv. 1. Partiţionarea adresei de memorie pe biţi (figura 11). Utilizatorul alege ca parametrii de intrare dimensiunea memoriei RAM (între 256 KB şi 32 MB), dimensiunea memoriei cache (între 64 KB şi 512 KB), dimensiunea blocului de date (între 2 B şi 32 B) şi tipul de mapare: directă sau asociativă pe seturi (cu dimensiunea setului între două blocuri şi 8 blocuri). Programul afişează ca rezultate numărul blocurilor din memoria cache, numărul de biţi în tag, precum şi diagrama repartizării biţilor (tag, index şi offset) în adresa memoriei cache. 
Fig. 11. Partiţionarea adresei pe biţi. 2. Încărcarea blocurilor memoriei cache (figura 12). Utilizatorul alege ca parametrii de intrare dimensiunea memoriei cache (între 128 B şi 1 KB), dimensiunea blocului de date (între 2 B şi 32 B), tipul de mapare: directă sau asociativă pe seturi (între două căi şi 8 căi) şi valoarea în binar a adresei ( 16 digiţi). Programul afişează ca rezultate modul de repartizare al biţilor tag, index şi offset, valoarea indexului în zecimal, precum şi tabelul repartizării şirurilor pe blocuri în memoria cache. 
Fig. 12. Încărcarea blocurilor memoriei cache. 3. Reînnoirea blocurilor memoriei cache (figura 13). Utilizatorul alege ca parametrii de intrare dimensiunea memorie cache (între 1 KB şi 256 KB), numărul de seturi (între 1 şi 128), algoritmul de înlocuire (LRU, FIFO sau RANDOM) şi secvenţa de test (valori numerice succesive, separate prin Enter). Programul afişează ca rezultate modul de repartizare al blocurilor pe seturi la fiecare pas, evidenţiind cu verde succesele, cu albastru ratările impuse sau inerente (compulsory misses) – care apar la umplerea memoriei cache (blocuri plasate pentru prima oară), iar cu galben ratările de limitare sau de conflict (capacity misses) – provocate de depăşirea capacităţii memoriei. Paşii pot fi parcurşi iterativ în ambele sensuri, în ordinea directă sau inversă a introducerii valorilor numerice. Sunt afişate procentele de hit rate şi miss rate, obţinute prin raportul numărului de succese sau de ratări la numărul total de teste. 4. Analiza în timp a memoriei cache (figura 14). Utilizatorul alege ca parametrii de intrare dimensiunea memorie cache (între 1 KB şi 256 KB), numărul de seturi asociative (între 1 şi 8), dimensiunea blocului de date (între 16 biţi şi 128 biţi), decalajul de ratare, intervalul de succes, scrierea în memorie (toate în număr de cicluri), metoda de scriere (Write Back sau Write Through, cu variantele No-Write Allocate – blocul este modificat în memoria principală, dar nu este încărcat în cache, sau Allocate on Miss – blocul este actualizat în memoria principală şi încărcat în cache), procentajul de scrieri şi procentajul de utilizare pentru dirty data. Programul afişează ca date de ieşire numărul cuvintelor pe bloc de date şi valorile pentru hit rate şi miss rate. Rezultatele calculate sunt intervalele de succes şi ratare pentru citiri şi scrieri, precum şi timpul mediu de acces la memoria cache, exprimat în număr de cicluri de acces. Programul desenează analiza în timp a funcţionării memoriei cache, reprezentând intervalele de succes şi ratare pentru citiri şi scrieri.  
Fig. 13. Reînnoirea blocurilor memoriei cache. 
Fig. 14. Analiza în timp a memoriei cache. 5. Conectarea memoriei cache la microprocesor (figura 15). Utilizatorul alege ca parametrii de intrare tipul de conectare (serială sau paralelă) şi dacă există data solicitată în memoria cache (DA sau NU). Programul afişează ca rezultate organigramele conectării seriale şi/sau paralele. 
Fig. 15. Conectarea memoriei cache la microprocesor. 4. Desfăşurarea lucrării
5. Întrebări
Yüklə 57,18 Kb. Dostları ilə paylaş:
|
