Sisteme de Memorie - Memoria Asociativă

Sisteme de Memorie

• Există o ierarhie a memoriilor.
• Există diferite tipuri de memorii, inclusiv memorii semiconductoare, memorii cu unități multiple, memorie asociativă, memorie cache și memorie virtuală.

Memoria Asociativă (1)

• În memoriile RAM, datele sunt identificate cu adrese unice.
• În memoriile asociative, datele sunt identificate prin conținutul lor, nu prin adrese.
• Memorii adresabile prin conținut (CAM - Content Addressable Memory).
• Pentru o memorie asociativă cu n cuvinte, timpul de căutare a unei date este independent de n.
• Toate cuvintele din memorie pot fi comparate în paralel cu cuvântul căutat.

Memoria Asociativă (2)

• Memorile asociative sunt mai scumpe decât memoriile RAM.
• Exemple de utilizare: memorii cache (translatarea adreselor, recunoașterea modelelor).
• Două tipuri de memorii asociative:
  • Cu potrivire exactă: datele sunt identificate pe baza egalității cu o cheie.
  • Cu comparație: folosesc operatori relaționali.

Memoria Asociativă (3)

• Organizarea logică a memoriei asociative poate fi fixă sau variabilă.
• Organizare fixă: un cuvânt este imparțit în segmente fixe, un segment cheie. Fiecare bit din acest segment trebuie utilizat pentru interogare.
• Organizare variabilă: un cuvânt poate fi imparțit în segmente fixe. Orice parte a unui segment poate fi utilizată pentru interogare, făcând-o complet interogabilă.

Memoria Asociativă (4)

• Diagrama prezintă arhitectura internă a unei memorii asociative.
• Elemente: registre pentru argument și cheie/mască, o matrice de memorie asociativă, registre pentru potrivire și ieșire. Circuit de selecție pentru extragerea rezultatelor.

Memoria Asociativă (5)

• O celulă de memorie asociativă necesită aproximativ 10 tranzistoare.
• Sunt prezentate componentele electronice, precum tranzistoare și porți logice și modul de funcționare.

Memoria Asociativă (6)

• Prelucrarea asociativă este executată cu un procesor asociativ.
• Un procesor asociativ conține o memorie asociativă și o unitate de control suplimentară.
• Memoria asociativă poate executa în paralel instrucțiuni primitive.
• Exemple de instrucțiuni executate de o memorie asociativă: SET (setare la 1 a tuturor biților de potrivire).

Memoria Asociativă (7)

• COMPARE: comparații paralele ale argumentului mascat cu toate cuvintele.
• READ: transmiterea pe liniile de date a cuvintelor care au biții de potrivire setați.
• WRITE: scrierea în paralel a argumentului mascat în toate cuvintele care au biții de potrivire setați.
• REPORT: raportarea unității centrale dacă există o potrivire după o căutare precedentă.

Memoria Asociativă (8)

• Avantajele prelucrării asociative: viteză mare pentru anumite probleme (timp de execuție redus cu un factor n), un mod mai natural de rezolvare a problemelor de calcul și operații locale.
• Aplicații: prelucrarea imaginilor, urmărirea semnalelor radar și inteligența artificială în timp real.

Memoria Cache

• Funcția principală este păstrarea temporară a datelor și instrucțiunilor pentru utilizare imediată.
• Este mai rapidă decât memoria principală, dar și mai costisitoare.
• Dimensiunea memoriei cache este limitată într-un sistem de calcul.
• O mare parte a cererilor de acces sunt satisfăcute de memoria cache datorită proprietății de localitate a referințelor.

Principiul Memoriei Cache (1)

• Memoria cache este o memorie rapidă, folosită temporar pentru păstrarea unei părți din date și instrucțiuni, pentru a îmbunătăți timpul de acces.
• Memoria cache este costisitoare, iar dimensiunea sa este limitată.
• O mare parte a cererilor de acces sunt satisfăcute de memoria cache.

Principiul Memoriei Cache (2)

• Memoria cache este plasată între memoria principală și unitatea centrală de procesare (UCP).
• Conține copii ale unor blocuri din memoria principală, care sunt accesate mai frecvent.

Organizarea Memoriei Cache (1)

• Cuvintele de memorie sunt grupate în pagini (blocuri, linii).
• Fiecare bloc/linie din memoria cache are un marcaj ("tag") ce conține adresa blocului.
• Adresele marcajelor din memoria cache sunt stocate într-o memorie de marcaje.

Organizarea Memoriei Cache (2)

• Bitul de validare (V) este adăugat fiecărui marcaj indicând dacă acesta conține o adresă validă.

Funcționarea Memoriei Cache (1)

• Dacă UCP solicită o adresă, cererea este trimisă mai întâi la memoria cache.
• Dacă blocul cuvântului cerut este găsit în memoria cache, cuvântul este furnizat direct de cache.
• Dacă blocul nu este găsit, cuvântul este solicitat din memoria principală.

Funcționarea Memoriei Cache (2)

• Diagrama prezintă fluxul de date în timpul unei operații de citire din memorie cache.
• Elementele implicate: comparație marcajele din cache cu adresa de intrare, selecție/procurarea datelor.

Funcționarea Memoriei Cache (3)

• UCP generează o cerere de scriere, cererea e trimisă mai întâi la cache.
• Dacă blocul cuvântului cerut nu este în cache, se încarcă o copie a blocului din memoria principală în cache și se execută operația de scriere.
• Dacă blocul este în cache, se execută operația de scriere direct în cache.

Funcționarea Memoriei Cache (4)

• Diagrama prezintă fluxul datelor în timpul unei operații de scriere din memorie cache, similar cu operaţia de citire.

Funcționarea Memoriei Cache (5)

• Poate apare incoerența datelor între cache și memorie principală.
• O incoerența temporară este acceptabilă.
• Problema coerenței memoriilor cache: necesitatea prevenirii utilizării improprii a datei vechi în sistemele multiprocesor și uniprocesor.

Funcționarea Memoriei Cache (6)

• Strategii de scriere: write-back, write-through.
• Strategia write-back scrie un bloc doar în cache, în timp ce strategia write-through scrie un bloc în cache și în memoria principală.
• Fiecare bloc din cache are un bit de modificare("dirty bit") care indică dacă a fost modificat.
• Write-back scrie în memoria principală doar când blocul trebuie înlocuit, dacă bitul este setat.

Funcționarea Memoriei Cache (7)

• Avantaje: operații multiple de scriere în cache necesită o singură scriere în memoria principală, reducând încărcarea magistralei și consumul de energie.
• Dezavantaje: posibilitatea incoerenței temporare între cache și memorie principală și complexitatea recuperării în cazul defectelor de sistem.

Funcționarea Memoriei Cache (8)

• Strategia write-through: un bloc este modificat atât în cache cât și în memoria principală.
• Avantajele: implementare simplă, păstrarea coerenței datelor și simplitatea gestionării cache-urilor multi-nivel.
• Dezavantaje: încetinește UCP datorită multiplelor scrieri.

Translatarea Adreselor

• Procesul de traducere a adreselor de memorie specificate de UCP în locații din memoria cache.
• Tipuri de translatare: asociativă, directă, cu seturi asociative.

Translatarea Asociativă (1)

• În memoria cache cu asociativitate totală, un bloc de memorie poate fi plasat în orice locație.
• Căutarea unui bloc necesită parcurgerea tuturor locațiilor din cache.
• Organizarea memoriei: combinație de memorie asociativă și memorie RAM, cu marcaje în memoria asociativă și date în memoria RAM.

Translatarea Asociativă (2)

• Fiecare marcaj conține doar o parte a adresei din memoria principală, neconținând deplasarea octetului din bloc.
• Adresele de memorie conțin două părți(deplasament + marcaj), unde deplasamentul identifică octetul și marcajul identifică blocul.
• Dezavantajul: necesită o memorie asociativă.

Translatarea Asociativă (3)

• Specificații pentru exemplul 3.1 dintr-un cadru conceptual cu translatare asociativă: memorie principală 64KB, adresabilă la nivel de octet, adrese de 16 biți, cuvinte de date de 32 biți, dimensiunea cache 1KB, dimensiunea unui bloc 4 cuvinte (16B).

Translatarea Asociativă (4)

• Adresarea unui octet dintr-un bloc de 16B este cu 4 biți (2⁴ = 16).
• Calcule pentru deplasament, numărul de blocuri în memoria principală, marcaje și cuvinte de date.

Translatarea Asociativă (5)

• Diagramă bloc a translatării asociative, prezentând structura memoriilor principale și cache, registrele și fluxul de date.

Translatarea Directă (1)

• Se folosește memorie RAM în locul memoriilor asociative reducând costul, memoria principală este împărțită în blocuri.
• Memoria cache este împărțită în seturi, unde fiecare bloc din memoria principală poate fi plasat în exact un bloc din cache.

Translatarea Directă (2)

• Exemplu de calcul al adresei setului pentru o adresă specifică de octet.

Translatarea Directă (3)

• Calculare a adresei setului pentru o adresă specifică de octet.
• structură a adresei de memorie (deplasament, index, marcaj).

Translatarea Directă (4)

• Marcajul: biții de ordin superior ai adresei din memoria principală.
• Identificarea blocului din memoria principală corespunzător adresei specificate de index.
• Memorarea blocului în memoria cache și în memoria de date

Translatarea Directă (5)

• Avantaje ale translatării directe: necesită un număr mai mic de biți pentru fiecare bloc în cache, cache-uri cu mai multe cuvinte pe set, reducerea totală a marcajelor.
• Dezavantaje: performanțele pot scădea dacă mai multe cuvinte cu același index, dar marcaje diferite sunt accesate frecvent.

Translatarea Directă (6)

• Exemplu de calcul al adresei unui bloc dat.

Translatarea Directă (7)

• Diagrama bloc a translatării directe demonstrând procesul de calcul al adresei pentru o locație din memoria cache și fluxul de date.

Translatarea Directă (8)

• Caracteristici ale translatării directe prin intermediul unui exemplu: procesor, magistralii de adrese și date, dimensiune memorie cache, și dimensiunea unui set.

Translatarea Directă (9)

• Calcul al adresei, numărul de seturi, marcaj, și dimensiunea memoriei/cuvinților de date.

Translatarea Directă (10)

• Diagrama bloc a translatării directe, prezentând procesul de acces la memorie, inclusiv UCP, memorii de marcaje și de date, registre.

Translatarea cu Seturi Asociative (1)

• Permite memorarea mai multor blocuri cu același index în memoria cache.
• Divizarea memoriei cache în seturi.
• Un bloc poate fi plasat oriunde în setul corespunzător.
• Cazuri speciale: translatare directă (k=1), translatare complet asociativă (b=1).

Translatarea cu Seturi Asociative (2)

• În practică, se folosesc valori mici pentru numărul de blocuri pe set (k).
• Memoriile cache cu seturi asociative: suportă memorarea mai multor blocuri pe set cu același index.
• Această structură asigură o eficiență mai mare decât memoria cache directă.

Translatarea cu Seturi Asociative (3)

• Exemplu de calcul al adreselor, număr de seturi/cale, index, marcaj și calculul numărului de cuvinte din memoria de date.

Translatarea cu Seturi Asociative (4)

• Diagrama bloc a translatării cu seturi asociative, demonstrând procesul de acces, inclusiv comparație, selecția datelor și multiple căi de asociere, similare cu memoria cache directă.

Translatarea cu Seturi Asociative (5)

• Descriere a designului unei memorii cache cu seturi asociative: procesor, magistrala de adrese, magistrala de date, dimensiune memorie cache, dimensiunea setului și tipul de set asociativ.

Translatarea cu Seturi Asociative (6)

• Calcule pentru adresare, numărul de seturi, selectarea seturilor, marcaj, cuvinte de date (exemplu concret).

Translatarea cu Seturi Asociative (7)

• Diagrama bloc similară cu celelalte, dar specifică translatării cu seturi asociative.

Strategii de Înlocuire (1)

• Înlocuire aleatorie: un bloc este ales aleator pentru înlocuire; implementare simplă, dar blocurile cele mai utilizate au aceeași șansă de eliminare cu blocurile mai puțin utilizate.

Strategii de Înlocuire (2)

• LFU (Least Frequently Used): se folosește un contor pentru numărul total de utilizări ale fiecărui bloc; avantaj: blocurile utilizate frecvent au o șansă mai mare să rămână în cache. Dezavantaj: calcule suplimentare la inițializare/referire.

Strategii de Înlocuire (3)

• LRU (Least Recently Used): Se păstrează evidența blocurilor accesate recent pentru a identifica blocul cel mai puțin accesat.
• Are cea mai bună performanță și cost ridicat comparativ cu celelalte metode.

Strategii de Înlocuire (4)

• Pseudo-LRU: aproximare a strategiei LRU; un număr de biți pentru fiecare cale a seturilor din cache sunt utilizați pentru evidențierea blocurilor cel mai puțin utilizate recent.

Strategii de Înlocuire (5)

• Exemplu de memorie cache cu 4 seturi asociative cu 2 căi, bloc de memorie format din mai multe cuvinte.

Rezumat (1)

• Descriere generală a memoriei asociative (determinarea rapidă a unui cuvânt, logică suplimentară pentru comparație, metode de organizare fixă sau variabilă, instrucțiuni primitive executabile în paralel, avantaje pentru anumite sarcini).

Rezumat (2)

• Memoria cache: memorie rapidă, salvează instrucțiuni și date; reduce accesele la memoria principală; este compusă din memorii de date și marcaje.
• Strategie de scriere: write-back, write-through.
• Translatarea asociativă a adreselor: flexibilitate maximă, dar necesită memorie asociativă.

Rezumat (3)

• Caracteristici ale translatării directe și translatării cu seturi asociative.
• Strategii de înlocuire: aleatorie, LFU, LRU, Pseudo-LRU.

Acesta este un quiz despre sistemele de memorie, cu un accent special pe memoria asociativă. Vei explora ierarhiile memoriilor, tipurile de memorii, precum și caracteristicile și utilizările memoriei asociative. Testează-ți cunoștințele despre cum funcționează diferitele tipuri de memorii în contextul informaticii.