Metode avansate de predicţie integrate în arhitecturi cu...

Universitatea „Lucian Blaga” din Sibiu Facultatea de inginerie „Hermann Oberth” Catedra de Calculatoare şi Automatizări

Metode avansate de predicţie integrate în arhitecturi cu

procesări speculative

Teză de doctorat

Rezumat

Autor: Asist. univ. ing. Árpád GELLÉRT, MSc

Conducători ştiinţifici: Prof. univ. dr. ing. Lucian N. VINŢAN

Prof. univ. dr. Theo UNGERER (cotutelă)

SIBIU, 2008

2

Mulţumiri

În primul rând doresc să mulţumesc conducătorului meu de doctorat prof. univ. dr. ing. Lucian VINŢAN, pentru încrederea acordată, pentru deosebita responsabilitate a coordonării sale ştiinţifice, pentru discuţiile profesionale extrem de stimulative pe care le-am avut şi pentru întreg sprijinul acordat cu multă generozitate. De asemenea, mulţumesc conducătorului de doctorat prin cotutelă, prof. dr. Theo UNGERER de la Universitatea din Augsburg, Germania, pentru discuţiile utile şi pentru sprijinul oferit. Ţin să mulţumesc colegului meu dr. Adrian FLOREA pentru ajutorul acordat şi pentru sfaturile sale deosebit de utile. Mulţumesc şi d-lui Dr. Colin EGAN de la Universitatea din Hertfordshire pentru colaborarea sa precum şi pentru observaţiile şi sugestiile făcute. De asemenea, doresc să mulţumesc colegilor de la Catedra de Calculatoare şi Automatizări din cadrul Universităţii „Lucian Blaga” pentru sprijinul acordat şi pentru climatul favorabil asigurat. Nu în ultimul rând, doresc să mulţumesc familiei pentru sprijinul necontenit şi pentru răbdarea de care a dat dovadă în această perioadă.

Cercetările prezentate în această lucrare au fost parţial susţinute prin granturile CNCSIS TD-248/2007-2008 şi A-39/2007-2008 respectiv prin proiectul HPC-EUROPA (RII3-CT-2003-506079) din cadrul programului FP6 „Structuring the European Research Area”, cu suportul Comunităţii Europene (Research Infrastructure Action).

3

Cuprins

1. Introducere ______________________________________________________________ 4

2. Arhitecturi cu execuţii speculative ____________________________________________ 6

3. Identificarea branch-urilor dificil predictibile___________________________________ 7 3.1. Metodologia de identificare_______________________________________________________ 7 3.2. Rezultate experimentale _________________________________________________________ 8

4. Predicţia dinamică a branch-urilor dificil predictibile ___________________________ 10 4.1. Predictoare Markoviene ________________________________________________________ 10 4.2. Utilizarea condiţiei de salt precedente ca informaţie de predicţie ______________________ 11 4.3. Rezultate experimentale ________________________________________________________ 12

5. Gradul de aleatorism al branch-urilor nepolarizate _____________________________ 14 5.1. Metrici de caracterizare a aleatorismului branch-urilor nepolarizate __________________ 14

5.1.1. Modele Markov cu legături ascunse ____________________________________________________ 14 5.1.2. Entropia discretă ___________________________________________________________________ 15 5.1.3. Rata de compresie __________________________________________________________________ 15 5.1.4. Complexitatea Kolmogorov __________________________________________________________ 15

5.2. Rezultate experimentale ________________________________________________________ 16 6. Metode de reutilizare şi predicţie selective a valorilor instrucţiunilor în arhitecturi superscalare ________________________________________________________________ 19

6.1. Anticiparea rezultatelor instrucţiunilor cu latenţă ridicată ___________________________ 19 6.1.1. Reutilizarea selectivă a instrucţiunilor __________________________________________________ 19 6.1.2. Predicţia selectivă a valorilor instrucţiunilor Load _________________________________________ 20 6.1.3. Rezultate experimentale _____________________________________________________________ 21

6.2. Predicţia dinamică a valorilor orientată pe registrele procesorului_____________________ 22 6.2.1. Predictoare de valori centrate pe registre ________________________________________________ 22 6.2.2. Rezultate experimentale _____________________________________________________________ 25

7. Arhitectură SMT îmbunătăţită cu metode de reutilizare şi predicţie a valorilor instrucţiunilor_______________________________________________________________ 26

7.1. Metode de reutilizare a instrucţiunilor şi predicţie a valorilor în arhitecturi SMT ________ 26 7.2. Rezultate experimentale ________________________________________________________ 26

8. Concluzii şi dezvoltări ulterioare ____________________________________________ 28

Bibliografie selectivă _________________________________________________________ 31

4

1. Introducere

Paralelismul la nivelul instrucţiunilor este limitat de dependenţele existente între instrucţiuni, iar pentru eliminarea lor microprocesoarele moderne, unele din ele prezentate în Capitolul 2, folosesc tehnici speculative. Principalul obiectiv al acestei teze îl reprezintă creşterea performanţelor unor microarhitecturi superscalare şi SMT (Simultaneous Multithreading) prin tehnici anticipatorii dinamice precum predicţia branch-urilor, predicţia valorilor şi reutilizarea instrucţiunilor. Această lucrare aduce contribuţii originale în identificarea branch-urilor dificile şi îmbunătăţirea predictibilităţii lor, în caracterizarea comportamentului acestora din punct de vedere al gradului de aleatorism, respectiv în dezvoltarea unor tehnici de reutilizare şi predicţie selective a valorilor instrucţiunilor în cadrul arhitecturilor superscalare şi al celor cu fire multiple de execuţie.

Instrucţiunile de ramificaţie, generate de construcţii de limbaj de tipul if, switch, for, while etc., reprezintă un obstacol major în exploatarea paralelismului la nivelul instrucţiunilor (ILP). Rezultate statistice bazate pe simulări laborioase pe benchmark-uri reprezentative arată că o instrucţiune de ramificaţie apare la fiecare 5 – 8 instrucţiuni executate, ceea ce înseamnă că rata de aducere a instrucţiunilor este limitată la cel mult 8, aducerea simultană a mai multor instrucţiuni fiind inutilă. Pentru creşterea gradului de paralelism la nivelul instrucţiunilor procesoarele moderne folosesc predictoare markoviene, neuronale, bayesiene, bazate pe arbori de decizie sau pe algoritmi de tipul support vector machine etc., simplificate pentru a putea fi implementate în hardware. Prin predicţia dinamică a branch-urilor pot fi procesate mai multe basic block-uri în paralel. Pentru îmbunătăţirea performanţei instrucţiunile de ramificaţie trebuie identificate şi atât direcţia cât şi adresa de salt trebuie predicţionate corect. Factorul de superscalaritate al microprocesoarelor devine din ce în ce mai mare, permiţând rate de procesare mai agresive pentru îmbunătăţirea performanţelor. Procesoarele cu factor mare de superscalaritate pot fi afectate din punct de vedere al performanţelor în cazul predicţiilor greşite când contextul CPU trebuie refăcut şi instrucţiunile trebuie reexecutate pe căile corecte. De aceea, performanţa globală depinde foarte mult de acurateţea predictorului de salturi. Având în vedere faptul că numărul de instrucţiuni executate per ciclu creşte neliniar cu acurateţea predicţiei, este foarte importantă îmbunătăţirea acurateţii predictoarelor actuale.

Calitatea unui model de predicţie este dependentă de calitatea informaţiei disponibile. Este foarte importantă alegerea caracteristicilor pe baza cărora se generează predicţia. Marea majoritate a predictoarelor de salturi se bazează pe mai multe informaţii de intrare (adresa instrucţiunii de salt, istoria locală, istoria globală, informaţii de cale etc.) fără să ţină cont de cauzele reale (ex. instrucţiuni de salt nepolarizate) care produc o acurateţe scăzută şi implicit performanţe mai slabe. În Capitolul 3 am identificat instrucţiunile de ramificaţie dificile, cu polarizare scăzută în contextul dinamic considerat, oscilând între taken (saltul se face) respectiv not taken (saltul nu se face) într-un mod nedeterminist, entropic (comportament dezordonat), şi am încercat îmbunătăţirea predictibilităţii lor prin extinderea informaţiei de predicţie. În Capitolul 4 am arătat că pentru anumite instrucţiuni de ramificaţie, informaţiile de predicţie limitate (istorie locală, istorie globală şi calea spre branch-ul supus predicţiei) folosite de predictoarele actuale nu sunt întotdeauna suficient de relevante şi, din această cauză, ele nu pot fi predicţionate cu acurateţe. De aceea, am dezvoltat diferite predictoare care folosesc ca informaţie de predicţie suplimentară condiţia de salt precedentă sau istoria comprimată a precedentelor condiţii de salt. În Capitolul 5 am arătat că aleatorismul comportării acestor branch-uri dificile este o consecinţă a complexităţii uriaşe a programelor care le generează. Totodată, am arătat că problema esenţială a predicţiei lor, la ora actuală, o constituie încercarea de a le reprezenta mai adecvat în spaţiul caracteristicilor.

Introducere

5

Instrucţiunile cu latenţă ridicată reprezintă o altă sursă de limitare a paralelismului la nivelul instrucţiunilor. În Capitolul 6 am dezvoltat o arhitectură superscalară cu mecanism de anticipare selectivă a valorilor instrucţiunilor cu latenţă de execuţie ridicată, care include o schemă de reutilizare pentru instrucţiunile Mul şi Div, respectiv un predictor de valori pentru instrucţiunile Load critice. De asemenea, am extins predicţia dinamică a valorilor prin introducerea conceptului de predicţie a valorilor centrată pe contextul CPU (registre) şi nu pe instrucţiuni. Practic se prezice valoarea registrului destinaţie curent bazat pe analiza valorilor anterioare ale acestuia. Astfel se reduce semnificativ numărul predictoarelor şi scade corespunzător complexitatea şi consumul de putere statică/dinamică. În Capitolul 7 am analizat eficienţa mecanismului de anticipare selectivă a valorilor instrucţiunilor cu latenţă de execuţie ridicată şi într-o arhitectură SMT, focalizându-ne pe aceleaşi instrucţiuni: Mul şi Div respectiv Load-uri critice.

În Capitolul 8 sunt trecute succint în revistă contribuţiile ştiinţifice ale acestei lucrări şi sunt evidenţiate câteva dintre direcţiile viitoare de cercetare.

6

2. Arhitecturi cu execuţii speculative

În această lucrare am folosit două simulatoare: Simplesim [Bur97] şi M-SIM [Sha05] care extinde Simplesim cu suport pentru multithreading respectiv evaluarea consumului de putere. Sim-outorder din cadrul setului de instrumente Simplesim suportă execuţie out of order şi speculativă pe baza unităţii RUU (register update unit). Schema RUU utilizează un buffer de reordonare (ROB) necesar în redenumirea automată a registrelor şi reţinerea rezultatelor pentru instrucţiunile aflate în aşteptare. În fiecare ciclu, bufferul de reordonare retrage instrucţiunile încheiate în ordinea iniţială a programului şi le depune şi în setul de registre. Sistemul de memorie cuprinde şi un buffer aferent instrucţiunilor Load/Store (LSQ). Valorile de memorat sunt plasate în coadă dacă instrucţiunea Store este speculativă. Instrucţiunile Load pot fi satisfăcute fie prin execuţie propriu-zisă fie printr-un mecanism de bypassing realizat hardware, preluând valoarea de înscris a unei instrucţiuni Store direct din coada de aşteptare, în cazul unei potriviri de adresă.

Simulatorul foloseşte un pipeline cu cinci faze importante implementate în software: fetch, dispatch, issue, write back şi commit. Faza clasică de execuţie este distribuită în fazele dispatch şi issue. În implementarea software a acestei arhitecturi superscalare fazele pipeline sunt executate secvenţial generând astfel probleme de sincronizare. Deoarece un ciclu de execuţie corespunde unei iteraţii secvenţiale ale tuturor fazelor pipeline, efectele unei anumite faze sunt văzute „instantaneu” de fazele următoare prea devreme, în ciclul curent. Pentru eliminarea acestor probleme de sincronizare, fazele pipeline sunt executate în ordine inversă, efectele unei anumite operaţii (de un ciclu) fiind astfel vizibile doar în următorul ciclu (iteraţie).

În faza fetch a structurii pipeline se citesc următoarele instrucţiuni din cache-ul de instrucţiuni care sunt depuse apoi într-un buffer de prefetch, în aşteptare, de unde vor fi expediate spre decodificare şi execuţie. De asemenea, se calculează cu ajutorul predictorului noua linie din cache-ul de instrucţiuni de unde va avea loc următorul proces de fetch.

În faza dispatch are loc decodificarea instrucţiunilor şi alocarea intrărilor în structurile RUU/LSQ. În fiecare ciclu procesor, sunt preluate din bufferul de prefetch un număr de instrucţiuni, cel mult numărul maxim de instrucţiuni ce pot fi executate simultan.

Nivelul issue al structurii pipeline localizează în fiecare ciclu instrucţiunile pentru care registrele sursă sunt disponibile. Dacă unităţile funcţionale sunt disponibile se startează execuţia instrucţiunilor (fiecărei unităţi funcţionale libere i se asociază, dacă există, o instrucţiune de acelaşi tip cu unitatea). În final, rutina organizează evenimentele de scriere a rezultatelor (în registre, memorie) în funcţie de latenţele unităţilor funcţionale.

Scrierea efectivă a rezultatelor se realizează în faza writeback. În fiecare ciclu maşină se scanează coada de evenimente aferente instrucţiunilor care au încheiat faza de execuţie. La găsirea unei instrucţiuni în această coadă, se parcurge lanţul dependenţelor de date aferent instrucţiunii respective pentru a marca instrucţiunile dependente aflate în aşteptare.

Faza commit tratează instrucţiunile care sunt gata să actualizeze corect (in-order) structurile hardware folosite (buffer de reordonare, set de registre, coada de instrucţiuni Load/Store, unitatea RUU). De asemenea, se actualizează şi cache-ul de date (sau memoria) şi sunt tratate accesele cu miss în bufferul de date TLB.

Fazele fetch, dispatch şi commit sunt executate în ordine, în timp ce fazele celelalte pot fi executate out of order. Execuţia instrucţiunii este efectuată „instantaneu” în rutina ruu_dispatch, fazele următoare fiind executate doar în vederea evaluării timing-ului. Astfel, nu e necesară stocarea rezultatelor instrucţiunilor în structurile RUU/LSQ la sfârşitul fazei writeback, şi nici actualizarea setului de registre în faza commit, aceste operaţii fiind deja efectuate în faza dispatch.

7

3. Identificarea branch-urilor dificil predictibile

O posibilitate de a îmbunătăţi performanţele microarhitecturilor speculative moderne constă in identificarea şi rezolvarea instrucţiunilor de salt dificile – instrucţiuni de salt nepredictibile prin informaţiile de corelaţie folosite de metodele actuale de predicţie (istorie locală, istorie globală şi cale). Primul obiectiv este identificarea branch-urilor dificile din benchmark-urile SPEC 2000 [SPEC]. În acest capitol am considerat că instrucţiunile de salt în anumite contexte dinamice nepolarizate ar putea fi nepredictibile şi am demonstrat acest lucru prin simulări. Al doilea obiectiv constă în îmbunătăţirea acurateţii predicţiei acestor instrucţiuni de ramificaţie cu entropie ridicată, cu predictoare eficiente, folosind informaţii de context mai potrivite.

3.1. Metodologia de identificare

În acest paragraf este prezentată, pe baza lucrărilor publicate [Gel06a, Vin06, Oan06, Gel07c], metodologia de identificare a branch-urilor dificile. Pentru fiecare branch dinamic (în curs de procesare), predicţia se face pe baza unei informaţii binare de context ataşată respectivului branch şi considerată relevantă pentru comportamentul său (istoria locală sau globală a branch-ului memorată pe un anumit număr de biţi, calea de program pe care s-a ajuns la saltul condiţionat curent – branch’s path etc.). Am observat statistic că anumite branch-uri dinamice, într-un anumit context binar de apariţie, au un comportament nepolarizat, fiind atât taken cât şi not taken în proporţii semnificative (unbiased branches le-am numit în [Vin06, Gel07c]).

Mai precis, se consideră contextul de apariţie al unui branch dinamic ca fiind pe p biţi. Fiecare branch static are asociate k contexte dinamice de apariţie ( pk 2≤ ). Indexul de polarizare al unui branch apărut într-un context dat se defineşte ca fiind:

<≥

==5,0,5,0,

),()(01

0010 ff

ffffMaxSP i (3.1)

unde: • { }kSSSS ...,,, 21= = mulţimea contextelor distincte apărute pentru toate instanţele

branch-ului; • k = numărul de contexte distincte, pk 2≤ ;

• NTT

NTfNTT

Tf+

=+

= 10 , , NT = numărul de instanţe not taken corespunzătoare

contextului Si, T = numărul de instanţe taken corespunzătoare contextului Si, ki ...,,2,1)( =∀ şi evident 110 =+ ff ;

• P(Si) ]1;5,0[∈ , semnificând pentru minimul 0,5 nepolarizare maximă a contextului iS . În plus, daca aceste branch-uri nepolarizate au şi un comportament haotic, entropic, adică

în contextul dat sunt amestecate (taken şi not taken), ele sunt practic impredictibile (comportamentul lor nu poate fi învăţat). Relativ la un context binar Si, am definit indicatorul numit grad de amestecare, astfel:

>⋅

==

0,),min(2

0,0)(

tt

t

i nTNT

nn

SD (3.2)

Identificarea branch-urilor dificil predictibile

8

unde:

• nt = numărul de tranziţii binare ( 10 → or 01→ ) într-un anumit context Si; • ),min( TNT reprezintă minimul dintre numărul de apariţii al lui ‘0’ (not taken) respectiv

al lui ‘1’ (taken). Deci ),min(2 TNT⋅ = numărul maxim de tranziţii binare posibile.

Se observă imediat că D(S) ]1,0[∈ , fiind maxim în cazul unor amestecări maximale ale simbolurilor ‘0’ şi ‘1’ în secvenţă.

Am evaluat indexul de polarizare pentru fiecare context din benchmark-urile SPECint2000 şi am identificat branch-urile dinamice care au apărut în contexte cu un index de polarizare (P) de sub 0,95 (am ales acest prag cu scopul de a obţine acurateţi de predicţie finale de cel puţin 95%). Am încercat apoi reducerea numărului acestor branch-uri dificile prin extinderea informaţiei de predicţie (Figura 3.1).

GH16 bits

LH16 bits

GH20 bits

LH20 bits

GHp bits

LHp bits

U

U

U

U

U

Unbiasedbranches

GH16 bitsGH

16 bits

LH16 bitsLH

16 bits

GH20 bitsGH

20 bits

LH20 bitsLH

20 bits

GHp bitsGHp bits

LHp bitsLHp bits

U

U

U

U

UUU

UnbiasedbranchesUnbiasedbranches

Figura 3.1. Reducerea numărului de branch-uri nepolarizate prin extinderea informaţiei de predicţie

Pentru lista finală de branch-uri nepolarizate vom căuta alte informaţii de context, relevante, care să le reduca entropia (haosul) şi deci să devină astfel mai predictibile.

3.2. Rezultate experimentale Pe baza unor simulări laborioase am arătat că procentajul branch-urilor nepolarizate, pe istoria locală şi globală, este semnificativ: în medie între 6% şi 24% pe benchmark-urile SPEC 2000 (Figura 3.2), în funcţie de contextul de predicţie folosit şi de lungimea acestuia (16-28 biţi).

6.19

17.48

0

5

10

15

20

25

30

16 bits 20 bits 24 bits 28 bits

Feature Set Length

Unb

iase

d C

onte

xt In

stan

ces

[%] LH

GH

Figura 3.2. Reducerea procentajului de branch-uri nepolarizate (P<0,95) prin extinderea informaţiei de

predicţie

Identificarea branch-urilor dificil predictibile

9

De asemenea, am arătat că 89,37% din contextele nepolarizate identificate, au un index de distribuţie de peste 0,4, având astfel un comportament dezordonat.

Cercetările noastre au arătat că adăugarea informaţiei de cale (formată din PC-urile ultimelor k branch-uri) la cele clasice de istorie locală/globală determină o polarizare mai ridicată doar în cazul folosirii unor contexte de istorie locală/globală scurte (sub 16 biţi).

15%20%25%30%35%40%45%50%55%

p=1 p=4 p=8 p=12 p=16 p=20 p=24

Context Length

Unb

iase

d C

onte

xt In

stan

ces

GH (p bits)GH (p bits) + PATH (p PCs)

Figura 3.3. Scăderea procentajului de branch-uri nepolarizate prin introducerea informaţiei de cale

Figura 3.3 arată că istoriile locale şi globale suficient de lungi aproximează foarte bine informaţia de cale, îmbunătăţirea fiind astfel nesemnificativă prin adăugarea acestei noi informaţii de predicţie.

10

4. Predicţia dinamică a branch-urilor dificil predictibile

În Capitolul 3 am arătat că procentajul branch-urilor dificile este semnificativ (între 6% şi 24%, în funcţie de informaţia de predicţie folosită şi lungimea acesteia). În acest capitol am evaluat cele mai importante predictoare actuale, unele îmbunătăţite cu istoria precedentelor condiţii de salt propuse în [Gel07a, Gel07b, Gel07c], pe branch-urile nepolarizate identificate în Capitolul 3.

4.1. Predictoare Markoviene

A doua idee de reducere a numărului de branch-uri nepolarizate, după extinderea informaţiei de predicţie (prezentată în Capitolul 3), a fost aceea de a căuta alte informaţii de context, relevante, care să le reduca entropia (haosul) şi deci să devină astfel mai predictibile. Altfel spus, am căutat acele informaţii relevante prin prisma cărora branch-urile unbiased să devină mai polarizate şi deci, mai predictibile. Am încercat inclusiv predicţia valorii (semnului) condiţiei de salt întrucât aceasta determină comportamentul saltului. Astfel, o anumită instrucţiune de ramificaţie asociată cu semnul condiţiei de salt ar fi polarizată perfect. Dacă semnul condiţiei de salt ar fi predictibil, atunci şi comportamentul instrucţiunii de ramificaţie ar fi predictibil, datorită corelaţiei deterministe dintre condiţia şi respectiv direcţia de salt. De aceea, predicţia semnului condiţiei de salt pe baza unei istorii locale/globale a condiţiei de salt, pare să fie raţională. Am dezvoltat diferite predictoare de valori Markoviene care folosesc istoria comprimată a precedentelor condiţii de salt, ale cărei elemente pot fi -1, 0 sau 1, în funcţie de semnul diferenţei dintre operanzi. Astfel, condiţia branch-ului curent (B0) este predicţionată pe baza condiţiilor aferente branch-urilor precedente (B1, B2, ..., Bh). Comportamentul branch-ului curent (taken sau not taken) este determinat speculativ pe baza condiţiei predicţionate.

Cea mai eficientă dintre aceste scheme, prezentată în Figura 4.1, combină predicţiile mai multor predictoare Markoviene printr-un mecanism de tip voter.

PC of B0

Branch DifferenceHistory Table (BDHT)

dif(Bh) dif(B2) dif(B1)

Predicteddif(B0)

(-1, 0, +1)

Speculativeexecution of B0

Markovord. 1

Predicteddif(B0)

(-1, 0, +1)

Predicteddif(B0)

(-1, 0, +1)

Predicteddif(B0)

(-1, 0, +1)

Voter

Markovord. k

Markovord. n

PC of B0PC of B0

Branch DifferenceHistory Table (BDHT)

dif(Bh) dif(B2) dif(B1)dif(Bh) dif(B2) dif(B1)

Predicteddif(B0)

(-1, 0, +1)



Markovord. 1

Markovord. 1

Predicteddif(B0)

(-1, 0, +1)

Predicteddif(B0)

(-1, 0, +1)

Predicteddif(B0)

(-1, 0, +1)

Voter

Markovord. k

Markovord. k

Markovord. n

Markovord. n

Figura 4.1. Mecanism de predicţie a branch-urilor cu predictoare Markoviene

Predicţia dinamică a branch-urilor dificil predictibile

11

Tabela BDHT (Branch Difference History Table) păstrează pentru fiecare branch static condiţiile ultimelor h instaţe dinamice (B1, B2, ..., Bh). Intrarea BDHT este selectată cu PC-ul branch-ului curent (B0). Istoria condiţiilor, preluată din locaţia BDHT selectată, este folosită de predictoarele componente pentru generarea predicţiei. Predicţia finală este selectată prin vot majoritar sau pe baza unor numărătoare saturate asociate.

4.2. Utilizarea condiţiei de salt precedente ca informaţie de predicţie

Am evaluat influenţa condiţiei de salt precedente asupra procentajului de salturi nepolarizate. Am folosit diferenţa aferentă ultimei condiţii globale de salt împreună cu o istorie globală de p biţi (1≤p≤24). Diferenţa condiţiei de salt (Previous Branch Condition – PBC) constă în valoarea diferenţei dintre operanzii instrucţiunii de ramificaţie. Figura 4.2 compară procentajele de branch-uri nepolarizate pentru istoria globală (GH), istoria globală concatenată cu informaţia de cale (GH + PATH), respectiv istoria globală concatenată cu diferenţa ultimei condiţii de salt (GH + PBC).

15%

20%

25%

30%

35%

40%

45%

50%

p=1 p=4 p=8 p=12 p=16 p=20 p=24

Context Length

Unb

iase

d Co

ntex

t Ins

tanc

es

GH (p bits)

GH (p bits) + PATH (p PCs)

GH (p bits) + PBC

Figura 4.2. Reducerea procentajului de branch-uri nepolarizate din benchmark-urile SPEC2000, prin informaţia de cale (PATH) respectiv condiţia saltului precedent (PBC), pentru diferite lungimi ale

contextului.

Rezultatele prezentate în Figura 4.2 arată că ultima condiţie de salt (PBC) este mai eficientă decât informaţia de cale (PATH): a redus procentajul de branch-uri nepolarizate pentru toate lungimile de context evaluate (1≤p≤24). De aceea, folosind această nouă informaţie în predictoarele actuale [Gel07a, Gel07b], s-ar putea obţine o creştere semnificativă a acurateţii predicţiei.

O provocare importantă constă în integrarea acestei noi informaţii de predicţie într-un predictor dinamic. Am îmbunătăţit diferite mecanisme de predicţie convenţionale (GAg, PAg) şi neuronale cu această nouă informaţie de predicţie, cel mai eficient fiind perceptronul. Figura 4.3 prezintă schema perceptronului care foloseşte ca informaţie de predicţie suplimentară diferenţa aferentă ultimei condiţii de salt globale (PBC). Partea mai puţin semnificativă a adresei branch-ului (PC) selectează un perceptron din tabela de perceptroni respectiv un registru de istorie locală din tabela istoriilor locale. Astfel, diferenţa aferentă ultimei condiţii de salt este folosită alături de istoria locală respectiv globală ca intrare pentru perceptronul selectat, pentru generarea predicţiei.


12

PC

Selected Perceptron

Selected LHR

Local BranchHistory Table

Prediction

LH

Table of Perceptrons

GHR

GH

PBC

PBCPC

Selected Perceptron

Selected LHR

Local BranchHistory Table

Prediction

LH

Table of Perceptrons

GHRGHR

GH

PBCPBC

PBC

Figura 4.3. Predictor neuronal care foloseşte diferenţa aferentă ultimei condiţii globale de salt

4.3. Rezultate experimentale

Prin schema de predicţie a diferenţelor care combina predicţiile furnizate de cinci predictoare Markov folosind un mecanism de tip voter, s-a obţinut o acurateţe de 72,24% pe instrucţiunile de ramificaţie nepolarizate. În concluzie, acurateţea de predicţie a instrucţiunilor de ramificaţie nepolarizate rămâne în continuare scăzută. Figura 4.4. prezintă comparativ acurateţea predicţiei obţinută cu diferite predictoare de branch-uri actuale.

77.30%

60%

65%

70%

75%

80%

85%

bzip gzip mcf parser twolf Average

SPEC 2000 Benchmarks

Pred

ictio

n A

ccur

acy Local PPM

Global-Local PPMMultiple MarkovPerceptronPiecewiseFrankenpredictorO-GEHL

Figura 4.4. Acurateţea predicţiei branch-urilor nepolarizate cu scheme neuronale, Markoviene şi predictorul O-GEHL

Cu cel mai performant predictor, perceptronul [Jim05], s-a obţinut o acurateţe de 77,30% pe branch-urile nepolarizate. Cu acelaşi predictor s-a obţinut o acurateţe globală de 94,92%.

Figura 4.5 prezintă acurateţile de predicţie obţinute, pe branch-urile nepolarizate, cu piecewise linear branch predictor folosind ca informaţie de predicţie suplimentară diferenţa aferentă ultimei condiţii globale de salt. Numărul ponderilor s-a variat între 8590 şi 30713.


13

94.92%95.45%

77.30% 78.30%

75%

80%

85%

90%

95%

PW_859

0w

PW_PBC_8

590w

PW_PBC_1

2530

w

PW_PBC_1

5720

w

PW_PBC_2

0573

w

PW_PBC_3

0713

w

Different size perceptron-based predictors

Pred

ictio

n A

ccur

acy

all_branchesunbiased

Figura 4.5. Acurateţile de predicţie pe salturile nepolarizate cu piecewise linear branch predictor folosind PBC global

Am obţinut o creştere nesemnificativă folosind diferenţa completă (32 de biţi) a ultimei condiţii de salt, chiar şi în condiţiile unui număr mare de ponderi. Oricum, acurateţea de predicţie obţinută cu piecewise linear branch predictor modificat, este de 78,30% în comparaţie cu cea obţinută cu predictorul GAg modificat, de 69,87%, respectiv cu PAg modificat, de 73,75%. Această diferenţă semnificativă se datorează probabil utilizării PBC fără hashing de piecewise linear branch predictor, spre deosebire de predictoarele GAg şi PAg. Analizând comparativ rezultatele prezentate în Figurile 4.4 şi 4.5, se poate observa îmbunătăţirea acurateţii predicţiei branch-urilor nepolarizate folosind PBC cu 1% faţă de cel mai performant predictor. Această îmbunătăţire contribuie la creşterea acurateţii predicţiei globale cu 0,53%.

14

5. Gradul de aleatorism al branch-urilor nepolarizate

În Capitolul 4 am arătat că branch-urile nepolarizate sunt nepredictibile cu cele mai performante predictoare. Pornind de la această provocare tehnică, în acest capitol am realizat un studiu comparativ privind gradul de aleatorism al secvenţelor de simboluri (taken şi not taken) generate de branch-uri polarizate respectiv nepolarizate.

5.1. Metrici de caracterizare a aleatorismului branch-urilor nepolarizate

Pe baza cercetării bibliografice efectuate, în [Vin08b] am dezvoltat patru metrici pentru carecterizarea comportamentului unui branch din punct de vedere al gradului de aleatorism: complexitatea Kolmogorov a secvenţei de program care generează branch-ul, rata de compresie, entropia discretă respectiv acurateţea de predicţie cu modele adaptive Markov cu legături ascunse (Hidden Markov Models – HMM) a secvenţei generate de branch [Rab89, Gel06c].

5.1.1. Modele Markov cu legături ascunse

O informaţie relevantă asupra generatorului de secvenţe haotice (în general, greu sau chiar imposibil de găsit), ar putea reduce entropia secvenţelor generate de branch-urile nepolarizate astfel încât să devină (mai) predictibile. De aceea, merită să încercăm să le predicţionăm cu algoritmi mai puternici, de genul modelelor adaptive Markov cu legături ascunse. Această ipoteză se bazează pe faptul că aceste modele stohastice cu legături ascunse, care consideră că stările modelului Markov observabil sunt generate de un alt model Markov ascuns, ar putea compensa necunoaşterea acelor informaţii relevante pentru predicţie prin chiar procesul stohastic ascuns, pe post de generator al stărilor observabile (cu o semantică neinteligibilă pentru observator). Figura 5.1 prezintă un HMM generic, unde qt este starea ascunsă în momentul t, Ot este starea observabilă în momentul t, A este matricea probabilităţilor de tranziţie între stările ascunse şi B este matricea probabilităţilor simbolurilor observabile pentru fiecare stare ascunsă.

q1 q2 q3 qTA A A A

B B B B

O1 O2 OTO3

Hidden State Sequence (Q):

Observation Sequence (O):

q1 q2 q3 qTAA AA AA AA

BB BB BB BB

O1 O2 OTO3

Hidden State Sequence (Q):

Observation Sequence (O): Figura 5.1. Model Markov cu legături ascunse

Prin utilizarea acestor modele HMM aleatorul n-ar mai constitui o fatalitate ireductibilă, din cauza modelului stohastic ascuns care îl generează pe cel observabil. Astfel, acurateţea predicţiei unui şir de simboluri printr-un astfel de model puternic, ar putea constitui un grad de aleatorism al secvenţei, din punct de vedere practic. În acest capitol vom folosi algoritmul HMM de ordin R,

1≥R , propus în lucrarea [Gel06c].

Gradul de aleatorism al branch-urilor nepolarizate

15

5.1.2. Entropia discretă

O măsură a aleatorismului unei secvenţe S de simboluri aparţinând mulţimii }...{ 21 kXXXX = s-ar putea baza chiar pe entropia informaţională discretă a secvenţei S:

0)(log)()(1

2 ≥−= ∑=

k

iXiPXiPSE (5.1)

cu un maxim ( k2log ) în cazul simbolurilor echiprobabile în S. Totuşi, măsura entropiei nu este suficientă întrucât se pot găsi secvenţe cu entropie ridicată dar care să fie generate în mod determinist. Se observă imediat că D(S) ]1,0[∈ , definit în formula (3.2), este maxim în cazul unor amestecări maximale ale simbolurilor ‘0’ şi ‘1’ în secvenţă. Astfel o măsură inginerească acceptabilă de definire a gradului de aleatorism aferent unei secvenţe binare S ar putea fi

]log,0[)()()( 2 kSESDSRD ∈⋅= (5.2)

O valoare RD mare indică un grad ridicat de aleatorism.

5.1.3. Rata de compresie

Rata de compresie a unei secvenţe de simboluri, obţinută prin algoritmi cunoscuţi de compresii fără pierderi (ex. Huffman, Gzip), ar putea constitui o altă măsură a aleatorismului secvenţei. Pentru evaluarea ratei de compresie a secvenţelor generate de branch-uri polarizate şi nepolarizate am folosit următoarele două metrici:

%100⋅=SizeCompressedSizeedUncompressRatenCompressio (5.3)

%1001 ⋅

−=

SizeedUncompressSizeCompressedSavingsSpace (5.4)

În cazul secvenţelor binare generate de instrucţiunile de ramificaţie dificile, rata de compresie a acestora ar trebui să fie mai mică decât în cazul celorlalte branch-uri.

5.1.4. Complexitatea Kolmogorov

Kolmogorov şi Chaitin au definit aleatorismul unei secvenţe finite de simboluri, cu referire la lungimea celui mai scurt program de calculator care descrie secvenţa respectivă. Dacă lungimea acestui program este (sensibil) egală cu lungimea secvenţei însăşi, atunci secvenţa este considerată aleatoare (deci nu există un program generator, mai scurt). O secvenţă X are complexitatea Kolmogorov K(X) egală cu lungimea celui mai scurt program p implementat pe o maşină Turing U care generează secvenţa:

)(min)()(:

plXKXpUp =

= (5.5)

unde l(p) este lungimea programului p în biţi. Complexitatea Kolmogorov identifică o secvenţă X ca fiind aleatoare dacă )()( XKXl − este mic.

Complexitatea Kolmogorov a secvenţei de program maşină care generează salturile condiţionate impredictibile ar putea constitui o altă metrică care să le caracterizeze aleatorismul. Astfel, complexitatea acestora ar trebui să fie mai mare decât a celorlalte salturi condiţionate. Cum în viitor complexitatea programelor va creşte, este de aşteptat ca numărul şi influenţa salturilor nepolarizate să crească.


16


Am selectat din fiecare benchmark contexte puternic nepolarizate (P(S)∈[0,501; 0,565]) respectiv polarizate (P(S)∈[0,979; 0,997]) cu instanţe dinamice de ordinul sutelor de mii. Indexul de polarizare s-a definit în formula (3.1). Secvenţele binare ale comportamentelor (taken, not taken) acestor contexte vor fi analizate din punct de vedere al gradului de aleatorism pe baza metricilor propuse.

Predicţia cu algoritmul HMM s-a efectuat folosind o istorie de 64 de biţi. Am evaluat acurateţea predicţiei algoritmilor HMM de ordin 1 (R=1) şi 2 (R=2) variind numărul stărilor ascunse (N). Acurateţea predicţiei obţinută cu HMM optim (R=1, N=2) pe contexte polarizate este semnificativ mai mare fata de cea obtinuta pe contextele nepolarizate (Figura 5.2).

98.43%

65.03%

40%50%60%70%80%90%

100%

bzip gc

cgz

ip mcf

parse

rtw

olf

Averag

e


Pred

ictio

n A

ccur

acy

Biased (R=1, N=2)Unbiased (R=1, N=2)

Figura 5.2. Acurateţea predicţiei obţinută cu HMM optim (R=1, N=2) pe contexte polarizate (biased)

respectiv nepolarizate (unbiased)

Se poate observa diferenţa considerabilă din punct de vedere al predictibilităţii secvenţelor generate de contextele polarizate respectiv nepolarizate (98,43% vs. 65,03%). După cum ne aşteptam, acurateţea medie de 98,43% arată forţa de excepţie a acestui predictor HMM, care ar putea fi un excelent candidat ca şi „limită ultimativă” a predictibilităţii branch-urilor. După cunoştinţa noastră suntem primii care am proiectat şi utilizat predictoare HMM în domeniul predicţiei dinamice a branch-urilor. Pe de altă parte, neputinţa acestor predictoare puternice în faţa branch-urilor nepolarizate sugerează gradul ridicat de aleatorism intrinsec al acestora, ele fiind generate prin construcţii software extrem de complexe după cum arătăm în continuare.

În continuare, am considerat gradul de aleatorism RD(S), al unei secvenţe binare S, produsul dintre entropia discretă E(S) şi rata de distribuţie D(S) a respectivei secvenţe:

)()()( SESDSRD ⋅= . Figura 5.3 ilustrează rezultate statistice privind gradul de aleatorism al secvenţelor binare obţinute prin metodologia expusă, generate de branch-urile polarizate şi nepolarizate.

9.16%

40.00%

0%10%20%30%40%50%60%70%

gzip gcc mcf parser bzip2 twolf Average


Ran

dom

Deg

ree

RD BiasedRD Unbiased

Figura 5.3. Gradul de aleatorism al secvenţelor polarizate (biased) vs. nepolarizate (unbiased)


17

Întrucât supoziţia noastră iniţială era că secvenţele puternic predictibile (biased) sunt caracterizate de un grad de aleatorism scăzut, rezultatele obţinute confirmă faptul că metrica RD(S) considerată reprezintă o bună măsură pentru gradul de aleatorism al unei secvenţe binare. Un grad de aleatorism de 40% arată că branch-ul respectiv este greu sau chiar imposibil de predicţionat cu acurateţe.

În continuare, secvenţele binare generate de branch-urile polarizate şi respectiv nepolarizate au fost transformate în fişiere ASCII (s-au grupat succesiuni de 8 biţi şi s-a generat octetul cu codul ASCII corespunzător). Aceste fişiere au fost compresate folosind utilitarul Gzip [Gzip] şi respectiv o aplicaţie proprie care implementează codificarea Huffman [Cor01].

90.37%

83.78%

19.15%

5.52%

-10%

10%

30%

50%

70%

90%

gzip gcc mcf

parser

bzip2

twolf

Average


Spac

e Sa

ving

s Gzip-Biased

Huffman-Biased

Gzip-Unbiased

Huffman-Unbiased

Figura 5.4. Compresia secvenţelor polarizate (biased) respectiv nepolarizate (unbiased) folosind utilitarul

Gzip şi algoritmul Huffman

Din analiza Figurii 5.4 se pot extrage câteva concluzii. În primul rând, în cazul secvenţelor binare generate de branch-urile nepolarizate, rata de compresie (19,15% cu utilitarul Gzip) este semnificativ mai mică decât în cazul branch-urilor polarizate (90,37% cu utilitarul Gzip). A doua concluzie se referă practic la superioritatea algoritmului de compresie Gzip faţă de Huffman, firească ţinând cont de faptul că Gzip include codificarea Huffman ca fază finală a compresiei. Analizând ratele de compresie pe benchmark-urile mcf şi twolf obţinute cu ambele metode de compresie putem afirma că influenţa algoritmului LZ77 pe cele două programe de test este aproape nulă, ceea ce conduce la concluzia că nu au putut fi identificate prea multe pattern-uri repetitive. Acest lucru practic l-am sesizat şi în [Gel07b] prin acurateţea foarte slabă a predicţiei branch-urilor nepolarizate cu predictoare Markoviene pe cele două benchmark-uri.

Pornind de la câteva programe de test din suita de benchmark-uri de numere întregi Stanford, puternic recursive, se va arăta că anumite secvenţe de cod cu caracter determinist generează secvenţe practic impredictibile. Pentru început ne vom concentra asupra saltului cu adresa PC=58 din benchmark-ul perm din suita Stanford, care s-a dovedit a avea un comportament impredictibil chiar şi atunci când contextul său de apariţie a fost de o lungime considerabilă (54 de biţi de istorie globală). Procentul de 1,53% salturi nepolarizate din benchmark-ul perm se datorează exclusiv acestui branch cu PC=58.

Un predictor de tip perceptron fast path-based (FPBP) cu o istorie globală de 54 de biţi [Rad07] predicţionează acest salt cu o acurateţe de doar 65,91%. Totuşi, caracterul recursiv al benchmark-ului este exploatat de către un predictor PPM cu o acurateţe de predicţie a branch-ului 58 de 94,30% (folosind un context global de 500 de biţi şi un pattern de căutare de 30). Cum această soluţie este complet nefezabilă s-a încercat folosirea unui PPM simplificat, dar rezultatele au fost nesatisfacatoare, acurateţea predicţiei fiind de doar 79,85%. Acurateţea globală de predicţie obţinută folosind predictorul PPM complet este de 98,41%, inferioară celei


18

obţinute cu predictorul FPBP care este de 99,04%. Practic din cele 869 de predicţii eronate ale predictorului PPM, 287 sunt generate de saltul 58. Deci, predictoarele FPBP şi PPM nu reuşesc să predicţioneze corect un salt nepolarizat. Procentajul ridicat de 94,30% pe branch-ul 58 oferit de PPM este practic centrat pe întreg comportamentul său şi nu pe contextul lui nepolarizat.

Analizând din prisma complexităţii Kolmogorov comportamentul saltului 58 (notată cu K(58)) se observă că lungimea minimă a secvenţei de program maşină care generează acest salt condiţionat impredictibil este egală cu lungimea subrutinei Permute (masurată în instrucţiuni), întrucât la saltul 58 se ajunge după cel puţin o execuţie completă a funcţiei Permute (apelată recursiv). Astfel, K(58)=42 instrucţiuni HSA sau 8 instrucţiuni C. Dintre celelalte branch-uri, practic unul singur (PC=35) s-a mai dovedit nepolarizat pentru istorii globale scurte (≤32 de biţi) dar care, la un context de 54 de biţi devine complet polarizat (practic predictibil). Analizând acest salt din prisma complexităţii Kolmogorov se observă că K(35)=12 instrucţiuni HSA sau 3 instrucţiuni C. Astfel, intrucât testul saltului 35 nu presupune execuţia integrală a funcţiei Permute, K(35)<K(58), ceea ce arată că recursivitatea în combinaţie cu anumite instrucţiuni condiţionale generează branch-uri cu comportament nepolarizat şi complexitate Kolmogorov ridicată.

19

6. Metode de reutilizare şi predicţie selective a valorilor instrucţiunilor în arhitecturi superscalare

În capitolele anterioare am arătat că instrucţiunile de ramificaţie nepolarizate nu pot fi predicţionate cu acurateţe de predictoarele actuale, indiferent de informaţia de predicţie folosită. De asemenea, am arătat că secvenţele generate de branch-urile nepolarizate sunt caracterizate de grad ridicat de aleatorism. Aceste branch-uri dificile reprezintă o sursă importantă de penalităţi datorate predicţiilor greşite, afectând serios performanţa globală a procesorului. În [Gel06b] am arătat că 28,68% din instrucţiunile de ramificaţie (5,61% fiind chiar nepolarizate) sunt dependente de instrucţiuni cu latenţă ridicată (Load, Mul şi Div). Aceste dependenţe implică penalităţi ridicate în cazul unei predicţii greşite a branch-urilor nepolarizate, fiind necesară aşteptarea finalizării instrucţiunii cu referire la memorie şi astfel, o degradare semnificativă a performanţei. Impactul negativ al branch-urilor nepolarizate asupra performanţei globale de procesare ar putea fi atenuat prin anticiparea rezultatelor instrucţiunilor mari consumatoare de timp. Pe de altă parte, ascunderea latenţelor acestor instrucţiuni în procesoarele pipeline superscalare reprezintă o provocare importantă, intrinsecă. De aceea, în acest capitol sunt prezentate pe baza lucrărilor [Gel08b, Vin05a] metode anticipatorii originale dezvoltate pentru arhitecturi superscalare.

6.1. Anticiparea rezultatelor instrucţiunilor cu latenţă ridicată

Obiectivul constă în dezvoltarea unui mecanism de anticipare selectivă a valorilor instrucţiunilor cu latenţă de execuţie ridicată. Gradul de reutilizabilitate a instrucţiunilor MUL şi DIV a fost de 28,9% pe benchmark-urile de numere întregi respectiv 61,9% pe cele de numere flotante [Gel08a]. Pentru aceste instrucţiuni se va folosi o schemă de reutilizare dinamică a instrucţiunilor. Gradul de reutilizabilitate a valorilor instrucţiunilor Load a fost de 77,4% pe benchmark-urile de numere întregi respectiv 76,4% pe cele de numere flotante [Gel08a]. Un buffer de reutilizare pentru valorile instrucţiunilor Load nu e necesar, pentru că un mecanism de reutilizare similar este deja asigurat de cache-urile de date L1 şi L2. De aceea, pentru instrucţiunile Load cu miss în cache-ul de date L1 (abordare selectivă) se va folosi o schemă de predicţie a valorilor.

6.1.1. Reutilizarea selectivă a instrucţiunilor

Pentru instrucţiunile MUL şi DIV vom folosi schema de reutilizare Sv. Informaţiile necesare sunt păstrate pentru fiecare instrucţiune în tabela de reutilizare (Reuse Buffer – RB). Tabela de reutilizare este accesată în faza issue, pentru că majoritatea instrucţiunilor MUL/DIV găsite în RB în faza dispatch nu au operanzii disponibili (91,5% pe benchmark-urile de numere întregi şi 64,6% pe cele de numere flotante). Fiecare intrare RB are următoarele câmpuri: Tag (partea mai semnificativă din PC), SV1 şi SV2 (valorile operanzilor sursă ale instrucţiunii MUL/DIV), Result (rezultatul instrucţiunii MUL/DIV). Deoarece nu reutilizăm instrucţiuni Load cu această schemă, câmpurile Address şi Mem Valid folosite în [Sod97] nu sunt necesare. Astfel, structura noastră este mai simplă şi mai eficientă decât schema iniţială propusă de Sodani şi Sohi.

Metode de reutilizare şi predicţie selective a valorilor instrucţiunilor în arhitecturi superscalare

20

Sv Reuse Buffer (RB)

PC of MUL / DIV

Tag SV1 SV2 Result

Sv Reuse Buffer (RB)

PC of MUL / DIV

Tag SV1 SV2 Result

Figura 6.1. Schema de reutilizare folosită pentru instrucţiunile MUL şi DIV

Dacă o anumită instrucţiune este găsită în RB, se efectuează testul de reutilizare. Dacă valorile operanzilor, preluate din ROB, se regăsesc în câmpurile SV1 şi SV2 din intrarea RB selectată, unitatea de execuţie este evitată, rezultatul fiind deja disponibil pentru instrucţiunile dependente. Fiecare instrucţiune Mul/Div nereutilizată actualizează RB în faza commit. Câştigul reutilizării instrucţiunilor cu latenţă ridicată constă în deblocarea instrucţiunilor dependente (Figura 6.2).

Fetch Decode Issue Execute Commit

RBLookup (PC, V1, V2) Result (if hit)


RBLookup (PC, V1, V2) Result (if hit)

Figura 6.2. Pipeline cu RB

De asemenea, am detectat operaţiile triviale V*0, V*1, 0/V, V/1 şi V/V implementând o tehnică introdusă în [Ric93] de Richardson. O schemă simplă de detecţie a operaţiilor triviale şi selectare a rezultatului este prezentată în [Gol07]. Detecţia operaţiilor triviale are loc în faza dispatch. Structura RB este accesată în faza issue doar dacă operaţia Mul/Div n-a fost detectată în faza dispatch ca fiind trivială.

6.1.2. Predicţia selectivă a valorilor instrucţiunilor Load

Vom integra în arhitectura noastră şi un predictor simplu de tip Last Value pentru instrucţiunile Load cu miss în cache-ul de date L1 (abordare selectivă). Astfel, structura implementată este folosită mai eficient, numărul coliziunilor fiind redus faţă de abordarea care predicţionează toate instrucţiunile Load. Informaţiile despre instrucţiunile Load sunt păstrate într-o tabelă cu mapare directă numită LVPT (Load Value Prediction Table). Structura LVPT se accesează în faza issue doar în caz de Load cu miss în cache-ul de date L1 (Load critic). Fiecare intrare LVPT are următoarele câmpuri: Tag (partea mai semnificativă din PC), Counter (numărător saturat pe 2 biţi cu două stări nepredictibile şi două stări predictibile) şi Value (rezultatul instrucţiunii Load).

Load Value PredictionTable (LVPT)

PC of Load with missin L1 Data Cache

Tag Counter Value

Load Value PredictionTable (LVPT)

PC of Load with missin L1 Data Cache

Tag Counter Value

Figura 6.3. Arhitectura predictorului Last Value


21

În caz de hit în LVPT, dacă numărătorul corespunzător este într-o stare predictibilă, valoarea din intrarea LVPT selectată se înaintează speculativ instrucţiunilor dependente. În faza commit când valoarea reală este disponibilă, în cazul în care predicţia a fost greşită, instrucţiunile dependente executate speculativ sunt retrimise spre execuţie cu valorile corecte (recovery). În faza commit instrucţiunile Load critice actualizează structura LVPT. În simulările noastre am considerat o latenţă de predicţie de un ciclu, respectiv de 7 cicli în caz de predicţie greşită.


LVPTIf Load with missin L1 Data Cache

Predicted Value

Misprediction Recovery



Predicted Value



Predicted Value


Figura 6.4. Pipeline cu mechanism de predicţie a valorilor instrucţiunilor Load

6.1.3. Rezultate experimentale

Am integrat în simulatorul M-SIM [Sha05], care permite evaluarea performanţei de procesare şi a consumului de putere, arhitectura noastră superscalară cu tehnicile selective de reutilizare a instrucţiunilor şi predicţie a valorilor. Evaluările s-au efectuat pe şapte benchmark-uri de numere întregi (bzip, gcc, gzip, mcf, parser, twolf, vpr) şi şase de numere flotante (applu, equake, galgel, lucas, mesa, mgrid). Deşi structurile RB şi LVPT consumă putere dinamică adiţională, anticipând rezultatele instrucţiunilor cu latenţă ridicată creşte IPC-ul şi astfel scade consumul relativ de energie (EDP). În Figurile 6.5 şi 6.6 IPC Speedup reprezintă creşterea relativă de performanţă şi EDP Gain reprezintă câştigul relativ de energie faţă de arhitectura clasică (fără RB şi LVPT). Figura 6.5 arată îmbunătăţirile obţinute cu RB de diferite dimensiuni. Se poate observa că dimensiunea optimă a structurii RB este de 1024 de locaţii.

0.0%0.5%1.0%1.5%2.0%2.5%3.0%3.5%4.0%4.5%

16 32 64 128 256 512 1024 2048

RB entries

EDP GainIPC Speedup

Figura 6.5. Creşterea relativă de performanţă şi câştigul relativ de energie pe benchmark-urile flotante

SPEC 2000 cu RB şi detecţia operaţiilor triviale

Figura 6.6 prezintă îmbunătăţirile obţinute cu RB de dimensiune optimă (1024 de locaţii) şi LVPT de diferite dimensiuni. Creşterea relativă de performanţă şi câştigul de energie sunt mai importante pe benchmark-urile de numere flotante. Această diferenţă se datorează în primul rând numărului de două ori mai mare de instrucţiuni Load critice în benchmark-urile de numere


22

flotante. Diferenţa este accentuată de procentajul mai mare de Load-uri predicţionate (85% în benchmark-urile de numere flotante şi doar 40% în cele de numere întregi [Gel08a]) şi de acurateţea predicţiei mai ridicată în cazul benchmark-urilor de numere flotante.

0%5%

10%15%20%25%30%35%40%

16 32 64 128

256

512

1024

2048

LVPT entries

FP - EDP GainFP - IPC SpeedupINT - EDP GainINT - IPC Speedup

Figura 6.6. Creşterea relativă de performanţă şi câştigul relativ de energie cu RB de 1024 de intrări,

detecţia operaţiilor triviale şi LVPT

Metoda de reutilizare a instrucţiunilor propusă de Golander şi Weiss în [Gol07] îmbunătăţeşte performanţele de procesare (IPC Speedup) cu 2,5% respectiv 5,9% pe benchmark-urile de numere întregi respectiv flotante şi un câştig relativ de energie (EDP Gain) de 4,80% respectiv 11,85%. În comparaţie, tehnicile noastre îmbunătăţesc performanţele de procesare cu 3,5% respectiv 23,6% pe benchmark-urile de numere întregi respectiv flotante şi un câştig relativ de energie de 6,2% respectiv 34,5%.

6.2. Predicţia dinamică a valorilor orientată pe registrele procesorului

Obiectivul principal al acestui paragraf constă în focalizarea predicţiei dinamice a valorilor pe contextul procesorului [Vin05a, Vin05b], prin introducerea conceptului de predicţie orientată pe registre. Centrarea predictoarelor de valori [Lip96a, Saz99] pe registre va reduce complexitatea şi costurile hardware. Există însă şi unele dezavantaje: adresarea tabelei de predicţie cu numele registrului destinaţie în locul adresei instrucţiunii (PC) poate determina o serie de interferenţe.

6.2.1. Predictoare de valori centrate pe registre

Rezultate statistice bazate pe simulare au arătat că programele de uz general sunt caracterizate de repetiţia valorilor [Lip96a, Sod00]. Principalele cauze ale acestui fenomen le constituie: redundanţa datelor şi codului, constantele din program, subrutinele compilatorului destinate rezolvării apelurilor virtuale de funcţii, alias-urilor de memorie. Localitatea valorilor registrelor este frecvent întâlnită în programe şi exprimă raportul dintre numărul situaţiilor în care un registru este scris cu o valoare care a fost stocată anterior (într-o istorie dată) în acelaşi registru şi numărul total de instrucţiuni care au acest registru ca destinaţie [Flo02, Gel03].

În lucrarea [Vin05a] am arătat că localitatea valorii pe anume registre ale arhitecturii MIPS este remarcabilă (cca. 90%), conducând în mod evident la ideea predicţiei valorilor cel puţin pentru aceste registre. Figura 6.7 prezintă structura pipeline cu mecanism de predicţie a valorilor


23

registrelor. Tabela de predicţie VPT (Value Prediction Table) se accesează cu numele registrului destinaţie în a doua jumătate a fazei de decodificare (decode). Valoarea registrului destinaţie se predicţionează pe baza valorilor sale anterioare (cele mai recente într-o istorie dată). Instrucţiunile dependente succesoare folosesc valoarea prezisă iar execuţia speculativă este validată când valoarea reală a registrului devine cunoscută, după faza de execuţie. Dacă valoarea prezisă este corectă atunci calea critică ar putea fi redusă, cu implicaţii benefice asupra timpului total de execuţie, respectiv a performanţei globale de procesare (IPC). În caz contrar, instrucţiunile executate cu intrări eronate trebuie reluate din nou (proces de recovery).


RVPRdest Predicted Value



RVPRdest Predicted Value


Figura 6.7. Implementarea mecanismului de predicţie a valorilor registrelor în structura pipeline aferentă

unei microarhitecturi generice

În [Vin05a, Gel03] am dezvoltat şi simulat diferite predictoare de valori centrate pe registrele procesorului: de tip last value, incrementale, contextuale şi hibride, cele mai eficiente fiind cele hibride. Studiile cercetătorilor din domeniul predicţiei valorilor [Wan97] au arătat că un singur tip de predictor nu dă în general rezultatele cele mai bune. Acest lucru se datorează în primul rând faptului că anumite tipuri de secvenţe de valori sunt prezise mai bine de un anumit predictor, iar altele, de către un alt tip de predictor particular. Din acest motiv a apărut ca naturală ideea predicţiei hibride, adică două sau mai multe predictoare de valori să conlucreze în mod dinamic în procesul de predicţie. Figura 6.8 prezintă predictorul hibrid format dintr-un predictor contextual PPM şi unul incremental. Predictorul contextual are întotdeauna prioritate, ca în [Wan97]. Astfel, valoarea generată de predictorul incremental este folosită doar dacă predictorul contextual nu poate predicţiona.

State Str1 LRU V3

Predicted value

Value History Table (VHT)

indexRdest

V2V1 V4

PPM

MUX 4:1

+

MUX 2:1

Str2

Figura 6.8. Predictor hibrid (PPM & incremental)


24

Figura 6.9 prezintă predictorul hibrid format dintr-un predictor pe două niveluri şi unul incremental (schema centrată pe instrucţiuni a fost propusă în [Wan97]), adaptat pentru predicţie centrată pe registre (indexare cu numele registrului destinaţie în locul adresei instrucţiunii). Prioritizarea statică (neadaptivă) folosită în Figurile 6.8 şi 6.9 pare a fi neoptimală. O soluţie pentru rezolvarea acestei probleme ar putea consta în selectarea dinamică, bazat pe grade de încredere, a structurii care să fie utilizată pentru predicţie.

LRU Data Values

Value History Table(VHT)

VHP

MUX 4:1

PredictedValue

C0 C1 C2 C3

Pattern History Table(PHT)

MAX

2

2p

State Stride

MUX 4:1 +

MUX 2:1

indexRdest

LRU Data Values


VHP

MUX 4:1

MUX 4:1

PredictedValue

PredictedValue

C0 C1 C2 C3


MAX

22

2p

State Stride

MUX 4:1

MUX 4:1 +

MUX 2:1

MUX 2:1

indexRdestindexRdest

Figura 6.9. Predictor hibrid (contextual pe 2 niveluri & incremental) cu prioritizare statică

LRU Data Values


VHP

MUX 4:1

PredictedValue

C0 C1 C2 C3


MAX

2

2p

Stride

MUX 4:1 +

MUX 2:1

indexRdest

C2Lev CStr LRU Data Values


VHP

MUX 4:1

MUX 4:1

PredictedValue

PredictedValue

C0 C1 C2 C3


MAX

22

2p

Stride

MUX 4:1

MUX 4:1 +

MUX 2:1

MUX 2:1

indexRdestindexRdest

C2Lev CStr

Figura 6.10. Predictor hibrid (contextual pe 2 niveluri & incremental) cu prioritizare adaptivă


25

Schema hibridă adaptivă prezentată în Figura 6.10 foloseşte câte un numărător saturat pentru fiecare predictor (C2Lev pentru predictorul contextual pe 2 niveluri şi CStr pentru predictorul incremental) şi selectează dinamic predictorul cu gradul de încredere cel mai ridicat.

6.2.2. Rezultate experimentale

Am extins simulatorul sim-outorder din setul de instrumente SimpleScalar [Sim], integrând predictoarele de valori propuse. Figurile 6.11 şi 6.12 compară din punct de vedere al acurateţii predicţiei cele trei scheme hibride: PPM-incremental cu prioritizare statică (PPM-Stride), contextual-incremental cu prioritizare statică (2Lev-Stride) şi contextual-incremental cu prioritizare adaptivă (2Lev+Stride). Hibridul bazat pe algoritmul PPM foloseşte o istorie de 256 de valori şi un pattern de 4, în timp ce schemele bazate pe predicţie contextuală pe 2 niveluri folosesc o istorie de 32 de valori şi un pattern de 4.

0

10

20

30

40

50

60

70

80

90

100

R01

R02

R03

R04

R05

R06

R07

R08

R09

R10

R11

R12

R13

R14

R15

R16

R17

R18

R19

R20

R21

R22

R23

R24

R25

R29

R30

R31

Ave

rage

MIPS Registers

Pred

ictio

n A

ccur

acy

[%]

2Lev-Stride

2Lev+Stride

PPM-Stride

Figura 6.11. Acurateţea predictoarelor hibride pe SPEC’95

0

10

20

30

40

50

60

70

80

90

100

R01

R02

R03

R04

R05

R06

R07

R08

R09

R10

R11

R12

R13

R14

R15

R16

R17

R18

R19

R20

R21

R22

R23

R24

R25

R29

R30

R31

Ave

rage

MIPS Registers

Pred

ictio

n A

ccur

acy

[%]

2Lev-Stride

2Lev+Stride

PPM-Stride

Figura 6.12. Acurateţea predictoarelor hibride pe SPEC 2000

Figurile 6.11 şi 6.12 arată că schema hibridă cu prioritizare dinamică compusă dintr-un predictor contextual pe 2 niveluri şi unul incremental (2Lev+Stride) este comparabilă din punct de vedere al acurateţii predicţiei cu schema hibridă mult mai complexă PPM-incremental (PPM-Stride).

26

7. Arhitectură SMT îmbunătăţită cu metode de reutilizare şi predicţie a valorilor instrucţiunilor

În Capitolul 6 am îmbunătăţit o microarhitectură superscalară cu tehnici selective de reutilizare a instrucţiunilor şi predicţie a valorilor focalizate pe instrucţiuni cu latenţă ridicată. Creşterea semnificativă a performanţei de procesare şi scăderea consumului relativ de energie demonstrează necesitatea acestor metode pentru creşterea paralelismului la nivelul instrucţiunilor. Poate fi îmbunătăţită chiar şi o arhitectură de tip multithreading simultan (SMT) cu aceste tehnici anticipatorii? Acest capitol răspunde la această întrebare prin evaluarea unei arhitecturi SMT îmbunătăţită cu mecanismul de anticipare selectivă a rezultatelor instrucţiunilor cu latenţă ridicată.

7.1. Metode de reutilizare a instrucţiunilor şi predicţie a valorilor în arhitecturi SMT

Obiectivul final al acestei cercetări îl reprezintă cuantificarea impactului mecanismului de anticipare selectivă a valorilor instrucţiunilor cu latenţă ridicată într-o arhitectură SMT, care implică multiplicări ale tabelelor de reutilizare (RB) şi a predictoarelor de valori (LVPT) pentru fiecare fir în parte [Vin08a]. Am integrat în simulatorul M-SIM [Sha05], care suportă execuţie superscalară şi SMT, structurile RB şi LVPT propuse în paragraful 6.1. Figura 7.1 prezintă arhitectura SMT îmbunătăţită cu metodele selective de reutilizare a instrucţiunilor şi predicţie a valorilor.

FetchUnit

Branch Predictor PC I-Cache Decode Issue

QueueRename

Table

PhysicalRegister

File

ROB

LVPT

FunctionalUnits

LSQ

D-Cache

RB

FetchUnit

FetchUnit

Branch PredictorBranch

PredictorBranch

Predictor PCPC I-CacheI-Cache Decode IssueQueueIssue

QueueRename

TableRename

TableRename

Table

PhysicalRegister

File

PhysicalRegister

File

ROB

LVPT

FunctionalUnits

LSQ

FunctionalUnits

FunctionalUnits

LSQLSQ

D-CacheD-Cache

RBRB

Figura 7.1. Arhitectură SMT îmbunătăţită cu metode selective de reutilizare a instrucţiunilor şi predicţie

a valorilor

În mod de execuţie SMT, anumite structuri ale procesorului sunt partajate (setul de registre, unităţile de execuţie, cache-urile etc) în timp ce altele sunt private pentru fiecare fir (ROB, predictoare de branch-uri, RB, LVPT etc).


Evaluările arhitecturii superscalare s-au efectuat pe şapte benchmark-uri de numere întregi (bzip, gcc, gzip, mcf, parser, twolf, vpr) şi şase de numere flotante (applu, equake, galgel, lucas, mesa, mgrid). În mod SMT simulatorul M-SIM rulează în paralel benchmark-uri multiple

Arhitectură SMT îmbunătăţită cu metode de reutilizare şi predicţie a valorilor instrucţiunilor

27

considerându-le thread-uri diferite. De aceea, pentru evaluarea SMT, am combinat benchmark-urile în grupuri de 2, 3 sau 6 în funcţie de arhitectura SMT simulată. Astfel, am folosit {bzip, gcc}, {gzip, parser}, {twolf, vpr}, {applu, equake}, {galgel, lucas}, {mesa, mgrid} pentru SMT cu două fire, {bzip, gcc, gzip}, {parser, twolf, vpr}, {applu, equake, galgel}, {lucas, mesa, mgrid} pentru SMT cu trei fire şi {bzip, gcc, gzip, parser, twolf, vpr}, {applu, equake, galgel, lucas, mesa, mgrid} pentru arhitectura SMT cu şase fire.

Am evaluat performanţa de procesare (IPC) şi consumul de putere pentru arhitectura SMT cu respectiv fără RB şi LVPT, variind numărul de fire procesate. Am folosit dimensiunea optimă de 1024 de intrări pentru structurile RB şi LVPT, conform rezultatelor obţinute cu arhitectura superscalară îmbunătăţită (prezentate în paragraful 6.1.3). Rezultatele simulărilor au arătat că structurile RB şi LVPT îmbunătăţesc performanţele de procesare pentru toate configuraţiile arhitecturale (superscalar şi SMT) evaluate. Cu cât numărul de fire este mai mare cu atât unităţile de execuţie partajate sunt exploatate mai eficient datorită nivelului de paralelism la nivelul thread-urilor mai ridicat, mecanismele de reutilizare a instrucţiunilor şi predicţie a valorilor devenind mai puţin importante. Astfel, pe benchmark-urile de numere flotante, cu şase thread-uri am obţinut performanţele de procesare (IPC) cele mai bune, dar îmbunătăţirile (IPC speedup) cele mai mici. Figurile 7.2 şi 7.3 prezintă creşterea relativă a performanţei de procesare respectiv câştigul relativ de energie obţinute cu arhitectura superscalară (un thread) şi cele SMT (2, 3 şi 6 thread-uri) îmbunătăţite.

0%

5%

10%

15%

20%

25%

1 2 3 6

Threads

IPC

Spe

edup

FP

INT

Figura 7.2. Creşterea relativă a performanţei de procesare (SMT îmbunătăţit vs. SMT clasic) variind

numărul de fire

0%5%

10%15%20%25%30%35%40%

1 2 3 6

Threads

EDP

Gai

n

FPINT

Figura 7.3. Câştigul relativ de energie (SMT îmbunătăţit vs. SMT clasic) variind numărul de fire

Performanţele cele mai bune pe benchmark-urile întregi s-au obţinut cu două fire: o creştere IPC de 5,95% şi un câştig relativ de energie (EDP gain) de 10,44%. Deşi cele mai mari îmbunătăţiri au fost obţinute de arhitectura superscalară cu RB şi LVPT, şi configuraţia SMT cu 3 fire a oferit o creştere de performanţă de 16,51% şi un câştig substanţial de energie de 25,94%.

28

8. Concluzii şi dezvoltări ulterioare

Acest capitol prezintă unele concluzii cantitative şi calitative privind rezultatele experimentale obţinute şi accentuează posibile dezvoltări ulterioare. Principalele contribuţii ale acestei lucrări sunt următoarele:

• O metodologie de identificare a instrucţiunilor de ramificaţie dificile: am demonstrat că o instrucţiune de ramificaţie într-un anumit context dinamic al informaţiei de predicţie (adresa branch-ului, istoria locală sau globală, calea) este greu de prezis dacă este nepolarizată în acel context, oscilând între taken (saltul se face) respectiv not taken (saltul nu se face) într-un mod nedeterminist, entropic (comportament dezordonat). Am identificat aceste branch-uri dificile din benchmark-urile SPEC 2000 şi am încercat îmbunătăţirea predictibilităţii lor prin extinderea informaţiei de predicţie. Extinzând lungimea contextului binar la 28 de biţi, procentajul branch-urilor nepolarizate a scăzut la cca. 6%. De asemenea, cercetările noastre au arătat că adăugarea informaţiei de cale (formată din PC-urile ultimelor k branch-uri) la cele clasice de istorie locală/globală determină o polarizare mai ridicată doar în cazul folosirii unor contexte de istorie locală/globală scurte (sub 16 biţi). Istoriile locale şi globale suficient de lungi aproximează foarte bine informaţia de cale.

• Predictoare dedicate dezvoltate pentru îmbunătăţirea acurateţii de predicţie a branch-urilor nepolarizate: am arătat că pentru anumite instrucţiuni de ramificaţie, informaţiile de predicţie limitate (istorie locală, istorie globală şi calea spre branch-ul supus predicţiei) folosite de predictoarele actuale nu sunt întotdeauna suficient de relevante şi, din această cauză, ele nu pot fi predicţionate cu acurateţe. Acurateţea cea mai ridicată pe branch-urile nepolarizate, de doar 77,30%, am obţinut-o cu piecewise linear branch predictor [Jim05]. De aceea, este deosebit de importantă găsirea unor informaţii relevante care determină comportamentul instrucţiunilor de ramificaţie, pentru a fi utilizate de predictoare mai eficiente. Am dezvoltat diferite predictoare de valori Markoviene care folosesc istoria comprimată a precedentelor condiţii de salt, ale cărei elemente pot fi -1, 0 sau 1, în funcţie de semnul diferenţei dintre operanzi. Nici aceste predictoare puternice, capabile să exploateze corelaţia dintre comportamentul branch-ului şi istoria condiţiilor, n-au reuşit să îmbunătăţească predictibilitatea acestor branch-uri dificile. De asemenea, am îmbunătăţit predictoare convenţionale (GAg, PAg) şi neuronale, prin utilizarea condiţiei de salt precedente – Previous Branch Condition (PBC) – sub forma unei diferenţe pe 32 de biţi dintre operanzi. Chiar şi predictorul piecewise linear branch predictor îmbunătăţit, cel mai performant pe branch-urile nepolarizate, obţine o acurateţe modestă de 78,3% pe branch-urile nepolarizate, în timp ce acurateţea globală a predicţiei este de 95,45%. Aşadar, branch-urile nepolarizate sunt caracterizate de acurateţi de predicţie scăzute, indiferent de informaţia de predicţie folosită, reprezentând astfel o limitare fundamentală în domeniul predicţiei branch-urilor. Astfel, creşterea acurateţii de predicţie a acestor instrucţiuni de ramificaţie nepolarizate constituie o problemă deschisă, deoarece fiecare procent de astfel de instrucţiuni reduce decisiv acurateţea predicţiei şi implicit performanţa de procesare.

• Metrici de caracterizare a aleatorismului secvenţelor generate de branch-uri nepolarizate: pornind de la această provocare tehnică, am realizat un studiu comparativ privind gradul de aleatorism al secvenţelor de simboluri (taken şi not taken) generate de branch-uri polarizate respectiv nepolarizate. Pe baza cercetării bibliografice efectuate, am dezvoltat patru metrici pentru caracterizarea comportamentului unui branch din punct de vedere al gradului de aleatorism: complexitatea Kolmogorov a secvenţei de program care

Concluzii şi dezvoltări ulterioare

29

generează branch-ul, rata de compresie, entropia discretă respectiv acurateţea de predicţie cu HMM (Hidden Markov Models) a secvenţei generate de branch. Rezultatele simulărilor efectuate pe şase benchmark-uri de numere întregi din suita SPEC 2000 arată că toate cele patru metrici de caracterizare intrinsecă a unei secvenţe binare din punct de vedere al gradului de aleatorism asociat, converg în aceeaşi direcţie. Ele sunt foarte utile arhitectului de microprocesoare întrucât arată dacă un anumit branch dinamic este sau nu este „aleator” sau „nepredictibil”. În cazul în care metricile utilizate arată în mod clar că branch-ul nu este unul intrinsec aleator, arhitectul are şanse reale de îmbunătăţire a predictorului aferent. În cazul aleatorismului ridicat, răspunsul este unul pesimist întrucât secvenţa este una intrinsec, şi deci iremediabil, aleatoare. De precizat că aleatorismul comportării acestor branch-uri este o consecinţă a complexităţii uriaşe a programelor care le generează, după cum arătăm în lucrare.

• Metode anticipatorii selective integrate în arhitecturi superscalare: am arătat că 28,68% din instrucţiunile de ramificaţie sunt dependente de instrucţiuni cu latenţă ridicată (Load-uri critice, înmulţiri, împărţiri). Mai mult, 5,61% din instrucţiunile de ramificaţie sunt atât nepolarizate cât şi dependente de instrucţiuni cu latenţă ridicată. Aceste dependenţe reprezintă o sursă importantă de penalităţi datorate predicţiilor greşite, afectând serios performanţa globală a procesorului. De aceea, impactul negativ al branch-urilor, în special al celor nepolarizate, asupra performanţei globale poate fi atenuat anticipând rezultatele instrucţiunilor cu latenţă ridicată. Am dezvoltat un mecanism de anticipare selectivă a valorilor instrucţiunilor cu latenţă de execuţie ridicată, care include o schemă de reutilizare pentru instrucţiunile Mul şi Div, respectiv un predictor de valori pentru instrucţiunile Load critice. Rezultatele simulărilor efectuate, au arătat creşteri de performanţă (IPC) de 3,5% pe benchmark-urile de numere întregi respectiv 23,6% pe cele flotante şi o scădere importantă a consumului relativ de energie (a EDP-ului) de 6,2% respectiv 34,5%, evidenţiind eficienţa tehnicilor anticipatorii propuse în arhitecturi superscalare. De asemenea, am arătat că există o corelaţie temporală între numele registrelor şi valorile memorate în acestea. De aceea am extins predicţia dinamică a valorilor prin introducerea conceptului de predicţie a valorilor centrată pe contextul CPU (registre) şi nu pe instrucţiuni. Practic se prezice valoarea registrului destinaţie curent bazat pe analiza valorilor anterioare ale acestuia. Localităţile valorilor obţinute pe anumite registre ale arhitecturii MIPS au fost remarcabile conducând la concluzia că predicţia valorilor poate fi aplicată cu succes cel puţin centrat pe aceste registre favorabile, prin ataşarea câte unui predictor la nivelul acestora. Astfel se reduce semnificativ numărul predictoarelor şi scade corespunzător complexitatea şi consumul de putere statică/dinamică. Am dezvoltat şi simulat diferite predictoare de valori centrate pe registrele procesorului: de tip last value, incrementale, contextuale şi hibride. Rezultatele evaluărilor au arătat că predictorul hibrid cu prioritizare dinamică, format dintr-un predictor adaptiv pe două niveluri şi unul incremental, exploatează cel mai eficient această corelaţie, depăşind chiar şi hibridul mult mai complex format dintr-un predictor PPM (Prediction by Partial Matching) şi unul incremental.

• Metode anticipatorii selective integrate în arhitecturi SMT: după ce am arătat utilitatea anticipării selective a instrucţiunilor cu latenţă ridicată într-o arhitectură superscalară, am analizat eficienţa acestor metode şi într-o arhitectură SMT, focalizându-ne pe aceleaşi instrucţiuni (Mul şi Div respectiv Load-uri critice). Am implementat structuri RB şi LVPT private pentru fiecare thread. Simulările efectuate pe benchmark-urile SPEC 2000 au arătat îmbunătăţiri IPC pe toate configuraţiile SMT evaluate. Cu cât numărul de fire este mai mare, cu atât creşterea de performanţă devine însă tot mai puţin semnificativă, datorită exploatării tot mai eficiente a unităţilor de execuţie partajate de către procesorul SMT. Plastic spus, cu motorul SMT mergând în plin, sporul de performanţă aferent tehnicilor anticipative implementate adiţional devine mai mic. Cele mai bune performanţe medii, de 2,29 IPC pe benchmark-urile de numere întregi respectiv

Concluzii şi dezvoltări ulterioare

30

de 2,88 IPC pe cele flotante, s-au obţinut cu şase fire de execuţie. Performanţele cele mai bune pe benchmark-urile întregi s-au obţinut cu două fire: o creştere IPC de 5,95% şi un câştig relativ de energie (EDP gain) de 10,44%. Deşi cele mai mari îmbunătăţiri au fost obţinute de arhitectura superscalară cu RB şi LVPT, şi configuraţia SMT cu 3 fire a oferit o creştere de performanţă de 16,51% şi un câştig substanţial de energie de 25,94%. Ca o concluzie, focalizarea unor metode anticipatorii cunoscute pe instrucţiuni cu latenţă de execuţie ridicată, îmbunătăţeşte performanţele şi reduce consumul de energie în arhitecturile superscalare şi SMT.

În continuare sunt trecute succint în revistă câteva direcţii de cercetare interesante care merită să fie investigate în viitor. Deoarece acurateţea de predicţie a instrucţiunilor de ramificaţie nepolarizate rămâne în continuare o problemă deschisă, identificarea şi utilizarea unor contexte relevante (anumite informaţii din codul sursă de nivel înalt) este imperios necesară. O alternativă ar putea fi un mecanism care să asigure predicţiei dinamice a branch-urilor suportul compilatorului. Astfel, prin reorganizarea codului s-ar putea elimina cât mai multe branch-uri (în special nepolarizate), supunând predicţiei dinamice doar branch-urile rămase. O altă alternativă ar putea fi utilizarea conceptului de micro-threading prin care fragmente scurte de cod (ex. ambele direcţii ale branch-ului) sunt executate concurenţial, reducând astfel importanţa problemei instrucţiunilor de ramificaţie. Ar fi de asemenea utilă cuantificarea impactului branch-urilor nepolarizate în arhitecturi multicore. O altă provocare importantă ar putea fi evaluarea eficienţei mecanismului de anticipare selectivă a valorilor instrucţiunilor cu latenţă ridicată într-o arhitectură multicore.

31

Bibliografie selectivă

[Bur97] Burger D., Austin T., The SimpleScalar Tool Set, Version 2.0, (ftp://ftp.cs.wisc.edu/pub/sohi/Code/simplescalar), Technical Report, University of Wisconsin, Madison, USA, June 1997.

[Cor01] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, Section 16.3, pages 385–392, Second Edition, MIT Press and McGraw-Hill, 2001

[Flo02] Florea A., Vintan L., Sima D., Understanding Value Prediction through Complex Simulations, Proceedings of the 5th International Conference on Technical Informatics, University “Politehnica” of Timisoara, Romania, October, 2002.

[Flo06] Florea A., Gellert A., Memory Wall — A Critical Factor in Current High-Performance Microprocessors, Science and Supercomputing in Europe, ISBN 978-88-86037-19-8, Barcelona, Spain, 2006.

[Flo07a] Florea A., Radu C., Calborean H., Crapciu A., Gellert A., Vintan L., Designing an Advanced Simulator for Unbiased Branches Prediction, Proceedings of 9th International Symposium on Automatic Control and Computer Science, ISSN 1843-665X, Iasi, 2007.

[Flo07b] Florea A., Radu C., Calborean H., Crapciu A., Gellert A., Vintan L., Understanding and Predicting Unbiased Branches in General-Purpose Applications, Bulletin of the Polytechnic Institute of Iasi, Tom LIII (LVII), Fasc. 1-4, Section IV, ISSN 1220-2169, 2007.

[Gel03] Gellert A., Contribuţii la procesarea speculativă a instrucţiunilor prin predicţia dinamică a valorilor, Lucrare de disertaţie, Universitatea “Lucian Blaga” din Sibiu, Catedra de Calculatoare şi Automatizări, 2003 (îndrumător Prof. L. Vinţan).

[Gel06a] Gellert A., Prediction Methods Integrated into Advanced Architectures, 1st PhD Report, Computer Science Department, "Lucian Blaga" University of Sibiu, January 2006.

[Gel06b] Gellert A., Florea A., Finding and Solving Difficult Predictable Branches, Science and Supercomputing in Europe, ISBN 978-88-86037-19-8, Barcelona, Spain, 2006.

[Gel06c] Gellert A., Vintan L., Person Movement Prediction Using Hidden Markov Models, Studies in Informatics and Control, Vol. 15, No. 1, ISSN 1220-1766 (IEE INSPEC), National Institute for Research and Development in Informatics, Bucharest, March 2006.

[Gel07a] Gellert A., Integration of Some Advanced Prediction Methods into Speculative Computing Systems, 2nd PhD Report, Computer Science Department, "Lucian Blaga" University of Sibiu, March 2007.

[Gel07b] Gellert A., Florea A., Vintan M., Egan C., Vintan L., Unbiased Branches: An Open Problem, Twelfth Asia-Pacific Computer Systems Architecture Conference (ACSAC’07), Seoul, Korea, August 2007; Lecture Notes in Computer Science, Advances in Computer Systems Architecture, vol. 4697, pp. 16-27, ISSN 0302-9743 (Print) 1611-3349 (Online), Springer-Verlag Berlin / Heidelberg, 2007 (ISI Thomson Journals).

[Gel07c] Gellert A., Vintan L., Florea A., A Systematic Approach to Predict Unbiased Branches, ISBN 978-973-739-516-0, “Lucian Blaga” University Press, Sibiu, Romania, 2007 (http://webspace.ulbsibiu.ro/arpad.gellert/html/Unb_Br_Book.pdf).

[Gel08a] Gellert A., Developing and Improving the Performances of Some Predictive Architectures, 3rd PhD Report, Computer Science Department, "Lucian Blaga" University of Sibiu, April 2008.


32

[Gel08b] Gellert A., Florea A., Vintan L., Exploiting Selective Instruction Reuse and Value Prediction in a Superscalar Architecture, Revised version submitted to Journal of Systems Architecture, July 2008 (ISI Thomson Journals).

[Gol07] Golander A., Weiss S., Reexecution and Selective Reuse in Checkpoint Processors, HiPEAC Journal, 2007.

[Gzip] http://www.gzip.org/.

[Jim05] Jiménez D., Idealized Piecewise Linear Branch Prediction, Journal of Instruction-Level Parallelism, April 2005.

[Lip96a] Lipasti M.H., Wilkerson C.B., Shen J.P., Value Locality and Load Value Prediction, Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 138-147, October 1996.

[Oan06] Oancea M, Gellert A., Florea A., Vintan L., Analyzing Branch Prediction Contexts Influence, Advanced Computer Architecture and Compilation for Embedded Systems, (ACACES 2006), ISBN 90 382 0981 9, pages 5-8, L’Aquila, Italy, July 2006.

[Rab89] Rabiner L.R., A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, Vol 77, No. 2, February 1989.

[Rad07] Radu C., Calborean H., Crapciu A., Gellert A., Florea A., An Interactive Graphical Trace-Driven Simulator for Teaching Branch Prediction in Computer Architecture, The 6th EuroSim Congress on Modeling and Simulation, 2007, Ljubljana, Slovenia.

[Ric93] Richardson S., Exploiting trivial and redundant computation, Proceedings of the 11th Symposium on Computer Arithmetic, July 1993.

[Saz99] Sazeides Y., An analysis of value predictability and its application to a superscalar processor, PhD Thesis, University of Wisconsin-Madison, 1999.

[Sha05] Sharkey J., Ponomarev D., Ghose K., M-SIM: A Flexible, Multithreaded Architectural Simulation Environment, Technical Report CS-TR-05-DP01, Department of Computer Science, State University of New York at Binghamton, October 2005.

[Sim] The SimpleSim Tool Set, ftp://ftp.cs.wisc.edu/pub/sohi/Code/simplescalar.

[Sod97] Sodani A., Sohi G., Dynamic Instruction Reuse, Proceedings of the 24th Annual International Symposium on Computer Architecture (ISCA’97), Denver, 1997.

[Sod00] Sodani A., Dynamic Instruction Reuse, PhD Thesis, University of Wisconsin-Madison, USA, 2000.

[SPEC] SPEC 2000, The SPEC benchmark programs, http://www.spec.org.

[Vin04a] Vintan L., Gellert A., Florea A., Register value prediction using metapredictors, Proceedings of the 8th International Symposium on Automatic Control and Computer Science, Iasi, October 2004.

[Vin04b] Vintan L., Gellert A., Petzold J., Ungerer T., Person movement prediction using neural networks, Technical Report 2004-10, Institute of Computer Science, University of Augsburg, Germany, April 2004, (http://www.informatik.uniaugsburg.de/skripts/techreports/)

[Vin04c] Vintan L., Gellert A., Petzold J., Ungerer T., Person Movement Prediction Using Neural Networks, Proceedings of the KI2004 International Workshop on Modeling and Retrieval of Context (MRC 2004), Vol-114, ISSN 1613-0073, Ulm, Germany, September 2004.

[Vin05a] Vintan L., Florea A., Gellert A., Focalising Dynamic Value Prediction to CPU’s Context, IEE Proceedings. Computers & Digital Techniques, Vol. 152, No. 4, Stevenage, UK, July 2005 (ISI Thomson Journals).


33

[Vin05b] Vintan L., Gellert A., Florea A., Value prediction focalized on CPU registers, Advanced Computer Architecture and Compilation for Embedded Systems, (ACACES 2005), Academia Press, ISBN 90 382 0802 2, pages 181-184, Ghent, Belgium, July 2005.

[Vin06] Vintan L., Gellert A., Florea A., Oancea M., Egan C., Understanding Prediction Limits through Unbiased Branches, Eleventh Asia-Pacific Computer Systems Architecture Conference (ACSAC’06), Shanghai, China, September 2006; Lecture Notes in Computer Science, Advances in Computer Systems Architecture, vol. 4186, pp. 480-487, ISSN 0302-9743, ISBN-13 978-3-540-40056, Springer-Verlag Berlin / Heidelberg, 2006 (ISI Thomson Journals).

[Vin08a] Vintan L., Florea A., Gellert A., Forcing Some Architectural Ceilings of the Actual Processor Paradigm, Invited Paper, The 3rd Conference of The Academy of Technical Sciences from Romania (ASTR), Cluj-Napoca, November 2008.

[Vin08b] Vintan L., Florea A., Gellert A., Random Degrees of Unbiased Branches, Proceedings of the Romanian Academy, Series A, No. 3, 2008 (ISI Thomson Journals).

[Wan97] Wang K., Franklin M., Highly Accurate Data Value Prediction using Hybrid Predictors, Proceedings of the 30th Annual ACM/IEEE International Symposium on Microarchitecture, December 1997.

Metode avansate de predicţie integrate în arhitecturi cu...

Documents

Transcript of Metode avansate de predicţie integrate în arhitecturi cu...