Strategii hardware
de predicție branch

O metodă consacrată în acest sens și care constituie punctul de plecare al tehnicilor actuale de predicție, o constituie metoda "branch prediction buffer" (BPB). BPB-ul reprezintă o mică memorie adresată cu cei mai puțin semnificativi biți ai PC-ului aferent unei instrucțiuni de salt condiționat.

Cuvântul BPB este constituit în principiu dintr-un singur bit. Dacă acesta este 1, atunci se prezice că saltul se va face, iar dacă este 0, se va prezice că saltul nu se va face. Evident că nu se poate ști în avans dacă predicția este ori nu corectă. Oricum, structura va considera că predicția este corectă și va declanșa aducerea instrucțiunii următoare de pe ramura prezisă. Dacă predicția se dovedește a fi fost falsă, structurile pipeline de procesare ale instrucțiunilor se evacuează și se va iniția procesarea celeilale ramuri de program. Desigur, acest proces implică penalizări semnificative asupra ciclilor de execuție. Totodată, în acest caz, valoarea bitului de predicție din BPB se inversează.

BPB cu un singur bit are un dezavantaj care se mani festă cu precădere în cazul buclelor de program, ca cea din figura "Bucla de program și acuratețea predicției BPB", în care saltul se va face ( N - 1)

o dată, la ieșirea din buclă, nu se va mai face. Bazat pe tehnica BPB, în acest caz vom avea uzual 2 predicții false: una la intrarea în buclă (prima parcurgere) și alta la ieșirea din buclă (ultima parcurgere a buclei).

Așadar, acuratețea predicției va fi de (N - 2) * 100 / N [%], iar saltul se face în proporție de (N - 1) * 100 / N [%]. Pentru a elimina acest dezavantaj, se utilizează 2 biți de predicție modificabili conform grafului de tranziție "Automatul de predicție de tip numărător saturat pe 2 biți" (numărător satu rat). În acest caz, acuratețea predicției unei bucle care se face de (N - 1) ori va fi (N - 1) * 100 / N [%].

Variațiuni ale acestui automat, pe 2 sau chiar mai mulți biți sunt posibile, dar fără să inducă creșteri semnificative ale performanțelor [Vin97].

Prin urmare, în cazul în care se prezice că branch-ul se va face, aducerea noii instrucțiuni se face de îndată ce conținutul noului PC e cunoscut. În caz contrar, se evacuează structura pipeline și se atacă cealaltă ramură a instrucțiunii de salt. Totodată, biții de predicție se modifică în conformitate cu graful din figură numit și numărător saturat.

Probabilitatea p ca predicția să fie corectă pentru o instrucțiune de salt e dată de relația:

  p = p1 * p2 + (1-p2) * p3, 

unde:

p1, p2 - probabilitatea ca predicția adresată în BPB să fie corectă și să se refere la respectiva instrucțiune de salt;

(1-p2)*p3 - probabilitatea ca predicția să fie corectă, deși nu se referă la instrucțiunea în curs de aducere. ( Există .posibilitatea ca 2 instrucțiuni de branch distincte să aibă cei mai puțin semnificativi biți ai PC-ului identici).

Este evident că maximizarea probabilității P se obține prin maximizarea probabilităților p1, p2 (p3 nu depinde de caracteristicile BPB-ului).

O altă problemă delicată constă în faptul că, deși predicția poate fi corectă, de multe ori adresa de salt (noul PC) nu este disponibilă în timp util, adică la finele fazei de fetch a instrucțiunii (IF- Instruction Fetch). Acest timp necesar calculului noului PC are un efect defavorabil asupra ratei de procesare. Soluția la această problemă este dată de metoda de predicție numită "branch target buffer" (BTB), cea mai utilizată la ora actuală (Ex. Intel Pentium). Un BTB este constituit dintr-un BPB care conține pe lângă biții de predicție, noul PC de după instrucțiunea de salt condiționat (target address) și eventual alte informații. De exemplu, un cuvânt din BTB ar putea conține și instrucțiunea țintă (target opcode). Astfel, ar crește performanța, nemaifiind necesar un ciclu de aduce re a acestei instrucțiuni, dar în schimb ar crește costurile de implementare. Diferența esențială între memoriile BPB și BTB constă în faptul că prima e o memorie operativă, în timp ce a 2-a poate avea un anumit grad de asociativitate.

La începutul fazei IF se declanșează o căutare asociativă în BTB (full associative), după conținutul PC-ului în curs de aducere. În cazul în care se obține hit, se obține în avans PC-ul aferent instrucțiunii următoare. Mai precis, considerând o structură pipeline pe 3 faze (IF- fetch, RD- decodificare, EX- execuție) algoritmul de lucru cu BTB-ul este prezentat în "Schema de predicție Branch Target Buffer" [Hen96].

IF) Se trimite PC-ul instrucțiunii ce urmează a fi adusă spre memorie și spre BTB. Dacă PC-ul trimis corespunde cu un PC din BTB, se trece în pasul RD 2, altfel în pasul RD1.

RD1) Dacă instrucțiunea adusă e o instrucțiune de branch, se trece în pasul EX 1, altfel se continuă procesarea normală.

RD2) Se trimite PC-ul prezis din BTB spre memoria de instrucțiuni. În cazul în care condițiile de salt sunt satisfăcute, se trece în pasul EX 3, altfel în pasul EX 2.

EX1) Se introduce PC-ul instrucțiunii de salt precum și PC-ul prezis în BTB. De obicei, această alocare se face în locația cea mai de demult neaccesată LRU (least recently used).

EX2) Predicția s-a dovedit eronată. Trebuie reluată faza IF de pe cealaltă ramură.

EX3) Predicția a fost corectă, însă numai dacă PC-ul predicționat este într-adevăr corect, adică neschimbat.În acest caz, se continuă execuția normală.

În tabelul "Avantaje - dezavantaje scheme BTB" sunt rezumate avantajele și dezavantajele tehnicii BTB.

Rezultă că numărul de cicli de penalizare CP este dat de următoarea relație:

 CP = PBTB (Ptn*Ctn +Pnt*Cnt) +(1-PBTB)*P*Ct 

unde:

P_BTB - probabilitatea ca instrucțiunea de salt să se afle în BTB;

P_tn - probabilitatea ca saltul să fie prezis că se face și în realitate nu se face;

P_nt - probabilitatea ca saltul să fie prezis că nu se face și în realitate se va face;

P - probabilitatea ca respectiva instrucțiune de salt să se facă;

În acest caz, rata de procesare a instrucțiunilor ar fi dată de relația:

 IR= 1/(CPI + Pb*CP), [instr./tact], 

unde P_b= probabilitatea ca instrucțiunea curentă sa fie una de ramificație, iar

CPI = rata [cicli / instrucțiune] ideal obtena bilă (maximă) de procesorul paralel. Actualmente, CPI e cuprins între 0.25 și 0.17 (Alpha 21164)

Un model matematic simplu al acestei tehnici pentru un BTB cu N biți de memorare, se referă la maximizarea funcției F [Per93] :

 F = Pex(i)[P(i)*Ptt(i)*V(i)            
         - (1 - P(i))* Ptn( i )*W(i)] 

astfel încât

n( i ) <=N,          

unde :

n( i ) - numărul de biți din BTB alocat instrucțiunii de branch i;

N - numărul total de biți din BTB;

S - numărul de instrucțiuni branch procesate în cadrul programului;

Relativ la expresia funcției F avem următorii termeni:

P_ex( i ) - probabilitatea ca branch-ul i să se execute în cadrul programului ;

P( i ) - probabilitatea ca branch-ul i să se facă;

P_tt( i ) - probabilitatea ca branch-ul i să fie prezis că se face și într-adevăr se va face;

V( i ) - numărul de cicli economisiți în cazul unei predicții corecte a branch-ului i;

W( i ) - numărul de cicli de penalizare în cazul unei predicții incorecte a branch-ului i;

Obs.1) P_tt( i ) = P_tn( i ) = 0, dacă branch-ul i nu se află în BTB.

Obs.2) S-a considerat că BTB nu îmbunătățește performanța pentru o predicție corectă de tipul "saltul nu se face" (P_nn( i ) = 0), întrucât în acest caz structura se comportă la fel ca și o structură fără BTB. De asemenea, pentru o predicție incorectă a faptului că "saltul se face" , am considerat costul același cu cel pe care l-am avea fără BTB; din acest motiv P_nt( i ) nu intră în expresia funcției.

Obs.3) În consecință, un branch trebuie introdus în BTB, cu prima ocazie când el se va face. Un salt care ar fi prezis că nu se va face nu trebuie introdus în BTB, pentru că nu are potențialul de a îmbunătăți performanța (nu intră în expresia funcției F). Există strategii care, atunci când trebuie evacuat un branch din BTB, îl evacuează pe cel cu potențialul de performanță minim, care nu coincide neapărat cu cel mai puțin folosit tip LRU (vezi [Per93]). Astfel, în [Per93] se construiește câte o variabilă MPP ( Minimum Performance Potential), implementată în hardware , asociată fiecărui cuvânt din BTB. Evacuarea din BTB se face pe baza MPP-ului minim. Acesta se calculează ca un produs între probabilitatea ca un branch din BTB să fie accesat și, respectiv, probabilitatea ca saltul să se facă, pe baza unei euristici implementată "run- time". Minimizarea ambilor factori duce la minimizarea MPP-ului și deci la evacuarea respectivului branch din BTB, pe motiv că potențialul său de performanță este minim. Rezultatele sunt cu puțin mai bune decât cele implicate de binecunoscutele strategii LRU sau Random.

În literatură se arată că prin astfel de scheme se ajunge la predicții corecte în (80-90%) din cazuri. Există implementări de mare performanță în care biții de predicție sunt gestionați și funcție de "istoria" respectivei instrucțiuni de salt, pe baze statistice (INTEL NEX GEN, TRON, etc). Prin asemenea implementări, crește probabilitatea de predicție corectă a branch-ului.

În literatură [Hen96, Per93], bazată pe testări laborioase, se arată că se obțin predicții corecte în 88% din cazuri folosind un bit de predicție și, respectiv, în 93% din cazuri folosind 2 biți de predicție. Acuratețea predicțiilor crește asimptotic cu numărul biților de predicție utilizați, adică practic cu "istoria predicției". Se arată că pentru a obține performanțe satisfăcătoare sunt necesare predicții corecte în peste 97% din cazuri [Yeh92]. O acuratețe a predicției de 98%, încă neatinsă (ca medie armonică pe benchmarkurile SPECint ‘95), provoacă o degradare a performanței cu peste 10% față de cazul ideal, ceea ce este semnificativ.

Schema de automat de predicție pe 4 stări poate fi generalizată ușor la N = 2^k stări. Se poate arăta că există N^2N * 2^N (stări x ieșiri) automate distincte de predicție cu N stări, deși multe dintre acestea sunt triviale din punct de vedere al predicțiilor salturilor.

În literatură se arată într-un mod elegant, pe bază teoretică și de simulare, că predictorul de tip numărător saturat pe 2 biți este cvasioptimal în mulțimea acestor automate de predicție. După cum vom arăta, prin scheme de predicție corelate salturilor se pot obține performanțe superioare.

În acord cu literatura de specialitate, mărirea numărului N de stări ale automatului de predicție pe k biți nu conduce la creșteri semnificative ale performanței.

Predicția corelată (adaptivă) a ramificațiilor

Schemele de predicție anterior prezentate se bazau pe comportarea recentă a unei instrucțiuni de salt, de aici predicționându-se comportarea viitoare a acelei instrucțiuni de salt. Este posibilă îmbunătățirea acurateței predicției, dacă aceasta se va baza pe comportarea recentă a altor instrucțiuni de salt, întrucât frecvent aceste instrucțiuni pot avea o comportare corelată în cadrul programului. Schemele bazate pe această observație se numesc scheme de predicție corelată sau adaptive și au fost introduse pentru prima dată în 1992 de către cercetătorii americani Yeh și Patt [Hen96, Yeh92].

Să considerăm pentru o primă exemplificare a acestei idei o secvență de program C, extrasă din banchmark-ul Eqntott din cadrul grupului SPECint ‘92:

   (b1) if (x = = 2) 

     x = 0;  

   (b2) if (y = = 2) 

     y = 0; 

   (b3) if (x ! = y) { 

Se observă imediat că, în acest caz, dacă salturile b1 și b2 nu se vor face, atunci saltul b3 se va face sigur (x = y = 0). Așadar, saltul b3 nu depinde de comportamentul său anterior, ci de comportamentul anterior al salturilor b1 și b2, fiind deci corelat cu acestea. Evident că în acest caz schemele de predicție, anterior prezentate, nu vor da randament.

Să considerăm acum pentru analiză o secvență de program C simplificată, împreună cu secvența obținută în urma compilării (s-a presupus că variabila x este asignată registrului R1).

 if (x = = 0) (b1) BNEZ R1, L1 

  x = 1;   ADD R1, R0, #1 

 if (x = = 1)  L1: SUB R3, R1, #1 

    (b2) BNEZ R3, L2 

Se poate observa că, dacă saltul condițio nat b1 nu se va face, atunci nici b2 nu se va face, cele 2 salturi fiind deci corelate.

Vom particulariza secvența anterioară, considerând iterații succesive ale acesteia pe parcursul cărora x variază de exemplu între 0 și 5. Un BPB clasic, inițializat pe predicție NU, având un singur bit de predicție, s-ar comporta ca în tabelul "Comportarea unui BPB clasic, pe o secvență defavorabilă de program".

Așadar, o astfel de schemă ar predicționa în acest caz, întotdeauna greșit! Să analizăm acum comportarea unui predictor corelat având un singur bit de corelație (se corelează deci cu instrucțiunea de salt anterior executată) și un singur bit de predicție. Acesta se mai numește și predictor corelat (1,1). Acest predictor va avea 2 biți de predicție pentru fiecare instrucțiune de salt: primul bit predicționează dacă instrucțiunea de salt actuală se face sau nu, în cazul în care instrucțiunea anterior executată nu s-a făcut, iar al doilea analog, în cazul în care instrucțiunea de salt anterior executată s-a făcut. Conform tabelului "Conținutul biților de predicție pt. o schemă corelată (1,1)", există deci următoarele 4 posibilități.

Ca și în cazul BPB-ului clasic cu un bit, în cazul unei predicții care se dovedește a fi eronată, bitul de predicție indicat se va complementa. Comportarea predictorului (1,1) pe secvența anterioară de program este prezentată în tabelul "Comportarea unui predictor corelat pe aceeași secvență de program" (s-a considerat că biții de predicție asociați salturilor b1 și b2 sunt inițializați pe NU / NU).

După cum se observa în tabel, singurele două predicții incorecte sunt când x = 5 în prima iterație. În rest, predicțiile vor fi întotdeauna corecte, schema comportându-se deci foarte bine, spre deosebire de schema BPB clasică.

În cazul general, un predictor corelat de tip (m,n) utilizează comportarea precedentelor m instrucțiuni de salt executate, alegând deci o anumită predicție de tip Da sau Nu din 2^m posibile iar n reprezintă numărul biților utilizați în predicția fiecărui salt.

Un alt avantaj al acestor scheme este dat de simplitatea implementării hardware, cu puțin mai complexă decât cea a unui BPB clasic. Aceasta se bazează pe simpla observație că "istoria" celor mai recent executate m salturi din program poate fi memorată într-un registru binar de deplasare pe m ranguri ( history register). Așadar, adresarea cuvântului de predicție format din n biți și situat într-o tabelă de predicții, se poate face foarte simplu prin concatenarea c.m.p.s. biți ai PC-ului instrucțiunii de salt curente cu acest regis tru de deplasare în adresarea BPB-ului de predicție. Ca și în cazul BPB-ului clasic, un anumit cuvânt de predicție poate corespunde la mai multe salturi. Există în implementare 2 structuri deci: un registru de predicție al cărui conținut concatenat cu PC- ul c.m.p.s. al instrucțiunii de salt, pointează la un cuvânt din tabela de predicții (aceasta conține biții de predicție, adresa destinație, etc.). În [Yeh92], nu se face concatenarea PC- regis tru de predicție și, în consecință, se obțin rezultate nesatisfăcătoare datorită interfe renței diverselor salturi la aceeași locație din tabela de predicții, lucru constatat și dove dit de noi prin simulări proprii.

De remarcat că un BPB clasic reprezintă un predictor de tip (0,n), unde n este numărul biților de predicție utilizați.

Numărul total de biți utilizați în implementarea unui predictor corelat de tip (m,n) este N:

  N = 2m * n * NI,  

unde NI reprezintă numărul de intrări al BPB-ului utilizat.

Există citate în literatură mai multe implementări de scheme de predicție a ramificații lor. Astfel, de exemplu, implementarea tipică a unui predictor corelat de tip GAg (Global History Register, Global Prediction History Table) este prezentată în figură. Tabela de predicții PHT (Prediction History Table) este adresată cu un index rezultat din concatenarea a două informații ortogonale: PClow (i biți), semnificând gradul de localizare al saltului, respectiv registrul de predicție (HR- History Register pe k biți), semnificând "contextul" în care se situează saltul în program. Desigur, PHT poate avea diferite grade de asociativitate. Un cuvânt din această tabelă are un format similar cu cel al cuvântului dintr-un BTB.

În scopul reducerii interferențelor diverselor salturi în tabela de predicții, în [Yeh92] se prezintă o schemă numită PAg- Per Address History Table, Global PHT, a cărei structură este oarecum asemănătoare cu cea a schemei GAg. Componenta HR^*(k) a introdus-o autorul acestui articol, având semnificația HR de la GAg, adică un registru global care memorează comportarea ultimelor k salturi. Fără această componentă, cred că schema PAg și-ar pierde din capacitatea de adaptare la contextul programului, în sensul în care schema GAg o face. În schimb, componenta HR din History Table, conține "istoria" (taken/ not taken) saltului curent, ce trebuie predicționat. După cum se va arăta mai departe, performanța PAg este superioară celei obținute printr-o schemă GAg.

O comparare echitabilă între schemele de predicție clasice și cele corelate trebuie să impună același număr de biți, utilizați în implementarea celor 2 scheme de comparat. Așa de exemplu, în [Hen96] se compară un predictor (0,2) de capacitate 4k cu predictor (2,2) de capacitate 1k. Acuratețea predicții lor schemei corelate este clar mai bună. Simulările s-au făcut pe procesorul DLX, bazat pe 10 benchmark-uri SPECint ‘92. Schema corelată a obținut predicții corecte în 82%-100% din cazuri. Mai mult, predictorul (2,2) obține rezultate superioare în comparație chiar cu un BPB, având un număr infinit de locații.

O altă problemă dificilă este determinată de instrucțiunile de tip RETURN, întrucât o aceeași instrucțiune poate avea adrese de revenire diferite, ceea ce va conduce în mod normal la predicții eronate, pe motivul modi ficării adresei eronate în tabela de predicții. Desigur, problema se pune atât în cazul schemelor de tip BTB cât și a celor de tip corelat. Soluția de principiu [Kae91] constă în implementarea în hardware a unor așa zise "stack - frame"- uri diferite. Acestea vor fi niște stive, care vor conține perechi CALL/ RETURN cu toate informațiile necesare asocierii lor corecte. Astfel, o instrucțiune CALL poate modifica dinamic în tabela de predicții adresa de revenire pentru instrucțiunea RETURN corespunzătoare, evitându-se astfel situațiile nedorite mai sus, schițate. Același lucru este valabil și în cazul unor salturi în moduri de adresare indirecte prin registru, unde modificarea dinamică a registrului pointer poate avea efecte defavorabile în procesul de predicție.

O altă soluție în problema ramificațiilor de program, radical diferită dar dificilă și costisitoare, constă în aducerea instrucțiunilor din cadrul ambelor ramuri ale branch-ului în structuri pipeline paralele (multiple instructions streams). Când condiția de salt e determinată, una din ramuri se va abandona. Desigur că în acest caz sunt necesare redundanțe importante ale resurselor hardware, precum și complicații în logica de control. Dacă pe o ramură a programului există de ex. o instrucțiune de tip STORE, procesarea acestei ramuri trebuie oprită, întrucât există posibilitatea unei alterări ireparabile a unei locații de memorie. Această soluție implică creșteri serioase ale costurilor, dar, se pare că ar fi singura capabilă să se apropie oricât de mult față de idealul predicției absolut corecte. În cazul microprocesoarelor, aceste mecanisme de prefetch ale ambelor ramuri, nu se aplică în prezent decât în cazuri rare, în principal datorită lărgimii de bandă limitate între microprocesor și memoria principală dar și a unor dificultăți legate de biportarea acesteia. Tehnica s-a întâlnit rar în cazul supercomputerelor anilor ‘70, ‘80 (IBM- 3033).

Aceste tehnici de predicție hardware a branch-urilor, datorită complexității lor, nu sunt implementate în mod uzual în microprocesoarele RISC (Reduced Instruction Set Computing) scalare, întrucât se preferă tehnicile software de "umplere" a " branch delay slot"-ului (limitat în general la o instrucțiune) cu instrucțiuni utile, anterioare celei de salt. În schimb, predicția hardware este implementată în cazul unor procesoare superscalare, care lansează în execuție mai multe instrucțiuni din bufferul de prefetch, simultan, și unde datorită BDS-ului de câteva instrucțiuni, umplerea lui cu instrucțiuni anterioare independente devine practic imposibilă [Vin97, Vin98].

O investigație și câteva rezultate

În continuare, se prezintă pe scurt o investigație inițiată la Universitatea "Lucian Blaga" din Sibiu, Catedra de Calculatoare și Auto ma tizări, ce abordează pe bază de simulare software, problema extrem de interesantă și dezbătută, a celor mai performante scheme de predicție la ora actuală, cele corelate pe 2 nivele. Se încearcă integrarea unei asemenea predicții hardware în cadrul arhitecturii HSA (Hatfield Superscalar Architecture), dezvoltată la Universitatea din Hertfordshire, UK. Menționăm că, până în prezent, această arhitectură se baza pe tehnici pur software de tip compensare "Branch Delay Slot" [Ste96]. De asemenea, se prezintă rezultatele obținute, aflate în deplină concordanță cu cele publicate în literatura de specialitate recentă.

În continuare, se prezintă un simulator de tip "trace driven simulation", destinat predicției hardware adaptive pe două nivele, a instrucțiunilor de ramificație, implementat de către dipl. ing. Ion Breazu în cadrul unei teze de masterat dezvoltate sub directa îndrumare a autorului acestui articol, la Universitatea "Lucian Blaga" din Sibiu [Bre97]. De precizat că acest tip de scheme de predicție, după cum deja am arătat, sunt cele mai performante la ora actuală în cadrul procesoarelor paralele [Yeh92, Vin96, CheC96].

Acest predictor hardware este integrat, pentru prima dată, în cadrul arhitecturii de procesor HSA, care, inițial, nu a fost gândită să realizeze predicția hardware a ramificații lor [Ste96], aceasta constituind ideea autorului acestei lucrări. Se va urmări deci analizarea fezabilității unui astfel de predictor integrat în cadrul arhitecturii HSA.

Hist Reg reprezintă "registrul istorie" al predicțiilor și conține valori binare semnificând comportarea ultimelor k instrucțiuni de ramificație. În cadrul simulatorului dezvoltat de grupul de cercetare de la Universitatea "Lucian Blaga" din Sibiu, Hist Reg are o lungime variabilă, realist cuprinsă între 6 și 14 biți. De asemenea, s-a parametrizat și lungimea variabilei PClow (i biți), utilizată în adresarea tabelei de predicții.

Pentru tabela de predicții s-a folosit o structură vectorială de înregistrări. Fiecare înregistrare memorează adresa destinație a saltului și respectiv starea automatului de predicție asociată contextului la acel moment dat. În cadrul simulatorului, schema de automat de predicție utilizat poate fi stabilită inițial de către utilizator. Astfel, se pot alege automate având între 2 și 16 stări.

Programul procesează trace-uri HSA speciale, provenite din compilarea și executarea benchmark-urilor Stanford pe simulatorul HSA, scris în C sub Unix la Universitatea din Hertfordshire, UK [Ste96]. Aceste 8 benchmark-uri au fost scrise în C și propuse de către profesorul John Hennessy de la Universitatea din Stanford, U.S.A., cu scopul de a constitui "numitorul comun" în evaluarea performanțelor arhitecturilor ILP (Instruction Level Parallelism). Ele sunt considerate deosebit de reprezentative pentru aplicațiile de uz general (non-numerice) și realizează aplicații generale precum: sortări prin tehnici consacrate (bench-urile bubble, tree și sort), aplicații puternic recursive (bench-urile: permute, puzzle, tower-proble ma turnurilor din Hanoi), și alte aplicații clasice (matrix- procesări de matrici, queens - problema de șah a celor 8 regine). Aceste trace-uri speciale vor conține, după cum este și firesc, toate instrucțiunile de ramificație din benchmark, în ordinea executării lor. Fiecare dintre aceste instrucțiuni de rami ficație din trace are asociat PC-ul cores punzător și respectiv adresa destinație a saltului, esențială pentru verificarea corectitudinii predicției.

În realitate, trace-urile HSA conțin doar branch-urile care s-au făcut, din motive de economie de spațiu, după cum am mai arătat. Au trebuit deci generate pe baza acestora și a surselor în asamblare, trace-uri speciale conținând și salturile inefective.

În principiu, simulatorul dezvoltat funcționează astfel [Bre97]:

1. Inițializare simulator

Aici, utilizatorul va stabili numărul biților ce caracterizează registrul Hist Reg, PClow, precum și tipul automatului de predicție din cadrul tabelei de predicții. Tot acum se inițializează cu zero adresele destinație și starea automatului de predicție utilizat.

2. Simularea propriu-zisă

Se stabilește de către utilizator benchmark-ul de tip trace care va fi utilizat. Din acest benchmark, se citesc secvențial instrucțiunile de ramificație și se compară predicția reală din trace cu cea propusă din tabelă. Aici pot să apară 3 cazuri distincte: predicție corectă, predicție incorectă, predicție incorectă datorată exclusiv adresei de salt incorecte din tabelă. Acest ultim caz se poate datora faptului că adresa de salt din tabelă a fost modificată, de exemplu de către un alt salt, având astfel un fenomen de interferență al salturilor dar pot fi și alte cauze posibile (modificarea dinamică a adresei de salt aferentă aceleiași instrucțiuni). În continuare, se vor actualiza corespunzător registrul Hist Reg și respectiv locația folosită din tabela de predicții.

3. Generarea de rezultate

La finele simulării propriu-zise se generează rezultate semnificative, precum numărul total de salturi executate, procentajul de predicții corecte, incorecte și respectiv afectate de interferențe ale salturilor, rata de procesare, etc.

În continuare, se prezintă câteva rezultate semnificative obținute prin exploatarea simu latorului anterior descris pe câteva din suita benchmark-urilor Stanford, pentru scheme de predicție de tip BTB, respectiv GAg. Rezultă că, în cadrul acestor programe, în medie 15% din instrucțiuni sunt ramificații. Dintre acestea, cca 78% se fac.

Astfel, în figura "Acuratețea predicțiilor pt. diverse HR-uri" se prezintă procentajul predicțiilor eronate, obținute prin exploa tarea simulatorului pe benchmark-urile respective. Simularea s-a făcut considerând o tabelă de predicții având capacitatea 16k, considerând registrul Hist Reg de 10, 8 și 6 biți.

În aceste condiții, s-au obținut rate medii (armonice-HM) de miss de 7.06%, 6.95% și 6.4% respectiv. Dacă s-ar fi ajuns la Hist Reg pe 4 biți, s-ar fi obținut o rată medie de miss de 7.07%, ceea ce arată clar faptul că, performanța optimă se obține pentru Hist Reg pe 6 biți și anume o acuratețe a predicției de 93.6%, comparabilă cu cele obținute prin cercetări consacrate [Yeh92, Per93]. Normal, cel mai bine s-a comportat benchmark-ul matrix (predicție corectă în 96.5% din cazuri), întrucât aici 97% din salturi se fac. În plus, acestea sunt deosebit de predictibile, ca în toate programele cu un carac ter numeric accentuat de altfel.

O problemă interesantă care s-a dorit studiată a fost următoarea: în ce măsură predicțiile, altfel corecte, sunt afectate de modificarea adresei efective în tabela de predicții? La această întrebare se răspunde în graficul din figura "Predicții greșite din cauza modificării adresei de salt în predictor".

Simularea s-a realizat considerând Hist Reg de 10, 8 și 6 biți și s-au obținut adrese efective modificate în 5.16%, 4.89% și 4.73% din cazuri respectiv (medii armoni ce). Din nou optimul se obține și din acest punct de vedere pentru Hist Reg pe 6 biți (simulări pentru Hist Reg pe 4 biți generează adresă greșită în 4.8% din cazuri).

Din cele prezentate, precum și din alte cazuri particulare, explorate cu ajutorul simu latorului implementat, rezultă că optimul între gradul de corelare (Hist Reg) și capaci tatea tabelei (adresată prin intermediul PClow & Hist Reg ), se obține pentru lun gimi ale Hist Reg de cca 40% din numărul total al biților de adresare tabelă.

Altfel spus, aici stabilește simularea compromisul optim între 2 procese complementare: gradul de corelare al saltului (Hist Reg "mare") și respectiv gradul de localizare al saltului (PClow "mare"). Suma celor doi parametri este fixată prin proiectare, așadar compromisul optim trebuie găsit. Rezultatele acestei simulări demonstrează foarte clar următorul proces: un grad de localizare scăzut determină interferențe ale unor salturi diferite la aceeași locație din tabelă, rezultând predicții eronate pe motiv de adresă de salt alterată, deci scade performanța. Pe de altă parte, un grad de localizare ridicat determină un grad de corelare scăzut și deci schema devine inefectivă în cazul unor salturi corelate, datorită nesituării adecvate în context a predicției. Și în acest caz, performanța globală scade. Optimul este un compromis între aceste două situații extreme, după cum a și rezultat.

Desigur că fenomenul de interferență, poate fi evitat parțial prin creșterea gradului de asociativitate al schemelor de predicție, lucru care s-a și simulat de altfel și va fi prezentat în continuare. Astfel, de exemplu, prin adăugarea unui câmp de TAG în cadrul cuvântului tabelei de predicții, care să fie comparat dinamic în faza IF cu PChigh, se exclude posibilitatea mapării unor salturi diferite în aceeași locație din tabelă. Ar mai ramâne nerezolvată problema acelor salturi care modifică dinamic adresa țintă (instrucțiuni tip RETURN). Ea poate fi rezolvată de exemplu, prin implementarea unor stack-frame-uri diferite, asociate biunivoc diferitelor taskuri în curs de execuție. Și această soluție a fost evaluată prin simulare. Toate aceste soluții determină însă creșterea complexității și deci a costurilor de implementare, în spiritul unui etern compromis între performanță și prețuri. Simulatorul construit generează soluția optimală pentru orice schemă corelată de predicții.

Un astfel de predictor integrat în cadrul procesorului HSA conduce la rezultate foarte bune, pe deplin comparabile cu cele prezentate în literatură și constituie o alternativă superioară compensării statice a "branch delay slot"-ului, propuse în cadrul acestui procesor [Ste96]. Simulatorul construit conduce la soluția constructivă optimă de schemă de predicție corelată pe 2 nivele sau chiar tip BTB, integrată într-o arhitectură superscalară.

Se observă că, particularizând schema de predicție corelată pentru lungimea HR egală cu zero biți, se obține o schemă de predicție clasică, de tip BTB. Simulatorul implementat permite următoarele câmpuri în cuvântul BTB: PChigh (Tag), automat predicție parametrizabil ca tip, adresa țintă a saltului respectiv, opcode instrucțiune țintă (opțional). În continuare, se prezintă câteva rezultate, considerate ca fiind extrem de interesante, în cadrul acestei particulari zări de tip BTB.

În figura "Acuratețea predicției BTB pt. diverse automate de predicție", se prezintă influența numărului biților de predicție asupra acurateții predicției [%], într-o arhitectură BTB clasică. S-a considerat capacitatea BTB-ului de 50 intrări și numărul ciclilor de penalizare (CP) pentru o predicție eronată de 5 tacte. După cum se poate observa, diferențele între cele 3 variante sunt relativ nesemnificative, cea cu 2 biți de predicție fiind totuși mai bună. Acest rezultat este în concordanță cu cele obținute de alți cercetători [Per93].

Figura "Ratele de procesare funcție de numărul ciclilor de penalizare" prezintă influența numărului ciclilor de penalizare în cazul predicțiilor eronate pentru un BTB de 50 intrări, având 2 biți de predicție. După cum se poate observa, pentru CP=1 tact s-a obținut IR (Issue Rate- Rata medie de execuție a instrucțiunilor exprimată în instrucțiuni / ciclu) = 0.89, iar pentru CP=5 tacte s-a obținut IR=0.82, adică o deteriorare a performanței cu cca 9%, ceea ce era de așteptat.

În figura "Performanța funcție de capaci tatea BTB" se prezintă influența capacității BTB-ului asupra ratei de procesare conside rând 2 biți de predicție și CP=5. Astfel, s-a obținut pentru un BTB de 10 intrări un IR=0.65 [instr./ ciclu], iar pentru un BTB având 50 intrări, un IR=0.83 [instr./ ciclu], adică o creștere medie armonică de 28%. Se precizează că pentru capacități ale BTB-ului mai mari de 50 intrări, performanța crește asimptotic, ceea ce implică faptul că această capacitate generează performanțe optime.

În figura "Accelerarea produsă de introducerea opcode-ului în BTB" s-a prezentat accelerația S [%] determinată de introduce rea instrucțiunii țintă în cadrul cuvântului din BTB. Așadar, în acest caz, procesorul află prin predicție nu numai adresa de salt dar și opcode-ul instrucțiunii destinație, fiind deci scutit de penalizarea indusă de necesitatea aducerii acestui opcode. Simularea s-a realizat pe o schemă având 2 biți de predicție, capacitate 50 de intrări și CP=5. S-a constatat o accelerare medie armonică de 8.5%, iar media aritmetică de 12.25%, ceea ce este semnificativ și în acord cu alte rezultate publicate în literatură.

În figura "Comparare între schemele BTB și cele adaptive" se prezintă acuratețea predicțiilor comparativ pentru o schemă BTB cu tag și o schemă corelată pe două nivele. Se observă că, per ansamblu, schema corelată pe două nivele lucrează ceva mai bine.

În figura "Accelerarea unui predictor tip GAg cu Tag" se prezintă raportul (S%) între acuratețea obținută pentru un predictor corelat cu tag și cea obținută pentru un predictor corelat fără tag. S-a obținut în media armonică S=29%, rezultat previzibil având în vedere că schema cu tag elimină în bună parte interferențele branch-urilor, după cum am mai arătat.

Cercetari mai recente, efectuate de grupul nostru de cercetare pentru arhitecturi paralele și neconvenționale, au arătat că, din punct de vedere al raportului performanță / cost, schemele corelate de tip PAg par a fi cele optime. Grade ridicate ale asociativi tății tabelei "History Table" conduc la creșteri semnificative ale performanțelor predictive.

Bibliografie

[Bre97] Breazu I. (coord. L. Vintan) - Teh nici adaptive de predicție a ramificațiilor în arhitecturile superscalare, Teza de masterat, Universitatea "Lucian Blaga" din Sibiu, 1997

[CheC96] Chen C., King C.- Designing Dynamic Two- Level Branch Predictors Based on Pattern Locality, EuroPar Conf., Lyon, 1996

[Hen96] Hennessy J., Patterson D.- Compu ter Architecture- A Quantitative Approach, Morgan Kaufmann Publishers, 1996

[Kae91] Kaeli D., Emma P.- Branch History Table Prediction of Moving Target Branches due to Subroutine Returns, 18-th Int’l Conf. on Computer Architecture, Toronto, May, 1991

[Per93] Perleberg C., Smith A. J. - Branch Target Buffer Design and Optimisation, IEEE Trans. on Computers, No. 4, 1993.

[Ste96] Steven G. B., s.a. - A Superscalar Architecture to Exploit ILP, Euromicro Conference, 2-5 september, Prague, 1996.

[Vin97] Vințan L.- Metode de evaluare si optimizare in arhitecturile paralele de tip ILP, Editura Universitatii "Lucian Blaga" din Sibiu, ISBN 973-9280-67-6, 1997

[Vin98] Vințan L., Steven G.- Static Data Dependence Collapsing in a High Performance Superscalar Architecture,The 3-rd International Conference on Massively Parallel Computing Systems, Colorado Springs, U.S.A., 6-9 April, 1998

[Vin98b] Vințan L., Armat C., Steven G.- The Impact of Cache Organisation on the Instruction Issue Rate of a Superscalar Processor, Proceedings of European Conference on Parallel Architectures, 1-4 September, 1998. Southampton, UK

[Vin98c] Vințan L., Breazu I.- Branch Prediction into a RISC Environment, Acta Universitatis Cibiniensis, seria Electronica si Calculatoare, Ed. Univ. "L. Blaga" din Sibiu, 1998

[Yeh92] Yeh T., Patt Y. - Alternative Implementations of Two Level Adaptive Branch Prediction, 19 th Ann. Int.’L Symp. Computer Architecture, 1992

BYTE România - septembrie 1998

(C) Copyright Computer Press Agora