simularea sistemului ierarhic de memorie În...

Computer Science and Electrical Engineering

Adrian FLOREA

1

SIMULAREA SISTEMULUI IERARHIC DE MEMORIE ÎN ARHITECTURI DE TIP MULTIPROCESOR CU MEMORIE

PARTAJATĂ

1.1. INTRODUCERE. SCOPUL LUCRĂRII

Limitările majore în cresterea performanței sistemelor monoprocesor (așa numitul brickwall: limitarea frecvenței de procesare cu implicatii directe asupra puterii consumate, paralelismul limitat la nivelul instrucțiunilor și respectiv decalajul semantic accentuat între viteza procesorului și latența sistemului ierarhic de memorie) au condus la dezvoltarea sistemelor multicore.

Una dintre provocările majore ale arhitecturilor multicore o reprezinta sistemul ierarhic de memorie care trebuie îmbunătăţit, fiind nevoie de o lăţime de bandă foarte mare pentru a satisface nevoile nucleelor. Memoriile cache constituie un mecanism omniprezent în microprocesoarele curente, dedicat mascării latenţei ridicate a memoriei principale. Datorită importanţei lor, acestea sunt considerate elemente cheie (fundamentale) în programa specifică arhitecturii calculatoarelor. În acest sens, prin intermediul acestei lucrari autorii spera ca studentii sa cunoasca in profunzime conceptele legate de cache-uri – modul de organizare, regulile de mapare, algoritmii de înlocuire a blocurilor conflictuale, strategia de scriere, notiunile teoretice referitoare la sistemul ierarhic de memorie din arhitecturile multicore (coerenta cache-urilor, protocoale de coerenta, etc.). Aplicatia software care permite evidentierea practica a conceptelor amintite anterior este SMPCache. Simulatorul SMPCache a fost dezvoltat de către grupul de cercetare ARCO condus de profesorul Miguel A. Vega-Rodríguez [Veg01], la departamentul de Calculatoare și Tehnologia Comunicațiilor, Universitatea Extremadura din Caceres, Spania. SMPCache reprezintă un simulator trace-driven dedicat analizei coerenței în sistemul ierarhic de memorie din arhitecturile de tip multiprocesor cu memorie partajată folosind o retea de interconectare de tip bus. Prin utilizarea SMPCache se urmareste o mai buna insusire si intelegere a aspectelor teoretice care sa conduca la imbunatatirea calitatii in sistemul educational si reprezinta un exemplu elocvent prin care aplicatii utilizate anterior in cercetare sunt translatate cu succes in procesul de predare / invatare [Yi06].

Lucrarea continuă cu un memento teoretic referitor la protocoalele de coerenta cunoscute in sistemele multiprocesor urmata de descrierea detaliată a modului de functionare al simulatorului SMPCache [Veg01].

1.2. MEMENTO TEORETIC

În acest subcapitol vor fi trecute în revistă doar câteva aspecte referitoare la sistemul ierarhic de memorie din arhitecturile multicore (coerenta cache-urilor, protocoale de coerenta, etc.), întrucât există suficientă documentaţie care tratează în detaliu acest subiect [Cul97, Han98, Hen07], inclusiv autorii acestei cărţi având astfel de contribuţii [Vin00]. Practic se vor prezenta acele noţiuni care intervin apoi în procesul de simulare a interfeţei multiprocesor - cache.

Un multiprocesor simetric (SMP) este un sistem de calcul cu mai multe procesoare identice care partajează aceeaşi memorie şi se conectează prin intermediul unui bus (magistrală) [Hen07]. Arhitecturile de tip SMP oferă, în general, aceeași latență de comunicare (timp de acces) între oricare dintre procesoare și spațiul de adresă partajat. Astfel de arhitecturi au insă dezavantajul că busul reprezintă un punct central, toate elementele de procesare se află in competiţie unele cu altele,


Adrian FLOREA

2

pentru a obţine acces la bus, deoarece acesta este cel care asigură comunicarea cu memoria principală. Busul este aşadar un element arhitectural care limitează viteza de comunicaţie, un bottleneck care reduce scalabilitatea arhitecturilor SMP. Ca rezultat, un SMP in general, nu cuprinde mai mult de 32 procesoare [Hen07].

1.2.1. COERENȚA CACHE-URILOR

Coerenţa memoriilor distribuite este o problemă care afectează arhitecturile multiprocesor, cu memorie partajată. În cazul arhitecturilor uniprocesor această problemă nu apare deoarece există un singur procesor care să citească şi să scrie date din/în memorie. În plus, se poate face o singură operaţie asupra memoriei la un moment dat, astfel că, atunci când o locaţie din memorie se schimbă, toate operaţiile următoare, care implică citirea acelei locaţii de memorie, vor accesa valoarea correct modificată.

În sistemele multiprocesor există două sau mai multe procesoare care lucrează în paralel, existând deci posibilitatea ca o locaţie de memorie să fie accesată în acelaşi moment de timp, de mai multe procesoare. Atât timp cât acea locaţie de memorie este accesată doar pentru citire (niciun procesor nu o modifică), partajarea ei se poate face fără probleme. Dar, atunci când valoarea este modificată de un procesor, există riscul ca celelalte procesoare să lucreze cu o copie veche, invalidă, a locaţiei de memorie partajată. Aşadar, într-o astfel de situaţie, apare o incoerenţă la nivelul memoriei.

Coerenţa cache-urilor se referă la integritatea datelor din memoriile cache locale, ale unei resurse partajate (memoria principală) şi este un caz special al coerenţei memoriilor. Coerenţa cache-urilor garantează că toate copiile datelor sunt actualizate. În funcţie de modul şi momentul în care sunt efectuate aceste actualizări, o operaţie de citire poate returna, uneori, valori neaşteptate. Coerenţa defineşte ce valori pot fi returnate în urma unei citiri, iar consistenţa specifică când o valoare scrisă va fi returnată în urma unei operaţii de citire (returnarea unei valori greșite / neaşteptate poate apare dacă actualizarea nu s-a efectuat complet). Atunci când mai multe procesoare păstrează în cache-urile lor locale (private) copii ale unor locaţii dintr-o memorie partajată, orice modificare a unei astfel de locaţii, la nivel de cache (locală deci), poate cauza o inconsistenţă la nivelul global al memoriei partajate.

O definiţie simplă a coerenţei memoriei este următoarea: un sistem de memorie este coerent dacă orice citire a unei locaţii de memorie oarecare returnează cea mai recentă valoare scrisă, în acea locaţie de memorie.

O definiţie completă a coerenţei este însă următoarea: un sistem de memorie este coerent dacă: 1. O citire de către un procesor oarecare, P, a unei locaţii X, urmată de o scriere a acelei locaţii X,

de către P, returnează întotdeauna valoarea scrisă de P, atunci când niciun alt procesor nu scrie în locaţia X, între cele două operaţii (citire şi scriere) făcute de P;

2. O citire a locaţiei X, de către P, urmată de o scriere a aceleiaşi locaţii, dar de către un alt procesor, întoarce valoarea scrisă, dacă cele două operaţii sunt suficient de separate în timp şi dacă nu are loc nicio altă scriere, între cele două accese la locaţia X;

3. Operaţiile de scriere ale aceleiaşi locaţii de memorie sunt serializate. Prin serializarea acestora se înţelege că: două scrieri ale aceleiaşi locaţii de memorie, de către oricare două procesoare, sunt văzute în aceeaşi ordine de către toate procesoarele.

Prima proprietate asigură păstrarea ordinii din cadrul programului. A doua proprietate pune în evidenţă importanţa coerenţei memoriei: dacă un procesor ar citi o valoare veche din memorie am putea trage concluzia că acea memorie este incoerentă. Serializarea operaţilor de scriere este o proprietate care asigură faptul că toate scrierile făcute la nivelul unei locaţii de memorie sunt văzute de către procesoare în ordinea în care acestea au fost făcute.


Adrian FLOREA

3

Incoerenţa cache-urilor poate fi cauzată de: partajarea datelor, migrarea proceselor, sau de operaţii de intrare/ieşire. În vederea soluţionării acestei probleme, există mai multe mecanisme de asigurare a coerenţei memoriilor cache:

1. mecanisme bazate pe directori (menţin un director central al blocurilor cache); 2. „Snooping” (procesul prin care fiecare memorie cache supraveghează liniile de adresare a

memoriei, pentru locaţiile de memorie păstrate. Atunci când o operaţie de scriere asupra unei locaţii de memorie este observată, locaţia de memorie corespunzătoare din cache este invalidată);

3. „Snarfing” (procesul prin care se monitorizează atât adresa locaţiei de memorie cât şi noua valoare, astfel ca actualizarea locaţiei de memorie să poată fi făcută de către controllerul memoriei cache, atunci când modificarea a avut loc extern, la nivelul unui alt cache, al unui alt procesor).

În cele ce urmează, ne vom orienta atenţia asupra mecanismului „snooping”, principala strategie de păstrare a coerenţei memoriilor cache, în cadrul sistemelor multiprocesor cu memorie partajată, bazate pe magistrală (bus). Busul este un mecanism convenabil de asigurare a consistenţei memoriilor cache deoarece permite tuturor procesoarelor din cadrul arhitecturii CMP (Chip Multi-Processors) să „observe” tranzacţiile care se fac la nivelul memoriei.

Există două protocoale principale în cadrul categoriei de protocoale de coerenţă bazate pe supravegherea busului:

1. write invalidate: procesorul care vrea să modifice o locaţie de memorie într-un cache al său va cauza mai întâi invalidarea tuturor celorlalte copii păstrate în restul memoriilor cache (de la celelalte procesoare) şi de abia apoi va actualiza blocul cache (locaţia de modificat); este cel mai frecvent implementată

2. write update sau write broadcast: procesorul care face modificarea emite valoarea actualizată tuturor celorlalte cache-uri astfel că toate copiile locaţiei de memorie partajată rămân identice.

Cele mai cunoscute protocoale de coerenţă a cache-urilor de tip „snoopy” sunt următoarele: 1. MSI; 2. MESI (Illinois); 3. MOSI; 4. MOESI;

Dintre acestea, în cadrul SMPCache sunt implementate MSI, MESI (ambele fiind protocoale de tip write back invalidation) și Dragon (protocol de tip write back update).

1.3. DESFĂŞURAREA LUCRĂRII

1.3.1. GHID DE UTILIZARE AL SIMULATORULUI SMPCache

Prin intermediul unei interfete prietenoase pot fi modificati parametri referitori la memoria principala a sistemului, la cache (capacitate, dimensiune bloc – exprimata in cuvinte, dimensiune cuvant – exprimata in octeti, organizare – regula de mapare, politica de inlocuire blocuri, protocoale de coerenta), numarul de microprocesoare, schema de arbitrare pe bus, benchmark-urile care pot fi incarcate in memoria partajata spre executie particulara a fiecarui microprocesor in parte.

Variind acesti parametri se poate studia localitatea (in principal cea temporala dar si cea spatiala) din benchmark-urile analizate prin intermediul ratei de miss, se pot vizualiza grafic, in fiecare ciclu de executie, tranzitiile blocurilor din cache, dintr-o stare in alta, conform protocolului de coerenta selectat, si de asemenea, se poate observa grafic, evolutia dinamica a microprocesoarelor (pe masura ce trace-urile sunt parcurse). In aceasta versiune (SMPCache 2.0) exista cativa parametri prestabiliti. Astfel, nivelul ierarhic de memorie este realizat dintr-un singur


Adrian FLOREA

4

nivel de cache („si din cate se pare unificat pe instructiuni si date”) si memoria principala de tip DRAM, strategia de scriere fiind writeback.

Configuratiile stabilite pot fi salvate in fisiere text avand extensia (*.cfg) putand fi ulterior reincarcate in vederea simularii si analizei rezultatelor (vezi figura 1).

Figura 1. Salvarea cofiguratiei selectate in figura 2

Pe fiecare linie impara este salvata denumirea parametrului arhitectural iar pe linia para, imediat urmatoare, valoarea respectivului parametru sau codul specific acestuia (vezi tabelul 1). In tabelul 2 sunt descrise plajele de valori aferente fiecarui parametru, dimensiunea maxima a unora dintre acestia (cum ar fi blocul de date, memoria principala, cache-ul), obtinute utilizand valorile maxime ale parametrilor care ii influenteaza.

Valori posibile Cod Protocol coerenta cache MSI 1

MESI 2 DRAGON 3

Schema de arbitrare pe bus Random 1 LRU 2 LFU 3

Regula de mapare Mapata direct 1 Cu seturi asociative 2 Complet asociativa 3

Numarul de seturi din cache NO 0 1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 sau 2048 256, 512, 1024 sau 2048

Politica de evacuare a blocurilor conflictuale din cache

NO 0 Random 1 LRU 2 FIFO 3


Adrian FLOREA

5

LFU 4 Strategia de scriere Write through 1 Write back 2

Tabelul 1. Optiuni de configurare non-numerice si codurile lor numerice asociate

Numarul de procesoare din arhitectura multicore 1, 2, 3, 4,5, 6, 7 sau 8 Protocolul de coerenta a cache-urilor MSI, MESI sau DRAGON Schema de arbitrare pe bus Random, LRU sau LFU Dimensiunea cuvantului in biti (word) 8, 16, 32 sau 64 (=26) Numarul de cuvinte din bloc (block) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 sau

1024 (=210) Numarul de blocuri din memoria principala 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,

1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152 sau 4194304 (=222)

Numarul de blocuri din cache 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 sau 2048 (=211)

Organizarea cache-ului / Regula de mapare Mapata direct, cu seturi asociative, complet asociativa

Cache sets (for set associative caches) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 sau 2048

Politica de evacuare a blocurilor conflictuale din cache

Random, LRU, FIFO sau LFU

Strategia de scriere Write through, Write back Numarul de niveluri ierarhice de cache 1 Referinte Accesul (adresarea se face direct) la

cuvantul de memorie Dimensiunea maxima a blocului de date in octeti 8 Kbytes=max_word(26) * max_block

(210) / 8 Dimensiunea maxima a memoriei principala in octeti

32 Gbytes=(213)* (222)

Dimensiunea maxima a cache-ului in octeti (excluzand etichete, biti de stare aferenti blocurilor, contoare, etc.)

16 Mbytes=(213)* (211)

Tabelul 2. Caracteristicile arhitecturale suportate de SMPCache

SMPCache prezintă folosind date statistice mai multe tipuri de grafice (vezi Figura 3), reprezentând măsurători interesante cum ar fi:

• Numarul tranzactiilor pe magistrala (bus) de interconectare (dependent de protocolul de coerenta al cache-urilor).

• Numarul de blocuri transferate pe bus. • Numarul de tranzitii de stare aferente blocurilor din cache • Numarul de tranzitii dintr-o anumita stare in alta • Numarul total de accese la memoria globala: accese de tip Fetch Instructiune, Citiri / Scrieri

date din / in memorie • Numar de accese cu Hit / Miss


Adrian FLOREA

6

Figura 3. Rezultate statistice ilustrate grafic

1.3.1.1. Intelegerea dialogului procesor – sistem ierarhic de memorie intr-o configuratie monocore

Presupunem urmatoarele valori in fereastra Memorie (Main memory): Selectie dimensiune cuvant – word wide in bits: 16 biti Numarul de cuvinte din bloc – words by block: 8 Numarul de blocuri din memoria principala: 8192 Numarul de blocuri din cache: 32 Rezulta: dimensiunea in octeti a blocului = dimensiune cuvant x Numarul de cuvinte din bloc / 8 dimensiunea in octeti a blocului = 16 x 8 / 8 = 16 bytes dimensiunea in octeti a memoriei = 8192 x 16 = 1024 x 8 x 16 = 128 kbytes dimensiunea in octeti a cache-ului = 32 x 16 = 512 bytes


Adrian FLOREA

7

Figura 2. Stabilirea uni configuratii de simulare (arhitectura monocore)

Observatie: Trebuie retinut faptul ca pentru ca orice modificare sa aiba loc este absolut

necesara apasarea (click) butonului de validare .

1.3.1.2. Intelegerea dialogului procesor – sistem ierarhic de memorie intr-o configuratie multicore

Figura 3 ilustrează configurația arhitecturală stabilită conform setărilor din Figura 2 (arhitectură monocore, dimensiunea cuvântului de 16 biți, 8 cuvinte per bloc, 32 de blocuri într-un cache mapat direct). V reprezintă bitul de validare (1 / 0 – informația este / nu este validă), care inițial are valoarea 0 (similar stării I - invalid din mecanismul de coerență). D este bit de dirty, necesar la scrierea în cache-ul de date prin strategie write back. În [Vin00, Flo03] sunt prezentate cazurile generale de arhitecturi monocore cu cache-uri semi și complet asociative.


Adrian FLOREA

8

Figura 3. Configuratia arhitecturala care respecta parametri setati (în figura 2)

Un exemplu din benchmark-ul NASA7.prg: Adresa_MP reprezinta adresa locatiei (cuvantului) de memorie de la care se aduce instructiunea / data sau la care se va scrie data in memorie1. Numarul_blocului_din_MP (Block)= (Adresa_MP / numar_cuvinte_din_bloc) = 0x190 / 8 =

0x32 = 50

Index_bloc_in_cache = (Adresa_MP / numar_cuvinte_din_bloc) % nr_blocuri_din_cache

1 S-a considerat adresabilitatea pe cuvânt, nu neapărat pe octet ci pe câți biți se stabilește dimensiunea cuvântului, iar adresa fizică de memorie a unui cuvânt din memorie (AF) pe 32 de biți.


Adrian FLOREA

9

Index_bloc_in_cache = (0x190 / 8) % 0x20 = 0x32 % 0x20 = 0x12=1810 TAG_bloc_in_cache = (Adresa_MP / numar_cuvinte_din_bloc) / nr_blocuri_din_cache = 0x32 / 0x20 = 1 Index_cuvant_in_blocul_din_cache = Adresa_MP % numar_cuvinte_din_bloc

Index_cuvant_in_blocul_din_cache (word) = 0x190 % 8 = 0

Dat fiind protocolul de coerenta MSI (chiar daca s-a optat pentru o configuratie monocore) in

urma accesarii blocului 50 de memorie (provocat de citirea unei instructiuni), acesta determina in primul rand un acces cu miss (de start rece) in blocul 18 din cache, iar starea in care va tranzita blocul este Shared (nu mai este Invalid blocul din cache, dar nici nu contine o copie modificata a datei diferita de cea din memorie pentru a fi Modified). Astfel vom avea o tranzitie din I in S. Este selectat primul cuvant din cadrul blocului (Index_cuvant_in_blocul_din_cache (word) = 0).

Urmatorul acces (citire data din memorie de la adresa 0x7FE0) va fi, conform formulelor

anterior prezentate, la blocul de memorie 4092 (0xFFC). In acest caz se va accesa cu miss blocul 28 (0x1C) din cache iar tranzitia se va face din nou din Invalid in Shared.


Adrian FLOREA

10

Daca configuratia este de tip monocore tranzitiile sunt simple (una per acces), daca insa

configuratia microarhitecturala este de tip multicore (sunt atatea tranzitii per acces cate core-uri exista in sistemul multiprocesor). Aici, de regula, un acces determina tranzitie in starea Invalid pentru blocul din cache-ul aferent procesorului care nu executa accesul, iar pentru procesorul care determina accesul la memorie tranzitia are loc fie in S fie in M.

Simularea sistemului ierarhic de memorie pe o configuratie multicore folosind benchmark-urile multiprocesor Se selecteaza o configuratie microarhitecturala cu 2 core-uri si protocol de coerenta MESI. Dimensiunea cuvantului de 16 biti, 8 cuvinte per bloc, 16 blocuri in cache si 4096 de blocuri in memorie (valoarea minima impusa de adresele de memorie utilizate in cele doua trace-uri de test). Pe rand se incarca din calea C:\Program Files\GACDL\SMPCache 2.0\SAMPLES\EXAMPLES cele doua fisiere trace MESI2.prg (Select processor 1 / OK) si apoi MESI3.prg (Select processor 2 / OK). Nefacand in acest fel riscam in a se incarca doar ultimul program de test in memoria ambelor core-uri.

Intrucat arbitrarea pe bus este implicit random este posibil ca la executia operatiei (aceeasi pe ambele core-uri) 2 0x00001111 (citire data din memorie) la vizualizarea cache-ului aferent core-ului 1 unii studenti sa vada Exclusiv blocul din cache iar altii sa-l vada Shared (in functie de care procesor primeste bus-ul – random).

In continuare este analizat in mod text cache-ul procesorului P1 in care se afla incarcat trace-ul MESI2.prg. Continutul acestuia este urmatorul:


Adrian FLOREA

11

Concomitent cu rularea lui MESI2.prg de catre P1, pe al doilea core (P2) ruleaza trace-ul MESI3.prg. Continutul acestuia este urmatorul:

Trebuie inteles urmatorul fapt: desi va fi prezentata o dinamica a executiei (a se vedea figura

urmatoare), la o a doua simulare dinamica executiei poate sa fie total alta, depinde de care procesor va accesa primul magistrala.

Exemplul ilustrat in succesiunea de 4 figuri este poate unul mai putin elocvent intrucat primele 4 accese din 9 sunt din partea procesorului P1 (trei tranzitii din starea I(invalid) in E(exclusiv) datorate citirilor si o tranzitie din I in M (modified) datorata unei scrieri).

Reluand simularea in aceleasi conditii, blocul 546 se afla in S (shared) si nu E (exclusiv) ca

anterior, intrucat primul procesor care a accesat memoria a fost de aceasta data P2.


Adrian FLOREA

12

In ce priveste comunicatia pe bus-ul de interconectare, lucrurile stau astfel:

Primele doua accese la memorie sunt: citirea unei date – blocul 546 din memorie si respectiv citirea unei instructiuni – blocul 2184 din memorie (I �� E in cache-urile in care se aduce informatia si


Adrian FLOREA

13

respectiv I �� I in cache-urile in care se cauta informatia, aferent procesoarelor care nu au nevoie de ea).

La urmatorul acces (pentru citirea blocului 546 de catre procesorul P2) preluarea blocului se face din cache-ul procesorului P1 (Shared signal = YES). In consecinta, blocul 546 din cache-ul lui P1 trece din E �� S iar cel din cache-ul lui P2 trece din I �� S. La incheierea simularii rezulta (in aparenta) un numar de 7 tranzactii pe bus (intrucat 2 accese sunt cu hit in cache-ul procesorului P2 si pentru acestea nu e nevoie obtinerea de informatii prin intermediul bus-ului). Dar finalizarea executiei programelor presupune scrierea informatiei din cache in memoria principala intrucat strategia de scriere a fost Write Back. In consecinta rezulta 10 tranzactii pe bus datorate celor trei scrieri (doua din cache-ul lui P1 – blocurile 3276 si 3822 si una din cache-ul lui P2 – blocul 546).


Adrian FLOREA

14


Adrian FLOREA

15

1.3.2. BENCHMARK-URI “MONOCORE” / “MULTICORE”

SMPCache poate fi configurat cu un singur procesor (execută benchmark-uri „monocore” – o aplicație separată per core – vezi tabelul 3) sau cu mai multe procesoare și să ruleze benchmark-uri monocore care nu comunică între ele ca și zonă de memorie partajată respectiv benchmark-uri „multicore” – care execută aplicații reale paralele caracterizate de comunicare și sincronizare a firelor de execuție din cadrul aplicației (vezi tabelul 4). Benchmark-urile monocore simulate fac parte din suita SPEC’92 iar trace-urile de memorie aferente sunt caracterizate in tabelul 3.

Denumire

benchmark Descriere Clasificare Limbaj Numar

instructiuni Numar

accese la memorie

hydro Calculul jeturilor galactice utilizând ecuaţiile hidrodinamice ale lui Navier – Stokes. Domeniul Astrofizica.

Floating point

Fortran 1651 2127

nasa7 O colectie de 7 kernel-uri cel mai frecvent folosite in aplicatiile NASA.

Floating point

Fortran 1439 1855

cexp Fragment din compilatorul Gnu C caracterizat de un comportament puternic aleator

Integer C 18041 20000

Ear Simulează comportamentul urechii umane prin conversia unui fişier de sunet folosind Transformata Fourier rapidă şi alte funcţii din biblioteca matematica.

Floating point

C 4335 5308

wave Rezolvă ecuaţiile lui Maxwell si ecuatiile de miscare ale particulelor electromagnetice.

Floating point

Fortran 2709 3427

mdljd Rezolvă ecuaţiile de miscare ale unui model de 500 de atomi care interactioneaza intr-un camp de potential Lennard-Jones. Reprezinta un program numeric care exprima un comportament aleator si este caracterizat de o serie de bucle de program.

Floating point

Fortran 15931 20000

swm Rezolvă ecuaţiile lichidelor subţiri in ape de mica adancime utilizând ecuaţii cu diferenţe finite.

Floating point

Fortran 15205 20000


Adrian FLOREA

16

comp Foloseste algoritmul de compresie Lempel-Ziv pentru comprimarea unui fisier de 1 MB de 20 de ori.

Integer C 2055 2524

ucomp Versiunea decompresata a benchmark-ului comp

Integer C 2209 2733

Tabelul 3. Trace-urile benchmark-urilor “monocore” SPEC’92

Denumire benchmark

Descriere Limbaj Numar instructiuni

Numar accese la memorie

FFT Aplicație paralelă care simulaează dinamica fluidelor folosind transformata Fourier rapidă (FFT)

Fortran 3,124,454 7,451,717

Simple Versiunea paralelă a aplicației SIMPLE

Fortran 11,594,172 27,030,092

Tabelul 4. Trace-urile benchmark-urilor “multicore”

These traces were provided by David Chaiken (then of MIT) for NMSU PARL (The Performance

and Architecture Research Lab (PARL) supports cutting-edge research projects in wireless

networks, network security, and computer architecture, and frequently contributes to US and

international standards. PARL computer facilities include private research networks and wireless

systems, extensive simulation resources, and support Internet resources such as the NMSU

TraceBase, a repository of computer and network traces that is used in teaching and research

worldwide. Dr. Eric Johnson is the director of PARL).

Speech 11,771,664 --- Kirk Johnson and David Kranz (both at MIT) are responsible for this trace

Weather 31,764,036 Fortran Parallel version of the WEATHER application, which is used for weather forecasting. The serial version is from NASA Space Flight Center, Greenbelt, Md.

Fisierele trace aferente benchmark-urilor simulate contin adresele de memorie ale instructiunilor dar si ale fiecarei date citita si / sau scrisa. Pe fiecare core al sistemului multiprocesor poate fi incarcat, spre exemplu, un anumit trace. Trace-urile sunt fisiere de tip ASCII (cu extensia „.prg”) si pe fiecare linie se intalnesc doua numere separate printr-un caracter spatiu, astfel:

Eticheta Valoare

� Eticheta reprezinta un numar zecimal care identifica tipul accesului la memorie solicitat de catre procesor:

o Citirea / aducerea unei instructiuni (0) o Citirea unei date din memorie (2)


Adrian FLOREA

17

o Scrierea unei date de catre procesor in memorie (3) � Valoare reprezinta un numar hexazecimal care identifica adresa efectiva de memorie a

cuvantului (word) accesat de catre procesor.

1.3.2. PROBLEME PROPUSE SPRE REZOLVARE

A. Pentru benchmark-urile uniprocesor rezolvați următoarele probleme. 1. Studiaţi influenţa capacităţii cache-ului de instrucţiuni (în KB) asupra ratei de miss în cache

Rmiss(SIZE_Cache).

2. Pornind de la configurația inițială generați graficul Rmiss(BLOC_SIZE).


Adrian FLOREA

18

3. Determinați rata de miss variind dimensiunea blocului de date pentru diferite dimensiuni de cache.

4. Determinați rata de miss variind gradul de asociativitate pentru diferite dimensiuni de cache.

B. Pentru benchmark-urile multiprocesor rezolvați următoarele probleme. 5. Miss rate versus cache size


Adrian FLOREA

19

6. Miss rate versus cache coherence protocol

7. Miss rate versus number of processors


Adrian FLOREA

20

C. Generati fișiere trace pentru aplicațiile paralele din suita PARSEC și SPLASH-2 folosindu-vă de simulatorul multicore multi2sim [M2sim]. Practic, în urma simulării unui benchmark Parsec cu simulatorul multi2sim se va genera pentru fiecare CORE în parte pe care a rulat benchmark-ul un fișier trace. Trace-urile rezultate vor trebui simulate pe arhitectura SMPCache (configurația multicore). Realizați o documentație aferentă evoluției trace-urilor considerând protocoalele de coerență MSI / MESI și exemplificați diferențele.

• Din HarryDwyerE.pdf, Chi-ChengLinE.pdf, FernandoPardoE.pdf. • students must build a reduced version of the simulator.

BIBLIOGRAFIE

[Cul97] Culler D., Singh J.P., Gupta A. – Parallel Computer Architecture: A Hardware /

Software Approach, Morgan Kaufmann, 1997.

[Flo03] Florea, A., Vinţan N. L. – Simularea şi optimizarea arhitecturilor de calcul în aplicaţii

practice, Editura Matrix ROM, Bucureşti, ISBN 973-685-605-4, 2003 (443 pg. + CD atasat). Cartea a obtinut Premiul “Tudor Tanasescu” al Academiei Romane pe anul 2003, decernat in 23 decembrie 2005.

[Han98] Handy J. – The Cache Memory Book, The Morgan Kaufmann Series in Computer Architecture and Design, (2nd edition), 1998. [Hen07] Hennessy J. L., Patterson D. A. – Computer Architecture: A Quantitative Approach, Morgan Kaufmann, 2007 (4th edition).

[Vin00] Vinţan N. L., Florea A. – Microarhitecturi de procesare a informaţiei, Editura Tehnică, Bucureşti, ISBN 973-31-1551-7, 2000 (312 pg.)

[Yi06] Yi J.J., Lilja D.J. – Simulation of Computer Architectures: Simulators, Benchmarks,

Methodologies, and Recommendations, IEEE Transactions on Computers, vol. 55, No. 3, March 2006.

[Veg01] Vega-Rodríguez M.A., Sánchez-Pérez J.M., Gómez-Pulido J.A. – An Educational Tool

for Testing Caches on Symmetric Multiprocessors, Microprocessors and Microsystems, Elsevier Science, vol. 25, no. 4, pp. 187-194. June 2001, ISSN 0141-9331.

[M2sim] http://www.multi2sim.org/wiki/index.php5/Main_Page

simularea sistemului ierarhic de memorie În...

Documents