Execuția Speculativă a Instrucțiunilor

Execuţia speculativă a instrucţiunilor

Execuţia speculativă este deocamdată cea mai avansată tehnică de procesare a instrucţiunilor de salt. Execuţia speculativă se referă la abilitatea procesorului de a executa instrucţiuni în afara unei bucle condiţionale care nu a fost încă rezolvată şi în final de a produce rezultatele în ordinea execuţiei originale a fluxului de instrucţiuni. Execuţia speculativă conduce la estimarea cu o mai mare acurateţe a consumului de putere.

O instrucţiune, pentru a avea efecte permanente şi vizibile, trebuie neapărat să-şi scrie rezultatele undeva: fie într-un registru, fie în memorie. Asta înseamnă că atîta timp cît instrucţiunea nu a ajuns în stagiul de scriere ea nu este nicidecum vizibilă dinafară. Atunci putem face următorul lucru: putem încărca în ţeavă şi alte instrucţiuni de după cea de salt şi le lăsăm să se execute. Cînd ajungem cu saltul în stagiul de execuţie ştim deja dacă celelalte instrucţiuni trebuiau sau nu să fie executate; dacă observăm că am ales bine, suntem oameni făcuţi, pentru că saltul nu ne costă decît un ciclu, succesorii lui fiind deja gata de execuţie. Altfel recurgem la o soluţie asemănătoare cu cea de mai sus: ştergem conţinutul din începutul ţevii, introducînd mai multe bule.

Acest tip de execuţie în care mizăm pe anumite instrucţiuni de a fi utile, şi în care dacă ne dăm seama că am greşit renunţăm la ele, se numeşte execuţie speculativă (speculation). Această tehnică este din ce în ce mai folosită în procesoarele moderne.

Performanţa poate creşte, pentru că instrucţiunile pentru care am ghicit bine vor fi mai scurte, iar celelalte vor dura tot atît.

Un procesor superscalar poate face şi mai multă speculaţie: poate porni în execuţie ambele destinaţii ale ramurii (presupunînd că adresa destinaţie poate fi calculată rapid, înainte de a ajunge în stagiul de execuţie), după care poate alege să păstreze numai destinaţia reală.

Există două feluri de execuţie speculativă:

•-Care prezice instrucţiunile care se vor executa în viitor şi le execută mai devreme;

•-Care execută instrucţiuni în toate direcţiile posibile simultan şi păstrează numai rezultatele corecte.

În general microprocesoarele execută programele după prima strategie. A doua strategie este însă adesea folosită în circuitele hardware. Figura 1 ilustrează beneficiile execuţiei speculative.

Figura 1

(a)Un fragment de program în C

(b)Execuţie a programului care respectă dependenţele de control: întîi trebuie evaluată condiţia C, şi abia după aceea se poate executa blocul A sau blocul B, depinzînd de rezultat

(c)Execuţia speculativă execută simultan A, B şi C. Apoi rezultatul evaluării condiţiei este folosit pentru a alege rezultatele corecte

Lucrurile nu sunt însă chiar aşa de simple: ce se întîmplă cu rezultatele speculaţiei dacă am executat ramura greşită? În acest caz va trebui să distrugem rezultatele parţiale calculate şi să recalculăm pe ramura corectă. Execuţia speculativă elimină dependenţele de tip control din program, dar nu poate elimina dependenţele de date.

Execuţia speculativă poate fi incorectă din două motive:

•-Bucata de cod pe care am ales-o nu trebuia executată de loc: de exemplu, alegem să executăm A, dar trebuia să executăm B;

•-Bucata de cod pe care o executăm speculativ are nevoie de informaţii care încă nu au fost calculate: de exemplu, o valoare calculată de C este necesară în calculul lui A.

În concluzie, pentru a implementa execuţia speculativă avem nevoie de următoarele ingrediente:

alegere:

Un mecanism care alege codul care va fi executat în viitor;

detecţie:

Un mecanism care depistează cînd execuţia speculativă este eronată, fie pentru că am ales o ramură greşită, fie pentru că am ignorat o dependenţă de date;

reparaţie:

Un mecanism care permite ca execuţia speculativă greşită să fie des-făcută (rezultatele ei să fie ``şterse'');

reluare:

Un mecanism care ne permite după o eroare să reluăm execuţia pe calea corectă.

Execuţia speculativă în software

Execuţia speculativă implementată în software este folosită în cazul procesoarelor paralele. Avem atunci de a face cu programe pe care vrem să le executăm pe mai multe procesoare simultan, dar care nu au fost scrise în mod paralel. Cînd compilatorul nu poate paraleliza automat codul, poate recurge la execuţia paralelă speculativă. Iată un astfel de exemplu:

for (i=0; i < N; i++)

a[b[i]] = f(i);

Să presupunem că N=2, şi că evaluarea funcţiei f nu are ``efecte laterale''. Dacă matricea b conţine valorile [1,1], atunci cele două atribuiri din buclă trebuie executate una după alta, pentru că amîndouă modifică variabila a[1]. Dacă matricea b însă conţine valorile [1,2], cele două atribuiri se pot efectua în paralel, pentru că folosesc indici diferiţi în a.

Un compilator nu poate în general şti care sunt valorile din vectorul b, şi ca atare nu va paraleliza acest cod. Dacă N este mare şi ştim că în vectorul b nu există două valori identice, atunci putem distribui toate aceste operaţii pe mai multe procesoare, fiecare procesor efectuînd unele dintre ele.

Lawrence Rauchwerger a fost primul care a studiat în detaliu execuţia speculativă complet în software; în schema pe care o propune, compilatorul generează un program cu următoarea structură:

•-Execută codul speculativ în paralel pe mai multe procesoare, colectînd rezultatul într-un vector auxiliar aux;

•-Monitorizeaza valorile din vectorul b;

-Dacă în final nu există două valori identice în b, copiază rezultatul din variabila aux în variabila a;

-Dacă se depistează două valori identice în b, execută versiunea originală secvenţială a codului şi ignoră variabila aux.

Frumuseţea acestei scheme este că, atunci cînd speculaţia este corectă, programul se execută mult mai repede, iar cînd speculaţia este incorectă, nu se pierde foarte mult timp (se iroseşte doar timpul pentru o execuţie paralelă, care e mai mic decît cel pentru execuţia secvenţială). Preţul suplimentar pe care îl plătim este execuţia codului care verifică dacă valorile din vectorul b se suprapun.

Observaţi toate ingredientele pe care le-am descris mai sus:

alegere:

în cazul nostru, se vor executa viitoarele iteraţii ale buclei for;

detecţie:

cod suplimentar care monitorizează accesele la variabila b;

reparaţie:

variabila auxiliară aux stochează rezultatele intermediare, fără a ``polua'' variabila reală a;

reluare:

codul generat de compilator, care include atît versiunea paralelă cît şi pe cea secvenţială.