pcspim cache

8/8/2019 Pcspim Cache

1/19

Computer Science and Automation ControlAdrian FLOREA

1

SIMULATORUL PCSPIM-CACHE

1.1. SCOPUL LUCRRII

Memoriile cache reprezint un mecanism omniprezent n microprocesoarele curente, dedicatmascrii latenei ridicate a memoriei principale. Datorit importanei lor, acestea sunt considerateelemente cheie (fundamentale) n programa specific arhitecturii calculatoarelor. n acest sens, lucrareade fa urmrete evidenierea conceptelor legate de cache-uri modul de organizare, regulile de mapare,algoritmii de nlocuire a blocurilor conflictuale, strategia de scriere din prisma unor aplicatii scrise inlimbaj de asamblare MIPS. Lucrarea continu cu descrierea detaliat a simulatorului PCspim-cache,instrument software care permite vizualizarea grafica in fiecare ciclu de executie a impactului unoralgoritmi simpli atat asupra setului de registrii generali cat i asupra arhitecturii cache-ului [Pet06].Simulatorul, de tip execution-driven, a fost dezvoltat de colectivul de cercettori de la Departamentultiina i Ingineria Calculatoarelor din cadrul Universitii Politehnica din Valencia condus de profesorAna Pont i extinde simulatorul SPIMSal scris pentru uz didactic de ctreJames Larus [Lar93] i care a

fost prezentat detaliat n lucrarea [Flo03]. n finalul lucrrii sunt explicate dou aplicaii de complexitatemedie i propuse alte dou probleme pentru rezolvare avnd ca scop nelegerea aspectelor arhitecturalespecifice procesoarelor RISC, formarea deprinderilor practice privind programarea n asamblare MIPSdar i vizualizarea efectului optimizrilor software de tip loop interchange asupra reducerii ratei de miss

n cache-uri.

1.2. MEMENTO TEORETIC

n acest subcapitol vor fi trecute n revist doar cteva aspecte privitoare la memoriile cache

(definiie, arhitectur, metrici, strategii de scriere i metode de mbuntire a performanei acestora),ntruct exist suficient documentaie care trateaz n detaliu acest subiect [Hill88, Jou90, Sti94, Hen07],inclusiv autorii acestei cri avnd astfel de contribuii [Flo00, Vin00, Flo03]. Practic se vor prezentaacele noiuni care intervin apoi n procesul de simulare a interfeei microprocesor - cache.

Conform dicionarului american Websters New World Dictionary of the American Languagecache-ul reprezint a safe place for hiding or storing things. Sintetic, despre memoria cache se poatespune ca este:

situat din punct de vedere logic ntre CPU i memoria principal (uzual DRAM) mai mic, mai rapidi mai scump (per byte de tip SRAM) dect aceasta gestionat prin hardware astfel nct s existe o ct mai mare probabilitate statistic de gsire a

datei accesate de ctre CPU, n cache.In evaluarea performantei memoriilor cache si a ntregului sistem de calcul sunt folosite urmtoarele

metrici: Rata de Hit = raportul statistic ntre numrul acceselor cu hit (gsesc informaia cutata) n cache

respectiv numrul total al acceselor CPU la memorie.Rata de miss =1 Rata de Hit

Timpul mediu de acces al CPU la sistemul ierarhic de memorie (MP)= T_acces_cache*R_hit + T_acces_DRAM*(1-R_hit)

Rata de procesare (viteza de execuie) = Nr. Instruciuni executate / Timp total execuie


2/19


2

Din punct de vedere arhitectural, exist 3 tipuri distincte de memorii cache n conformitate cu

gradul de asociativitate:1. cache-urile cu mapare direct un bloc din memoria principala (MP) poate fi gsit n cache

(hit) ntr-un bloc unic determinat. Regula de mapare a unui bloc in MP n cache (daca bloculcontine un singur cuvant de date 1 byte) este:

(Adresa bloc MP) modulo (Nr. blocuri din cache)%

Daca insa dimensiunea blocului din cache este mai mare de 1 byte atunci indexul blocului din cachese determina dupa regula:

(Adresa bloc MP /Dimensiunea_blocului in bytes) % Nr. blocuri din cache)

Stricteea regulii de mapare constituie atat un avantaj intrucat conduce la o simplitate constructiva acestor memorii, o implementare hardware usoara (accesul la cache se face folosind ultimii biti deadresa) dar constituie totodata i un dezavantaj datorita fenomenului de interferen al blocurilor din MP

n cache.

2.la cache-urile N-way asociative (semiasociative) exist mai multe seturi, fiecare set avnd Nblocuri componente. Blocul dorit se poate mapa oriunde n setul respectiv (asociativitatemaxima in set). Regula de mapare precizeaz strict doar setuln care se poate afla blocul dorit:

(Adresa bloc MP) modulo (Nr. seturi din cache)Daca insa dimensiunea blocului din cache este mai mare de 1 byte atunci indexul blocului din cache

se determina dupa regula:

(Adresa bloc MP/Dimensiunea_blocului in bytes) modulo (Nr. seturi din cache)

La un miss n cache, nainte de ncrcarea noului bloc din MP, memoriile asociative implicaevacuarea unui anumit bloc din setul respectiv. n principiu exist implementate dou-trei tipuri dealgoritmi de evacuare: FIFO (primul bloc introdus in set este primul bloc care va fi evacuat la un miss incache), PseudoRandom (cvasialeator) i LRU (Least Recently Used). Algoritmul LRU evacueaz

blocul din cache cel mai demult neaccesat, n baza principiului de localitate temporal (aflat oarecum ncontradicie cu o probabilistic markovian care ar sugera s fie pstrat!).

Politica de nlocuire LRU este departe de a fi cea optim pentru unele din programe. Aceastanomalie poate fi evitat prin folosirea algoritmului optim (OPT) n loc de LRU ca baz pentruclasificarea miss-urilor n cache. Algoritmul OPT, nlocuiete ntotdeauna blocul care va fi adresat celmai trziu n viitor (eventual nu va mai fi adresat deloc). Un astfel de algoritm s-a dovedit a fi cvasi-optimal pentru toate pattern-urile de program, ratele de miss fiind cele mai mici n acest caz, dintre maitoate politicile de nlocuire folosite. Politica se dovedete optim doar pentru fluxuri de instruciuni read-only. Pentru cache-urile cu modalitate de scriere write-backalgoritmul de nlocuire nu este ntotdeaunaoptim (spre exemplu poate fi mai costisitor s se nlocuiasc blocul cel mai trziu referit n viitor dacblocul trebuie scris i n memoria principal, fiind "murdar", fa de un bloc "curat" referit n viitor puinmai devreme dect blocul "murdar" anterior; n plus, blocul curat nu mai trebuie evacuat, ci doar supra-scris). Este evident un algoritm speculativ, practic imposibil de implementat n practic. Totui el aredou caliti majore: (1) reprezint o metric de evaluare teoretic a eficenei algoritmului de evacuareimplementat n realitate, absolut necesar i (2) induce ideea fecund a predictibilitii valorilor defolosin ale blocurilor din cache, conducnd astfel la algoritmi predictivi rafinai de evacuare (memoriaSVC implementeaz un astfel de algoritm).

Intr-un astfel de cache rata de interferen se reduce odat cu creterea gradului de asociativitate (Nmare), determinnd mbuntirea ratei de hit i deci a performanei globale (vezi paragraful de mai susreferitor la metrici). Pe de alt parte ns, asociativitatea impune cutarea dup coninut (se caut deci


3/19


3

ntr-un set dac exist memorat blocul respectiv) ceea ce conduce la complicaii structurale i deci lacreterea timpului de acces la cache i implicit la diminuarea performanei globale. Optimizarea graduluide asociativitate, a capacitii cache, a lungimii blocului din cache etc., nu se poate face dect prinlaborioase simulri software, variind toi aceti parametrii n vederea maximizrii ratei globale deprocesare a instruciunilor [instr./cicli].

3.cache-urile complet asociative exist un singur set permind maparea blocului practicoriunde n cache.Memoriile cache total asociative, implementeaz practic un singur set permind maparea blocului

practic oriunde n cache. Ele nu se implementeaz deocamdat n siliciu datorit complexitii deosebitei a timpului prohibit de cutare. Reduc ns (practic) total interferenele blocurilor la aceeai locaiecache i constituie o metric superioar util n evaluarea ratei de hit pentru celelalte tipuri de cache-uri(prin comparaie).

Folosind CACTI4.0 (instrument software de evaluare al unui model arhitectural de cache din punct devedere al timpului de acces, perioadei de tact, al modului de organizare i al ariei de integrare,precum i al puterii consumate)cu o tehnologie de integrare de 90 nm, timpul de acces la un cache 2-way, 4-way, i 8-way asociativ este de 1.32, 1.39 i 1.43 mai mare dect timpul de acces la un cache

mapat direct de aceeai capacitate.

Memorii Harvard spaii i busuri separate pentru instruciuni i date vs. Memorii Princeton(unificate). Avantaje Harvard (se reduc coliziunile n procesoarele pipeline IF/MEM). DezavantajeHarvard (rata de hit mai mic). De regula cache-urile de nivel 1 (L1) sunt implementate on chip separatpe instruciuni i date respectiv unificat, offchip, cache-urile de nivel 2 sau chiar 3 (L2; L3).

Strategii de scriere

write back (informaia este scris numai n cache, blocul modificat fiind transferat n MP numaila evacuarea din cache). Bit Dirty marcheaza modificarea => minimizeaz evacurile de blocuri

n MP.

write through (informaia este scris de ctre procesor att n blocul aferent din cache ct i nblocul corespunztor din memoria principal). Util pentru pastrarea coerenei cache-urilor cuprecdere n sistemele multimicroprocesor, Chip Multiprocessor Architecture.

In general existdoua opiuni la o scriere cu miss:Write Allocate - the block is loaded on a write miss, followed by the write-hit action.

No Write Allocate - the block is modified in the main memory and not loaded into the cache.

ntruct ambele opiuni pot fi asociate cu strategia de scriere implementata (write back / write through),rezulta 4 scenarii posibile.Write Through with Write Allocate:

on hits it writes to cache and main memory

on misses it updates the block in main memory and brings the block to the cacheBringing the block to cache on a miss does not make a lot of sense in this combination becausethe next hit to this block will generate a write to main memory anyway (according to Write Throughpolicy)

Write Through with No Write Allocate:on hits it writes to cache and main memory;on misses it updates the block in main memory not bringing that block to the cache;


4/19


4

Subsequent writes to the block will update main memory because Write Through policy is employed.So, some time is saved not bringing the block in the cache on a miss because it appears uselessanyway.

Write Back with Write Allocate:on hits it writes to cache setting dirty bit for the block, main memory is not updated;on misses it updates the block in main memory and brings the block to the cache;Subsequent writes to the same block, if the block originally caused a miss, will hit in the cache

next time, setting dirty bit for the block. That will eliminate extra memory accesses and result invery efficient execution compared with Write Through with Write Allocate combination.

Write Back with No Write Allocate:on hits it writes to cache setting dirty bit for the block, main memory is not updated;on misses it updates the block in main memory not bringing that block to the cache;Subsequent writes to the same block, if the block originally caused a miss, will generate misses

all the way and result in very inefficient execution.

La o scriere cu miss n cache se poate face scrierea n cache (alocarea blocului write allocate) saurealizarea scrierii direct n memorie (nealocnd bloc n cache write no-allocate). n general, dar nu esteobligatoriu:

write allocate este asociat cu strategia de scriere n cache write-back. write no-allocate este asociat cu strategia de scriere n cache write-through.

3C caracterizarea acceselor cu miss Compulsory - sau de start rece. Apar la primul acces al unui anumit bloc n cache. De capacitate - apar n situaia n care cache-ul nu poate reine toate blocurile necesare iar cele

care sunt evacuate la un moment dat vor fi necesare ulterior. Cache-ul este plin. Deconflict - sau de interferen. Apar dac strategia de plasare a blocurilor n cache este mapat

direct sau semi-asociativ, situaie n care mai multe blocuri din memoria principal pot interfera(accesa) acelai bloc din cache. Setul este plin dar cache-ul nu.

Metode de mbun

t

ire a performanei cache-urilor:

1. Reducerea ratei de miss n cache Creterea dimensiunii blocurilor (din pcate cresc i penalitile de miss la evacuare-

ncrcare bloc) Creterea capacitii cache (crete timpul de acces la hit i costuri) Creterea gradului de asociativitate a cache-ului (crete timpul de acces la hit) Utilizarea mecanismelor de prefetch asupra instruciunilor (buffer de prefetch) i datelor

(data write buffer) Optimizarea de programe prin compilator

- intrarea ntr-un basic-blocks reprezinte nceputul unui bloc n cache- exploatarea localitilor spaiale ale datelor din cache loop interchange, loop fusion,

merging array etc.

2. Reducerea penalitii n caz de miss n cache Niveluri multiple de cache-uri (multi-level inclusion, exclusion, hibrid); Utilizarea conceptului de victim cache respectiv selective victim cache (a se vedea capitolul 5

din lucrarea [Flo03])

3. Reducerea timpului de execuie n caz de hit n cache. Way prediction, Trace caches.


5/19


5

Alte consideraii privind performana cache-urilor de instruciuni

Cercettorii au artat ca performanta cache-urilor de instruciuni poate varia in funcie de tipulaplicaiilor: procedurale sau obiectuale. Din punct de vedere dinamic, func iile din limbajul C execut deaproximativ trei ori mai multe instruciuni dect funciile i metodele din limbajul C++. Dimensiuneafunciilor reprezint un factor important att n optimizri precum macroexpandarea, fiind directproporional cu spaiul de overhead al fiecrei funcii - destinat salvrii regitrilor (scrieri / citiri

repetate din stiv), transmiterii parametrilor, pstrrii rezultatului, precum i n performana cache-ului deinstruciuni. Caracteristica programelor obiectuale de a realiza multe apeluri de funcii scurte (reduse canumr de instruciuni) constituie unul din principalele motive pentru care acest tip de programe nubeneficiaz de avantajele localitii spaiale oferite de blocurile mari de cache. n cercetrile sale,Calder afirm c programele obiectuale necesit un cache de instruciuni de dou mai mare pentru aobine rate de miss egale cu programele procedurale [Cal94].

Pornind de la limitrile tehnicilor de optimizare tradiionale bazate pe "eliminarea / adugarea" unorinstruciuni, doi cercettori angajai ai firmei Hewlett-Packard, Pettis i Hansen, au propus o tehnic noude optimizare global "procedure splitting", n vederea reducerii ratei de miss la cache-ul de instruc iunii mbuntirea performanei arhitecturilor de calcul. Avnd la baz informaii de profil culese n urmaexecuiei anterioare a programelor, procedure splitting urmrete partajarea n zone fizice de memoriedistincte a basic-block-urilor executate mai frecvent (codul util) i separat basic-block-urile executate

foarte rar sau deloc. Prin aceast separare se creeaz noi proceduri, mai scurte i mai dense (executate nntregime mult mai des) i care pot fi stocate mpreun ntr-un numr mai mic de pagini de memorie dectiniial, cnd codul util era dispersat. Basic-block-urile foarte rar executate sunt mutate la sfr itulprocedurii, pagina care le cuprinde nefiind necesar a fi ncrcat n memorie dect foarte rar. Deasemenea, n urma aplicrii acestei tehnici, la implementarea mecanismului de memorie virtual,dimensiunea paginii de memorie poate fi aleas mai mic, de capacitate optim ns, astfel nct scompenseze timpul mare de acces la disc. Procedure splitting a fost implementat cu succes n cadruloptimizatorului de cod realizat pentru procesorul PA-RISC al companiei Hewlett-Packard [Pett90].

1.3. DESFURAREA LUCRRII

1.3.1. GHID DE UTILIZARE AL SIMULATORULUI

Simulatorul PCspim-cache a fost prezentat la workshopul internaional dedicat educaiei inarhitectura calculatoarelor (WCAE) realizat in conjuncie cu cea mai prestigioasa conferina din domeniu(ISCA) inute in anul 2006 la Boston, SUA [WCAE06]. PCspim-cache reprezint un simulator puternicparametrizabil care permite vizualizarea grafica in fiecare ciclu de execuie a impactului unor algoritmisimpli att asupra setului de registrii generali cat si asupra arhitecturii cache-ului. De exemplu, se poatedetermina rata de hit in cache-urile de instruciuni si date (I/D) variind dimensiunea blocului, gradul deasociativitate, algoritmii de nlocuire a blocurilor conflictuale sau strategia de scriere. Codul simulatorului

(sursa i executabil) poate fi descrcat n mod gratuit de la adresa:http://www.disca.upv.es/spetit/spim.htm. Avnd n vedere caracterul didactic al lucrrii, pentru ovizualizare adecvat i pentru o mai bun nelegere a modului de lucru a interfeei microprocesor cache, s-a optat pentru un cache cu o organizare mai simpl, pe un singur nivel, integrat n procesorulIntel Pentium II.

Dupa lansarea in executie a aplicatiei spim-cache_080605.exe pe ecranul sistemului va apareameniul simulatorului (File / Simulator / Window / Help / CacheSimulation), o fereastra principala cu 6subferestre (frame-uri) asezate in maniera Tile ( Registers / Instruction Main Memory / Data Main


6/19


7/19


7

DATA se afieaza coninutul memoriei de date. In frame-ul TEXT se afieaza coninutul memoriei deinstructiuni. In subfereastra Registru sunt ilustrate valorile registrilor microprocesorului.

Spre deosebire de simulatorul SpimSAL la care fereastra Console era de dimensiune fix, in cadrulsimulatorului PCspim-cache fereastra de recepionare a ieirilor programului i care asigur intrareapentru programe, poate fi minimizat, ascuns, maximizat, redimensionat sau derulat. Programeleinteracioneaz cu fereastra Console prin apeluri sistem.

Figura 1.1. PCspim-cache: Interfaa cu utilizatorul

Pentru a starta o simulare cu studiul cache-ului incorporat utilizatorul trebuie sa selecteze mai intaioptiunea din fereastra care apare dupa un simplu click pe optiunea cuacelasi nume din meniul . Trebuie specificat ca, in situatia in care nu se opteaza pentrusimularea cache-urilor (I/D) atunci functionarea simulatorului PCspim-cache este identica cu cea a maivechiului SpimSAL implementat de catre James Larus [Lar93]. In acest caz toate instructiunile si datelese scriu / citesc in / din memoria principala (cu zonele Text,Data si Stack).


8/19


8

Figura 1.2. PCspim-cache: simulare cu studiul cache-ului incorporat

Dupa cum se poate observa in figura 1.3, cu ajutorul optiunii din meniul utilizatorul poate alege sa simuleze doar cache-ul de date, sau doar cel deinstructiuni, sau ambele intr-o arhitectura Harvard (bus-uri si cache-uri separate pentru instructiuni sidate). Daca se opteaza doar pentru un anumit tip de cache (instructiuni sau date) atunci in fereastraprincipala a simulatorului nu vor apare informatii referitoare la structura cache-ului nedorit. Totusi, pentruo mai buna intelegere a modului de lucru a intefetei procesor cache in aplicatiile propuse se vaexemplifica pe o arhitectura Harvard de memorii cache, care reprezinta de fapt configuratia implicitaimplementata in simulatorul PCspim-cache.


9/19


9

Figura 1.3. PCspim-cache: Configurarea cache-ului simulatorului

Cu ajutorul optiunii din meniul utilizatorul poate stabiligeometria cache-ului anterior selectat prin (vezi figura 1.4). Pentru a puteaconfigura independent cele doua tipuri de memorii cache (instructiuni si date) se va selecta corespunzator

din controlul de tip combo box, din dreapta ferestrei de configurare . Principalii parametriaferenti cache-ului care pot fi setati prin intermediul interfetei sunt:

Capacitatea, care variaza intre 128 bytes si 1 Kbyte. Dimensiunea blocului (4, 8 sau 16 bytes). Gradul de asociativitate (mapat direct, 2-way, 4-way sau complet asociativ). Politica de scriere in cache (la hit sau miss) write through sau write back cu alocare de bloc

(write allocate) sau nealocare (write noallocate). Algoritmul de inlocuire a blocurilor conflictuale in caz de miss in cache-urile asociative (LRU

sau FIFO).


10/19


10

Figura 1.4. PCspim-cache: Stabilirea configuratiei cache-urilor

Intrucat cache-ul de instructiuni nu poate fi modificat de catre programele utilizator, politica descriere la hit sau miss este disponibila doar pentru cache-ul de date. Daca este selectata optiunea vor fi afisate statistici referitoare la numarul de accese cu miss, numarul total de accesecorespondent fiecarui tip de cache (I/D), daca exista. Ferestrele specifice memoriilor cache de instructiunisi date vor ilustra continutul acestora. Configuratia implicita o reprezinta arhitectura mapata direct si esteorganizata sub forma unei matrici. Fiecare rand in matrice constituie o linie din cache (in cazul cache-

urilor mapate direct o linie este echivalenta cu un singur bloc iar in cazul cache-urilor semiasociative olinie este echivalenta cu un numar de blocuri egal cu gradul de asociativitate). Prima coloana contineidentificatorul liniei (sau al setului), in timp ce celelalte coloane contin informatii de date respectiv decontrol. In cazul cache-ului de instructiuni informatia de date o constituie codificarea fiecarei instructiuniin parte (in hexazecimal). In cazul cache-ului de date, informatia de date o reprezinta data propriu-zisafolosita de programul sursa. Informatia de control aferenta fiecarei linii din cache o reprezinta bitul devalidare si campul de tag (in hexazecimal). Din scop pur didactic a fost adaugat campul careindica rezultatul accesului la cache (hit sau miss). Odata cu cresterea gradului de asociativitate layout-ulcache-ului se modifica. Numarul coloanelor utilizate in cazul cache-urilor mapate direct sunt multiplicatecu gradul de asociativitate specificat in momentul configurarii. Procedand astfel, fiecare rand din fereastrareprezinta un singur set (linia apartinatoare setului), iar prima coloana indica identificatorul setului. Invederea implementarii politicii de evacuare a fost adaugata coloana (LRU/FIFO), pentru fiecare grad deasociativitate, care contine valoarea contorului corespondent algoritmului de inlocuire. In plus, dacautilizatorul specifica politica de scriere write back, este adaugata coloana M pentru fiecare grad deasociativitate (bloc din set) in parte, pentru a arata daca blocul respectiv a fost modificat (este Dirty) si nureprezinta copia fidela a celui stocat in nivelul inferior de memorie. Pentru o mai buna afisare, in cazulunui cache complet asociativ nu se mai aplica politica de replicare a coloanelor corespunzatoare fiecaruibloc din set. In acest caz, fiecare linie corespunde unui bloc.

Pentru cei familiarizati anterior cu simulatorul SpimSAL [Lar93], se impune in continuareprecizarea unor detalii de simulare care il diferentiaza pe PCspim-cache de instrumentul propus de JamesLarus. Astfel: La versiunea anterioara de simulator de procesor MIPS (SPIMSal) un pas de executie ( single step)

presupunea executia intregii instructiuni (indiferent de cati ciclii ar presupune in realitate un loadsau

un branch). In versiunea actuala (PCspim-cache), daca este utilizata optiunea de memorii cache, instructiunileload / store sunt executate in mai mult de 1 ciclu. Executia unei instructiuni cu referire la memorieimplica 2 accese la cache: unul pentru extragerea instructiunii din ICache si unul pentru aducerea sauscrierea datei din / in DCache. In cazul unui Hit in cache-ul de date, executia instructiunii se face intr-un ciclu. In caz de Miss, numarul de pasi de executie difera in functie de strategia de scriere. Sedisting urmatoarele cazuri:o I Load cu miss 3 pasi I1. Detectia si marcarea ca miss a accesului I2. Aducereablocului din MP in DCache I3. Incarcarea informatiei (blocului din DCache) in registrul destinatie.

o II Store cu miss 2 sau 3 pasio IIa. Folosind strategia write no-allocate

IIa1. Detectia si marcarea ca miss a accesului Iia2. Stocheaza registrul sursa in memoria principala (nu mai aduce blocul si in cache).

Este eficient in cazul in care s-a optat pentru Write Trough.o IIb. Folosind strategia write allocate

IIb1. Detectia si marcarea ca miss a accesului IIib2. Extrage blocul din MP in DCache


11/19


11

IIib3. Scrie datele noi in cache (valoarea registrului sursa) si in paralel in memoriaprincipala (aduce blocul si in cache). Este eficient in cazul in care s-a optat pentru WriteBack.

o III Miss in ICache Load cu miss doar ca al 3-lea pas (I3) reprezinta executiainstructiunii (aducerea instructiunii din MP in registrul instructiunii)

1.4. PROBLEME DE LABORATOR PROPUSE SPRE REZOLVARE

1.4.1. EXECUTIA UNOR PROBLEME REZOLVATE FOLOSIND SIMULATORUL

PCSPIM-CACHE

In acest subcapitol sunt propuse doua aplicaii: prima (g_cache.s) are un caracter explicativ cu rolul de aevidenia eficienta memoriilor cache din prisma celor dou principii de localitate: temporali spaial.De asemenea, sunt ilustrate interferentele produse de accesul n aceeai zona a cache-ului de date dinpartea a doua tablouri (aflate evident la adrese diferite in memoria principala). A doua aplica ie se referla implementarea unei metode software de optimizare care sa determine creterea ratei de hit, i anumeinterschimbarea buclelor.

Problema 1.Se consider urmtorul programul de test g_cache.s care realizeaz suma a 8 elemente ntregi pe 4octei fiecare 1,1,1,1,2,2,2,2 stocate n memorie la adresa 0x10000480. Aceasta operaie esteintercalat cu citirea a cate unui element dintr-un al doilea tablou de 8 elemente 3,3,3,3,4,4,4,4 stocatla adresa 0x10000500. S se ruleze pas cu pas secvena de cod i s se vizualizeze dinamicmodificrile de stare ale memorie cache. Observai respectarea principiului de localitate temporala ncache-ul de instruciuni, respectiv a celui de localitate spaial n cache-ul de date. Realizai o statisticprivind impactul asupra ratei de hit n cache-uri a urmtorilor parametri: dimensiunea blocului de

date, gradul de asociativitate, algoritmul de nlocuire, strategia de scriere.Secventa C aferenta problemei 1

intj; long suma=0;long Array_A={1,1,1,1,2,2,2,2};long Array_B={3,3,3,3,4,4,4,4};int main(){

for (j=8; j>0; j--){suma+=Array_A[j];

/* instructiune ce presupune citirea elementului Array_B[j], poate fi chiar si o afisarecout


12/19


12

.data 0x10000500 # adresa de memorie a celui de-al doilea tablou (Array_B)

Array_B:.word 3,3,3,3,4,4,4,4

.text

.globl __start

__start:la $2, Array_A # incarcare in registrul $2 a adresei primului element al tabloului Array_Ala $3, Array_B # incarcare in registrul $3 a adresei primului element al tabloului Array_Bli $6, 0 # $6 sumali $4, 8 # $4 contorulj

loop:lw $5, 0($2) # se citete elementul curent din tabloul Array_Alw $7, 0($3) # se citete elementul curent din tabloul Array_Badd $6, $6, $5 # suma+= Array_A[j]add $2, $2, 4 # elementele tabloului Array_A sunt de tip word, pe 4 octetiadd $3, $3, 4 # elementele tabloului Array_B sunt de tip word, pe 4 octetiaddi $4, $4, -1 # decrementare contor: j--

bgt $4, $0, loop # test continuare bucla: j>0

li $v0, 10 # apel sisistem de incheiere program si cedare control catre sistemul desyscall # operare

La ncrcarea codului sursa in memoria simulatorului apar modificri in trei dintre ferestreleacestuia (vezi figura 1.5). Astfel, in fereastra registru, PC-ul se va actualiza cu valoarea 0x00400000,adresa de nceput a segmentului de cod specific ISA procesoarelor MIPS. De asemenea, registrul SP indicatorul de stiv, care pointeaz la primul cuvnt liber pe stiv, va lua valoarea 0x7FFFEFFC, adresaprimei zone libere din stiva. In fereastra de cod (TextSegment), apar instruciunile programului. Se disting4 coloane (de la stnga spre dreapta): adresa instruc iunilor, codificarea pe 4 octei a acestora, exprimareainstruciunilor in mnemonica asamblare MIPS aa cum se proceseaz si codificarea in mnemonica

pseudo-asamblare (aa cum a scris utilizatorul codul).


13/19


13

Figura 1.5. PCspim-cache: Ferestrele Registru, Text si Data dupa incarcarea unui program de test

De exemplu, prima instruciune din codul sursa la $2, Array_A, este in realitate o pseudo-instruciune, care se executa din doua instruciuni reale MIPS: lui $1, 4096 [Array_A] si ori$2, $1, 1152.Prima dintre cele doua instruciuni este stocata in memoria la adresa 0x00400000. Practic, registrul $1este folosit de ctre asamblorul MIPS pentru stocarea adreselor de baza in cazul instruc iunilor de

ncrcare a adreselor. Astfel, instruciunea lui $1, 4096 [Array_A] ncarc in partea superioara (high) aregistrului $1 valoarea 409610=0x1001 rezultnd valoarea 0x10010000 adresa de nceput a segmentuluide date dinamice. A doua instruciune finalizeaz operaia propusa prin pseudo-instruciunea la $2,

Array_A, si anume, adaug deplasamentul 115210=0x0480 (pe 16 biti) la registrul $1, printr-o operaie deSAU logic cu ultimii (mai puin semnificativi) 16 bii ai acestuia, depunnd rezultatul in registruldestinaie $2 (ori$2, $1, 1152 [Array_A]), obinndu-se in acest fel adresa primului element al tablouluiArray_A.

In fereastra Data, vor fi stocate pe cate 4 octei (datorita directivei de asamblare .word) elementelecelor doua tablouri ncepnd cu adresele 0x10000480 respectiv 0x10000500.

nainte de a prezenta detalii privind execuia pas cu pas a programului se considera o arhitecturaHarvard implicita, cu urmtoarele caracteristici: cache-uri de instruciuni si date mapate direct, de 128bytes fiecare, cu blocuri de 4 bytes. Astfel, rezulta 32 de seturi (intrri/linii) in cache. innd cont de

regula de mapare a unui bloc din memoria principala in cache (vezi capitolul 2) si tiind parametrii cache-urilor si adresa primei instruciuni din memoria principala care este 0x400000 se poate trece la calcululTagului emis prin adresa si a indexului de bloc din cache. Evident ca primul acces la cache va fi cu miss(de start rece), biii de validare afereni fiecrui bloc din cache fiind resetai (vezi in figura 1.6 la cache-ulde instruciuni pentru toate blocurile exceptndu-l pe primul, cel de Set=0).


14/19


14

Figura 1.6. PCspim-cache: Modificri in cache-ul de instruciuni la execuia programului

Astfel,Index_bloc_in cache = (Adresa bloc MP / Dimensiunea_blocului in bytes) % Nr. blocuri din cache =>Index_bloc_in cache = (0x400000 / 4) % 0x20 = 0x100000 % 0x20 = 0.

De asemenea,Tag_Emis = (Adresa bloc MP / Dimensiunea_blocului in bytes) / Nr. blocuri din cache sauTag_Emis = (Adresa bloc MP / Dimensiunea cache-ului =>Tag_Emis = (0x400000 / 4) / 0x20 = 0x8000.

Primul acces la indexul 0 (setul 0) emis prin adresa, va determina miss in campulAcc, dupa care

bitul de validare (V) va fi setat pe 1, marcand blocul valid in cache. Tagul din cache este inlocuit cu Tagulblocului reprezentat de prima instructiune din program (0x8000). Urmeaza apoi aducerea instructiunii incampul cu informatii de date a cache-ului de instructiuni (0x3c011000 codificarea instructiunii lui $1,4096). Odata adusa instructiunea in cache, ea este excutata intr-un singur pas, practic rezultatul operatieise va regasi in registrul destinatie. Astfel, in registrul $1 se va incarca valoarea 0x1000000.

In acelasi fel se procedeaza pentru aducerea si executia urmatoarelor instructiuni. Diferenta estedata de faptul ca acestea vor fi inscrise in cache la alte adrese (indexi) si continutul va fi dat deinstructiunile respective. Spre exemplu, instructiunea urmatoare este stocata in memorie la adresa0x400004. Astfel, indexul si tagul vor fi cele de mai jos iar continutul este: ori $2, $1, 1152.

Index_bloc_in cache = (Adresa bloc MP / Dimensiunea_blocului in bytes) % Nr. blocuri din cache =>Index_bloc_in cache = (0x400004 / 4) %0x20 = 0x10001 % 0x20 = 1.

De asemenea,Tag_Emis = (Adresa bloc MP / Dimensiunea_blocului in bytes) / Nr. blocuri din cache sauTag_Emis = (Adresa bloc MP / Dimensiunea cache-ului =>Tag_Emis = (0x400004 / 4) / 0x20 = 0x8000.Continuand in acest mod, cele 14 instructiuni reale ale codului sursa sunt aduse in cache-ul de

instructiuni la adrese distincte. La aducerea instructiunii cu referire la memorie lw $5, 0($2), dupa tratareaaccesului la cache-ul de instructiuni (cu miss la prima executie a acesteia) se va accesa si cache-ul dedate. Valoarea adresei specificata prin registrul $2 (0x10000480) va determina tagul si indexul din cache-ul de date, dupa aceeasi regula de mapare, avand in vedere setarile stabilite initial. Astfel, indexul si tagul


15/19


15

vor fi cele de mai jos iar continutul este 1 (primul element al tabloului Array_A, stocat pe 4 octeti) vezifigura 1.7.

Index_bloc_in cache = (Adresa bloc MP / Dimensiunea_blocului in bytes) % Nr. blocuri din cache =>Index_bloc_in cache = (0x10000480 / 4) % 0x20 = 0x4000120 % 0x20 = 0.

De asemenea,Tag_Emis = (Adresa bloc MP / Dimensiunea_blocului in bytes) / Nr. blocuri din cache sauTag_Emis = (Adresa bloc MP / Dimensiunea cache-ului =>

Tag_Emis = (0x10000480 / 4) / 0x20 = 0x200009Toate aceste accese cu miss au fost de tip compulsory intrucat au reprezentat primele accese lacache (atat pentru instructiuni cat si pentru date). Urmeaz execuia celei de-a doua instruciuni cu referirela memorie lw $7, 0($3). Se va accesa cache-ul de date cu adresa specificata prin registrul $3(0x10000500) obinndu-se tagul (0x20000A) si indexul (0). Din cate se observa, accesul este cu miss,insa de conflict de aceasta data deoarece la indexul 0 in cache se gsete alt tag dect cel emis, si anume0x200009. Coninutul locaiei 0 din cache se va modifica cu valoarea 3, (primul element al tablouluiArray_B, stocat pe acelai numr de octei, si anume 4).

Figura 1.7. PCspim-cache: Primul acces la cache-ul de date


16/19


16

A 15-a instruciune dinamica (al 15 acces la cache-ul de instructiuni) presupune reluarea primeiinstruciuni din bucla loop si anume: lw $5, 0($2), ceea ce conduce la aparitia primului acces cu hit lacache-ul de instruciuni. Continund execuia practic se vor obine accese cu hit la cache-ul de instruciunipana cnd se parcurg ambele tablouri. Ultimele doua instruciuni (apelul sistem de ncheiere a execuiei sicedare a controlului ctre sistemul de operare) sunt aduse abia la final dup repetarea instruciunilor dinbucla. Din punct de vedere statistic cache-ul de instruciuni este caracterizat de urmtoarele rezultate: 56accese cu hit dintr-un total de 72 accese. Practic sunt 4 pseudo-instruciuni in afara buclei (6 instruciuni

reale MIPS), 2 dup bucla, iar aceasta conine 7 pseudo-instruciuni care n realitate sunt 8 instruciunireale MIPS si care se reiau de 8 ori (6+8*8+2). Din cele 8 iteratii ale buclei doar prima va fi cu miss =>7*8 accese cu hit. In ce privete cache-ul de date, la aceasta configuraie (cache mapat direct) sunt 0accese cu hit din 16 accese (attea elemente sunt in cele doua tablouri). Cre tem dimensiunea blocului.Cretem asociativitatea, reluam execuia, determinam statisticile.

Problema 2 (atenie variabile declarate s coincid n C cu MIPS de finisat, eventual tratat i subliniatctigul prin interschimbare dar cu cretere a dimensiunii blocului).

Se consider urmtorul programul de test cache_loop.s care realizeaz n paralel suma elementelor ntregi(pe un octet) ale unei matrice Array_A[10,20] mai nti toate elementele unei coloane. Se aplic metoda

loop interchange (nsumarea nti a tuturor elementelor de pe o linie cod sursa cache_loop_i.s) i sevizualizeaz comparativ rata de hit in cache. S se studieze localitatea temporal, variind numrul deiteraii (1, 5, 10 i 20) ale buclei exterioare (numrul de coloane ale matricei).

Secvena C aferenta problemei 2,buclele in configuraia iniial

s=0;for(j=0;j


17/19


17

li $4, 10 # m - nr. linii din matrice

li $5, 20 # n - nr. coloane din matriceli $10,0 # j - indexul pe coloane

loop_j:# addi $10, $10, 1

li $8, 0 # i - indexul pe linieloop_i:# addi $8, $8, 1

multu $5,$8 # $11


18/19


18

__start:la $2, Array_Ali $6, 0 # s - sumali $4, 10 # m - nr. linii din matrice

li $5, 20 # n - nr. coloane din matriceli $8,-1 # i - indexul pe coloane

loop_i:addi $8, $8, 1li $10, 0 # j - indexul pe linie

loop_j:multu $5,$8 # $11


19/19

pcspim cache

Documents