1

L. N. VINAN - Direcii de cercetare n domeniul sistemelor multicore / Main Challenges in Multicore Architecture Research, Revista Romana de Informatica si Automatica, ISSN: 1220-

1758, ICI Bucuresti, vol. 19, nr. 3, 2009, http://www.ici.ro/RRIA/ria2009_3/index.html

Direcii de cercetare n domeniul sistemelor multicore

Main Challenges in Multicore Architecture Research

Lucian N. VINAN1,2

1Universitatea Lucian Blaga, Str.E. Cioran, Nr. 4, Sibiu - 550025, ROMNIA, Tel./Fax:++40-269-212716, E-mail: lucian.vintan@ulbsibiu.ro, http://webspace.ulbsibiu.ro/lucian.vintan

2Academia de tiine Tehnice din Romnia, www.astr.ro

Rezumat: S-a realizat un studiu asupra impactului arhitecturilor multicore i manycore n cadrul ingineriei calculatoarelor. S-a pornit de la geneza acestor sisteme, determinat de limitele paradigmei monoprocesor. S-au identificat i s-au analizat n mod sistematic, pe baza unei literaturi de specialitate recente, urmtoarele provocri importante pentru cercetarea i dezvoltarea acestor sisteme: arhitecturi multicore omogene vs. eterogene, exploatarea sinergic a tipurilor de paralelism, ierarhia de memorii cache, coerena i consistena variabilelor partajate, reele de interconectare, modele de programare paralel, paralelizarea aplicaiilor, simularea ca instrument de cercetare, benchmarking, explorarea automat a spaiului parametrilor, arhitecturi multicore cu procesri anticipative, putere consumat, disipaie termic. Concluzia de baz este c sunt necesare progrese importante n toate aceste domenii, pentru ca proiectarea i utilizarea sistemelor multicore i manycore s fie adecvate. Cu sau fr voia noastr, aceste sisteme vor constitui dispozitivele de calcul universale. Abordarea oricreia dintre aceste provocri trebuie s fie una de tip holistic. S-a artat cum vor schimba aceste noi arhitecturi, paradigma tiinei ingineriei calculatoarelor. n particular, programarea acestor sisteme constituie o provocare major, pentru care nu suntem nc pregtii suficient. Cuvinte cheie: arhitectura calculatoarelor, sisteme multicore i manycore, sisteme paralele Abstract: It is presented the impact brought by the new multicore and manycore systems in the computer engineering field. There were explained the limits of the actual mono-processor paradigm that involved the multicore shift. A state of the art in multicore architecture and compiler research was presented. We identified and analysed some important research challenges in multicores research and development, like the followings: homogenous vs. heterogeneous multicores, synergistic exploitation of parallelism grains, cache hierarchy, cache coherence and consistency protocols, interconnection networks, parallel programming models, applications parallelisation methods, simulation, benchmarking, automatic design space exploration, speculative multicore architectures, power consumption and thermal effects. There are necessary important progresses related to all these scientific challenges, in order to adequately develop and program multicore and manycore systems. The research approach must be a holistic one for each

2

of the above topics. It is shown how these systems would change the computer science and computer engineering paradigm. Keywords: advanced computer architecture, parallel computing, multicore and manycore

Geneza arhitecturilor tip multicore Arhitecturile de procesoare de tip single-core, care s exploateze n mod agresiv paralelismul la nivel de instruciuni prin execuii speculative de tip out of order, trebuie cercetate i dezvoltate n continuare, dei frecvena tactului nu mai poate crete prea mult, din cauza consumului de putere dinamic (Pd=kCV2f) i a disipaiei termice. La actualele frecvene de tact de civa GHz, densitile de putere din chip-uri sunt enorme, de cteva sute de W/cm2. Supercalculatoarele actuale, cu mii de procesoare, consum puteri de ordinul MWatt. Totodat, la o frecven de tact de 14 GHz (70 ps), estimabil n anul 2014, ntrzierea semnalului pe 5 mm de conductor devine enorm (390 ps). Evident c, n aceste condiii, creterea frecvenei de tact practic nu mai este posibil, performana putnd crete doar prin inovaii arhitecturale. Provocarea esenial aici const n determinarea compromisului optimal ntre performana procesrii (Instructions Per Cycle IPC) i complexitatea arhitectural (puterea consumat, disipaia termic, aria de integrare i bugetul de tranzistori). Astfel, metrici de evaluare de tip MIPS (Million Instructions per Second) per watt, MIPS per area of silicon etc. sunt tot mai frecvent utilizate. Aceste microarhitecturi monoprocesor vor exploata paralelismul la nivel fin din cadrul aplicaiilor cu secvenialitate intrinsec (scrise n limbaje secveniale). n acest sens pot fi avute n vedere inclusiv metode i tehnici de compilare adaptiv a codului obiect, bazate pe informaii de tip profilings (tipul algoritmilor, gradul de utilizare al resurselor hardware, nivelul i granularitatea paralelismelor la nivelul thread-urilor etc.). Aceste metode pot determina adaptarea sau reconfigurarea microarhitecturii la cerinele aplicaiei, n vederea maximizrii IPC ului i minimizrii puterii consumate. i totui, metodele de exploatare a ILP-ului (Instruction Level Parallelism) au ajuns la o oarecare saturaie ILP Wall (superpipeline cu frecvene mari de tact, procesarea out of order, branch prediction, trace-cache, procesri speculative, metode de scheduling static, metode de eliminare a memory-wall etc.) Sisteme multicore i manycore Soluia cea mai frecvent la ora actual pentru creterea performanei i evitarea limitrilor anterior schiate, const ns n dezvoltarea de arhitecturi multicore i manycore. Dei vor face mai dificil activitatea calculatoritilor, acestea ofer o rat de performan/Watt mai bun dect sistemele monoprocesor, la o performan similar. n plus, aceste sisteme care exploateaz paralelismul thread-urilor, au anse mai mari dect sistemele monoprocesor ca s mai micoreze din prpastia de comunicare ntre microprocesor i memorie (DRAM). Cercetarea n acest domeniu este extrem de necesar avnd n vedere faptul c n anul 2015 se ateapt microprocesoare comerciale de uz general de 256 de nuclee. Se consider c sistemele multicore (eterogene) vor deveni dispozitivul universal de calcul. Se sper c aceste sisteme vor putea corela eficiena procesrii cu creterea densitii de integrare, care evolueaz conform legii lui Moore. Compania Intel a fabricat deja un chip cu 80 de core-uri integrate, v. http://techfreep.com/intel-80-cores-by-2011.htm, pe care l va lansa n producia de mas n curnd. Procesoarele grafice Nvidia Tesla C1060, cu 240 de nuclee integrate n chip, ofer

3

performane de pn la un Teraflop/s. Procesorul multicore Sony/Toshiba/IBM Cell, cu 9 nuclee neomogene integrate per chip, atinge rate de procesare de 200 Gflop/s. Programarea i utilizarea eficient n asemenea cazuri, nu vor fi posibile pn cnd nu vor avea loc schimbri radicale n modelele de programare i n instrumentele software disponibile. Metricile succesului n cadrul dezvoltrii sistemelor multicore se refer n principal la productivitatea programrii i la performana aplicaiei. Performana trebuie s aib n vedere minimizarea acceselor la datele aflate n afara memoriilor locale (prin managementul localitii datelor), optimizarea balansrii ncrcrii procesoarelor i respectiv optimizarea comunicaiilor i sincronizrilor. n acest scop, se impune o nou proiectare a algoritmilor, n vederea maprii lor optimale pe sistemele de tip multicore. Arhitecturi multicore omogene vs. eterogene Nu putem fi de acord n totalitate cu opinia specialitilor de la Berkeley care afirm c nucleele viitoarelor multiprocesoare vor consta n procesoare simple [Asa06, pg. 22]. n acest caz, paralelismul la nivel de instruciuni, (singurul) exploatabil la nivelul programelor secveniale, ar fi mult diminuat. Acest dezavantaj este inacceptabil avnd n vedere c peste 99% din programele scrise pn acum au fost scrise n limbaje secveniale. Din acest motiv credem c viitorul, n calculul de uz general, este cel al unor sisteme multicore eterogene (cteva nuclee superscalare out of order cu execuii speculative + multe nuclee superscalare mai simple, de tip in order, cu structuri pipeline scurte, de 5-9 stagii). Eterogenitatea permite adaptarea dinamic la diferitele caracteristici ale programelor rulate. Acest fapt este agreat de multe cercetri recente i este justificabil n baza unui exemplu simplu preluat din [Hen07]. Se presupune, spre ex., c f=10% din timp, un program nu poate fi accelerat prin paralelizare pe un sistem cu N=100 de procesoare. Se consider c pentru a rula aceast parte secvenial de doua ori mai rapid dect pe un procesor simplu, este nevoie de un procesor complex, care are de 10 ori mai multe resurse (complexitate) dect procesorul simplu. Aplicnd legea lui Amdahl, accelerarea obinut pe un sistem omogen cu 100 de nuclee simple este:

N

f)(1f

1S

+

= = 1 / (0.1 + 0.9/100) = 9.2 (1)

Accelerarea obinut pe un sistem neomogen de complexitate echivalent, avnd 90 de nuclee simple i un nucleu complex, este superioar:

S = 1 / (0.1/2 + 0.9/90) = 16.7 (2) Totui, superioritatea sistemelor neomogene fa de sistemele omogene, va trebui dovedit mult mai convingtor prin simulri complexe, att pe benchmark-uri secveniale ct i paralelizate (IPC, energie consumat, buget tranzistori, arie integrare etc.). De altfel, chiar i actualele multiprocesoare comerciale sunt neomogene, avnd un nucleu superscalar out of order foarte puternic (IBM Cell BE, Intel IXP procesoare de reea etc.) i totui, la nivelul unor manycore uri eterogene, modelele de programare ar putea deveni foarte complicate. Virtualizarea va juca un rol important att n vederea portabilitii aplicaiilor ct i n vederea evidenierii concurenelor, mai facil la nivelul mainii virtuale, care poate beneficia de meta-informaii derivate din codul HLL (High Level Language). n schimb, n multe aplicaii din calculul dedicat (aplicaii grafice, aplicaii numerice etc.) este foarte probabil ca sistemele multicore omogene s aib succes.

4

Exploatarea sinergic a tipurilor de paralelism

Cercetrile viitoare trebuie s vizeze i exploatarea sinergic a diverselor tipuri de paralelism (de tip pipeline prin suprapunerea execuiei fazelor instruciunilor, ILP, TLP Thread Level Parallelism, ori chiar la nivelul unor task-uri independente) Extensiile de paralelizare ale limbajelor de programare (ex. OpenCL, Grandcentral) vor ajuta aplicaiile s beneficieze de toate resursele disponibile (CPU, multi-cores, GPU). Nici paralelismul la nivelul datelor (bit, cuvnt arhitecturi vectoriale) nu trebuie neglijat. Spre exemplu modelul OpenMP permite exploatarea paralelismelor la nivel de task-uri, bucle i date, deopotriv. Aplicaiile de tip web, mobile (cloud computing) sau bazele de date sunt caracterizate de paralelism la nivel de fire sau la nivelul acceselor la memorie i mai puin la nivel ILP. n asemenea cazuri, fiecare client poate fi servit de ctre un nucleu separat. Aceste aplicaii necesit multe procesoare simple, cu memorii performante de mare capacitate. Ierarhia de memorie Se arat n literatur c ierarhia de cache-uri este departe de a fi optimal proiectat. Circa 50% din blocurile din cache sunt moarte (analog, cca. 50 % din datele dintr-o pagin sunt nefolosite). Sistemul de cache-uri nu mai trebuie vzut ca un modul fix, pe care soft-ul trebuie s se plieze. Acest sistem trebuie s devin mai maleabil, adaptat la cerinele rulrii dinamice a aplicaiilor. Sunt necesare cercetri n vederea optimizrii ierarhiei de memorii cache n sistemele multiprocesor, prin exploatarea agresiv a localitilor (vecintilor) spaiale i temporale. Astfel, spre exemplu, n [Wat09] autorii se focalizeaz pe mecanisme hardware care adapteaz dimensiunea logic a blocului din L2 cache la caracteristicile aplicaiei. Accesarea L2 cache se face n paralel cu accesarea unor aa numite cache-uri de monitorizare (Observation Cache - OC), fiecare avnd lungimi diferite ale blocului. Cache-ul OC care contorizeaz pe un anumit interval de timp un numr minim de miss-uri, determin blocul optimal din punct de vedere al dimensiunii, necesar a fi adoptat n L2 cache. Un bloc de o asemenea dimensiune exploateaz cel mai bine vecintatea spaial a datelor i a instruciunilor. Un controller special de ntreruperi monitorizeaz periodic starea cache-urilor OC si, n consecin, modific n mod corespunztor lungimea blocului logic din L2 cache. Mecanismul este unul simplu, eficient i robust, care nu implic intervenia compilatorului ori a aplicaiei software. Sunt necesare cercetri care s dezvolte noi scheme de protocoale de coeren a cache-urilor n sistemele MIMD, scalabile, flexibile, reconfigurabile chiar, care s suporte sute i chiar mii de nuclee de procesare integrate pe un singur chip de uz general. Exist studii empirice care arat c la o tehnologie de integrare de 30 nm se pot integra 1000-1500 de nuclee simple pe o singura pastil de siliciu (actualmente Intel utilizeaz tehnologii la 45 nm). Tehnicile de coeren actuale de tip snooping (MSI, MESI, MOESI etc.) precum i cele de tip directory-based sunt depite, fiind nescalabile la nivelul sutelor i miilor de nuclee integrabile pe un chip. Totui, cercetri incrementale utile, bazate n principal pe predicie i speculaie, ar putea perfeciona chiar i aceste protocoale. Tehnicile de coeren vor trebui s aib n vedere noile caracteristici specifice sistemelor multicore (latenele miss-urilor cache to cache, lrgimea de band a bus-urilor de interconectare etc., care sunt mult diferite dect cele aferente sistemelor multiprocesor clasice.) n consecin, viitorul aparine sistemelor multicore cu memorie partajat distribuit (Distributed Shared Memory sau Non

5

Uniform Memory Architectures) cu protocoale de coeren hardware-software sau de tip Message Passing (NoC Networks on a Chip) i n tehnologii de integrare de tip 3 D [Mog09]. n optimizarea mecanismelor de coeren trebuie inut cont n mod deosebit de minimizarea puterii consumate. Coerena i consistena Un program paralel trebuie s specifice, printre altele, ordinea operaiilor de scriere-citire. Cel mai simplu, ar fi s se pstreze ordinea impus de dependenele de date din program. Cnd ordinea implicit a acestor operaii nu este determinat n mod unic, sunt necesare operaii explicite de sincronizare ntre fire (creare/unificare fire, excludere mutual, alocare memorie partajat, bariere etc.). Coerena cache-urilor asigur o viziune consistent a memoriei pentru diversele procesoare din sistem. Nu se rspunde ns la ntrebarea "ct de consistent?", adic n ce moment trebuie s vad un procesor c o anumit variabil a fost modificat de un altul? Cea mai simpl soluie const n forarea fiecrui procesor care scrie o variabil partajat, de a-i ntrzia aceast scriere pn n momentul n care toate invalidrile cauzate de ctre procesul de scriere, se vor fi terminat. Aceast strategie simpl se numete consisten secvenial. Ea impune ca orice simulare a procesrii unui anumit program, prin respectarea secvenialitii interne din cadrul unui fir (data-flow order) i, respectiv, prin ordinea aleatoare de execuie a firelor ntre ele, atunci cnd nu este specificat una anumit, s conduc la aceleai rezultate finale. Altfel spus, un program scris corect va duce la aceleai rezultate, indiferent de ntreeserea firelor. Dei consistena secvenial prezint o paradigm simpl, totui ea reduce performana, n special pentru sistemele cu un numr mare de procesoare sau cu reele de interconectare de latene ridicate. Aadar, este necesar dezvoltarea unor noi modele, mai relaxate dect cel al consistenei secveniale (release consistency) de asigurare a consistenei memoriei partajate. Unele cercetri alternative se focalizeaz pe anumite mecanisme de prefetch a datelor, implementate n cadrul mecanismului simplu al consistenei secveniale, ncercnd astfel s reduc degradarea de performan pe care acest mecanism o implic prin secvenialitatea acceselor la memoria de date. Reele de interconectare Sunt necesare reele de interconectare de lrgime de band ridicat, n cadrul unor sisteme cu memorie partajat on-chip, scalabil. Actualmente, reelele de interconectare (on chip) au lrgimi de band relativ modeste, fiind limitate de capacitile parazite, datorate modulelor interconectate, ntrzierilor de arbitrare etc. n plus, ele sunt nescalabile la nivelul sutelor ori miilor de nuclee integrate. O excepie pozitiv o constituie HyperTransport, o reea de interconectare de tip point to point (pachete), bidirecional, serial/paralel, scalabil, de laten mic i de lrgime de band ridicat, v. http://www.hypertransport.org. Ea permite interconectarea procesoarelor, a acestora cu interfeele de I/O i cu diferitele acceleratoare. AMD utilizeaz aceast reea flexibil n multe dintre multicore-urile sale (Athlon 64, Athlon 64 X2, Athlon 64 FX, Opteron, Sempron i Phenom). HyperTransport ofer legturi distincte ntre procesor memorie i respectiv ntre procesor - sub-sistemul de I/O. Mai mult, ea ofer legturi fizice distincte pentru citiri i scrieri din/n spaiul de I/O, oferind deci paralelizri agresive ale acestora. La ora actual reeaua ofer rate de transfer de pn la 10400 MB/s (versiunea a 3-a).

6

n domeniul reelelor de interconectare implementate on-chip, cercetrile vor avea n vedere, n special, arhitecturile switch-urilor, topologiile i algoritmii de rutare. Tehnologia VLSI utilizat influeneaz n mod direct soluiile arhitecturale. Probabil c cercetrile se vor inspira din reelele de interconectare ale supercomputerelor actuale (spre exemplu supersistemul IBM BlueGene care conine 65536 de noduri, clusterizate n cate 80 CPU 2-SMT PIM - Processing n Memory, conectate Crossbar/cluster. Aceste clustere sunt interconectate prin intermediul unei reele tip 3 D Torus Network care face ca fiecare nod s poat comunica direct cu ali 6 vecini situai pe axele ortogonale XYZ. Aici i subsistemul ierarhic de cache-uri va juca un rol extrem de important, fiind necesar mbuntirea sa prin noi idei. De remarcat c eficientizarea acestui subsistem va conduce la scderea presiunii asupra reelelor de interconectare i a memoriei principale partajate. Detecia i abortarea execuiei instruciunilor Store care doresc s scrie o valoare deja existent n memoria partajat, numite Silent Stores, ajut de asemenea n mod semnificativ la reducerea presiunii asupra reelei de interconectare [Vin07]. Cercetri novatoare n arhitectura memoriilor DRAM sunt foarte necesare, avnd n vedere c un chip DRAM de 512 Mbit, spre exemplu, conine sute de blocuri fizice independente, oferind deci un potenial uria n creterea lrgimii de band, prin accesri ntreesute. Integrarea on-chip a memoriilor DRAM nu mai presupune multiplexarea adreselor (necesar n memoriile off-chip datorit costurilor mari ale terminalelor). Acest fapt conduce la scderea semnificativ a timpului de acces. De altfel, sistemele masiv paralele se bazeaz pe conceptul de PIM. n acest caz, memoria DRAM este integrat n cadru procesorului, cu mari beneficii asupra latenei i lrgimii de banda procesor-memorie. O reea de procesoare PIM se numete arhitectur celular. n arhitecturile celulare se pot conecta milioane de procesoare, fiecare procesor fiind conectat doar la civa vecini din cadrul topologiei de interconectare. Sistemele multicore au accentuat i mai mult gap-ul ntre CPU i sistemul secundar de memorie (discuri), conducnd la scderea lrgimii de band per core. Este deci imperios necesar un sistem de I/O mult mai rapid, bazat pe abilitatea de a mapa n mod eficient un numr mare de operaii concurente de I/O, pe sutele de uniti de stocare. n acest scop trebuie aduse mbuntiri aplicaiilor, mainii virtuale, sistemului de operare i controlerului dedicat al unitilor de disc. Modele de programare paralel Conform [HiPEAC], n urmtoarea decad, n cadrul aplicaiilor vor fi deosebit de pregnante urmtoarele tendine: accesul ubicuu, servicii personalizate i delocalizate, sisteme masive de procesare a datelor, realitate virtual de nalt calitate, senzori inteligeni. Aceste tendine se vor manifesta n aplicaii concrete, precum cele legate de roboi domestici, vehicule auto-pilotate, teleprezen, jocuri, implanturi i extensii ale corpului uman (human++) etc. Pentru programarea acestor aplicaii pe sistemele multicore i manycore sunt necesare modele eficiente, performante dar i simple (!) de programare paralel. Cercetrile n acest domeniu trebuie s investigheze metodele de evideniere a concurenelor la nivelul limbajelor de programare. n general, este de dorit ca aceste modele s fie independente de numrul de procesoare din sistem. Paralelismul reprezint rezultatul exploatrii concurenei pe o platform paralel. Rolul modelului de programare este acela de a exprima concurena, ntr-un mod independent de platform. Este sarcina compilatorului i a mainii hardware s decid cum s exploateze concurena, prin procesri paralele. Gradul de abstractizare al modelului de programare trebuie ales prin prisma compromisului optimal ntre productivitatea i eficiena programrii paralele. Aceste modele trebuie s pun n evidena paralelismele inter-thread-uri, alocrile de memorie, accesul la zonele

7

de date partajate i modurile de sincronizare. Ingineria programrii se focalizeaz n continuare pe corectitudinea i pe reutilizarea codului, pe productivitatea dezvoltrii dar nu i pe exploatarea paralelismelor. Se estimeaz c n viitorul apropiat, circa 10% dintre programatori vor dezvolta programe paralele n mod explicit. Actualmente aceste modele de programare paralel sunt nesatisfctoare, conducnd la o programare, testare i depanare extrem de dificile. Spre exemplu, standardul Posix este considerat ca fiind puin flexibil i de nivel jos. Standardul OpenMP nu exploateaz localitatea datelor. De asemenea, modelele de programare actuale nu iau n considerare eterogenitatea arhitecturii. n plus, scalabilitatea acestor modele este una sczut. Productivitatea actualelor paradigme de programare paralel (shared memory - memorie partajat respectiv message passing - memorie distribuit logic) este una sczut. Astfel, de exemplu, metodele actuale de sincronizare, bazate pe seciuni critice atomice (excluziune mutual prin lock/unlock), nu mai sunt fezabile, fiind nevoie de metode noi, mai productive. In acest sens, conceptul de memorie tranzacional (Transactional Memory - TM) pare a fi unul promitor, dei cercetrile sunt nc ntr-un stadiu incipient. Tranzacia constituie o secven de cod care se execut atomic, n mod speculativ, prin mai multe citiri i/sau scrieri la nivelul unei memorii partajate. Rularea programului nu ine cont de seciunile critice. Dac apar conflicte la nivelul variabilelor partajate accesate de fire multiple, rezidente pe diferite procesoare, aceste conflicte se vor detecta i firul violat i va relua execuia tranzaciei n mod corespunztor (roll-backs). Aadar gestiunea coerenei nu se mai face la nivelul fiecrei scrieri aferente unei variabile partajate, ci la nivelul unor pachete atomice, fiecare pachet coninnd mai multe astfel de scrieri. Tranzacia este atomic (se execut dpdv logic n totalitate sau deloc), consistent (dpdv al variabilelor partajate inter-tranzacii) i durabil (odat nceput, nu mai poate fi abortat). TM simplific tehnicile de excluziune mutual din programarea paralel. Avantajul principal al conceptului de TM nu o constituie att performana rulrii, ct corectitudinea acesteia, chiar i n condiiile n care programatorul (compilatorul) efectueaz n mod eronat paralelizarea aplicaiei. Productivitatea i facilizarea programrii constituie alte obiective importante asociate acestui concept. Probabil c cercetrile n domeniul TM trebuie s abordeze scheme hibride, de tip hardware-software. Aceste cercetri trebuie dezvoltate n paralel cu extensia i optimizarea setului de instruciuni main (ISA Instruction Set Architecture) i a interfeei hardware-software, n vederea facilizrii programrii paralele. n lucrarea [Ham04], cercettori de la Stanford propun un nou model de memorie partajat, numit Transactional memory Coherence and Consistency (TCC), practic o memorie tranzacional implementat n hardware. Aici, tranzaciile atomice sunt ntotdeauna unitile de baz ale procesrii paralele. TCC trebuie s grupeze, n hardware, toate scrierile dintr-o tranzacie, ntr-un singur pachet. Acest pachet se trimite n mod atomic la memoria partajat, iar scrierile variabilelor partajate se efectueaz la finele execuiei tranzaciei (commit). Se controleaz prin hardware roll-back-urile tranzaciilor procesate n mod speculativ. Aceste tranzacii speculative necesit roll-back atunci cnd mai multe procesoare ncearc s citeasc i s scrie, n mod simultan, aceeai dat. Protocoalele de coeren de tip snoopy se implementeaz la nivelul acestor tranzacii atomice i nu la nivelul scrierilor individuale. Ele permit detecia faptului c tranzacia curent a utilizat date care au fost deja modificate de o alt tranzacie (dependence violation), i deci, este necesar roll-back-ul tranzaciei n curs. n consecin, consistena secvenial se implementeaz la nivelul tranzaciilor, care se vor termina n ordinea secvenial a programului original, i nu la nivelul scrierilor individuale. ntreeserea ntre

8

scrierile diferitelor procese este permis numai la nivelul tranzaciilor. Acest model TCC impune la nivelul programatorului s insereze explicit tranzaciile n codul surs, ca pe nite regiuni paralelizabile. Aceste tranzacii pot fi rafinate iterativ i adaptiv, n urma diferitelor rulri ale programului. Evident c o anumita tranzacie nu poate separa un Load de un Store succesiv, care acceseaz aceeai variabil partajat ca i Load-ul. O alt provocare, extrem de importanta, o constituie dezvoltarea unui model de programare care s permit utilizarea transparent i simultan att a modelului cu memorie partajat ct i a celui cu memorie distribuit. Ceva ncercri n acest sens se regsesc n limbajele Co-Array Fortran, UPC, X10, Fortress, Chapel etc. [HiPEAC]. De asemenea, sunt necesare mecanisme novatoare care s permit compilatorului i sistemului run-time s optimizeze structurile de date partajate, adaptndu-le la condiiile execuiei. Ideea de esena este c o structura de date partajat s fie distribuit automat n sistem. Cercetrile n domeniul arhitecturilor reconfigurabile, n special n lumea embedded, sunt i ele extrem de necesare ntruct aceste arhitecturi se pot adapta n mod static sau/i dinamic mai bine la cerinele aplicaiei specifice. Avantajul limbajului Java n arhitecturile multiprocesor const n faptul c implementeaz n mod nativ conceptul de fir de execuie. Din acest motiv, cercetrile n domeniul sistemelor multicore care utilizeaz procesoare capabile s execute direct n hardware bytecode-urile Java, sunt deosebit de utile, n special n lumea sistemelor dedicate. Este necesar suport hardware pentru programarea paralel, inclusiv pentru depanarea programelor paralele prin monitorizarea execuiilor. Depanarea unor sisteme multi-core cu sute de thread-uri procesate n limbaje native diferite, de ctre procesoare neomogene, este o problem deschis de mare actualitate i interes. O singura sesiune a depanrii trebuie s vizualizeze toate instruciunile main, informaii legate de variabile i funcii, punerea n evidenta a erorilor de comunicare ntre module dar i a erorilor locale etc. Evitarea violrilor de timing n cazul sistemelor n timp real avnd constrngeri tari (Worst Case Execuion Time) i a erorilor de execuie avnd cauze incerte (Heisenbugs), constituie provocri majore. Fr ajutorul hard-ului, care s ofere o viziune global a strii mainii multicore, asemenea cerine par imposibil de ndeplinit. Proiectarea hardware trebuie s aib n vedere deci i observabilitatea rulrilor multiple, fr a genera ns prea mari cantiti de date nerelevante. Paralelizarea aplicaiilor Paralelizarea automat constituie un obiectiv maximal, vizat de vreo 40 de ani de cercetri asidue. n acest sens s-au obinut realizri notabile, ndeosebi n paralelizarea automat a programelor tiinifice scrise n limbaje orientate pe vectori (Fortran, Matlab etc.) i pentru arhitecturi omogene cu memorie partajat, n special din lumea embedded. Aceste realizri trebuie extinse la tipuri ct mai diverse de aplicaii, la limbaje bazate pe pointeri i la sisteme multiprocesor eterogene, cu diferite modele de memorie. n acest scop sunt necesare, n special, tehnici statice noi de analiz a programelor scrise n limbaje bazate pe pointeri. O alt direcie insist pe limbajele orientate pe domenii, unde punerea n eviden a concurenelor este mai facil dect n cele de uz general. Paralelizrile speculative, incluznd aici tehnici de multithreading speculativ, vor juca un rol tot mai important. Planificarea dinamic a thread-urilor n vederea optimizrii comunicaiilor i sincronizrilor este deosebit de important. Astfel, de exemplu, n [Gio09] autorii dezvolt o aa numit Decoupled Threaded Architecture (DTA) n

9

vederea exploatrii paralelismelor fine i medii la nivel TLP n cadrul nor sisteme many-core eterogene. Comunicaiile i sincronizrile ntre fire sunt interesante, fcndu-se pe un model de tip flux de date (data-flow) i prin mecanisme de sincronizare de tip non-blocking. La crearea unui fir, acestuia i se asigneaz un numrtor de sincronizare (SC), reprezentnd numrul datelor de intrare pe care firul trebuie s-l primeasc de la alte fire. Acest numrtor este decrementat de fiecare dat cnd firul primete o astfel de dat n memoria sa local, destinat comunicaiilor inter-fire. Cnd SC-ul firului a ajuns la zero, se va starta execuia firului respectiv prin ncrcarea datelor din memoria local n registre. Din pcate, metodologia de simulare din aceast lucrare este una superficial. De asemenea, transmiterea de ctre compilator a unor informaii de semantic a aplicaiei ctre sistemul multicore pe care aceasta va rula, ar putea conduce la optimizri semnificative n procesarea aplicaiei. Simularea ca instrument de cercetare Sunt necesare metode de simulare adecvate, stpnirea complexitii cercetrii-dezvoltrii sistemelor multicore, inclusiv prin simulare tranzacional, Transaction-Level Modeling - TLM, precum permite mediul de dezvoltare pentru sisteme multicore UniSim, v. - www.unisim.org. Astfel, metoda TLM lucreaz la un nivel de abstractizare superior celui utilizat la nivelul simulrii ciclu cu ciclu. Aici, simulrile se focalizeaz preponderent pe comunicaiile ntre modulele componente. Este important simularea ntregului sistem de calcul, inclusiv a sistemului de operare, cu toate nivelurile ierarhice funcionale pe care acesta le deine (full-system simulation FSS, exemple: M5, Simics, GEMS etc.). Simulatoarele monolitice, gen SimpleScalar, M-Sim, etc., vor fi nlocuite cu simulatoare modulare, care s exploateze actualele tehnici ale ingineriei programrii obiectuale, n vederea facilizrii scrierii programelor i a reutilizrii codului (exemple SystemC, Liberty, MicroLib, GEMS, SimFlex, M5, UniSim sau ASIM). O idee important n acest sens const n maparea facil, intuitiv, a blocurilor hardware pe modulele (funciile, clasele) software ale simulatorului. Prin instanierea acestor blocuri i specificnd conexiunile lor, se poate realiza o dezvoltare ierarhizat a sistemului multicore. Astfel, dezvoltarea proiectului va fi una mult mai facil dect ntr-un mediu monolitic de simulare. Calitatea unui simulator de sisteme multicore este dat de caracteristici precum: posibiliti de dezvoltare (modularitate), benchmark-uri & compilatoare, posibiliti full-system simulation, tipuri de procesoare oferite, caracteristici multiprocesor oferite (UMA/NUMA, protocoale de coeren, reele interconectare, modele de programare pe care le pune la dispoziie, modele de consisten etc.), facilitate de calcul putere/temperatur, vitez de simulare, acuratee de simulare, gradul de parametrizare (flexibilitatea arhitectural). Un simulator pentru sistemele multicore care simuleaz ntregul sistem de calcul este Simics (Virtutech - v. http://www.virtutech.com). Acesta ofer un set larg de procesoare (Alpha, ARM, MIPS, PowerPC, SPARC, x86-64) i interfee. Simics poate ncrca i rula sisteme de operare precum Linux, Solaris, Windows XP. Poate virtualiza maina int n sisteme multiprocesor, clustere de procesoare sau reele. Un simulator pentru sistemele multicore, dezvoltat n mediul academic american, este RSim - v. http://rsim.cs.uiuc.edu. Implementeaz o memorie partajat distribuit fizic (fiecare procesor avnd o memorie local) i protocoale de coeren de tip directory (MSI, MESI). Ofer procesoare superscalare puternice cu execuii out-of-order i arhitecturi complexe de memorie (CC-NUMA), inclusiv cu posibiliti de adresare intreesut. Comunicarea ntre procesoare se face prin intermediul unei reele bidimensionale, de tip plas. De asemenea, ofer suport pentru implementarea consistenei secveniale sau chiar a unor modele mai relaxate. Un

10

alt simulator interesant, la nivel de ciclu main (emulator de arhitectur MIPS), destinat sistemelor multicore cu un numr configurabil de nuclee, este SESC, http://sesc.sourceforge.net. Acesta deine un modul de calcul al timing-ului de mare acuratee. M5 este un FSS-simulator dezvoltat n tehnologia programrii pe obiecte (C++), permind deci instanierea facil a modulelor sistemului multiprocesor. Conine modele pentru procesoarele Alpha, MIPS, ARM i SPARC. Implementeaz ierarhii complexe de cache cu protocoale de coeren de tip snoopy. ncarc sistemele de operare Linux i Unix (Solaris). Permite 3 moduri de lucru n vederea compromisului ntre viteza de simulare i acurateea simulrii. n domeniul sistemelor multicore dedicate aplicaiilor multimedia, simulatorul Sesame dezvoltat la Universitatea din Amsterdam este unul cunoscut i apreciat. O alt problem major const n viteza simulrilor. La ora actual, simularea cu acuratee total a unui sistem monoprocesor real, la nivel RTL Register Transfer Logic, necesit n jur de o zi de simulare, pe sisteme performante! Pentru sisteme multicore acest timp de simulare va crete cel puin ntr-o maniera liniar. Avnd n vedere complexitatea enorm a simulrilor de tip cycle by cycle, care le face nefezabile pentru optimizarea unor sisteme cu sute de nuclee integrate, exist un mare interes inclusiv pentru dezvoltarea unor metode de simulare la nivel de tranzacii sau chiar a unor metode analitice de optimizare. Se au n vedere inclusiv metode de simulare statistic, bazate pe eantioane reprezentative ale procesrii (sampling simulation). Ideea de esena aici const n selectarea unor subseturi ale benchmark-urilor avnd un comportament suficient de similar cu cel al ntregului set de benchmark-uri. O bun sintez a cercetrilor din acest domeniu se gsete n [Yi06]. Se pune problema extragerii caracteristicilor benchmark-urilor n urma rulrii i construcia unor benchmark-uri sintetice avnd aceleai caracteristici, reprezentative i mai scurte (statistical simulation). O alt soluie n vederea reducerii timpului de simulare const n paralelizarea simulatorului i rularea lui pe sisteme multicore performante precum IBM Cell BE de exemplu. O alt soluie n vederea reducerii timpului de simulare o constituie clasificarea / clusterarea prin metode statistice a benchmark-urilor. n fine, o alt provocare important o constituie mbuntirea acurateii simulrilor prin metodologii specifice. Acurateea relativ a simulrilor poate fi mai important dect acurateea absolut a acestora, n fazele incipiente ale proiectului. Benchmarking Ca metodologie de cercetare-dezvoltare se impune tot mai mult proiectarea hardware-software integrat (hardware-software co-design). Tot aici se pune problema dezvoltrii unor metode de benchmarking adecvate evalurii sistemelor de tip multicore. Problema este una extrem de delicat, ntruct companiile i protejeaz atent aplicaiile comerciale. Astfel, n locul uzitatelor benchmark-uri (SPEC pentru procesoare de uz general, EEMBC i MiBench pentru sisteme dedicate, Mediabench, ALPBench pentru sisteme multimedia, TPC pentru baze de date, Livermoore, Parsec, SPLASH 2 pentru sisteme cu paralelism masiv etc.) s-au propus aa numitele dwarfs, constnd n metode algoritmice tipice calculului paralel care s conin att pattern-uri computaionale ct i, mai ales, pattern-uri de comunicaie ntre nucleele componente [Asa06]. i totui, problema rmne una deschis, cu multe semne de ntrebare (spre exemplu, benchmarking-ul trebuie s in cont i de tendina accentuat a virtualizrii, ca i metod esenial n asigurarea compatibilitii i portabilitii.)

11

Automatic Design Space Exploration

Se pune problema dezvoltrii unor metode de cutare euristic optimizat n spaiul enorm al parametrilor aplicaiilor i arhitecturii cercetate - Automatic Design Space Exploration (ADSE). Spre exemplu, proiectarea unui 4-core n care fiecare nucleu poate fi ales dintr-o bibliotec coninnd 480 de modele, impune evaluarea a peste 2.2 miliarde de posibiliti! Dac evaluarea fiecrei posibiliti ar necesita o zi, evaluarea tuturor posibilitilor ar necesita aproape 1 milion de ani. Relativ la aplicaii, se au n vedere transformrile algoritmice i de limbaj ce pot crete gradul de paralelism TLP. Scopul este evident, anume determinarea acelor parametri care conduc la optimizarea raportului performan/cost (IPC, energie, arie de integrare etc.) Optimizrile au deci obiective multiple. Evident c nu se pune problema cutrii complete n spaiul enorm al tuturor parametrilor arhitecturii sau/i aplicaiilor investigate. Tehnici din domeniile nvrii automate (machine learning), a cercetrilor operaionale ori data mining ar putea fi utile, n vederea reducerii spaiului de cutare i deci, a reducerii numrului de simulri. Aceste metode de optimizare automat a parametrilor arhitecturii se vor integra sub forma unor API-uri n cadrul simulatoarelor dezvoltate. Tot aici, sunt necesare tehnici euristice, inspirate din domeniul machine learning, n vederea optimizrii incrementale a compilrii. Ideea este c programul s se adapteze la schimbrile din hardware (spre ex. creterea numrului de procesoare) dar i la evenimentele dinamice care apar pe parcursul procesrii (spre exemplu miss-uri n cache). La ora actual, nu exist un instrument ADSE matur, care s fie larg folosit n optimizarea sistemelor de calcul. Obiectivele constau n creterea performanei, dar i n reducerea consumului de putere (att dinamic ct i static). Evident c n acest sens sunt necesare informaii de feedback, captate n urma rulrilor aplicaiei. Este necesar deci o abordare mai strns ntre cercetrile n domeniul microarhitecturilor i cel al compilatoarelor (compiler-architecture co-design). Compilatorul trebuie s poat manipula infrastructura microarhitecturii, n timp ce aceasta trebuie s beneficieze de informaiile transmise ei prin intermediul ISA, de ctre compilator. Din pcate, este foarte dificil trecerea de la actualele compilatoare, orientate pe exploatarea ILP, la compilatoare noi, orientate pe exploatarea TLP i a paralelismelor la nivelul task-urilor. Totodat, aceast abordare holistic este una mare consumatoare de timp. n scopul reducerii timpului de proiectare integrat a dualitii arhitectur-compilator, se dezvolt modele bazate pe nvare automat, care pot prediciona performana unui compilator optimizat pentru o anumit arhitectur, fr ca s l construiasc efectiv. Modelele folosesc ca intrare o parte infim din spaiul parametrilor compilator-arhitectur. Avem aadar nevoie de tehnici inteligente i eficiente de cutare n spaiul enorm de parametri ai sistemului. Adaptarea tehnicilor de cutare-optimizare din domeniul nvrii automate a fost investigat de ctre muli autori. n [Suk07], spre exemplu, autorii dezvolt un instrument complex de accelerare a DSE pentru arhitecturi multicore, numit Magellan. Acesta determin parametrii cvasioptimali, cei care maximizeaz rata de procesare pentru un buget prestabilit al ariei de integrare i puterii disipate. Magellan folosete algoritmi euristici de cutare de tip hill climbing, genetici, stigmergici etc. Clasificarea soluiilor i a benchmark-urilor funcie de caracteristicile acestora, poate accelera cutarea. Algoritmul Steepest Ascent Hill Climbing (SAHC) implic n acest caz, cutarea n vecintatea celui mai bun k-procesor curent. Un procesor vecin este un procesor care difer de cel curent, prin valoarea unui singur parametru. Urmtorul procesor optimal este ales ca fiind cel mai bun

12

vecin, dac este superior procesorului curent. Algoritmul se oprete n proximul punct de extrem. Avantajul principal al acestui algoritm simplu const n rapiditatea convergenei. Dezavantajele constau n complexitatea exponenial cu numrul de core-uri (k) i n posibilitatea eurii n extreme locale. Evident, rafinamente ale acestui algoritm au fost propuse i investigate (spre exemplu, algoritmi tip annealing search SAHC + alegere random). Algoritmul genetic (AG) utilizeaz printre ali operatori i operatorul de reproducere, care transfer n populaia urmtoare vecinul cel mai bun. Se asigur astfel c algoritmul este cel puin la fel de bun ca SAHC. Operatorul crossover genereaz noi procesoare, prin combinarea a dou procesoare din populaie. Se implementeaz i mutaia, care modific aleator numrul de nuclee. n implementarea citat se pstreaz n populaia urmtoare doar cele mai bune 4 soluii. Astfel, algoritmul scaleaz foarte bine cu creterea numrului de nuclee (k), evalund doar 4 k-procesoare ntr-o iteraie. Nu exist la acest moment o soluie optimal de oprire a algoritmului. Algoritmii stigmergici se bazeaz pe comportamentul furnicilor din lumea real (ant colony optimizations - ACO). n cutarea hranei, furnicile marcheaz drumurile cu feromoni, astfel nct traseele s poat fi urmate i de alte furnici. Feromonii se evaporeaz n timp, eficientiznd astfel cutarea (spre exemplu se evit explorarea unor ci devenite, ntre timp, fr de succes.) Autorii foreaz cutarea pe cte o cale diferit n fiecare iteraie, prin pornirea cutrii de la o soluie situat n vecintatea celei precedente. Se evit astfel euarea n extreme locale, explorndu-se ns mai mult spaiul soluiilor. Concluzia acestor cercetri a artat c aceste tehnici euristice de explorare sunt cel puin de 3800 de ori mai rapide dect cutarea exhaustiv, genernd soluii cu maximum 1% mai puin performante dect aceasta, fapte remarcabile. Scalabilitatea este de asemenea asigurat. Dac n tiinele tari, mature din punct de vedere teoretic precum fizica sau biologia, posibilitatea reproducerii rezultatelor experimentale constituie o condiie sine qua non, n arhitectura calculatoarelor acest lucru este de multe ori imposibil, datorit faptului c nu exist o metodologie standardizat a cercetrii. n cadrul cercetrilor dintr-o companie, simularea modulara ar putea constitui o soluie, dac toi cercettorii ar folosi acelai simulator. Din pcate, la nivelul cercetrilor academice ori la nivel global inter-companii, aceast abordare este, practic, imposibil. n [Des08] se prezint o metodologie automat de optimizare euristic a parametrilor unei microarhitecturi (ADSE), implementat sub forma unui site web numit ArchExplorer.org. Aceasta este oarecum independent de simulatorul care implementeaz blocul hardware ce se dorete a fi optimizat, chiar dac, evident, l utilizeaz pentru cutarea n spaiul enorm al parametrilor afereni arhitecturii dar i compilatorului. Desigur c integrarea simulatorului corespunztor unui anumit bloc hardware (de tip cache, TLB, predictoare de branch-uri, module DRAM, uniti funcionale, reele de interconectare etc.) n ArchExplorer.org este mai facil dac acesta are deja o construcie modular, cu interfee bine definite ntre module (analoage API-urilor), compatibile cu cele definite n ArchExplorer.org. Un astfel de simulator este UniSim. Metodologia de explorare a spaiului parametrilor arhitecturali utilizat n [Des08] se bazeaz pe algoritmi genetici. Fiecare modul are asociat o gen, iar aceasta la rndul ei, deine mai multe sub-gene, codificnd parametrii modulului. Din pcate, modelarea operatorilor genetici utilizai nu este clar explicitat n lucrare. n cadrul ADSE, relaia arhitectura-compilator, dei subtil, este una puternic i adesea subestimat de ctre cercettori.

13

Modificrile arhitecturale pot produce modificri importante n strategiile de optimizare din compilator, dar i reciproc. Dac pentru un compilator neoptimizat performanele procesorului sunt mai bune pentru setul de parametri P1 dect pentru P2 atunci este posibil ca folosind un compilator optimizat pentru P1 respectiv P2, performanele n punctul P2 s fie mai bune dect n P1. Interesant este faptul c mediul ArchExplorer.org ofer o explorare continu a spaiului strilor pe un web-server special dedicat. O alt platform web DSE este implementat prin proiectul colaborativ intitulat cTuning.org - http://ctuning.org/wiki/index.php/Main_Page, care ofer n mod gratuit utilizatorilor o tehnologie inteligent n vederea optimizrii ansamblului arhitectur-compilator-aplicaie, pe baza unor metode din teoria nvrii statistice i automate. Se poate accesa o baz de date (Collective Optimization Database) care conine detalii asupra optimizrilor aplicate unor sisteme de calcul complexe. Accesarea acestei baze de date ofer utilizatorilor i posibilitatea schimbului reciproc de experiene, viznd optimizri interesante, pentru diferite aplicaii i respectiv platforme utilizate pentru rularea acestora. n principiu, oricine poate s-i optimizeze n mod automat, cu instrumentele puse la dispoziie, o anumit aplicaie sau benchmark. Trebuie specificate arhitectura hardware, sistemul de operare i compilatorul utilizate, urmnd ca apoi serviciul web cTuning.org s ncerce optimizarea parametrilor acestora, n vederea obinerii unui timp minimal de execuie dar i a unei lungimi ct mai mici a codului surs. n final, se genereaz automat parametrii optimali afereni procesorului, compilatorului (parametrii de optimizare a codului surs), sistemului de operare i aplicaiei. De asemenea se determin i ctigurile (performan, lungime de cod) obinute fa de un compilator GCC standard. Proiectul FP7 intitulat MultiCube se ocup i el de asemenea cercetri. Arhitecturi multicore cu procesri anticipative Puine sunt cercetrile care analizeaz tehnicile Value Prediction (VP) i Dynamic Instruction Reuse (DIR) [Vin07], n cadrul procesrii firelor concurente pe procesoare SMT (Simultaneous Multithreading) sau multicore (personal nu cunosc nici o cercetare pe problematica grefrii DIR n multicores). De aceea grupul nostru de cercetare dorete s activeze n aceasta ni, unde avem deja realizri apreciate (a se vedea http://acaps.ulbsibiu.ro/research.php). n asemenea arhitecturi, a prezice valoarea unei instruciuni i apoi, a verifica predicia, dup ce valoarea a fost produs, nu este ntotdeauna suficient. Mai mult, acest proces poate chiar implica erori de consisten a variabilelor predicionate. Astfel spre exemplu, n unele cazuri predicia poate s fie corect, dar execuia incorect datorit violrii consistenei unor variabile. n [Mar01] se exemplific n mod convingtor asemenea anomalii pe baza unui exemplu ce descrie un fir care insereaz un element (nod) n capul (head) unei liste simplu nlnuite. Problema este c, nainte de a insera noul nod n capul listei, firul i modific valoarea. Un alt fir, citete primul element al listei. Aceasta citire, bazat pe o VP corect, poate fi ns eronat. ntre predicia valorilor i problema consistenei cache-urilor n sistemele multiprocesor exist legaturi subtile, neexplorate nc n mod aprofundat. Instruciunile cu laten ridicat reprezint o surs de limitare a paralelismului la nivelul instruciunilor. n [Gel09] am prezentat dezvoltarea un mecanism de anticipare selectiv a valorilor instruciunilor cu laten ridicat de execuie, care include o schem de reutilizare pentru instruciunile Mul i Div, respectiv un predictor de valori pentru instruciunile Load

14

critice, adic cele cu miss n ierarhia de cache-uri. Rezultatele simulrilor efectuate, au artat creteri de performan (IPC) de 3,5% pe benchmark-urile SPEC 2000 ntregi respectiv 23,6% pe cele flotante i o scdere important a consumului relativ de energie (a EDP-ului), de 6,2% pe ntregi respectiv 34,5% pe flotante. Dup ce am artat utilitatea anticiprii selective a instruciunilor cu laten ridicat ntr-o arhitectur superscalar, am analizat eficiena acestor metode i ntr-o arhitectur SMT, focalizndu-ne pe aceleai instruciuni: Mul i Div respectiv Load-uri critice. n acest context firele de execuie coninnd Load-uri critice ori alte instruciuni de latena ridicat pot bloca resursele partajate ale procesorului i, n consecin, pot bloca celelalte fire i deci, pot reduce performana global. Rezultatele au artat mbuntiri ale IPC pe toate configuraiile SMT evaluate. Cu ct numrul de fire este mai mare, cu att creterea de performan devine ns tot mai puin semnificativ, datorit exploatrii tot mai eficiente a unitilor de execuie partajate de ctre procesorul SMT. Plastic spus, cu motorul SMT mergnd n plin, sporul de performan aferent tehnicilor anticipative implementate adiional devine mai mic. Cele mai bune performane medii, de 2,29 IPC pe benchmark-urile de numere ntregi respectiv de 2,88 IPC pe cele flotante, s-au obinut cu ase fire de execuie. In [Cra09] autorii se ocup tot de problema instruciunilor Load critice n arhitecturile SMT, ns abordarea lor este una diferit de a noastr. Ideea de baz este ca la detecia unui Load critic, n anumite condiii, s se declaneze execuia speculativ a instruciunilor urmtoare n scopul exploatrii paralelismelor la nivelul memoriei prin procese de pre-fetch (MLP Memory Level Parallelism). Gradul de MLP este dat de numrul de accese independente la memorie. Evident c un astfel de Load de mare laten va genera automat un checkpoint, salvnd deci starea curent a procesorului (regitrii logici, istoria branch-urilor etc.). Execuia anticipat a instruciunilor care urmeaz unui Load critic, n cadrul unui anumit fir, se face numai dac gradul de MLP estimat este unul suficient de ridicat. n plus, ele nu vor afecta starea arhitectural (logic) a procesorului. Exist implementat cte un predictor dinamic al gradului de MLP per thread. Acesta estimeaz gradul de MLP, dup detectarea run-time a fiecrei instruciuni Load critice. n caz contrar (grad MLP redus), firul respectiv este rejectat din procesor, evitnd astfel blocarea resurselor partajate ale acestuia. n cadrul procesrii speculative, unele instruciuni independente de Load-ul critic pot cauza miss-uri n ierarhia de cache-uri. Latena acestora se suprapune peste cea a Load-ului critic aflat n curs de execuie. Astfel se exploateaz gradul de MLP existent n programe. Cnd un Load critic se ncheie, procesorul iese din modul speculativ de execuie, golete pipe-urile, restaureaz checkpoint-ul i reia procesarea normal, cu instruciunea urmtoare Load-ului. Aceasta execuie normal se va face mai rapid avnd n vedere aducerile anticipate n cache-uri, efectuate pe parcursul execuiilor speculative. Aadar performana per thread crete. Foarte important, aceasta execuie speculativ a instruciunilor evit blocajul procesrii n momentul n care un Load critic a atins vrful Reorder Buffer-ului (reducnd deci Memory Wall-ul). Se arat c aceast arhitectur duce la beneficii considerabile, n special n cazul unor programe care lucreaz intensiv cu memoria. Asemenea idei merit aprofundate, mbuntite i investigate n continuare. Un studiu comparativ ntre aceste dou abordri, care urmresc reducerea influenei instruciunilor Load critice ntr-o arhitectur SMT, ar fi unul interesant i util. Desigur, comparaia trebuie efectuat multicriterial (IPC, energie consumat, disipaie termic, arie de integrare etc.) Mediul de simulare utilizat ar putea fi M-Sim ntruct permite i calculul puterii (prin simulatorul Wattch pe care l conine) i, totodat, l-am folosit deja n dezvoltarea arhitecturii SMT mbuntite prin

15

anticiparea valorilor instruciunilor critice. Astfel, sperm s obinem rezultate interesante ntr-un timp rezonabil. Grefarea unor asemenea tehnici anticipative precum cele de reutilizare dinamic a instruciunilor sau de predicie dinamic a instruciunilor n cadrul arhitecturilor multicore i manycore reprezint o problem de mare interes n opinia noastr. Implementarea unor scheme de VP i DIR care s nu violeze consistena variabilelor partajate n sisteme SMT i multicore este o problem de mare interes. Dup cum se arat n literatura de specialitate, chiar benchmark-urile paralele (SPLASH-2, PARSEC etc.) nu conin suficient paralelism pentru sistemele multiprocesor moderne [Liu08]. n aceste condiii, creterea performanei poriunilor secveniale de cod peste bariera impus de celebra lege a lui Gene Amdahl (practic, bariera generat de dependenele de date ntre instruciuni), se poate realiza prin anticiparea rezultatelor instruciunilor (nainte ca acestea s fie produse, nc din faza de decodificare). Aceste tehnici anticipative vor reduce semnificativ accesele la reeaua de interconectare n vederea comunicrii prin variabile partajate. La ora actual, influena prediciei dinamice a valorilor i, cu att mai puin a reutilizarii dinamice a instruciunilor, sunt departe de a fi nelese n cadrul sistemelor SMT sau multiprocesor. Acest fapt este valabil chiar i la nivel teoretic-principial, dup cum vom arta n continuare printr-un exemplu simplu. Este binecunoscuta legea lui Amdahls pentru un sistem MIMD cu N procesoare:

N

f)(1f

1S(N)

+

= (3)

In [Liu08] autorii ncearc s generalizeze aceasta formul, la un sistem paralel cu predicia valorilor instruciunilor. Notnd cu p acurateea medie a prediciei valorilor instruciunilor, autorii obin relaia de mai jos:

N

f)-(1fpp)-f(1

1Svp(N)

++

= (4)

Aceasta relaie, n opinia noastr, nu este corect. Pentru N=1 (monoprocesor) Svp(1)=1, ceea ce ar nsemna c tehnica de predicie a valorilor n sistemele monoprocesor nu ar aduce nici un avantaj. n mod evident, aceast afirmaie este fals. Aa cum s-a artat n [Gab98, Vin07],

considernd un program pur secvenial (f=1), ctigul de performan este n acest caz p1

1.

O formula corecta pentru Svp(N) trebuie s in cont c:

f(1-p) [%] din program este procesat n acelai timp n care ar face o main secvenial (SISD) echivalent.

fp [%] din program s-ar procesa teoretic instantaneu din cauza prediciei perfecte a valorilor instruciunilor.

(1-f) [%] din program s-ar procesa teoretic de N ori mai rapid dect pe maina secvenial.

In aceste condiii formula corect este:

16

N

f)-(1p)-f(1

1Svp(N)

+

= (5)

Pentru N=1 rezult:

Svp(1)=fp1

1 1. (6)

Particulariznd f=1 n formula precedent, n perfect acord cu [Gab98], rezult:

S=p1

1 (7)

Implementarea unor mecanisme DIR n arhitecturile multicore impune ca invalidrile din cadrul buffer-ului de reutilizare (Reuse Buffer RB) aferent procesorului considerat, s fie efectuate n mod global, deci inclusiv de ctre instruciuni Store executate de ctre un alt procesor, care scrie la o adres existent n RB-ul procesorului considerat. Mecanismele globale de asigurare a coerenei cache-urilor bazate pe invalidri la scrieri, ar putea ajuta la meninerea consistenei datelor din buffer-ul de reordonare. Invalidarea unei date din cache-ul de date ar trebui s determine automat invalidarea datei din RB, dac aceasta este stocat i acolo. Paradigma de procesare pe baza fluxurilor de date (Data-Flow, DF) gsete adepi i n domeniul multiprocesoarelor. Modelul DF, dezbtut puternic n anii 80, reprezint un model formal distribuit, inerent paralel, funcional i asincron. Execuia ntr-un nod starteaz de ndat ce toate datele de intrare sunt disponibile. Programul se reprezint sub forma unui graf n care nodurile reprezint operaii iar arcele reprezint sursele (cile) de date. Modelul Data Driven Multithreading (DDM), relativ nou, exploateaz modelul DF la nivelul firelor de execuie, n cadrul unor arhitecturi multicore. Modelul DDM se bazeaz pe conceptul paralelizrii automate la nivelul hardware software, incluznd tehnici de reprezentare poliedral a programelor. Actualmente se cerceteaz ansambluri multicore tip DDM compilator, att la nivel de virtualizare ct i la nivelul unor implementri FPGA. Putere consumat, disipaie termic Un obiectiv important const i n grefarea unor module care s calculeze automat puterea disipat i disipaia termic pe procesorul nostru SMT, mbuntit cu predicia valorilor instruciunilor Load critice (cu miss n L2 cache) respectiv cu reutilizarea instruciunilor de laten ridicat (Mul/Div etc.). Astfel, pentru calculul puterii statice i dinamice, am putea utiliza n cadrul simulatorului SMT mbuntit de noi, simulatorul Wattch (http://www.eecs.harvard.edu/~dbrooks/wattch-form.html) care este deja integrat n mediul M-Sim utilizat. Acesta se bazeaz pe simulatorul SimpleScalar sim-outorder, ver. 3.0 i calculeaz puterea disipat pentru structuri de tip vector, structuri asociative de tip Reorder Buffer, Load Store Queue etc., logica combinaional (pt. partea de comenzi ale procesorului i uniti funcionale) etc. Astfel vom extinde calculul puterii disipate la ntregul procesor (pn n acest moment am calculat puterea doar la nivelul unor structuri regulate, de tip cache). De asemenea, ne va interesa i calculul puterii statice, n special n cadrul unor memorii de capaciti mari precum L2 caches. n particular, unii autori au integrat simulatorul Simics cu Wattch-ul i au implementat un simulator performant numit SimWattch (simuleaz inclusiv procesarea sistemului de operare + putere disipat).

17

Un modul pentru investigarea efectelor de disipaie termic aferente acestor tehnici, implementat ca un API al simulatorului M-Sim, ar fi de mare utilitate. Se tie c hotspot-urile conduc la erori de procesare iar temperatura prea mare micoreaz durata de via a circuitului. Este interesant de evaluat efectul acesteia n contextul noilor structuri anticipative pe care noi le-am introdus n arhitectura SMT M-Sim. n acest sens deja am startat un studiu, n cooperare cu Politehnica din Milano, asupra problemelor, metodologiilor i instrumentelor utilizate n cercetarea efectelor disipaiei termice i de energie n cadrul microprocesoarelor. Cele dou procese nu sunt corelate. Apoi, va trebui s interfam pe simulatoarele deja dezvoltate de noi, un software specializat n analiza disipaiei termice (de exemplu simulatorul HotSpot - v. http://lava.cs.virginia.edu/hotspot, larg utilizat i care nu necesit costuri de achiziie). n continuare, vom analiza aceste efecte n cadrul arhitecturilor deja dezvoltate de noi, pe diverse benchmark-uri (n special n cadrul arhitecturii SMT mbuntite cu DIR i VP selective). Analiza comparativ a hrilor termale, cu i fr mbuntirile arhitecturale propuse de noi, va fi deosebit de util. Pe baza puterilor dinamice calculate pentru fiecare modul ntr-un interval (ex. 10 kcicli), a frecvenei de tact, a tehnologiei de integrare i a geometriei de plasare a modulelor pe pastila de siliciu (floorplan, matrice de adiacent), HotSpot-ul va calcula densitatea de temperatur pentru fiecare modul. Unul dintre obiectivele acestei cercetri const n proiectarea unui run-time thermal manager adaptiv care s valideze-invalideze modulele de DIR i VP n funcie de comportamentul termic i energetic al modulelor microprocesorului. n acest scop exist deja elaborate mai multe strategii: oprirea tactului, adaptarea tensiunii de alimentare sau a frecvenei tactului funcie de temperatur, mutarea calculului n module de rezerv etc. Ideea de baz este aceea de a reduce densitatea de putere n punctele fierbini. Aceste cercetri vor fi apoi extinse pe noile simulatoare multicore pe care le vom dezvolta. Concluzii Am realizat un studiu asupra impactului arhitecturilor multicore i manycore n cadrul ingineriei calculatoarelor. S-a pornit de la geneza acestor sisteme, determinat de limitele paradigmei monoprocesor. S-au identificat i s-au analizat n mod sistematic, pe baza unei literaturi de specialitate recente, urmtoarele provocri importante pentru cercetarea i dezvoltarea acestor sisteme:

Arhitecturi multicore omogene vs. eterogene Exploatarea sinergic a tipurilor de paralelism Ierarhia de memorii cache Coerena i consistena variabilelor partajate Reele de interconectare Modele de programare paralel Paralelizarea aplicaiilor Simularea ca instrument de cercetare Benchmarking Explorarea automat a spaiului parametrilor Arhitecturi multicore cu procesri anticipative o idee original Putere consumat, disipaie termic

18

Concluzia de baz este c sunt necesare progrese importante n toate aceste domenii, pentru ca proiectarea i utilizarea sistemelor multicore i manycore s fie adecvate. Cu sau fr voia noastr, aceste sisteme vor constitui dispozitivele de calcul universale. Abordarea oricreia dintre aceste provocri trebuie s fie una de tip holistic. S-a artat cum vor schimba aceste noi arhitecturi, paradigma tiinei ingineriei calculatoarelor. n particular, programarea acestor sisteme constituie o provocare major, pentru care nu suntem nc pregtii suficient. Bibliografie selectiv

1. [Asa06] Asanovic K. et al., The Landscape of Parallel Computing Research: A View from Berkeley, Technical Report No. UCB/EECS-2006-183, December 2006

2. [Cra09] Craeynest K. Van, Eyerman S., Eeckhout L., MLP-Aware Runahead Threads n a Simultaneous Multithreading Processor, Proceedings of The 4th HiPEAC International Conference, pp. 110-124, Paphos, Cyprus, January 2009

3. [Cul99] Culler D., Singh J., with Gupta A., Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers, 1999

4. [Des08] Desmet V., Girbal S., Temam O., ArchExplorer.org: Joint Compiler/Hardware Exploration for Fair Comparison of Architectures, The 6-th HiPEAC Industrial Workshop, Thales, Paris, Nov. 26th, 2008

5. [Gab98] Gabbay F., Mendelsohn A., Using Value Prediction to Increase the Power of Speculative Execuion Hardware, ACM Transactions on Computer Systems, vol. 16, nr. 3, 1998

6. [Gel09] A. Gellert, A. Florea, L. Vintan, Exploiting Selective Instruction Reuse and Value Prediction n a Superscalar Architecture, Journal of Systems Architecture, vol. 55, issue 3, Elsevier, 2009

7. [Gio09] Giorgi R., Popovic Z., Puzovic N., Implementing fine/medium grained TLP support n a many-core architecture, International Symposium on Systems, Architectures, Modeling and Simulation, Samos, Greece, July 20-23, 2009

8. [Ham04] Hammond L. et al., Transactional Memory Coherence and Consistency, The 31st Annual International Symposium on Computer Architecture (ISCA), Munich, 2004

9. [Hen07] Hennessy J., Patterson D., Computer Architecture. A Quantitative Approach, 4th Edition, Morgan Kaufmann Publishers, 2007

10. [HiPEAC] High-Performance Embedded Architecture and Compilation (HiPEAC) FP6/FP7 Network of Excellence, Research Challenges n High-Performance Embedded Architecture and Compilation, http://www.HiPEAC.net, 2008

11. [Jor03] Jordan H., Alaghband G., Fundamentals of Parallel Processing, Pearson Education, Inc., Prentice Hall, 2003

12. [Liu08] Liu S., Gaudiot J. L., The Potential of Fine-Grained Value Prediction n Enhancing the Performance of Modern Parallel Machines, The 13th IEEE Aia-Pacific Computer Systems Architecture Conference (ACSAC 2008), Taiwan, August 2008

13. [Mar01] Martin M., et al., Correctly Implementing Value Prediction n Microprocessors that Support Multithreading or Multiprocessing, Proceedings of the 34-th Annual ACM/IEEE International Symposium on Microarchitecture, Austin, Texas, December 3-5, 2001

19

14. [Mog09] Moga A., Dubois M., A comparative evaluation of hybrid distributed shared-memory systems, Journal of Systems Architecture, vol.55, issue 1, pp. 43-52, Elsevier, 2009

15. [Suk07] Sukhun Kang and Rakesh Kumar, Magellan: A Framework for Fast Muti-core Design Space Exploration and Optimization Using Search and Machine Learning, Illinois at Urbana-Champaign, CRHC Technical Report CRHC-07-05, October 2007

16. [Vin07] Vinan L., Prediction Techniques n Advanced Computing Architectures (in limba engleza), Matrix Rom Publishing House, Bucharest, 2007; http://www.matrixrom.ro/romanian/editura/domenii/informatica.php?id=867#867

17. [Vin08] Vinan L., Florea A., Gellert A., Random Degrees of Unbiased Branches, Proceedings of The Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science, Volume 9, Number 3, Bucharest, 2008 - http://www.academiaromana.ro/sectii2002/proceedings/doc2008-3/13-Vintan.pdf

18. [Wat09] Watkins M., McKee S., Schaelicke L., Revisiting Cache Block Superloading, Proceedings of The 4th HiPEAC International Conference, Paphos, Cyprus, January 2009

19. [Yi06] Yi J., Lilja D., Simulation of Computer Architectures: Simulators, Benchmarks, Methodologies, and Recommendations, IEEE Transactions on Computers, vol. 55, No. 3, 2006