Universitatea “Politehnica” TimisoaraFacultatea de Automatica si Calculatoare

MEMORII SEMICONDUCTOAREMemorii Set Associative Cache

~Referat~

Titular curs:Prof. Mircea Stratulat

Student:Mihalache Anca

Sectie, an si grupa: CTI, III, 2.1

24 Mai 2011

Cuprins

Pag.3 Scurta introducere: Memorii CachePrincipii de functionareModul de adresare

Pag.4 Memorii cache set-associative

Pag.6 Scurta comparatie intre maparea asociativa si maparea set-asociativa.

Pag.9 Bibliografie

Memorii Cache

1. Principii de functionare 2. Modul de adresare

Adresare directa Adresare complet asociativa Adresare set-asociativa

Un cache este o memorie intermediara, situata intre o unitate de prelucrare si o memorie mai lenta. Cache se gaseste de exemplu intre internet si HDD al calculatorului, intre CPU si RAM. Suportul fizic al memoriei cache este alcatuit din memoria RAM statica si controlerul de cache. Exista 2 nivele de cache: L1, in procesor, cache intern, aflat in acelasi chip cu CPU si L2, cache la care controlerul este integrat in CPU, iar memoria este plasata afara.

Principii de functionare

1. Localizari spatiale: Daca o celula de memorie a fost accesata, este foarte probabil sa fie accesate si celulele adiacente.

2. Localizarii temporale: Daca o celula de memorie a fost accesata, este foarte probabil sa fie accesata din nou. (principiu mai eficient)

Modul de adresare

Prin adresare se intelege modul in care se localizeaza o informatie. Modalitati de adresare:

1. RAM – informatia se localizeaza pe baza unei adrese unice;2. Stiva;3. Dispozitiv de memorare secvential (banda magnetica, CD-ROM);4. Dispozitive de memorare aleator secventiale (HDD). La memoriile cache

accesul este asociativ (mem. adresata prin continut). Mai concret: o parte a continutului serveste ca eticheta, iar restul este privit ca informatie utila.

Cache cu adresare directa: Un bloc de octeti din memoria principala se va regasi intotdeauna in aceeasi locatie din cache in functie de adresa sa. Daca in cache exista k blocuri, orice bloc i din memoria principala se va regasi in blocul j din cache, astfel incat j= i mod k. Eticheta asociata blocului va fi i/k.

Dezavantaj: Multe blocuri din RAM concureaza pentru aceeasi intrare din cache si se pot elimina reciproc.

Cache cu adresare complet asociativa: Nu mai exista notiunea de index. Eticheta este adresa de RAM in intregime. Toate intrarile din cache sunt liber alocabile si sunt vazute in paralel. Si localizarea si confirmarea se fac in aceeasi faza. Un bloc din RAM se poate plasa oriunde in cache.

Dezavantaj: Structura de control este deosebit de complexa.

Cache cu adresare set-asociativa: Cache-ul se imparte intr-un numar de cai paralele. Pentru fiecare cale exista un comparator. Cautarea se face pe baza de index, in paralel pe toate caile.

Memorii cache set-associative

Putem sa ne imaginam un cache set-associative(in romana-> partial-asociativ) ca o colectie de mai multe cache-uri directe care lucreaza in paralel. Fie K numarul de astfel de cache-uri directe. Cache-ul se mai numeste si “associative on K ways” adica: asociativ pe K directii.

Ideea este simpla: atunci cand caut o adresa folosesc adresare directa in toate cele K cache-uri directe simultan. Daca blocul se gaseste intr-unul am rezolvat problema. Daca nu, aleg unul dintre ele pentru inlocuire. Numele este de “partial asociativ”, pentru ca plasamentul in cele K blocuri posibile este oricare, ca la un cache asociativ.

Inainte de toate sa vedem din ce este alcatuit un slot. Acesta contine:-> V – bitul de validitate. Acesta indică validitatea datei păstrată in slot. Daca V=1 atunci data

este validă, iar daca V=0 atunci data este invalidă. Inițial aceasta este invalidă. În momentul în care a fost plasata o dată în slot, aceasta devine validă.

-> D – dirty bit. Importanta acestui bit releva abia când bitul de validitate este 1 (V=1). Acesta indică faptul ca data din slot a fost modificată sau nu. Atunci cand D=1 inseamna ca data este modificată din momentul in care a fost introdusa în cache. Daca D=0, data este la fel cum a fost scrisă prima dată în cache.

-> Tag-ul – sau eticheta - reprezintă biții cei mai semnificativi ai adresei. Lungimea Tag-ului este 32 – lgN, iar N este numărul biților din partea de date a slot-ului.

-> Cache Line – Linia de date respectiva. Are N bytes, unde N este o putere a lui 2. Acesta se mai numește și bloc de date.

Asadar vom avea:

O schema set-associative reprezinta un hibrid intre o memorie cache adresata in mod direct si una adresata full-associative. Este considerata drept un compromis rezonabil intre hardware-ul complex necesar cache-urilor full-associative (necesitand cautari paralele de slot-uri) si hardware-ul simplistic al schemei cache-ului adresat direct ceea ce ar putea sa produca coliziuni intre adrese catre acelasi slot(similar coliziunilor de pe o tabla de sah).

Sa presupunem ca avem 128 de slot-uri a cate 32 de octeti. Mai mult, putem sa grupam aceste slot-uri in seturi. In particular, com presupune de asemenea si ca intr-un set incap exact 8 slot-uri.

Vom trata aceste slot-uri ca pe un vector, numarandu-le de la 0000000 la 1111111(adica 128 de slot-uri). Totusi, grupam slot-urile in seturi iar ideea principala este de a tine evidenta seturilor si nu a slot-urilor. Vom avea prin urmare 16 seturi (128/8). Este necesar sa specificam numarul de seturi in locul numarului de slot-uri si asta ne ocupa (lg 16) adica 4 biti.

Iata cum vom imparti pe biti adresele. Vom utiliza cei 4 biti pentru set si nu pentru slot.

A4-0 -> Offset.A8-5 -> Numarul de seturi.

A31-9 -> Tag.

Gasirea slot-ului.Gasirea unui slot reprezinta un proces mult mai complex. Sa presupunem ca

dispunem de adresa B31-0.

Vom utiliza bitii B8-5 pentru a gasi setul din care face parte slot-ul pe care il cautam. Acest numar ar trebui sa specifice un grup de 8 slot-uri(am mentionat deja ca fiecare set contine 8 slot-uri). Fiecare slot ar avea urmatorul index:

B8-5: 000B8-5: 001B8-5: 010B8-5: 011B8-5: 100B8-5: 101B8-5: 110B8-5: 111

In esenta, numarul de set specifica index-ul prin intermediul celui mai semnificativ bit si valori secventiale ale slot-urilor reprezentate prin intermediul ultimilor 3 biti. Se cauta in toate cele 8 slot-uri pentru a se vedea daca tag-ul A31-9 se potriveste cu tag-ul din slot. Daca da, se trece byte-ul la offset-ul B4-0. Daca nu, se decide care dintre slot-uri ar trebui folosit, se aduc cei 32 bytes din memorie, slot-ul schimband valoarea bitului de validare, a bitului dirty si a tag-ului dupa cum este nevoie.

Aceasta se numeste memorie cache asociativa pe 8 directii din moment ce fiecare set contine cate 8 slot-uri. Pot exista memorii cache asociative pe N-directii unde fiecare set contine cate N slot-uri, iar N reprezinta o putere a lui 2.

Compromisuri

Aceasta schema reprezinta un asa-zis compromis. Tot ceea ce trebuie sa faci este sa aplici o comparatie complexa de hardware(pentru gasirea slot-ului corect) pe un set mic de slot-uri in locul intregului numar de slot-uri. Fara indoiala, o asemenea comparatie de hardware este mai mult decat liniara daca ne referim la numarul de slot-uri prin urmare, cu cat mai putine sunt slot-urile intre care trebuie sa efectuezi cautarea, cu atat mai simplu este si circuitul hardware de care ai nevoie. Totusi, este mult mai flexibila posibilitatea de a asocia unui slot pana la N linii de cache pentru o schema a unei memorii cache asociativa pe N directii.

Ex: Memorie cache asociativa pe 2 directii:

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ă.

Si totusi.... nu putem obtine o imagine extrem de clara in ceea ce priveste maparea set-asociativa daca nu stim cu exactitate ce inseamna maparea asociativa.Prin urmare propun mai jos o schema explicita asupra acestor doua tipuri de mapare.

Maparea asociativa:

Î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 de- termina 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 blocu- rilor 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.

Memorie cache cu mapare asociativă.

Maparea set-asociativaÎn acest caz, memoria cache este împărţită în I seturi, şi fiecare din acestea conţine J linii.

Avem:L = I*JK = A mod I

unde K = numărul setului. Cu această metodă, blocul conţinând adresa A poate fi mapat în oricare din liniile setului I. Va prezentam o mapare asociativă pe seturi cu două linii pe set. 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ă.

Observatii:

->dimensiunea blocului in memoria cache este aleasa in raport cu proprietatea de localizare a programelor.

->memoria cache este adresata cu adrese fizice si nu cu adrese virtuale (se elimina procesul de translatare a adresei virtuale in adresa fizica).

->algoritmii de reamplasare a blocurilor din memoria cache determina performanta memoriei cache, exprimata ca rata de pierderi (numar de incercari esuate de a gasi informatia dorita in cache).

Bibliografie

http://www.cs.umd.edu/http://www.wikipedia.org/http://www.scribd.ro/->diverse lucrari de laborator si de curs ale cadrelor didactice de profil de la Universitatea

“Politehnica”, Timisoara si Universitatea “Babes-Bolyai”, Cluj.