2 Predicţia dinamicăa valorilor în microprocesoarele generaţiei următoare

8/13/2019 2 Predicia dinamica valorilor n microprocesoarele generaiei urmtoare

1/412

CUPRINS

PREFA__________________________________________________5

1. INTRODUCERE N PROBLEMATICA MICROARHITECTURILORPREDICTIVEI SPECULATIVE ______________________________11

2. LIMITRI FUNDAMENTALE ALE PARADIGMEI ILP. SOLUII.202.1. LIMITAREA PRODUCTORULUI (FETCH BOTTLENECK).SOLUII. _____________________________________________________20

2.1.1. PROBLEMA N SINE __________________________________________ 202.1.2. SOLUIE: TRACE CACHE. TRACE PROCESOARE. ______________ 22

2.2. LIMITAREA CONSUMATORULUI (ISSUE BOTTLENECK).SOLUII. _____________________________________________________30

2.2.1. REUTILIZAREA DINAMICA INSTRUCIUNILOR _______________ 352.2.2. PREDICIA DINAMICA VALORILOR INSTRUCIUNILOR _______ 512.2.3. PROBLEME DE IMPLEMENTARE A PREDICIEI VALORILOR NARHITECTURI CU MICROFIRE MULTIPLE DE PROCESARE ____________ 89

3. METODOLOGIA DE SIMULARE____________________________94

3.1. BENCHMARK-URI UTILIZATE N SIMULARE.CARACTERISTICI. ____________________________________________94

3.1.1. BENCHMARK-URILE SPEC95._________________________________ 943.1.2. BENCHMARK-URILE SPEC2000. _______________________________ 953.1.3. ALTE BENCHMARK-URI: SPEC JVM98, MEDIABENCH. __________ 101

3.2. DEZVOLTAREA DE SIMULATOARE SUB MEDIULSIMPLESCALAR UTILIZND BENCHMARK-URILE SPEC. ______106

3.2.1. CE ESTE "SIMPLESCALAR TOOL SET" ? _______________________ 1073.2.2. AVANTAJELE UTILIZRII "SIMPLESCALAR TOOL SET". ________ 1083.2.3. DEZVANTAJE N UTILIZAREA SETULUI DE INSTRUMENTE

"SIMPLESCALAR". _______________________________________________ 1103.2.4. UTILITARE GNU.____________________________________________ 1113.2.5. INSTALAREA SETULUI DE INSTRUMENTE "SIMPLESCALAR". ___ 1123.2.6. SIMULATOARELE SETULUI DE INSTRUMENTE "SIMPLESCALAR3.0". ____________________________________________________________ 1143.2.7. COMPILAREA I EXECUIA PROGRAMELOR C I C++ SUB LINUX.INSTALAREA I COMPILAREA BENCHMARK-URILOR SPEC2000 PENTRUARHITECTURA SIMPLESCALAR PISA. ____________________________ 1243.2.8. FOLOSIREA DEBUGGER-ULUI GNU. __________________________ 132


2/412


3/412

Cuprins 3

5.3. CERCETRI PROPRII PRIVITOARE LA PREDICIASALTURILOR / APELURILOR INDIRECTE. ____________________248

5.3.1. PREDICTORUL PPM COMPLET. _______________________________ 2485.3.2.MBUNTIREA PERFORMANEI PREDICTORULUI TARGETCACHE. IMPLEMENTAREA UNUI MECANISM DE CONFIDEN. ______ 2565.3.3. PREDICIA SALTURILOR INDIRECTE:_________________________ 268

5.3.3.1. IMPLEMENTAREA PREDICTORULUI HIBRID CU SELECIEBAZATPE ARITATE.__________________________________________ 2685.3.3.2. PREDICTOR HIBRID CU SELECIE BAZATPE CONFIDEN.272

5.3.4. JIndirSim SIMULATOR FUNCIONAL PENTRU PREDICIASALTURILOR INDIRECTE. ________________________________________ 274

5.3.4.1. ARHITECTURA APLICAIEI.______________________________ 2745.3.4.2.JIndirSim. INTERFAGRAFIC. GHID DE UTILIZARE. ______ 277

6. CERCETRI CU PRIVIRE LA PREDICIA DINAMICAVALORILOR INSTRUCIUNILOR ___________________________284

6.1. PREDICIA VALORILOR INSTRUCIUNILOR (LOAD, ALU)._2846.1.1. DESCRIEREA SIMULATORULUI VALUE PREDICTOR. _________ 2846.1.2. IMPLEMENTAREA TIMING-ULUI N CADRUL SIMULATORULUI._ 290

6.2. VECINTATEA I PREDICIA VALORILOR CENTRATPECONTEXTUL CPU. ___________________________________________293

6.2.1. PREDICTOARE CLASICE (LASTVALUE, INCREMENTAL,CONTEXTUAL, HIBRID) __________________________________________ 2976.2.2. PREDICTOR HIBRID CU SELECIE BAZATPE METAPREDICTOARE.DESCRIERE SIMULATOR. _________________________________________ 302

7. REZULTATE OBINUTE PRIN SIMULARE. INTERPRETRI. _318

7.1. CERCETRI PRIVIND VECINTATEA I PREDICIAAPELURILOR INDIRECTE____________________________________319

7.1.1. REZULTATE OBINUTE PRIN SIMULAREA BENCHMARK-URILORSPEC____________________________________________________________ 3207.1.2. SIMULAREA PROPRIILOR PROGRAME DE TEST. REZULTATE.___ 338

7.2. CERCETRI PRIVIND VECINTATEA I PREDICIAVALORILOR INSTRUCIUNILOR _____________________________342

7.3. PREDICIA VALORILOR REGITRILOR CPU.______________3567.3.1. REZULTATE BAZATE PE PREDICTOARELE DE VALORI:INCREMENTAL, CONTEXTUAL I HIBRID CU PRIORITIZARE STATIC. 3567.3.2. EVALUAREA PREDICIEI NEURONALE APLICATREGITRILORPROCESORULUI._________________________________________________ 363

8. CONCLUZIII CONTRIBUII ORIGINALE. DEZVOLTRIULTERIOARE_____________________________________________368

BIBLIOGRAFIE ___________________________________375


4/412

4 Predicia dinamica valorilor n microprocesoarele generaiei urmtoare

ANEXA 1 _________________________________________________388EXEMPLE JUSTIFICATIVE PRIVIND IMPACTUL LA NIVELMICROARHITECTURAL AL UNOR TEHNICI DE MBUNTIRE APERFORMANEI PROCESOARELOR PRIN PREDICIASALTURILOR INDIRECTE__________________________________388

ANEXA 2 _________________________________________________393

EXEMPLU PRIVIND EFICIENA PREDICIEI PE REGITRIIPROCESORULUI MIPS [Flo03] ______________________________393

ANEXA 3 _________________________________________________395

LIMITAREA PREDICTIBILITII SALTURILOR PE ALGORITMIIDE SORTARE RAPID_____________________________________395

ANEXA 4 _________________________________________________398

REDUCEREA COMPLEXITII UNOR STRUCTURIMICROARHITECTURALE PRIN DISPERSIA ADRESELOR______398

ANEXA 5 _________________________________________________407

OPTIMIZAREA COLIZIUNILOR N STRUCTURILE PIPELINE __407


5/412

PREFA

Importanta rat de cretere, cu cca. 60% pe an, a performanelormicroprocesoarelor ultimilor 10 ani a fost susinut n principal prin douabordri corelate: prima vizeaz mbuntiri tehnologice (cretereafrecvenei tactului, scderea latenei memoriilor cache, creterea gradului deintegrare etc.) i are o pondere de cca. 35%, iar a 2-a, mai semnificativ(65%), vizeaz organizri arhitecturale tot mai eficiente. Aceast lucrarea

elaboratde ctre dl. dr.ing. Adrian Florea se focalizeazn esenpe cea dea 2-a abordare, innd desigur cont i de caracteristicile, uneori restrictive,ale tehnologiilor moderne din domeniul microarhitecturilor de calcul.

Paradigma actualde procesare a instruciunilor i datelor exploateazparalelismul la nivel de instruciuni prin tehnici de tippipelining(paralelismtemporal la nivelul fazelor de procesare ale instruciunilor main) irespectiv prin tehnici de execuii multiple ale instruciunilor independente(Multiple Instruction Issue). Desigur caceste paralelisme sunt posibile prinutilizarea unor metode hardware-software complexe, precum cele de

planificare i reorganizare a instruciunilor (n mod static, dinamic i hibrid)i respectiv de predicie a instruciunilor de ramificaie urmate de procesri

speculative etc. n ciuda performanelor deosebite ale acestei paradigmearhitecturale, ea implic cel puin dou limitri fundamentale, care nu vorputea fi depite dect printr-o nou generaie de microprocesoare de uzgeneral, cea de a 4-a, care va ngloba structuri novatoare de prelucrare.Prima limitare, cunoscutsub denumirea de fetch bottleneck (strangulareamecanismului de aducere a instruciunilor), se refer n principiu laimposibilitatea actualelor microprocesoare de a aduce din memorie mai multde o unitate secvenial de program (basic-block) ntr-un ciclu i estedatorat instruciunilor de salt. A 2-a limitare, denumit n literaturdataflow bottleneck sau issue bottleneck (strangularea mecanismului deexecuie a instruciunilor, datoratdependenelor reale de date ntre acestea),

se refer la imposibilitatea rulrii programului ntr-un timp mai mic dectlatena cii critice a acestuia.

Actualitatea i oportunitatea acestei lucrri de cercetare tiinificderivtocmai din curajul autorului de a ncerca selaboreze cteva soluiioriginale n vederea depirii acestor limitri fundamentale. Soluiile

propuse, ncadrate n mod pragmatic ntr-un ansamblu al unor cercetri deprestigiu i de actualitate pe problematica anterior schiat, vor puteaconstitui contribuii importante, cu un puternic caracter evolutiv, n


6/412


procesul, uneori fascinant, de elaborare a viitoarei generaii arhitecturale demicroprocesoare.

Pe de alt parte, o provocare continu n tiina i ingineriacalculatoarelor o reprezintnelegerea profunda complexelor i subtilelorinteraciuni hardware-software. Optimizrile interfeei hardware-software nusunt posibile dect pe baza unui asemenea proces de nelegere, carenecesito viziune integratoare asupra multiplelor i complicatelor procesede prelucrare a informaiei, codificatla niveluri semantice diferite. n acestsens, consider ccercetrile autorului relative la analiza legturilor adncidintre caracteristicile unor programe HLL (High Level Languages), pe de o

parte, i structurile hardware de predicie a salturilor indirecte prin registru,

pe de alt parte, constituie un valoros exemplu de aventur tiinificformativ, dar i aplicativ.

Iat doar cteva motive care m determin s constat c aceastmonografie tiinificeste una deosebit de necesar, actuali oportun, nmediul academic romnesc. Cnd idealurile profesionale sunt mici,

provinciale, realizrile nu pot fi dect pe msur. Nu este deloc cazul acesteicri, care i-a propus de la nceput ambiii mari, n deplinsincronizare cucele mai noi cercetri din domeniul fertil al microarhitecturilor de calcul cu

paralelism la nivelul instruciunilor i microfirelor de execuie.Dup ce n primul capitol autorul prezint n mod sintetic o

introducere n problematica microarhitecturilor predictive cu execuiispeculative ale instruciunilor, n capitolul al 2-lea se face o analizutilalimitrilor fundamentale aferente actualei generaii de microprocesoare.Capitolul este deosebit de bine plasat ntruct, n continuare, pornind de laaceste limitri fundamentale, prin rafinarea soluiilor propuse n literatura despecialitate, se dezvoltanumite soluii originale interesante. Autorul insistn mod justificat pe limitarea numit fetch bottleneck rezolvat prinarhitecturi de tip Trace-Cache (memorii cache care rein pe o intrare,secvene de basic-block-uri anterior procesate i deci, pretabile la re-

procesare), care ntre timp au fost implementate n microprocesoarelecomerciale (ex. Pentium IV). Apoi se prezint limitarea cii critice de

program mpreun cu cele dou soluii deja consacrate: reutilizareadinamic a instruciunilor i respectiv predicia dinamic a valorilorinstruciunilor. Ambele soluii se bazeazpe principiul vecintii temporalea valorilor instruciunilor (value locality), formulat prima datdeLipastiiShenntr-un articol din 1996. Se insistasupra celei de a 2-a soluii ntructaici autorul determin posibile oportuniti de cercetare, care vor fi

prezentate pe larg n continuarea lucrrii. Pe lng analiza riguroas aprincipalelor tipuri de predictoare dezvoltate n literatur, se fac consideraiiinteresante asupra performanei globale de procesare a acestor


7/412

Prefa 7

microarhitecturi (exprimat n instruciuni / ciclu), autorul elabornd i unmodel teoretic care corecteazun model anterior, aparinnd unor cunoscuicercettori israelieni. Foarte interesant mi s-a prut a fi i paragraful 2.2.3. ncare se abordeazdificila i extrem de importanta problema arhitecturilor

predictive i cu procesri multiple ale micro-firelor de execuie(multithreaded processors). Oarecum similar cu sistemele multiprocesor iaici se pun probleme legate de pstrarea unui model coerent i consistent alsistemului ierarhizat de memorie, din punct de vedere al variabilelorglobale. Sunt prezentate n mod succint cteva soluii propuse n literaturactualde specialitate.

n capitolul 3 autorul prezint metodologia de simulare utilizat n

cercetare. n esenaceasta se bazeazpe benchmark-urile SPEC (StandardPerformance Evaluation Corporation) i respectiv pe mediul de dezvoltarededicat cercetrii procesoarelor superscalare numit SimpleScalar, dezvoltatn mediile academice din SUA. Consider c prin utilizarea acestorinstrumente software, lucrarea este pe deplin sincronizat la acest nivel cucele mai noi cercetri academice i industriale din domeniu. Dei capitolulare mai degrabun caracter tehnic dect unul tiinific, utilitatea sa n cadrulmonografiei este indiscutabil. Subsemnatul a fost martor la eforturiledeosebite ale autorului de a nelege mediul SimpleScalar de simulare ntoatcomplexitatea sa, de a-l extinde cu noi module de program n scopulvalidrii cercetrilor sale originale i respectiv de a compila benchmark-urile SPEC2000 i alte programe de test elaborate de ctre autor pentruarhitectura int. Dup tiina subsemnatului dl. dr.ing. Adrian Florea este

primul din Romnia, care, bazat pe aceste instrumente software, a dezvoltatun cadru solid de investigare a microarhitecturilor cu execuii multiple ispeculative ale instruciunilor. De altfel, aceastproblematica prezentat-o

pe larg ntr-o consistentlucrare de peste 400 de pagini, scrisn colaborarecu subsemnatul, publicattot n editura Matrix Rom din Bucureti.

Capitolul al 4-lea este unul oarecum inedit ntruct autorul abordeazo problematic de grani, relativ puin dezbtut n literatur, i anumecea a influenei unor concepte de programare procedural respectiv

obiectual asupra generrii salturilor i apelurilor indirecte prin registru.Dup cum se tie, predicia adreselor destinaie ale acestor salturi este oproblem extrem de dificil (ntruct adresele int se modific n moddinamic) i actualiar soluiile propuse nu sunt ncmulumitoare. Autorula sesizat n mod corect faptul c, nainte de a aborda efectiv problema

prediciei ar trebui s neleag n profunzime modurile n care acesteapeluri indirecte sunt generate prin compilare. Pentru aceasta, el dezvolt

programe de test proprii, att procedurale ct i obiectuale, care conincorpuri suspectate de a genera apeluri i salturi indirecte n urma


8/412


compilrii. Pe baza acestei cercetri se extrag concluzii valoroase i deosebitde utile cu privire la construciile HLL generatoare ale unor astfel de salturi(apeluri indirecte de funcii prin pointeri, construcii switch/case n cazuri

bine precizate de autor, prezena funciilor de bibliotec, legarea dinamicrealizat prin polimorfism etc.). Cred c toate aceste informaii de nivelsemantic superior pot fi utilizate cu succes n predicia adreselor salturilor /apelurilor indirecte care, actualmente, utilizeazn majoritatea lor informaiide nivel semantic mai sczut, precum codul obiect, adrese binare etc. Maigeneral, pierderea semanticii codului de nivel nalt dupcompilare, cred cdevine inacceptabilpentru noua generaie de microprocesoare. Sper c ncercetrile sale viitoare dl. dr.ing. Adrian Florea va exploata mai mult i

aceastnifertil, pe care, de altfel, singur i-a creat-o.n capitolul 5 se abordeaz n mod natural interesanta problem a

prediciei salturilor indirecte n cadrul procesoarelor superscalare. Importantde remarcat faptul cautorul prezintmai nti o excelentsintez, deosebitde actual, asupra principalelor contribuii din literatura de specialitate. Deaici, rezultmai apoi i niele proprii de cercetare, bazat pe mbuntireaunora dintre aceste scheme de predicie. O prim contribuie original oreprezint utilizarea unei scheme de predicie de tip Target Cache (omemorie cache coninnd n principal ultimele instane ale adreselor intaferente unui salt / apel indirect) accesat cu o informaie extins, maicomplet, prin care acurateea prediciei poate crete. Principiul predicieiare la bazun model stohastic de tip Markovcorespunztor secvenelor devalori ale adreselor intaferente unui astfel de salt. Pornind de la aceeaischem Target Cache, autorul o mbuntete prin adugarea uneiinformaii de confiden(ncredere) a prediciei, ceea ce, iari, poate crete

performana. n acest ultim sens se propun metrici interesante de evaluare aperformanelor. n fine, se propun apoi alte dou noi predictoare de tiphibrid: unul cu selecie bazatpe aritatea adreselor destinaie ale salturilorindirecte i un altul cu selecie bazatpe confidenele asociate celor dou

predictoare componente. Dovezile cantitative referitoare la superioritateaacestor predictoare originale vor fi aduse n capitolul 7 al lucrrii, pe baza

unor laborioase simulri.Capitolul al 6-lea abordeaz o problem conex, prezentndcontribuii relative la predicia dinamic a valorilor instruciunilor. Peaceast baz, se ncearc apoi execuia speculativ a unor secvene deinstruciuni aparinnd cii critice de program. O contribuie deosebit devaloroas mi s-a prut aici cea legat de centrarea prediciei valorilor pecontextul CPU (registrele generale) i nu pe instruciuni, cum se face ntoate articolele studiate pnla acest moment. Avantajele sunt evidente, n

primul rnd reducerea drastic a numrului de predictoare implementate.


9/412

Prefa 9

Ideea este dezvoltatn continuare i autorul propune predictoare hibride devalori (contextuale i incrementale) n care selecia predictorului curent seface prin intermediul unor selectoare dinamice de tip automat finit respectivde tip neuronal. Desigur c selecia se va face n esen pe bazaconfidenelor ataate fiecrui predictor component. Cred c aceastcontribuie este una de for a lucrrii, faptul fiind justificat i prin

publicarea de ctre autor (n colaborare) a unui valoros articol pe aceasttem, n prestigioasa revist IEE Proceedings. Computers and DigitalTechniques (2005, acreditatISI Thomson). Rezultatele cantitative vor fi

prezentate i n acest caz n capitolul urmtor al lucrrii.Capitolul 7 prezintntr-o manierrealmente impresionantdin punct

de vedere al eforturilor de programare i simulare, cu totul deosebite, modulde optimizare al schemelor propuse precum i utile comparaii ntre acesteai cele deja publicate n literatura de specialitate. Mai nti se abordeaz

problema prediciei salturilor indirecte. ntr-un mod sistematic, autorulstudiaz vecintatea temporal a valorilor (value locality) adreselordestinaie care se dovedete a fi una extrem de semnificativ. Apoi sedeterminoptimul pattern-ului de cutare pentru predictoarele contextuale(modele stohastice Markovsimplificate). Foarte interesante mi s-au prut afi aici: validarea ideii de extindere a informaiei de corelaie pentru structuride tip Target Cache(cu rezultate spectaculoase !), validarea schemei TargetCache cu mecanismul de confidenpropus de autor, validarea schemelorhibride de predicie propuse, cu selecie bazat pe aritatea salturilor /apelurilor indirecte (acuratei de predicie medii cu cca. 4% mai mari fadeschemele Target Cache respectiv contextuale !). n continuare, se prezintrezultate extrem de interesante ale unor simulri focalizate pe prediciageneralizata valorilor instruciunilor. Deosebit de utile mi s-au prut a fi:optimizarea capacitii tabelei de predicie n cazul instruciunilorLoad(512locaii) precum i optimizarea predictorului hibrid de valori. Paragraful 7.3valideaz ntr-un mod remarcabil ideea centrrii prediciei valorilor pecontextul CPU. Autorul cerceteaz mai nti, ntr-un mod sistematic,vecintatea valorilor asociate registrelor CPU, pentru a nelege care dintre

aceste registre sunt predictibile din punct de vedere al coninutului. Maimult, se dau i explicaii calitative corecte, ca i justificare. Apoi sedezvolt, de asemenea ntr-un mod sistematic, mai multe predictoaredestinate registrelor respective, inclusiv predictoare hibride foarte

performante. Deosebit de interesant este cercetarea celor trei tipuri deselectoare dinamice propuse ntr-un capitol anterior, care cred car putea ficontinuati aprofundatcu succes.

n urma studierii i analizei acestei cri de adnc specialitate ningineria calculatoarelor, pot concluziona urmtoarele aspecte:


10/412


Lucrarea domnului dr.ing. Adrian Florea se refer la probleme actuale,extrem de importante, privind microarhitecturile predictive i speculative.

Pe baza unei cercetri bibliografice vaste, s-a elaborat o sintez criticvaloroas a domeniului, cu evidenierea principalelor limitri dar i aoportunitilor de cercetare.

S-au cercetat structurile de programe procedurale i obiectuale caregenereazsalturi / apeluri indirecte prin registru.

S-au elaborat scheme originale de predicie a salturilor / apelurilorindirecte, superioare majoritii schemelor publicate n literatura despecialitate.

S-au proiectat predictoare centrate pe contextul CPU, o idee completoriginal i care ofer avantaje deosebite n raport cu deja clasicelepredictoare centrate pe instruciune.

S-au dezvoltat o serie de simulatoare software complexe menite sevalueze i soptimizeze microarhitecturile novatoare propuse de ctreautor. Astfel, n urma unor laborioase simulri realizate sub mediulSimpleScalarcu utilizarea benchmark-urilor SPEC, autorul dovedete nmod convingtor superioritatea structurilor propuse de el, din punct devedere al raportului performan/ cost.

Aceast carte reprezint o cercetare bibliografic la zi privindaspectele actuale ale micro-arhitecturilor cu procesri speculative ntreesut

cu multe completri i contribuii originale, rodul unei munci a autorului nacest domeniu de circa 8 ani. Dincolo de rezultatele tiinifice obinute, credc scopul acestei monografii este unul deosebit de important i generos:anume acela de a arta ntr-un mod convingtor, c domeniul cercetriimicroarhitecturilor de mare performan poate i trebuie s fie abordat nmod creator i n mediile academice romneti. n acest sens, autorul pune ladispoziia celor interesai instrumente software utile pentru cercetare.Lucrarea este una formativ, pe baza unor experiene aplicative autentice aleautorului. Iatde ce, o recomand n mod clduros pentru a fi utilizatefectivn universiti de studenii din anii terminali ai studiilor de licen, destudenii masteranzi i de cei doctoranzi din domeniile tiinei i ingineriei

calculatoarelor, electronicii i domeniilor conexe; este util de asemeneainginerilor, cadrelor didactice universitare i cercettorilor, tuturor

profesionitilor IT i (mai ales !) celor foarte amatori de aventuri ningineria calculatoarelor.

Sibiu, 01 iunie 2005 Prof.univ.dr.ing. Lucian N. VINANMembru (c.) al Academiei de tiine Tehnice din Romnia


11/412

1. INTRODUCERE N PROBLEMATICAMICROARHITECTURILOR PREDICTIVE I

SPECULATIVE

Provocrile domeniului arhitecturii calculatoarelor cu paralelism lanivelul instruciunilor, ca de altfel a multora din tiina i ingineria

calculatoarelor, sunt n principal conceptuale, arhitecturale, i abia n finaltehnologice. n ultimii 10 ani performana relativ a microprocesoarelor acrescut cu cca. 60% pe an. Cercettorii susin c aproximativ 65% dinaceastcretere se datoreazmbuntirilor arhitecturale i doar 35% celorde naturtehnologic. Tendinele tehnologice se referla creterea graduluide integrare al tranzistorilor pe cip, creterea frecvenei ceasului

procesorului, diminuarea timpul de acces la memorie, reducerea costurilorde implementare hardware la aceeai putere de calcul ori capacitate dememorare etc. Tendinele arhitecturale urmresc exploatarea paralelismuluila nivelul instruciunilor i microfirelor de execuie, att prin tehnici statice(soft), ct i dinamice (hard) sau hibride (cazul arhitecturii IA-64, procesorul

Intel Itanium), o ierarhizare a sistemului de memorie prin utilizarea unorarhitecturi evoluate de memorii tip cache, reducerea latenei cii critice deprogram, utilizarea multiprocesoarelor n cadrul arhitecturilor serverelor istaiilor grafice etc.

Microarhitecturile predictive i speculative se nscriu n domeniulprocesoarelor cu paralelism la nivelul instruciunilor (ILPP). Acesteanglobeaz caracteristici hardware-software specifice procesoarelorviitorului apropiat fiind considerate de ctre cercettori ca aparinnd celeide a patra generaii arhitecturale (dup prima generaie compus din

procesoarele eminamente seriale von Neumann, a doua reprezentat deprocesoarele pipeline scalare i a treia reprezentatde mainile cu execuie

multipl MEM, categorie din care fac parte procesoarele pipelinesuperscalare i cele de tip Very Long Instruction Word). ArhitecturileMEM din a treia generaie arhitectural, sunt considerate arhitecturidecuplate, n sensul c lucreaz dup un mecanism de tip "productor -consumator". n fiecare ciclu se desfoar n mod simultan dou proceseindependente: unul de aducere a instruciunilor din memorie n staiile derezervare SR sau ntr-un buffer de prefetch (productorul) i un altul delansare n execuie a acestor instruciuni din respectivul buffer sau SR


12/412


(consumatorul). Mecanismul de reacie ntre consumator i productor esterealizat prin instruciunile de ramificaie (branch). Generaia arhitecturalurmtoare de microprocesoare se bazeazn principiu i ea pe acelai modeldoar cse vor utiliza tehnici de procesare mai agresive precum cele bazate

pe reutilizarea dinamic a instruciunilor care au mai fost aduse sau / iexecutate, pe memorii de mare capacitate integrate "on chip" (trace cache),

pe exploatarea paralelismului la nivel masiv de "microthread" sau pepredicia dinamica valorilor resurselor etc. Procesoarele superscalare dingeneraia a patra (trace procesorul, procesoare multithread, arhitecturamultiscalar) extrag paralelismul dinamic prin execuie speculativ,multithreading sau trimitere spre execuie "out of order".

Din pcate procesoarele ILP sunt caracterizate de limitri att dinpunct de vedere al productorului ct i din punct de vedere alconsumatorului. Rata de execuie a instruciunilor este fundamental limitatde ctre hazardurile reale de date (RAW read after write) ntre instruciuni(calea critic de program). Cauza principala acestei limitri o constituienatura intrinsec seriala programelor, n care se dicteazordinea secvenialde transmitere a datelor ntre instruciuni. Alte limitri sunt reprezentate dehazardurile structurale, hazardurile de ramificaie etc. Aceste ultime limitri,spre deosebire de dependenele RAW pot fi depite prin diverse tehnicisoftware sau hardware, n cadrul paradigmei actuale.

Un alt neajuns se referla paradigma actualde cercetare / exploataren domeniul arhitecturii calculatoarelor care este prea specializat, prealimitat. Instrumentele de cercetare aferente sunt destul de mbtrnite. Deasemenea, interfaa hardware-software nu poate fi neleas n

profunzime, sau formalizat ntr-o manier real calitativmetodele actualede cercetare sunt bazate n principal pe simulare, benchmarking i prelucrristatistice i mai puin pe teorie formalizatmatur. n consecin, rezultatelecantitative obinute reprezintdoar efecte i nu cauze reale ale fenomenelor

procesate. Metodologia actualde investigare impune necesitatea dezvoltriiunor instrumente de cercetare precum: compilatoare, asambloare, link-editoare, depanatoare la nivel de cod surs, benchmark-uri reprezentative a

cror execuie s fie simulat. Pe lng acestea, cel mai important ns,trebuie dovedit abilitatea cercettorului de a gsi soluii la dificileleprovocri ale domeniului sau de a investiga probleme noi, neabordate nc.

Istoria procesoarelor ILP contrapune douparadigme pentru cretereaperformanei, bazate pe software i respectiv pe hardware. n ciuda scopuluicomun de exploatare i cretere a paralelismului la nivelul instruciunilorcomunitatea cercettorilor se mparte n dou entiti aproximativdisjuncte n ncercrile lor de a-l ndeplini. Pe de o parte, arhitecii decalculatoare i canalizeaz eforturile pentru exploatarea / optimizarea


13/412

Introducere n problematica microarhitecturilor predictive i speculative 13

tehnicilor de procesare existente prin simulri substaniale pe programe detest reprezentative n format cod obiect, fr a ine cont de semanticacodului surs de nivel nalt, iar pe de alt parte, autorii de compilatoareurmresc optimizarea codului obiect, reducerea necesarului de memorie etc.Toate aceste eforturi sunt ndreptate de fapt pentru depirea limitrilortehnologice, dar mai ales arhitecturale, specifice procesoarelor ILP.Caracteristicile arhitecturale complexe implictehnologii tot mai sofisticate,

parte din ele nc nedisponibile. Totodat ns, mbuntirile aferenteprocesului tehnologic de fabricare, realizate prin creterea capacitii deintegrare a tranzistoarelor i reducerea timpilor de comutaie, determincreterea frecvenei procesoarelor actuale i viitoare. Micorarea continua

perioadei de tact a acestora conduce la imposibilitatea realizrii ntr-osingur perioad de tact a proceselor de predicie sau accese la diversestructuri de date, cu efect imediat i asupra vitezei globale de execuie a

programelor msurat n IPC (instruciuni per ciclu). De exemplu, exist ostrns legtur ntre dimensiunea informaiei de corelaie, capacitateatabelei de predicie, acurateea prediciei (informaii legate de arhitectur) itimpul n care se realizeazpredicia (informaie tehnologic), n condiiileimpuse de fezabilitate hardware. Pe de alt parte, performanelearhitecturilor cresc asimptotic pe actualele modele. Totui, schimbrifundamentale sunt mai greu de acceptat n viitorul apropiat, n primul rnddatorit compilatoarelor optimizate, avnd drept scop exploatarea mai

pronunat a paralelismului la nivel de instruciuni, deoarece acestea suntdeosebit de complexe i puternic dependente de caracteristicile hardware.Soluiile, dup cum se arat i n aceast carte, pot veni mai ales dintr-ombinare a ideilor din diverse domenii tiinifice: arhitectura calculatoarelori inteligenartificial.

n aceast lucrare este abordat o tehnic relativ nou, prediciavalorilor resurselor, menit s exploateze redundana instruciunilor idatelor, existent n programe. Tehnica a fost propus pentru depirealimitrilor fundamentale ale paradigmei procesoarelor cu paralelism lanivelul instruciunilor, scopul fiind de a reduce calea criticde program

efectul defavorabil provocat de dependenele reale de date asupraperformanei globale de procesare. Avnd n vedere puternica vecintate avalorilor asignate unei instruciuni sau resurse hardware, care sugereazcvalorile posibil a fi asignate respectivei resurse snu fie echiprobabile, cidimpotriv, localizate pe instruciune sau pe resursa hardware, face ca

predicia valorilor instruciunilor n vederea execuiei speculative a acestorasaibanse importante de reuit. O altproblematacatn lucrarea defa se refer la implementarea unor structuri moderne de predicie asalturilor codificate n moduri de adresare indirecte prin registru, pornind de


14/412


la asemnarea existent ntre problema prediciei valorilor i problemaprediciei adreselor destinaie aferente instruciunilor de salt indirect.Structurile de date implementate n hardware pentru ambele procese de

predicie au principii identice de funcionare, i anume asocierea cvasi-bijectiva contextului de apariie al instruciunii respective cu data / adresade predicionat, n mod dinamic, odatcu execuia programului. O soluie

proprie, novatoare, a constituit-o extinderea prediciei valorilor de la nivelulinstruciunilor la regitrii procesorului, cu implicaii benefice asupra

performanei, reducndu-se totodat complexitatea i costul hardware almicroarhitecturilor speculative.

Se pare c pentru a continua i n viitor creterea exponenial a

performanei microprocesoarelor, sunt necesare idei noi, revoluionare chiar,pentru depirea limitrilor paradigmei actuale din punct de vedereconceptual. Existnco puternictendinde specializare ngustcare faceadesea ca paradigma domeniului s fie una nchisn tipare preconcepute.Abordri recente, ilustrate i n aceastlucrare, arat nscsinergia unorinstrumente aparent disjuncte ale tiinei calculatoarelor converge sprerealizri novatoare ale unui anumit domeniu de cercetare (vezi conceptul de

predictor neural spre exemplu). Alte posibile soluii constau n abordriintegratoare de gen hardware-software, tehnologie-arhitectur, algoritmi,concepte, metode.

O primastfel de soluie se referla necesitatea mbinrii eficiente atehnicilor de scheduling software cu cele dinamice, de procesare hardware.n prezent, separarea ntre cele 2 abordri este artificial i poate preaaccentuat. n acest sens, programele ar trebui s expliciteze paralelismulintrinsec ntr-un mod mai clar. Cercetri actuale arat c un programoptimizat static ruleazmai prost pe un procesor Out of Order dect peunul In Order [Ste99]. Printre cauze se amintesc expansiunea codului dupreorganizare, noile dependene de date introduse prin execuia condiionatainstruciunilor, faptul c instruciunile gardate nu permit execuia Out ofOrder etc. Separarea schedulingului dinamic de cel static este o prejudecatnocivdar care este din pcate deja consacratn ingineria calculatoarelor

unde practic nimeni nu i-a pus problema dezvoltrii unui optimizator decod dedicat unei maini cu procesare Out of Order.Cercetarea algoritmilor ar trebui sinseama i de concepte precum,

de exemplu, cel de cache, n vederea exploatrii localitilor spaiale aledatelor prin chiar algoritmul respectiv. Se cunosc, la ora actual, relativ

puine lucruri despre ce se ntmplcu un algoritm cnd sunt implementateierarhii de memorii pe maina fizic. n general, algoritmii nu in cont la oraactual de caracteristicile mainii i acest lucru nu este pozitiv pentru calgoritmul ruleazntotdeauna pe o mainfizicavnd limitri importante


15/412


16/412


Capitolul 3 ilustreazprogramele de test standardizate (suita SPEC),metodologia de simulare, instrumentele software utilizate baza decercetare de la care s-a pornit n exploatarea schemelor de predicie propuse.Pentru compararea rezultatelor simulrilor cu cele obinute de ceilalicercettori din domeniu pe plan internaional se impune standardizarea

procesului de simulare. n acest sens a fost utilizat i descris setulSimpleScalar 3.0 o colecie de instrumente software, pus la dispoziiacercettorilor n arhitecturi moderne de calcul, care cuprinde: compilatoare,asambloare, link-editoare, simulatoare i instrumente de vizualizare a uneiarhitecturi (super)scalare generice. Pentru generarea codului la nivel limbajde asamblare MIPS i a codului obiect specific arhitecturii virtuale

SimpleScalar 3.0. a fost nevoie de recompilarea instrumentelor setului(utilitarele GNU, compilatorul Gcc). Cu ajutorul acestora au fostrecompilate benchmark-urile SPEC2000 i propriile programe de testfolosite n vederea studierii legturii calitative i cantitative existente ntre

paradigmele actuale de programare (programe procedurale vs. obiectuale) irespectiv generarea valorilor de anumite tipuri de instruciuni (salturiindirecte, instruciuni Load, ALU etc).

n capitolul 4 s-a ncercat investigarea legturii existente ntremotenire, polimorfism i alocarea dinamic a memoriei pe de o parte, icomportamentul salturilor indirecte (JR reg) de cealalt parte, fiindcunoscut ca o problem dificil predicia acestora. Se urmrete practictransmiterea de informaii de la nivel software ctre proiectanii dearhitecturi (hardware). S-a realizat o analizcomparativa limbajelor C iC++ din punct de vedere al procesrii lor pe arhitecturi cu paralelism lanivelul instruciunilor i s-au evideniat diferenele dintre acestea.Comportamentul diferit al celor dou tipuri de aplicaii i penuria de

programe obiectuale de test standardizate au impus generarea unorprograme proprii de test relativ simple, prin intermediul crora s-a artat ccele dou"emisfere" software i hardware sunt doar n aparendisjuncte.Cele 2 programe obiectuale C++ i 3 procedurale C propuse evideniazcorpuri i construcii de program prezente n sursele de nivel nalt

procedurale, respectiv concepte ale programrii obiectuale care genereazlanivel low salturi / apeluri indirecte. Finalul capitolului ilustreaz ctevaexemple de instruciuni de salt indirect cu caracter dinamic polimorf (caregenereaztrei sau mai multe target-uri distincte) din benchmark-urile SPECsimulate, pentru a se evidenia dificultatea prediciei acestora.

n capitolul 5 sunt prezentate cercetri ale autorului cu privire ladificila problem a prediciei branch-urilor n cadrul arhitecturilorsuperscalare de procesare, condiionate, dar mai ales cele codificate nmoduri de adresare indirecte. Sunt aduse argumente privind necesitatea


17/412


prediciei salturilor condiionate i indirecte, utilitatea pstrrii uneiinformaii de corelaie ct mai bogate, eventual variabile ca lungime nfuncie de fiecare salt. Capitolul se constituie ntr-un adevrat state of theart a structurilor de predicie dedicate att salturilor condiionate (de la

predictoare simple de tip BTB, corelate pe douniveluri pn la cele maicomplexe markoviene, neurale, bazate pe arbori de decizie) ct i celorindirecte (Target Cache, structuri hibride, cascadate pe mai multe niveluri,structuri preluate din predicia valorilor). n ce privete cercetrile proprii

privind predicia salturilor / apelurilor indirecte, s-a nceput cu arhitecturacea mai simpl, predictorul de tip last value i s-a continuat cu predictoarecontextuale PPM complet, de tip Target Cache, hibride etc. Cu ajutorul

predictorului contextual de tip PPM complet s-a ncercat determinareapattern-ului optim de cutare, stabilirea corelaiei existente ntre salturi nfuncie de context. n vederea mbuntirii acurateii prediciei aferenteinstruciunilor de salt indirect au fost aduse cteva modificri structurii de

predicie Target Cache originare. Mai nti a fost studiatinfluena istorieiglobale a salturilor condiionate asupra prediciei, urmat de extindereainformaiei de corelaie. Un ultim experiment privitor la aceaststructurl-aconstituit ncercarea de mbuntire a acurateii de predicie printr-oignorare selectiva efecturii unor predicii. A fost de asemenea exploatati o schemde predicie hibridcu selecie bazatpe aritate.

n capitolul 6 se prezintcontribuiile originale ale autoruluin analizade performan i respectiv determinarea unor parametri optimali de

proiectare, pentru diferite structuri de predicie a valorilor instruciunilor.Au fost implementate cele mai multe din schemele prezentate n capitolul 2(predictorul LastValue, Incremental, Contextual, Hibrid) i s-au studiat

probleme legate de vecintatea valorilor i predicia valorilor instruciunilorcu consecina execuiei speculative a instruciunilor avnd influene beneficeasupra timpului de procesare. De asemenea, n acest capitol s-a pus accentul

pe o noucontribuie originalcare pune n evidenconceptul de vecintatea valorilor asociate regitrilor generali afereni CPU. Ideea asocierii cteunui predictor de valori pentru anumii regitri predictoare centrate pe

regitri i nu pe instruciuni, ar putea implica tehnici arhitecturale novatoare structuri de predicie mult mai simple, i, n consecin, performanembuntite, complexitate i costuri mai reduse ale microarhitecturilorspeculative. n continuare au fost propuse soluii de nlturare a neajunsului

provocat de predictorul hibrid (de departe cel mai bun) cu prioritizarestatic, fix, n alegerea tipului de predictor component ce urmeaz a fifolosit n procesul de predicie i care conduce la o soluie neoptimal.Astfel, au fost descrise structurile de metapredicie implementate, careselecteazdinamic, bazat pe diverse grade de ncredere, structura care sfie


18/412


utilizatla un moment dat pentru predicie. Au fost propuse doutipuri demetapredictoare ne-adaptive, prin ataarea unui automat de confiden sauregistru binar de deplasare fiecrui predictor component, i respectiv unuladaptiv, care utilizeaz o reea neural de tip feedforwardMultiLayerPerceptron cu algoritm de nvare backpropagation.

Capitolul 7 prezint cele mai elocvente rezultate cantitative iinterpretarea acestora din punct de vedere calitativ. S-a realizat o structurarea rezultatelor pe trei categorii: prima dintre acestea evideniaz acurateea

prediciei salturilor indirecte obinut pe diverse scheme (Target Cache,predictoare PPM, hibride). A doua categorie analizeazprobleme legate devecintatea i predictia valorilor instruciunilor de tip Load i aritmetico-

logice. De asemenea, au fost repetate experimentele pentru locaiilememoriei de date. Ultima categorie de rezultate ncearc s dovedeascfezabilitatea conceptului novator de predictor de valori centrat pe regitrii

procesorului. Simulrile au fost efectuate pe procesoare Pentium III la 500MHz parial efectuate sub sistem de operare Microsoft Windows98, 2000,sau NT avnd la dispoziie emulatorul Cygwin i parial sub sistemul LinuxRedHat 7.3. Evalurile arhitecturilor propuse au fost fcute folosind ocolecie de simulatoare execution-driven specifice arhitecturilor ILP,originale i puternic parametrizabile (dezvoltate din setul de instrumenteSimpleScalar 3.0). Simularea a fost realizat pe cele dou versiuni ale

benchmark-urilor SPEC (95 i 2000).n capitolul 8 sunt trecute succint n revistcontribuiile tiinifice ale

acestei lucrri, este evideniat ctigul cantitativ al fiecrei tehnici introduse,sunt realizate comparaii ntre acestea i artate cteva dintre direciileviitoare de cercetare. Concluziile acestei lucrri sugereaznecesitatea unoranalize teoretice mai profunde, mai generale i mai sistematizate n acestdomeniu, dublate i verificate prin simulri laborioase. Cercetrile abordaten aceastlucrare trebuie continuate n scopul rezolvrii altor probleme aledomeniului ILP rmase deschise, interesante i conexe cu cele prezentateaici.

Lucrarea se ncheie cu o lista bibliografic a peste 120 de lucrri

utilizate pe parcursul cercetrii i conine peste 130 de figuri i 20 de tabele,dintre care peste 60% coninnd rezultatele cercetrilor efectuate de ctreautor i respectiv 30 de relaii analitice. Anexa 1 prezint dou exemple

justificative privind impactul la nivel microarhitectural al unor tehnici dembuntire a performanei procesoarelor prin predicia cu acuratee asalturilor indirecte. Prima aplicaie, simpl la nivel high-level, dar maicomplex i dificil de urmrit la nivel asamblare urmrete sevideniezesituaii n care extinderea informaiei de corelaie pentru instruciunile desalt indirect are sens, contribuind la creterea acurateii prediciei acestora.


19/412


Cea de-a doua aplicaie evideniazlimitarea avantajului introdus de tehnicade extindere a informaiei de corelaie pentru pattern-uri de salturicondiionate de istorie redus. Exemplul simplu prezentat n Anexa 2ilustreaz la un nivel redus necesitatea prediciei valorilor centrat peregitrii procesorului MIPS. Anexele 3, 4 i 5 reprezintexemple concretece demonstreaz necesitatea unor abordri integratoare de gen hardware-

software, tehnologie-arhitectur, algoritmi, concepte, metode, cunoscutfiind faptul c, n proiectarea procesoarelor noilor generaii, accentul

principal nu se mai pune pe implementarea hardware, ci pe proiectareaarhitecturii n strns legtur cu aplicaiile poteniale. n Anexa 3 sedemonstreaz c predictibilitatea salturilor n unele programe poate fi

analizat exact, furnizndu-se o limit superioar a predictibilitii pealgoritmii de sortare rapid. n Anexa 4 se evideniaz prin intermediul adou aplicaii practice cum dispersia adreselor ajut la reducereacomplexitii unor structuri microarhitecturale. Anexa 5 descrie posibilitateautilizrii algoritmilor greedy n optimizarea coliziunilor din structurile

pipeline. CD-ul care nsoete aceast lucrare cuprinde simulatoarele(sursele, executabilele, bibliotecile necesare) dezvoltate pentru exploatareaideilor de cercetare expuse anterior i prezentate mai amplu pe parcursulfiecrui capitol (structuri i mecanisme de predicie).

n finalul acestei introduceri doresc smulumesc att conductoruluimeu de doctorat, prof.dr.ing. Mircea Petrescu ct i domnului prof.dr.ing.Lucian Vinan pentru sprijinul lor profesional continuu i de o naltinuttiinific precum i pentru ncrederea pe care mi-au acordat-o pe toat

perioada pregtirii prin doctorat. De asemenea, in smulumesc domnilorprof.dr.ing. Adrian Petrescu i prof.dr.ing. Vladimir Creu pentru analizacompetent i amabilitatea de a recenza aceast lucrare ntr-o versiuneanterioar. Cuvinte de recunotinvreau stransmit i colegilor mei sibienidin catedra de Calculatoare, n special d-lui conf.dr.ing. Macarie Breazu

pentru discuiile profesionale extrem de fecunde cu privire la paradigmeleactuale de programare i posibilele lor implicaii n hardware. Din acelaicolectiv doresc smulumesc unui tnr cercettor de perspectiv, prietenul

meu Arpad Gellert cu care de multe ori am depanat, compilat i simulat cotla cot o parte din surse. Un gnd bun se ndreapt i spre personalulEditurii Matrix Rom care s-a implicat cu generozitate i profesionalism neditarea acestei lucrri. n final, i ntotdeauna pe nedrept la final, deicuvintele nu pot s exprime cu adevrat att ct ar trebui, vreau smulumesc familiei soiei Delilah i copilailor mei Adrian, Albert iDeborah, pentru nelegerea, rbdarea i dragostea cu care m-au nconjuratn toi aceti ani.


20/412

2. LIMITRI FUNDAMENTALE ALEPARADIGMEI ILP. SOLUII.

2.1. LIMITAREA PRODUCTORULUI (FETCH

BOTTLENECK). SOLUII.

2.1.1. PROBLEMA N SINE

Din punct de vedere funcional procesoarele superscalare de naltperforman sunt compuse din 2 mecanisme decuplate: mecanismul deaducere (fetch) a instruciunilor pe post de productor i respectivmecanismul de execuie a instruciunilor pe post de consumator. Separareantre cele 2 mecanisme (arhitectur decuplat) se face prin bufferele de

prefetch i staiile de rezervare, ca n figura 2.1. Instruciunile de ramificaiei predictoarele hardware aferente acioneazprintr-un mecanism de reacientre consumator i productor. Astfel, n cazul unei predicii eronate,

bufferul de prefetch trebuie sfie golit mcar parial iar adresa de acces lacache-ul de instruciuni trebuie i ea modificatn concordancu adresa lacare se face saltul.

Figura 2.1.Arhitectursuperscalardecuplat


21/412

Limitri fundamentale ale paradigmei ILP. Soluii. 21

Rezultate statistice bazate pe simulri laborioase pe benchmark-urireprezentative (SPEC95, 2000) arat c o instruciune de salt apare lafiecare 58 instruciuni dinamice executate, ceea ce nseamn c

productorul, prin rata de aducere a instruciunilor (fetch rate FR) estelimitat la cel mult 8, aducerea simultan a mai multor instruciuni fiindinutil(fetch bottleneck). Aceastlimitare fundamentalar avea consecinedefavorabile i asupra consumatorului cuantificat prin rata medie deexecuie a instruciunilor (issue rate IR) ntruct IRFR. n subcapitolul2.2.2.6 sunt prezentate informaii cantitative i calitative care evideniazinfluena defavorabila lrgimii reduse de banda mecanismului de aducerea instruciunilor asupra eficacitii unor tehnici de comprimare a cii criticede program, cum ar fi predicia valorilor. Pentru creterea gradului de

paralelism la nivelul instruciunilor este necesar dezvoltarea iimplementarea de noi tehnici care s reduc ntrzierile n procesare(hazarduri) pe oricare din cele doufluxuri: de instruciuni (control-flow) irespectiv de date (data-flow).

Progresele semnificative n algoritmii de lansare n execuie impunns depirea acestei bariere. n acest sens, cercetrile actuale insist pembuntirea mecanismelor de aducere a instruciunilor (fetch) prinurmtoarele tehnici:

predicia simultana mai multor ramificaii / tact rezultnd rate de

procesare (IR) sporite. posibilitatea accesrii i aducerii simultane a mai multor basic -block-uri din cache, chiar dac acestea sunt nealiniate, prinutilizarea unor cache-uri multiport (trace-cache).

pstrarea unei latene reduse a procesului de aducere ainstruciunilor, n contradicie cu cele 2 cerine anterioare.

Latena unitii de aducere a instruciunilor, pipeline-izat, are unimpact profund asupra performanei procesorului, n primul rnd datoritcostului de reumplere a structurii pipeline, n cazul unui salt greit

predicionat, cu instruciuni de la adresa corect. Evident c, necesitateaprediciei mai multor salturi simultan, precum i aliniamentul necontiguu n

memorie al instruciunilor contigue din punct de vedere al execuiei,determino crestere a latenei unitii de aducere a instruciunilor (fetch).Ali factori care determin limitarea ratei de fetch a instruciunilor (FR -Fetch Rate) sunt: lrgimea de band limitat a interfeei procesor - cache,capacitatea redus a buffer-ului de prefetch, accesele cu miss n cache,acurateea de predicie nesatisfctoare (procentajul cel mai ridicat obinutde cercettori este de 98.29%, realizabil printr-un predictor neural de tipPerceptron [Jim02]) i respectiv latena ridicatde refacere a contextului n


22/412


cazul unei predicii eronate. De asemenea, un alt factor care poate limita ratade fetch a instruciunilor l constituie instruciunile de salt indirect,revenirile din proceduri i ntreruperile software. Pstrnd contextul, o altlimitare poate fi reprezentatde nealinierea aa numitelor blocuri atomice[Pat98]. Unitatea de umplere fill unit(vezi subcapitolul 2.1.2)este forats creeze un segment de instruciuni (bloc atomic) mai mic dectdimensiunea maxim a liniei din trace cache deoarece basic-block-ulurmtor din irul dinamic de instruciuni care se executeste mai mare dectspaiul rmas disponibil n linia din trace cache.

ntruct asupra conceptului Trace Cache se va insista n subcapitolulurmtor (2.1.2), n continuare sunt descrise foarte pe scurt alte cteva soluii

alternative de extindere a lrgimii de bandaferente mecanismului de fetch.Mecanismul de predicieBranch Address Cache, propus n [Yeh93] ca

o extensie a structurii Branch Target Buffer [Smi84] este capabil sprediconeze mai multe salturi simultan, determinnd adresele de nceput abasic-blocurilor care se vor executa. Toate aceste target-uri multiple vor fitrimise ctre un cache de instruciuni cu grad ridicat de ntreesere pentru afi efectuat procesul de fetch simultan ntr-un singur ciclu de tact.

O alt schem, propus n [Con95] permite extragerea a dou liniinecontigue din cache-ul de instruciuni. Suplimentar este utilizat un bufferde colapsarepentru detecia branch-urilor scurte din interiorul unei linii decache i evacuarea instruciunilor dintre branch i target-ul su.

2.1.2. SOLUIE: TRACE CACHE. TRACE PROCESOARE.

O paradigmmenit s extindconceptul de superscalaritate i carepoate constitui o soluie interesantfade limitrile mai sus menionate, oconstituie trace - procesorul, adic un procesor superscalar avnd omemorie trace - cache (TC) vezi figura 2.6. Ca i cache-urile deinstruciuni (IC), TC este accesat cu adresa de nceput a noului bloc deinstruciuni ce trebuie executat, n paralel cu IC. n caz de miss n TC,instruciunea va fi adusdin IC sau - n caz de miss i aici - din memoria

principal. Spre deosebire nsde IC, TC memoreazinstruciuni contiguedin punct de vedere al secvenei lor de execuie, n locaii contigue dememorie. O linie din TC memoreazun segment de instruciuni executatedinamic i secvenial n program (trace - segment). Un trace poate coninemai multe basic-block-uri (uniti secveniale de program). Aadar, o linieTC poate conineNinstruciuni sauMbasic - block-uri, N> M, nscrise pe

parcursul execuiei lor.


23/412


Memoria TC este accesatcu adresa de nceput a basic - block-ului A,n paralel cu predictorul multiplu de salturi (vezi figura 2.2). Acesta, spredeosebire de un predictor simplu, predicioneaznu doar adresa de nceput aurmtorului basic - block ce trebuie executat ci toate cele (M- 1) adrese denceput aferente urmtoarelor (M- 1) basic - block-uri care urmeazdupA.Cei (M - 1) bii generai de ctre predictorul multiplu (taken/not taken)selecteazspre logica de execuie doar acele blocuri din linia TC care sunt

predicionate cse vor executa (n cazul acesta doar blocurile A i B ntructpredictorul a selectat blocurile ABD cse vor executa, n timp ce n linia TCerau memorate blocurile ABC).

O linie din TC conine:

N instruciuni n form decodificat, fiecare avnd specificatblocul creia i aparine.

cele 2M-1 posibile adrese destinaie aferente celor M blocuristocate n linia TC.

un cmp care codificnumrul i "direciile" salturilor memoraten linia TC.

Figura 2.2.Ansamblul trace-cache respectiv predictor multiplu

nainte de a fi memorate n TC, instruciunile pot fi predecodificate nscopul nscrierii n TC a unor informaii legate de dependenele de date ce


24/412


caracterizeaz instruciunile din linia TC curent. Aceste informaii vorfacilita procese precum bypassing-ul datelor ntre unitile de execuie,redenumirea dinamic a regitrilor cauzatori de dependene WAR (WriteAfter Read) sau WAW (Write After Write) ntre instruciuni etc., utile nvederea procesrii Out of Order a instruciunilor. n [Lee02] este propusostructurcare extinde Trace Cache-ul cu un predictor hibrid de valori pentruinstruciunile cauzatoare de dependene. Prin predicia selectiva valorilorinstruciunilor este redus numrul de accese la tabela de predicie, rezultndo utilizare mult mai eficientresurselor, permindu-se astfel reducerea ciicritice de program i implicit creterea ratei de execuie.

O linie din TC poate avea diferite grade de asociativitate n sensul n

care ea poate conine mai multe pattern-uri de blocuri, toate avnd desiguraceeai adresde nceput (A), ca n figura 2.3.

Figura 2.3.Selecia dintr-o linie trace-cache asociativ

Aadar, segmentele ncepnd de la aceeai adres(A), sunt memoraten aceeai linie asociativ din TC. Ca i n structurile TC neasociative,verificarea validitii liniei selectate se face prin compararea (cutarea) duptag. Deosebirea de esenconstn faptul caici este necesarselectarea - nconformitate cu pattern-ul generat de ctre predictorul multiplu - trace-ul celmai lung dintre cele coninute n linia respectiv. Este posibil ca aceastselecie complex s dureze mai mult dect n cazul neasociativ i prinurmare s se repercuteze negativ asupra duratei procesului de aducere ainstruciunilor (fetch). Avantajul principal ns, dupcum se observ i n


25/412


figur, const n faptul c este probabil s se furnizeze procesorului unnumr de blocuri "mai lung" dect un TC simplu. Astfel de exemplu, dac

pattern-ul real de blocuri executate este ABD, structura TC l va furniza frprobleme, n schimb o structurTC neasociativce conine doar pattern-ulABC, evident va furniza n aceastsituaie doar blocurile AB.

Pe msur ce un grup de instruciuni este procesat, el este ncrcatntr-o aa-numit "fill unit" (FU - unitate de pregtire), dupcum poate fivzut n figura 2.6. Rolul FU este de a asambla instruciunile dinamice, pemsurce acestea sunt executate, ntr-un trace - segment. Segmentele astfelobinute sunt memorate n TC. Este posibil ca nainte de scriereasegmentului n TC, FU sanalizeze instruciunile din cadrul unui segment

spre a marca explicit dependenele dintre ele. Acest lucru va uura mai apoilansarea n execuie a acestor instruciuni ntruct ele vor fi aduse din TC iintroduse direct n staiile de rezervare aferente unitilor funcionale.Unitatea FU se ocupdeci de colectarea instruciunilor lansate n execuie,asamblarea lor ntr-un grup de N instruciuni (sau Mblocuri) i nscriereaunui asemenea grup ntr-o anumitlinie din TC. Existdesigur cazuri cndFU poate crea copii multiple ale unor blocuri n TC (vezi figura 2.4).Aceastredundaninformaionalpoate implica degradri ale performanei(nlocuirea unor linii din trace cache care conin informaie utilcu blocurileredundante determin creterea ratei de miss i implicit diminuarea rateiglobale de procesare), dar pe de alt parte, lipsa redundanei ar degradavaloarea ratei de fetch a instruciunilor deci i performana global.

Figura 2.4.Segmente asamblate pe timpul execuiei unei bucle de program

Se poate deci afirma c un TC exploateaz reutilizarea eficient asecvenelor dinamice de instruciuni, reprocesate frecvent n baza a 2 motivede principiu: localizarea temporal a trace-ului i respectiv comportarea

predictibil a salturilor n virtutea comportrii lor anterioare. Aadar, TC


26/412


memoreaztrace-uri n scopul eficientizrii execuiei programului i nu doarn scopul eficientizrii procesului de aducere al instruciunilor. Aceasta, pemotiv c un segment din trace conine numai instruciuni care se vorexecuta. n cazul IC, dac ntr-un bloc exist o ramificaie efectiv,instruciunile urmtoare se aduceau inutil ntruct nu s-ar fi executat.

Cum TC trebuie slucreze ntr-o strnsdependencu predictorul desalturi, se impune mbuntirea performanelor acestor predictoare. Osoluie de viitor ar consta ntr-un predictor multiplu de salturi, al crui rol

principal constn predicia simultana urmtoarelor (M- 1) salturi asociatecelor maximum M blocuri stocabile n linia TC. De exemplu, pentru a

prediciona simultan 3 salturi printr-o schem de predicie corelat pe 2

nivele, trebuie expandat fiecare intrare din structura de predicie PHT(Pattern History Table), de la un singur numrtor saturat pe 2 bii, la 7astfel de automate de predicie, ca n figura 2.5. Predicia generatde ctre

primul predictor (taken/not taken) va multiplexa rezultatele celor 2predictoare asociate celui de al doilea salt posibil a fi stocat n linia curentdin TC. Ambele predicii aferente primelor 2 salturi vor selecta la rndul lorunul dintre cele 4 predictoare posibile pentru cel de-al treilea salt ce ar puteafi rezident n linia TC, predicionndu-se astfel simultan mai multe salturi.Dacpredictorul multiplu furnizeazsimultan mai multe PC-uri, TC rezolvelegant i problema aducerii simultane a instruciunilor pointate de acestePC-uri, frmultiportarea pe care un cache convenional ar fi implicat-o.

Figura 2.5.Predictor a 3 salturi succesive

Asemenea predictoare multiple n conjuncie cu structuri de tip TCconduc practic la o nou paradigm a procesrii unui program mainnumit "multiflow", caracterizat prin procesarea n paralel a mai multor

basic-block-uri dintr-un program. Cercetri bazate pe simulare asupraconceptelor novatoare de TC i predictor multiplu, integrate ntr-o


27/412


arhitectursuperscalar extrem de agresivdezvoltat la Universitatea dinMichigan, SUA evideniazurmtoarele aspecte [Pat97]:

creterea gradului de asociativitate a TC de la 0 (mapare direct) la 4(asociativitate n blocuri de 4 intrri/ bloc) poate duce la creteri aleratei medii de procesare a instruciunilor de pnla 15%.

capaciti egale ale TC i respectiv memoriei cache de instruciuni (64ko, 128 ko) conduc la performane cvasioptimale.

asociativitatea liniei TC nu pare a conduce la creteri spectaculoase deperforman.

performana global fa de o arhitectur echivalent, dar fr TC,crete cu circa 24%, iar rata de fetch a instruciunilor n medie cu92%.

Figura 2.6.Microarhitecturde procesare care nglobeazun TraceCache

n [Jac99] sunt propuse trei optimizri ale trace-urilor de instruciuni

n cadrul unui trace procesor: scheduling-ul instruciunilor, propagareaconstantelor i colapsarea instruciunilor dependente de date.Preprocesarea instruciunilor se face nainte de plasarea acestora n TraceCache. Scopul preprocesrii este de a completa prin transformri adiionaleaplicabile n momentul execuiei, i nu de a substitui optimizrilecompilatoarelor, pentru o mai bunutilizare a resurselor hardware (unitide execuie i lrgime de band a mecanismului de issue limitate).Scheduling-ul instruciunilor este unul dinamic. Practic instruciunile nu


28/412


sunt mutate n altordine ci le sunt asignate prioriti care vor fi utilizate delogica de execuie out-of-order. Daco instruciune este identificatpentrua-i fi crescut prioritatea, atunci i lanului de instruciuni dependente deaceasta le va fi sporitprioritatea. De asemenea, instruciunilor care folosescvalorile generate de trace-uri (basic-blocuri) anterioare le va fi decrementat

prioritatea, iar instruciunilor care vor fi productoare de valori pentrualte trace-uri le va fi incrementatprioritatea. Colapsarea transformun lande instruciuni dependente de date ntr-o singurinstruciune, mai complex,cu mai mult de doi operanzi surs. Exploatat n conjuncie cu colapsareadependenelor de date, beneficiul scheduling-ului dinamic este mai

pronunat. Ctigul de performan msurat pe benchmark-urile SPEC95

este ntre 4% i 24%.La ora actual, procesorul Intel Pentium IV reprezintprimul procesor

comercial care nlocuiete nivelul L1 de cache clasic cu unExecution TraceCache. Dect smemoreze instruciunile standard x86, acest Trace Cachereine instruciunile dup ce tocmai au fost decodificate n instruciunispecifice RISC, numite microoperaii - ops. n fiecare linie a Trace Cache-ului Intel stocheaz 6 ops. Un predictor de tip BTB cu 4096 de intrriaferent trace-cache-ului (Trace Branch Predictor) este menit ssprijine aanumitul Execution Trace Cache 8 way asociativ, cu mecanism deevacuare de tipul Least Recently Used, care poate nmagazina pnla 12000

de microoperaii la versiunea Northwood a procesorului Intel realizat ntehnologie de 130nm, i respectiv pnla 16000 de ops la versiunea IntelPrescott implementat n tehnologie de 90nm [Intel03]. Dacpredictorul dgretrebuie ateptat 7 cicli pncnd este adusinstruciunea din nivelul L2de cache sau mai mult dac trebuie accesat memoria central. Dac

predicia este corectatunci trace-cache-ul poate furniza 3 ops per ciclu detact scheduler-ului de execuie. ntruct memoria TC stocheaz doarinstruciunile contigue din punct de vedere al execuiei n zone contigue,rezult c spaiul de cache, destul de limitat, este astfel mult mai eficientfolosit. Adresarea Execution Trace Cache se face cu adrese virtuale, nefiindnevoie de conversie n adrese fizice pn la accesul spre nivelul L2 de

cache. Decodificatorul aferent procesorului Intel Pentium4 poate converticel mult o instruciune x86 per ciclu de tact, mai puin dect celelaltearhitecturi. Cu toate acestea, ntruct microoperaiile sunt stocate n TC i

posibil refolosite parte din ele, lrgimea de banda unitii de decodificarepoate asigura o rat de 3 ops per ciclu de tact, cerut de unitatea de pre-execuie (issue). Dac o instruciune x86 necesit mai mult de 4 ops(instruciuni complexe, consumatoare de timp), atunci decodificatorulextrage microoperaiile suplimentare dintr-o memorie ROM dedicat.


29/412


n final sunt subliniate cteva aspecte suplimentare referitoare lamemoria Trace Cache i structurile de predicie ajuttoare, care intervin launul din cele mai recente procesoare produse de Intel. Pentium4 Hyper-Thread conine douprocesoare logice (executpractic doufire n modconcurent) i arbitreaz n fiecare ciclu de tact accesul la Trace Cache. nfiecare ciclu de tact este deservit cte un microthread. n cazul n care unuldin firele de execuie este blocat atunci cellalt va putea accesa TraceCache-ul n fiecare ciclu. Intrrile din TC sunt extinse cu cte un cmp deTag avnd informaii despre fire alocarea fcndu-se dinamic dupnecesiti. Partajarea TC se poate face inegal ntre cele doufire dupcumeste nevoie. Structurile de predicie pot fi i ele partajate sau duplicate.

Buffer-ul Return Stackcare prezice destinaia instruciunii de revenire dinproceduri este duplicat deoarece este o structur foarte mic i perechileCall / Return sunt predicionate mai bine pentru fiecare fir de execuie n

parte. Cte un registru de istorie global este pstrat independent pentrufiecare thread n parte. Cu toate acestea, registrul de istorie globalaferentntregului procesor reprezint o structur partajat avnd intrri cu Tag

pentru identificarea fiecrui threadn parte (procesor logic).O tehnicde cretere a lrgimi de banda mecanismului de aducere

prin sporirea unitii atomice de instruciuni o reprezint promovareabranch-urilor. Prin aceast tehnic, salturile condiionate, puternic

polarizate (spre taken T sau not taken NT) sunt convertite dinamic nsalturi predictibile static. Astfel, numrul salturilor prezise dinamic (chiarsimultan) va scdea, iar predictorul va suferi mai puin datoritinterferenelor. Unitatea de umplere a Trace Cache-ului este responsabilcuconversia (filtrarea) branch-urilor. ntruct anumite salturi condiionate sunt

puternic polarizate spre not taken iar altele spre taken rezult c, prinpromovarea acestora, instruciunile din interiorul unei uniti atomice dinTrace Cache sunt garantat executate toate sau neexecutate toate. Branch-urile candidate la promovare sunt detectate printr-un mecanism hardware

bazat pe o tabelde salturi care conin rezultatul fiecrui salt (T / NT) i unautomat de confiden reprezentat printr-un numrtor saturat. Valoarea

numrtorului reprezint de cte ori consecutiv branch-ul a avut acelairezultat. Unitatea de umplere indexeazaceasttabela de cte ori branch-uleste adugat segmentului de instruciuni care va fi inserat n Trace Cache.Dacvaloarea numrtorului este mai mare dect un thresholdimpus, atuncisaltul va fi promovat. n cazul n care un branch promovat se dovedetea fi greit predicionat, procesarea instruciunilor este reluatdin anteriorulpunct de verificare sfaritul basic-block-ului anterior. Prin tehnica de

promovare a branch-urilor, un segment de trace (un basic block) va aveamai puini succesori, astfel cpredictorul dinamic trebuie sselecteze ntre


30/412


mai puine inte posibile (numrul prediciilor necesare n fiecare ciclu detact scade).

Simulri laborioase realizate pe branchmark-urile SPEC95 au artatc pentru un threshold de 64 este mbuntit rata de fetch cu 7%. Deasemenea, folosind acelai threshold, necesitatea de a efectua 2 predicii perciclu de tact este de 12%, iar necesitatea de a efectua 3 predicii per ciclu detact este de 3%, pentru a umple o linie de 16 instruciuni a Trace Cache-ului.

Tehnica de promovare poate fi realizat i static prin extindereaarhitecturii setului de instruciuni (ISA) cu un cmp suplimentar de bii

pentru comunicarea salturilor puternic polarizate (T/NT) procesorului, nmomentul execuiei. Cu toate acestea, salturile care i schimbrezultatul pe

perioada execuiei (pe termen lung), dar rmn puternic polarizate (petermen scurt) sau sunt senzitive la datele de intrare pot fi scpate dinvedere n timpul analizei statice. Exist ns avantajul c salturile nutrebuie streacprintr-o fazde nclzire (warm-up) pnsfie detectateca ipromovabile[Pat98].

2.2. LIMITAREA CONSUMATORULUI (ISSUEBOTTLENECK). SOLUII.

Rata de execuie a instruciunilor este fundamental limitatde ctrehazardurile RAW ntre instruciuni (calea critic de program). Cauza

principal a acestei limitri o constituie natura intrinsec serial aprogramelor, n care se dicteazordinea secvenialde transmitere a datelorntre instruciuni. Alte limitri nefundamentale, le reprezinthazardurilestructurale i hazardurile de ramificaie. Aceste ultime limitri nuconstituie o limit superioar de paralelism obtenabil la nivelulinstruciunilor ntruct pot fi depite prin diverse tehnici software sauhardware. Hazardurile structurale sunt determinate de conflictele laresurse comune, adicatunci cnd mai multe procese simultane aferente maimultor instruciuni n curs de procesare, acceseaz o resurs comun(principala cauza conflictelor reprezentnd-o deci centralizarea resurselor).Pentru a le elimina prin hardware, se impune de obicei multiplicarea acestorresurse. De exemplu, un procesor care are un set de regitri generali de tipuniport i n anumite situaii existposibilitatea ca 2 procese sdoreascsscrie n acest set simultan. O altsituaie de acest fel poate consta n accesulsimultan la memorie a 2 procese distincte: unul de aducere a instruciunii


31/412


(IF), iar cellalt de aducere a operandului sau scriere a rezultatului n cazulunei instruciuni LOAD / STORE (nivelul MEM). Aceast situaie serezolv n general printr-o arhitecturHarvard a bus-urilor i cache-urilor(spaii i bus-uri separate pe instruciuni i date).

O idee interesantbazatpe descentralizarea resurselor [Fra93] are nvedere implementarea mai multor aa numite "Instruction Windows" (IW)-un fel de buffere de prefetch multiple n locul unuia singur i respectiv peconceptul de multithreading. Lansarea n execuie a instruciunilor se face

pe baza determinrii celor independente din fiecare IW. De asemenea,trebuie determinate i dependenele inter- IW- uri. Ideea principalconstnexecuia paralel a mai multor secvene de program aflate n IW- uri

diferite, bazat pe mai multe uniti funcionale (multithreading). Astfel deexemplu, 2 iteraii succesive aferente unei bucle de program pot fi procesaten paralel dac sunt memorate n IW- uri distincte. O asemenea ideefaciliteaz implementarea conceptelor de expandabilitate i scalabilitate,deosebit de utile n dezvoltarea viitoare a arhitecturii.

Hazardurile de ramificaie sunt generate de ctre instruciunile deramificaie (branch). Cauzeaz pierderi de perfoman n general maiimportante dect hazardurile structurale i de date, mai ales la procesoarelesuperscalare. Efectele defavorabile ale instruciunilor de ramificaie pot fireduse prin metode soft (reorganizarea programului surs), sau prinmetode hard care determinn avans dacsaltul se va face sau nu (branchprediction) i calculeazn avans noul PC (program counter) vezi pe largn capitolul 5.

n momentul de fa se disting mai multe abordri moderne deexploatare i cretere a paralelismului la nivelul instruciunii (ILP):Procesoarele superscalare extrag paralelismul dinamic prin execuie

speculativ, multithreading sau trimitere spre procesare "out of order":trace procesorul [Rot97], procesoare multithread [Wall99, Mar00],arhitectura multiscalar [Fra93]. Trace procesorul i procesorulsuperspeculativ speculeaz att dependenele de date ct i cele decontrol, n timp ce arhitectura multiscalar este susintoarea unei

abordri multithread cu expediere vastde fire spre execuie.Eforturile de mbuntire tehnologic i arhitectural sunt canalizate

spre reducerea decalajului tehnologic dintre un procesor avansat isistemul ierarhic de memorie (selective victim cache) [Sti94].

Ali factori care determinlimitarea ratei de issue a instruciunilor sunt:lrgimea de band limitat a interfeei procesor - cache, miss-urile ncache-ul de date, alias-urile de memorie. Pentru a contracara efectulacestor factori se poate utiliza cu succes mecanismul Data Write Buffer


32/412


(DWB). DWB reprezint un mic procesor de ieire care lucreaz nparalel cu CPU degrevndu-l pe acesta de sarcina scrierii n cache. DWBofer porturi de scriere virtuale multiple spre deosebire de DataCachecare conine un numr limitat de porturi (LOAD/STORE). DWB rezolv

prin "bypassing" elegant hazardurile de tip "LOAD after STORE" cuadrese identice, deseori nemaifiind deci necesaraccesarea sistemului dememorie de ctre instruciunea LOAD.

Prin colapsarea dependenelor reale de date ntre instruciuni se urmreteeliminarea / reducerea parial a efectelor defavorabile cauzate dehazardurile RAW (deblocarea instruciunilor dependente aflate nateptare), folosind daceste posibil uniti aritmetico-logice cu mai multde dou intrri. Tehnicile hardware recente de reutilizare dinamic ainstruciunilor i predicia valorilor, menite sexploateze redundanaexistent n programe, reducnd timpul de execuie al acestora princolapsarea dinamica dependenelor de date, sunt reprezentative n acestsens [Lip96, Sod00].

Schedulerele de instruciuni exploateaz paralelismul n momentulcompilrii prin rearanjarea codului surs, dezambiguizarea referinelor lamemorie, metode de in liningaplicate procedurilor, tehnici de optimizarelocal i/sau global (loop unrolling, list/trace scheduling, software

pipelining), etc. Procesoarele EPIC [Vin00a], cu paralelism explicit la

nivelul instruciunilor (vezi Intel Itanium 2), prin execuia speculativipredicativ urmresc creterea abilitii compilatoarelor n exploatareaparalelismului n programele cu procentaj ridicat de instruciuni deramificaii [Sias04].

Dezvoltarea de noi instrumente de cercetare care aparin i altor domenii(inteligenartificial, algorimi genetici etc) pentru creterea acurateii de

predicie a ramificaiilor de program - predictoare neuronale, genetice[Vin00a].

n continuare se va insista foarte pe scurt asupra ultimelor dou idei,anterior enunate. Dacpn recent, majoritatea compilatoarelor urmau unstil evoluionist de dezvoltare, bazat pe mbuntirea metodelor tradiionale

de scheduling (global / local) pentru creterea paralelismului la nivelulinstruciunilor, o ultim abordare realizat de compilatorul IMPACT[Sias04], structural i bazat pe transformri radicale la nivelulcontrolului programului (execuie predicativi speculativ, replicare decod), ncearco exploatare ct mai eficienta caracteristicilor procesoarelorEPIC, avnd acelai deziderat de performan.

n calea optimizrilor compilatorului pentru creterea paralelismului lanivelul instruciunilor se remarccteva obstacole:


33/412


instruciunile de salt, care descriu modul de traversare al grafului decontrol. Efectul defavorabil este redus prin execuie predicativ ifolosirea regitrilor booleeni de gard. Dependenele de control sunttransformate n dependene de date.

false dependene: accesele la memorie i apelurile de subrutinereprezint bariere n calea micrii codului (percolation [Vin00a]),

blocnd att scheduling-ul ct i optimizarea acestuia. IMPACT ncearceliminarea acestor false dependene prin algoritmi compleci de analizinterprocedural[Sias04].

dependenele ocazionale, provocate de execuia out-of-order ainstruciunilor load / store, nu pot fi nlturate static fr suport

suplimentar hardware pentru execuie speculativ (analiza antialiasdinamic ce presupune utilizarea de cod i regitrii suplimentari)nerezolvat ncde IMPACT.

nedeterminismul, poate fi introdus, spre exemplu, de accesele cu miss lamemoria cache de date a instruciunilor cu referire la memorie.

Compilatorul dezvoltat n laboratoarele de cercetare ale universitiidin Ilinois (IMPACT) i dedicat versiunii de procesor EPIC pe 64 bii (IntelItanium 2), dezvoltat de Intel n colaborare cu Hewlett-Packard, realizeazoanaliz interprocedural, inlining aplicat procedurilor, dar i anumitemodificri impuse n urma obinerii informaiilor de profil. Un exemplu deastfel de optimizare o reprezinttype feedback (vezi detalii n subcapitolul4.1), care, bazat pe informaii de profil, transform apelurile indirecte defuncii n apel direct i crora li se poate aplica apoi tehnica de inlining.Abordarea structural se refer la procesul de simplificare a grafului decontrol, generarea de zone de cod largi, stabile din punct de vedere alexecuiei (trace-uri) i reorganizarea acestora. Dintre avantajelecompilatorului IMPACT relativ la arhitectura Intel Itanium 2 se remarcspeed-up-ul obinut fa de compilatorul GNU gcc (pn la 2.3 [Sias04]),reducerea numrului de salturi cu 27%, reducerea numrului de cicli de

penalizare n cazul unei predicii eronate cu 22%, mbuntirea eficieneiprocesului fetch instruciune i diminuarea cu 15% a stagnrilor datorate

miss-urilor n cache-ul de instruciuni. Ca i efecte secundare, ocazional,prin execuia speculativ a instruciunilor load pot apare ntrzierisuplimentare datorate miss-urilor n cache-ul de date.

Datorit nvechirii paradigmei actuale de cercetare, cercettorii[Vin01] opineaz c, pentru continuarea creterii exponeniale a

performanei microprocesoarelor, sunt necesare idei noi, revoluionare chiar,bazate pe o abordare integratoare, care s mbine eficient tehnicile descheduling software cu cele dinamice, de procesare hardware. n prezent,separarea ntre cele 2 abordri este destul de accentuat. n acest sens,


34/412


programele ar trebui s expliciteze paralelismul intrinsec ntr-un mod maiclar. Cercetri actuale aratcun program optimizat static merge mai prost

pe un procesor Out of Order dect pe unul In Order [Tat00]. Printre cauze seamintesc expansiunea codului dupreorganizare, noile dependene de dateintroduse prin execuia condiionata instruciunilor, faptul cinstruciunilegardate nu permit execuia Out of Order etc.

Cercetarea algoritmilor ar trebui sinseama i de concepte precum,cel de cache, n vederea exploatrii localitilor spaiale ale datelor princhiar algoritmul respectiv. n general, algoritmii nu in cont la ora actualdecaracteristicile mainii i acest lucru nu este bun pentru c algoritmul nuruleazntr-un "eter ideal"[Vin00a] ci, ntotdeauna pe o mainfizicavnd

limitri importante (de ex. elementele unui tablou se pot afla parial n cachei parial pe disc!). Astfel, dihotomia teorie - practicdevine una artificiali cu implicaii negative asupra performanei globale a mainii.

Realizatorii aplicaiilor obiectuale i vizuale trebuie s in cont defaptul c polimorfismul genereaz apeluri indirecte de funcii, greu

predictibile la nivel hardware [Flo04]. Preocuprile programatorilor nutrebuie svizeze doar interfaa care atrage sau diversele artificii care fac dinutilizator un simplu robot ci i implicaiile pe care aplicaia creat o areasupra microarhitecturii. Scopul aplicaiei trebuie s fie utilizarea optimatt a resurselor software (biblioteci, elemente de interfa) avute ladispoziie ct i a algoritmilor / conceptelor de programare cunoscute(declaraii de funcii virtuale, apeluri de funcii prin pointer chiar i acolounde nu este cazul). n caz contrar, "rul" (a se citi n primul rnd salturiindirecte, cod obiect masiv, resurse hardware suplimentare) se rsfrngeasupra performanelor arhitecturii. n ce-i privete pe proiectanii dearhitecturi, schemele propuse de acetia ar putea fi mai eficiente dacnu aranaliza numai codul obiect al benchmark-urilor avute la dispoziie(dezbrcat de orice semantic) ci ar privi "mai sus" spre sursa de nivel nalta programelor simulate.

Abordarea strict convenional, situat doar la nivelul arhitecturilorde calcul, pare s fie insuficient pentru ndeplinirea dezideratului de

performan ridicat. O abordare mai neconvenional, care s utilizezeconcepte ale unor domenii considerate pnn prezent a nu avea legaturcuarhitectura sistemelor de calcul (arbori de decizie, reele neuronale,algoritmi genetici, algoritmi de predicie PPM) poate genera rezultatesurprinztoare, precum i o mbuntire a paradigmei arhitecturiloravansate. n [Vin99b, Jim02] sunt propuse, cu mare success, structuri de

predicie alternative care fac o legtur neateptat ntre domeniularhitecturii procesoarelor avansate i cel al recunoaterii formelor.Predictoarele neurale de tip Perceptron i MultiLayerPerceptron costituie


35/412


soluii fezabile hardware i cu acuratei de predicie cel puin de nivelulpredictoarelor corelate pe douniveluri. n [Vin00b] este descris modul dedeterminare automat cu ajutorul arborilor binari a unor noi scheme de

predicie a salturilor pe baza unor algoritmi genetici, pornind de la opopulaie iniial de predictoare cunoscute. Exist cercetri cu rezultateremarcabile n domeniul prediciei salturilor [Vin99a] sau cel al predicieivalorilor [Saz99], care utilizeaz lanuri Markov i algoritmul de predicie

bazat pepotrivire parial(PPM complet), folosit cu succes n compresiadatelor. n subcapitolul 5.3 am descris cteva cercetri proprii privind

predicia target-urilor salturilor indirecte folosind predictoare bazate pecontext i algoritmul PPM-complet. Dintre cele mai recente cercetri, se

poate ilustra ca exemplu n sprijinul ideii de abordare neconvenional,folosirea arborilor de decizie pentru selecia celor mai relevantecaracteristici necesare procesului de predicie [Fern03].

2.2.1. REUTILIZAREA DINAMICA INSTRUCIUNILOR

Reutilizarea dinamic a codului se nscrie n domeniul optimizrilorarhitecturilor de calcul i s-a manifestat pentru prima datla nivel software,

prin tehnica deprogramare dinamic metodde rezolvare a problemelor a

cror soluie se construiete dinamic n timp. Introdus nc din 1957 dectre matematicianul american Richard Bellman [Bell57], programareadinamic opereaz ntr-o manier bottom-up, nerecursiv i presupunecunoaterea exact, de la nceput, a subproblemelor care nu suntindependente aprute n descompunerea problemei iniiale. Pentru a fieficient, metoda programrii dinamice trebuie s rezolve fiecare

subproblem o singur dati s memoreze soluia acesteia pentru a oputea utiliza n cazul reapariiei aceleai subprobleme n cadrul unei altesubprobleme. Fazele rezolvrii unei probleme prin metoda programriidinamice sunt:

rezolvarea subproblemelor de dimensiunile cele mai mici care aparn descompunerea problemei iniiale i memorarea soluiiloracestora;

rezolvarea treptata subproblemelor de dimensiuni din ce n ce maimari prin combinarea soluiilor subproblemelor de dimensiuni maimici i memorarea soluiilor acestora pnla obinerea rezultatuluifinal.

Reutilizarea dinamica instruciunilor(reutilizare de tip fine grain)este o tehnicnon-speculativmenit sexploateze fenomenul de repetiie


36/412


dinamica instruciunilor, reducnd cantitatea de cod - mainnecesar a fiexecutat i care prin colapsarea dependenelor de date determinmbuntirea timpului de execuie al instruciunilor crescnd gradul de

paralelism al arhitecturii. Ideea originaraparine cercettorilorA. Sodani iG. Sohii a fost introdusn 1997, la conferinaISCA 97inutla Denver,SUA. n [Sod97] se arat c reutilizarea unor instruciuni sau secvene deinstruciuni este relativ frecventi se datoreazmodului compact de scrierea programelor precum i caracteristicilor intrinseci ale structurilor de date

prelucrate. O instruciune dinamic este reutilizabil dac ea opereazasupra acelorai intrri i produce aceleai rezultate precum o instananterioara aceleiai instruciuni. Ideea de bazeste cdaco secvende

instruciuni se reia n acelai context de intrare, atunci execuia sa nu maiare sens fiind suficient o simpl actualizare a contextului de ieire, nconcordan cu unul precedent memorat. Se reduce astfel numrul deinstruciuni executate dinamic, acionndu-se direct asupra dependenelor dedate ntre instruciuni. Instruciunile reutilizate nu se vor mai executa dinnou, contextul procesorului fiind actualizat n conformitate cu aciuneaacestor instruciuni, bazat pe istoria lor memorat.

n [Sod98] se analizeaz mai nti dac gradul de reutilizare ainstruciunilor dinamice este semnificativ i se aratcrspunsul este unulafirmativ. Mai puin de 20% din numrul instruciunilor statice care suntrepetate implico repetabilitate de peste 90% a instruciunilor dinamice. nmedie armonic, msurat pe benchmarkurile SPEC95, 26% dintreinstruciunile dinamice sunt reutilizabile. Exist n acest sens 2 cauzecalitative: n primul rnd faptul cprogramele sunt scrise n mod generic,ele opernd asupra unei varieti de date de intrare, iar n al doilea rnd,aceste programe sunt scrise ntr-un mod concis aceasta semnificndmeninerea unei reprezentri statice compacte a unei secvene dinamice deoperaii n vederea obinerii rezultatelor dorite (n acest sens structurile detip recursiv, buclele de program etc. sunt reprezentative).

Pentru o mai bun nelegere a fenomenului de repetiie ainstruciunilor, execuia dinamic a programelor este analizat pe trei

niveluri: global, de funcie i local (n interiorul funciei). n analiza global,pattern-urile de date utilizate n programe sunt reinute ca entiti ntregi ideterminate sursele de repetiie ale instruciunilor (intrri externe, iniializriglobale de date sau valori interne ale programelor). ntruct repetiiainstruciunilor se datoreazn mare msurultimelor dousurse de repetiie,se impune concluzia cfenomenul de repetiie este mai mult o proprietate amodului n care calculul este exprimat n program i mai puin o proprietatea datelor de intrare. Concluziile generate n urma analizei la nivel de funciesunt cde foarte multe ori funciile sunt invocate repetat cu exact aceleai


37/412


valori ale parametrilor de intrare i crelativ puine apeluri de funcii nu auargumente repetate. Chiar i n cazul unor apeluri repetate ale unei funcii cu

parametrii de intrare diferii, procentajul de instruciuni dinamicereutilizabile poate fi semnificativ. La nivelul analizei locale, instruciunilefunciilor/procedurilor sunt clasificate n funcie de sursa valorilor folosite(exemplu: argumentele funciei, date globale, valori returnate de alte funciietc.) i funcie de sarcina realizat (exemplu: salvare - restaurare regitri,

prolog - epilog, calcul adrese globale etc.). Majoritatea repetiieiinstruciunilor se datoreazvalorilor globale sau argumentelor funciei dar ifunciilor prolog i epilog.

Preluat din [Sod97], se prezintn continuare un exemplu sugestiv n

care apare fenomenul de reutilizare dinamica instruciunilor. Funciafunc(figura 2.7.a) cauto valoare x n tabloul listde dimensiunea size. Funcia

principalmain_func(figura 2.7.c) apeleazfuncia funcde mai multe ori,cutnd cte un alt element n acelai tablou la fiecare apel. La apelulfunciei func tabloul este parcurs element cu element n mod iterativ,cutndu-se valoarea pna la captul tabloului, condiia de ncheiere acutrii reprezentnd-o gsirea elementului. Expandarea buclei din interiorulfunciei func corespondent unei iteraii este prezentat n figura 2.7.b.Instanele dinamice ale instruciunilor generate de primul apel func suntdescrise n figura 2

Date post:	04-Jun-2018
Category:	Documents
Upload:	stefanvnv
View:	227 times
Download:	0 times

2 Predicţia dinamicăa valorilor în microprocesoarele generaţiei următoare

Documents