 |
Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/
august 2001
Iată un citat din știrile de astăzi (16 august 2001): ``Pe data de 27 august, la Intel Developer Forum, compania Intel va lansa noul procesor Pentium 4 la 2 Ghz''.
Deja nu mai surprinde pe nimeni apariția unei noi generații de procesoare: timp de treizeci de ani noile generații s-au succedat celor vechi, crescînd performanța de fiecare dată cu un factor constant. Chiar dacă constanta în sine este mică, rezultatele acumulate de-a lungul timpului sunt copleșitoare. Pentru a măsura distanța parcursă, este suficient să ne uităm la Intel 4004, primul microprocesor, care avea o viteză de ceas de 0,7 Mhz. Creșterea înregistrată în exact 30 de ani este de 2 Ghz/0.7 Mhz = 2875 de ori!
Performanța computațională a calculatoarelor a crescut însă și mai mult în această perioadă. Acest lucru este posibil pentru că performanța unui microprocesor nu depinde doar de frecvența ceasului, ci și de numărul de instrucțiuni care pot fi executate într-un ciclu de ceas. Procesoarele au evoluat enorm și în această privință: Intel 4004 lucra la o singură instrucțiune la un moment dat, și îi trebuiau mai mulți cicli de ceas pentru a o executa complet, Pentium 4 poate avea simultan în execuție pînă la 126 de instrucțiuni diferite, și poate termina execuția mai multor instrucțiuni în fiecare ciclu.
În acest articol voi discuta despre contribuția la performanță a micro-arhitecturii și compilatoarelor și voi ignora contribuția ceasului. Voi discuta atît procesoare contemporane, dar și unele aflate încă pe ``planșetele'' designer-ilor, care încă nu au făcut saltul din laboratoarele de cercetare în fabrici.
Am mai scris articole în PC Report despre arhitectura procesoarelor moderne (unele sunt menționate în finalul acestui articol); în articolul de față mă voi concentra asupra unei singure tehnologii, și anume execuția speculativă a codului.
Pentru a motiva folosirea execuției speculative, trebuie să subliniem încă odată rolul paralelismului în performanța sistemelor de calcul. Dacă fixăm frecvența ceasului, singura metodă prin care putem crește performanța este să executăm mai multe instrucțiuni în aceeași perioadă de timp. (Putem face ca fiecare instrucțiune să dureze mai puțini cicli de ceas, dar beneficiile pe care le putem extrage cu această metodă sunt limitate.) O sursă de performanță este deci execuția mai multor instrucțiuni simultan. Toate procesoarele moderne folosite în calculatoare (nu neapărat și cele din sisteme de control) sunt superscalare, putînd executa mai multe instrucțiuni în paralel. De exemplu, Pentium 4 are 8 unități funcționale care pot opera în paralel.
Aparent punem deci mai multe unități computaționale în paralel și performanța crește. În realitate lucrurile sunt mult mai complicate, pentru că nu oricare două instrucțiuni dintr-un program se pot executa simultan. De exemplu, dacă o instrucțiune folosește rezultatul alteia, atunci prima trebuie să-și termine execuția înainte ca a două să înceapă. Acest fenomen se numește dependență între cele două instrucțiuni.
Există două feluri de dependențe între instrucțiuni: dependențe de date și dependențe de control. Acestea sunt ilustrate în figura 1.
|
Putem să ne punem întrebarea: cîte instrucțiuni independente există într-un program? Cît de multe instrucțiuni putem executa potențial în paralel, presupunînd că avem un procesor ideal, cu o infinitate de resurse? Care tipuri de dependențe impun mai multe constrîngeri?
Pentru a răspunde la astfel de întrebări, la începutul anilor '90 mai mulți cercetători au făcut niște studii ``limită'', care încercau să estimeze paralelismul total disponibil într-un program (cu alte cuvinte, care este limita superioară pentru paralelismul care poate fi exploatat de hardware).
Un astfel de studiu, a fost publicat de doi cercetători de la universitatea Stanford în 1992; titlul său este ``Limite ale dependențelor de control asupra paralelismului''. Voi rezuma aici doar concluziile principale ale studiului, care sunt foarte interesante.
Putem clasifica programele analizate în acest studiu în două mari categorii: programe ``numerice'', scrise în FORTRAN, care manipulează matrici mari și au structuri de date foarte simple, și programe ne-numerice, care sunt scrise în C, au structuri de date complicate alocate dinamic și folosesc pointeri. Această categorisire este relativ standard; suita de programe SPEC, cea mai folosită pentru a evalua performanța sistemelor de calcul, conține o mixtură de astfel de programe.
Natura paralelismului este diferită pentru cele două categorii: programele în FORTRAN exhibă mai mult paralelism și mai multă regularitate în calcul (de exemplu, instrucțiunile de salt sunt mai predictibile). Dacă socotim numai dependențele de date, paralelismul variază între 45 și 3200 de instrucțiuni simultan pentru programele ne-numerice și între 800 și 300000 (sic!) pentru programele FORTRAN.
Dacă însă ne uităm și la dependențele de control, situația se schimbă în mod dramatic: paralelismul disponibil coboară la o valoare sub 10 pentru programele ne-numerice, și la valori între 2 și 60000 pentru cele numerice. Acest lucru se întîmplă pentru că instrucțiunile de salt sunt foarte frecvente în programe: în medie, una din 7 instrucțiuni este un salt. Dacă în plus presupunem că calculatorul nu poate executa două salturi simultan, paralelismul coboară la o valoare sub 3 pentru programele ne-numerice și la un maxim de 400 pentru cele numerice.
Din acest studiu putem extrage următoarea concluzie:: dacă executăm instrucțiunile programului în ordine, respectînd dependențele de control, nu putem crește performanța programului prea mult: pur și simplu, nu există suficient paralelism în program. Acest lucru este foarte pregnant pentru programele ne-numerice, care constituie majoritatea covîrșitoare a programelor care se execută pe un desktop contemporan.
Dacă vrem să exploatăm mai mult paralelism, trebuie să facem ceva deosebit; nu putem executa instrucțiunile din programe în ordine. Soluția este să executăm cod înainte de a fi siguri că trebuie executat; în felul acesta, dacă mai tîrziu aflăm că am anticipat corect, vom avea rezultatele pre-calculate. Aceasta este execuția speculativă.
Există două feluri de execuție speculativă:
În general microprocesoarele execută programele după prima strategie. A doua strategie este însă adesea folosită în circuitele hardware. Figura 2 ilustrează beneficiile execuției speculative.
 |
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ă re-calculă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:
În concluzie, pentru a implementa execuția speculativă avem nevoie de următoarele ingrediente:
În cele ce urmează voi discuta pe scurt în ce fel este implementată execuția speculativă în procesoarele de astăzi, și apoi cum arată propunerile pentru procesoarele viitorului. Procesoarele contemporane execută speculativ cod la nivel de instrucțiune, pe cînd cele viitoare vor suporta probabil execuția speculativă la nivel de fir de execuție (thread).
Execuția speculativă poate fi implementată în software, în hardware, sau folosind o mixtură a ambelor tehnici.
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''.
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ă:
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:
O schemă de execuție speculativă implementată complet în hardware este folosită la ora actuală de toate microprocesoarele moderne: PowerPC 620, MIPS R10000, arhitectura P6 de la Intel, AMD K5 și succesorii acestora. Multe din ingredientele necesare le-am discutat în alte articole din PC Report:
Deși implementarea în hardware este foarte sofisticată, ideea este relativ simplă:
Arhitectura IA-64 de la Intel oferă o altă soluție pentru execuția speculativă, în care compilatorul colaborează cu procesorul. Fiecare instrucțiune este etichetată cu o valoare de 1 bit, numită predicat. Dacă predicatul unei instrucțiuni este 1, atunci instrucțiunea se execută, altfel instrucțiunea este ignorată. Dacă notăm cu
p# a = b + c
faptul că instrucțiunea a = b + c se execută numai dacă p=1, atunci un programul:
if (a < 0)
b = b + 1;
else
d = b * 2;
se va traduce în ceva de genul:
1# p = a < 0 /* predicatul este 1: instructiunea se executa neconditionat */ 1# q = not p p# b = b + 1 q# d = b * 2
Dacă are destule resurse, microprocesorul va executa toate aceste instrucțiuni simultan.
Execuția speculativă la nivel de fir de execuție (thread) este un subiect de cercetare foarte fierbinte; se publică în continuare foarte multe articole pe această temă, dar nici un procesor încă nu implementează astfel de scheme. În această secțiune voi ilustra pe scurt una dintre propuneri; legături web spre alte proiecte puteți găsi în finalul acestui text.
Motivația pentru acest gen de cercetare vine din faptul că, în viitorul foarte apropiat, din cauza miniaturizării, arhitecții vor avea atît de multe resurse încît vor putea implementa mai multe procesoare pe aceeași pilulă de siliciu. Desigur, aceste procesoare pot executa fiecare alt program, dar cercetarea pe care o voi descrie aici discută despre cum mai multe procesoare pot colabora la execuția unui singur program secvențial.
Cheia este, desigur, execuția speculativă: programul este împărțit în mai multe fragmente de cod, în general de zeci pînă la mii de instrucțiuni fiecare. Fiecare fragment este un thread, care este executat în paralel pe un alt procesor. Unul dintre thread-uri este cel ``corect''; celelalte execută părți din ``viitorul'' probabil al programului.
Să ne uităm la un simplu exemplu:
while (! gata) {
...
x = hash[index1];
...
hash[index2] = y;
}
Dacă valorile index1 și index2 sunt diferite pentru toate iterațiile, toate accesele făcute de buclă în tabela hash se pot efectua în paralel. Dacă însă valoarea lui index2 dintr-o iterație este aceeași cu valoarea lui index1 dintr-o iterație ulterioară, între valorile corespunzătoare din hash se stabilește o dependență de date, care împiedică execuția paralelă. În figura 3 (b) ilustrăm o posibilă execuție secvențială a acestui program; în dreptunghiuri am ilustrat fiecare iterație. În figura 3 (c) ilustrăm cum s-ar putea desfășura execuția acestui program pe un multiprocesor cu 3 procesoare, cînd fiecare iterație a buclei este un thread separat.
 |
Observați că, spre deosebire de schema software-pur pe care am descris-o mai devreme, în caz de speculație eronată aici nu reluăm întreg procesul de calcul, ci doar partea care a fost eronată.
Ingredientele acestei scheme sunt următoarele:
Dintre toate thread-urile, unul singur este ``cel mai bătrîn'': acesta se execută ne-speculativ, și poate face orice modificări. Celelalte thread-uri sunt ordonate după vîrstă: în figura 3 thread-ul de pe procesorul 1 este cel mai vechi, cel de pe procesorul 2 este următorul și cel de pe procesorul 3 este cel mai nou. Thread-urile 2 și 3 se execută speculativ, pînă cînd thread-ul 1 se termină. Apoi 2 devine cel mai bătrîn, și procesorul 1 poate porni un thread-ul 4 (care nu e ilustrat în figură).
Fiecare thread face toate citirile și scrierile din memorie folosind cache-ul propriu. Cînd un thread citește un cuvînt în cache, îl marchează ca accesat (de exemplu, thread-ul 3 marchează cuvîntul de la adresa hash[10]). Cînd un thread modifică un cuvînt, trimite această informație tuturor celorlalte thread-uri mai tinere decît el. Cînd un thread tînăr a folosit o valoare care apoi este modificată de un thread mai bătrîn (hash[10] în figură este citit de thread-ul tînăr 3 înainte de modificarea thread-ului bătrîn 1), mesajul de modificare care vine de la thread-ul 1 (indicat de săgeata roșie din figură) îi indică thread-ului 3 faptul ca a speculat incorect. Cînd un thread detectează o speculație eronată, se sinucide și repornește.
Thread-urile se pot termina numai în ordinea în care au fost create: chiar dacă thread-ul 3 se termină înainte de 1, trebuie să aștepte pînă cînd 1 s-a isprăvit și a anunțat toate modificările sale, ca să vadă dacă nu cumva unele din valorile pe care le-a folosit el însuși au fost ilegale.
În acest articol am discutat despre paralelismul prezent în programe, care poate fi exploatat pentru a executa programele mai rapid. Am văzut că există două feluri de dependențe care fac ca instrucțiunile să nu fie paralele: dependențe de date și dependențe de control. Ambele tipuri de dependențe limitează paralelismul, dar dependențele de control au impact foarte important, limitînd paralelismul în programe ne-numerice la valori între 2 și 8.
Am văzut că execuția speculativă încearcă să elimine impactul dependențelor de control, executînd cod înainte de a fi certă necesitatea lui. Am văzut de asemenea că execuția speculativă poate fi implementată în multe feluri: în software, în hardware, sau cu suportul amîndurora; de asemenea, am văzut că putem specula la nivel de instrucțiuni sau de thread.
Problema selecției thread-urilor și a suportului care trebuie să fie oferit de hardware este încă un subiect foarte activ de cercetare; cu certitudine însă speculația la nivel de thread va fi un ingredient al procesoarelor viitoarului.