Branch prediction

Introducere

Rolul unui predictor de branch-uri in cadrul procesoarelor este important pentru asigurarea performantei aplicatiilor. Un salt conditionat care este incorect prezis conduce la invalidarea instructiunilor prezente in pipeline, ceea ce poate reduce considerabil performanta. De asemenea, un salt spre o adresa pentru care datele nu sunt prezente in cache are un impact negativ asupra performantei. Pentru controlul branch-urilor conditionale sau neconditionale pe Cell/BE, programatorul trebuie sa cunoasca si sa controleze aspecte ca: function inlining, loop unrolling, indicii pentru branch-uri si utilizarea spu_sel, pentru implementarea unui flux de control fara branch-uri.

Maniera de abordare a branch-urilor pe SPU este complet diferita fata de cea de pe PPU, datorita particularitatilor SPU-ului, acesta neincluzand mecanisme hardware pentru prezicerea conditiilor branch-urilor si a adreselor viitoare ale salturilor. Implicit, pe SPU conditiile branch-urilor sunt prezise a fi false. O prezicere incorecta determina o invalidare a pipeline-ului, ceea ce reduce performanta programului. Problemele legate de branch-uri pot fi amortizate prin folosirea indiciilor software pentru branch-uri (branch hints), prin care hardware-ului ii este transmis ca un anume branch va fi luat. Programatorii pot imbunatati performanta branch-urilor fie specificand manual hint-uri, folosind directiva de compilator __builtin_expect, sau folosind instrumentul pentru optimizare automata, FDPR-Pro.

In continuare, branch-urile vor fi analizate din punct de vedere al SPU-ului. Branch-urile prezise corect sunt executate intr-un ciclu, un branch (conditional sau neconditional) prezis incorect aduce insa o penalitate de pana la 19 cicluri. Asadar, branch-urile incorect prezise pot scadea considerabil performanta programului. In plus, branch-urile limiteaza capacitatea compilatorului de a planifica instructiunile intr-un mod optim, deoarece reprezinta o bariera pentru reordonarea instructiunilor.

Pentru a reduce impactul branch-urilor prezise incorect, se poate incerca eliminarea acestora sau, atunci cand acest lucru nu este posibil, le pot fi asociate indicii (branch hints), reprezentand cea mai probabila cale de executie pentru branch. De asemenea, tinand cont ca, in lipsa hint-urilor, conditiile sunt considerate a fi false, codul cel mai probabil de a fi executat ar putea fi plasat de catre programator pe ramura „else”.

Metodele care pot fi folosite pentru eliminarea branch-urilor, sau amortizarea efectelor negative ale branch-urilor, sunt:

  • 'function inlining', prin care sunt eliminate branch-urile de la apelul unei functii si de la returnarea din functie
  • 'loop unrolling', care elimina buclele sau reduce numarul de iteratii dintr-o bucla, in vederea reducerii numarului de branch-uri
  • 'flux de control fara branch-uri', realizat prin instructiunea spu_sel cu ajutorul careia pot fi eliminate instructiunile de control
  • 'indiciu pentru branch (branch hint)', prin care programatorul ofera un indiciu hardware-ului despre calea cea mai probabila de a fi urmata de program pentru branch-ul respectiv

Function inlining

Function inlining este o metoda folosita pentru a creste numarul de instructiuni consecutive fara branch-uri. In acest caz, sunt eliminate branch-urile asociate cu apelul functiilor si intoarcerea din functia apelata.

Pentru a utiliza function inlining, programatorul poate apela la una din urmatoarele tehnici:

  • definirea ca inline a functiilor de dimensiuni mici sau a celor care au un numar relativ mic de instante, dar sunt apelate la runtime de un numar mare de ori (de ex. in cadrul unei bucle)
  • folosirea la compilare a optiunilor care transforma automat anumite functii in inline: -finline-functions, -finline-functions-called-once, -finline-limit=n.

Dezavantajul tehnicii function inlining consta in faptul ca poate produce un cod de dimensiuni mari, iar dimensiunea LS este relativ mica.

Loop unrolling

Procedura de loop unrolling (desfasurare a buclelor) duce la eliminarea completa a buclelor sau la reducerea numarului de iteratii dintr-o bucla, cu scopul de a reduce numarul de branch-uri.

Daca numarul de iteratii dintr-o bucla este relativ mic, bucla poate fi eliminata pentru a scapa de branch-urile din cod:

/* bucla initiala */
for(i = 0; i < 3; i++) 
	x[i] = y[i];
/* bucla initiala se poate inlocui cu: */
x[0] = y[0];
x[1] = y[1];
x[2] = y[2];

Daca numarul de interatii este mare, iar iteratiile sunt independente, numarul de iteratii poate fi redus prin cresterea numarului de instructiuni executate intr-o iteratie:

/* bucla initiala */
for(i = 0; i < 300; i++)
	x[i] = y[i];
/* bucla initiala se poate “desfasura” in: */
for(i = 0; i < 300; i += 3) {
	x[i]   = y[i];
	x[i+1] = y[i+1];
	x[i+2] = y[i+2];
}

Desfasurea buclelor poate fi realizata automat, de catre compilator, daca nivelul de optimizare este suficient de mare, sau daca este utilizata una dintre optiunile -funroll-loops sau -funroll-all-loops. Asemanator cu function inlining, principalul dezavantaj consta in cresterea dimensiunii codului. Avand in vedere dimensiunea redusa a LS-ului, aceste optimizari trebuie aplicate cu precautie.

Flux de control fara branch-uri

Branch-urile dintr-o constructie if-then-else pot fi eliminate prin calcularea rezultatelor pentru ambele clauze (then si else) si utilizarea ulterioara a instructiunii spu_sel pentru a selecta rezultatul in functie de conditia if-ului. Daca determinarea ambelor rezultate are un cost mai mic decat prezicerea incorecta a branch-ului, atunci este inregistrat un castig de performanta.

/* if-else-ul original */
if (a > b) 
	c += 1;
else
	d = a + b;
/* cod optimizat care elimina branch-ul folosind spu_sel */
select = spu_cmpgt(a, b);
c_plus_1 = spu_add(c, 1);
a_plus_b = spu_add(a, b);
c = spu_sel(c, c_plus_1, select);
d = spu_sel(a_plus_b, d, select);

Indiciu pentru branch

Prin intermediul indiciilor pentru branch-uri, programatorul sau compilatorul speculeaza ca unele branch-uri urmeaza cu precadere o anumita cale si transfera aceasta informatie hardware-ului. Daca un indiciu nu este furnizat pentru un branch, atunci hardware-ul prezice implicit ca branch-ul nu va fi luat. Altfel spus, in lispa hint-urilor, hardware-ul presupune ca executia continua in mod secvential.

Exemplul de mai jos prezinta indicarea unei conditii prezisa de programator ca fiind falsa:

/* programatorul indica a > b == 0 */
if(__builtin_expect((a > b), 0))
	c += a;
else
	d += 1;

Prezicerea este denumita statica atunci cand al doilea parametru al __builtin_expect este o constanta:

/* programatorul indica x == 0 */
if(__builtin_expect(x, 0)) {
	foo();
}

Atunci cand cel de-al doilea parametru este determinat in timpul executiei, prezicerea se cheama dinamica, asa cum se intampla in cazul de mai jos:

cond2 = ... /* prezice cond2 */
...
cond1 = ...
if(__builtin_expect(cond1, cond2)) { /* programatorul indica cond1 == cond2 */
	foo();
}

Exercitii

In memoria principala este definita o matrice ce descrie calea de la intrarea într-un labirint pana la o comoara. Drumul spre comoara este encodat în matrice ca un set de salturi de la niste coordonate (rand, coloana) la altele (un nod din drum contine ca informatie urmatorul nod la care trebuie sa se sara). Cautarea va incepe din celula (0, 0). Stim ca am ajuns la comoara cand trebuie sa sarim inapoi in celula (0, 0). Scheletul contine un program PPU care genereaza un labirint si trimite SPU-ului adresa catre începutul matricii precum si dimensiunea unei linii a labirintului. SPU-ul va trebui sa gaseasca coordonatele comorii si sa le scrie în prima celula a labirintului (0, 0). Programul PPU va verifica apoi daca in celula (0, 0) se gasesc coordonatele comorii.

Concluzii

Pentru a facilita programarea aplicatiilor pentru Cell/B.E. pot fi folosite tehnici precum software caching. Software caching-ul este recomandat mai ales in acele situatii in care datele necesare unui program sunt prea mari pentru LS, iar accesarea acestora se face mai mult aleator. Fara software cache, managementul transferurilor DMA trebuie facut manual, lucru care devine complicat atunci cand exista multe transferuri de dimensiuni reduse.

Lipsa unui mecanism hardware avansat pentru predictia branch-urilor pe SPE-uri este compensata pe Cell/B.E. de prezenta unor mecanisme software de control a predictiei branch-urilor. Prin intermediul acestor mecanisme, programatorul poate elimina branch-uri (ex.: folosind spu_sel) sau poate indica hardware-ului calea cea mai probabila de executie a unui branch folosind __builtin_expect.

Linkuri utile

asc/cellcookbook/branch.txt · Last modified: 2014/04/22 20:18 by alexandru.olteanu
CC Attribution-Share Alike 4.0 International
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0