Software managed cache. SPE overlays. Branch prediction.

Introducere

In cadrul acestui laborator vor fi adresate trei limitari hardware ale SPE-urilor, care fie ingreuneaza programarea, fie limiteaza performanta aplicatiilor:
  • lipsa cache-ului
  • dimensiunea redusa a Local Store-ului (LS)
  • inexistenta unui mecanism pentru predictia branch-urilor.

Din punct de vedere hardware, Local Store-ul (LS) de pe SPE-uri nu poate indeplini functia de cache pentru memoria principala a sistemului. Lipsa cache-ului ingreuneaza programarea SPE-urilor, programatorul fiind obligat sa controleze explicit tranferurile DMA intre SPE si memoria principala. Atunci cand datele incap in LS, acest lucru nu constituie o problema, dar ce se intampla atunci cand LS este prea mic pentru datele cu care se opereaza? In aceasta situatie, o parte din datele din LS ar trebui salvate in memoria principala si inlocuite cu datele noi aduse din memoria principala. Pentru a facilita comunicatia dintre SPE-uri si memoria principala, programatorul poate utiliza un cache implementat software care va gestiona transferurile DMA si va alege cele mai bune strategii pentru inlocuirea datelor.

Overlay-urile software (sau overlay-urile SPE) reprezinta o solutie pentru situatia in care dimensiunea unui program pentru SPE depaseste cei 256 KB ai LS-ului. Pe scurt, codul este segmentat, iar apoi se formeaza grupuri alcatuite din segmente, fiecare grup avand asociat o anumita regiune din cadrul LS-ului. Numai unul dintre segmentele dintr-un grup este incarcat in regiunea corespunzatoare din LS, in orice moment de timp. Dintr-o perspectiva simplificata, overlay-urile software pot fi privite ca si cache-uri software pentru cod.

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/B.E. 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.

Software Managed Cache

Concepte de baza despre cache

Cache-ul este o zona de stocare temporara care permite un acces rapid la date frecvent/recent accesate. Componentele si caracteristicile unui cache sunt:
  • din motive de performanta, cache-ul este impartit in blocuri de dimensiune fixa denumite 'linii de cache'
  • fiecare linie de cache poate contine 'o copie a unor date din memoria principala'
  • fiecare unitate de date din memoria principala poate fi pusa doar intr-un 'set redus si bine determinat de linii de cache'
  • fiecare linie de cache are un 'tag' care identifica (in cadrul unui set de linii de cache) zona din memoria principala ale carei date sunt stocate pe acea linie.

Cand se fac accese la memoria principala, se cauta mai intai datele (sau codul) in cache. Din motive de performanta, cautarea se face doar in submultimea bine specificata unde ar putea fi stocata acea unitate de memorie, si anume in setul coresponzator de linii de cache. Daca vreunul din tag-urile din acea zona corespund adresei referite spunem ca avem un cache-hit; altfel avem un cache-miss.

Tipuri de cache-uri

Din punct de vedere al asociativitatii, cache-urile se impart in trei categorii:
  • 'mapate direct', pentru care oricare bloc de memorie poate fi pozitionat pe o singura linie de cache.
  • 'mapate complet asociativ', in cadrul carora oricare bloc de memorie poate fi pozitionat pe oricare linie de cache
  • 'mapate set asociativ', pentru care fiecare bloc de memorie poate fi pozitionat pe oricare linie dintr-un set de N linii de cache. Cache-urile set asociative reprezinta un compromis intre cache-urile mapate direct si cache-urile complet asociative.

Cache implementat software pentru un SPE

SPE-urile pot accesa direct, atat pentru cod cat si pentru date, doar memoria locala (LS), care are o capacitate de 256 KB. Toate accesele la memoria principala (sau alte zone de memorie mapate in spatiul de adresa curent, cum ar fi memoria video) se fac prin cereri DMA, fapt ce impune un efort suplimentar din partea programatorului, marind complexitatea programului. Implementarea unui cache in software poate:
  • simplifica modelul de programare
  • micsora timpul de portare al unui algoritm pe SPE
  • fi optimizata pentru diferite tipuri de acces (secvential, random, in ordine inversa, etc.)
  • fi integrata cu algoritmi sofisticati de inlocuire (dezvoltati pentru subsistemele de paginare pentru memorie virtuala).

Utilizare

In tabelul de mai jos gasiti functiile care pot fi folosite pentru a interactiona cu sistemul de cache implementat software de pe SPE-uri:
Instructiune Descriere
cache_rd(name, eaddr) Copiaza valoarea stocata la adresa eaddr in cache. Returneaza valoarea.
cache_wr(name, eaddr, val) Scrie in cache valoarea val. In memoria principala valoarea va fi stocata la adresa eaddr.
cache_touch(name, eaddr) Aduce in cache valoarea stocata la adresa eaddr. Functia este non-blocanta. Functia intoarce adresa din spatiul de adrese al LS, unde va fi stocata valoarea la incheierea tranferului.
cache_wait(name, lsa) Asteapta terminarea unui transfer non-blocant, care intoarce date la adresa lsa din spatiul de adrese al LS-ului.
cache_rw(name, eaddr) Copiaza in cache valoarea stocata la adresa eaddr, transmitand sistemului de cache faptul ca valoarea ar putea fi modificata. Functia este blocanta si va intoarce adresa din LS unde va fi stocata valoarea. Linia de cache este marcata dirty la scrierea datelor.
cache_lock(name, lsa) Blocheaza datele de la adresa lsa in cache.
cache_unlock(name, lsa) Deblocheaza date de la adresa lsa.
cache_flush(name) Forteaza scrierea tuturor datelor modificate (dirty) in cache inapoi in memoria principala.
cache_rd_x4(name, eaddr4) Citeste un vector care contine 4 valori unsigned int.
e_pr_stats(name) Afiseaza statistici despre cache.

Un program care utilizeaza sofware caching trebuie sa includa fisierul header “cache-api.h” si poate contine la inceputul sau definitii pentru:

  • 'CACHE_NAME' - un nume unic ce va identifica cache-ul.
  • 'CACHED_TYPE' - tipul elementelor stocate in cadrul cache-ului. Poate fi orice tip de date valid in limbajul C.
  • 'CACHELINE_LOG2SIZE' - log2(dimensiunea_unei_linii_de_cache).
  • 'CACHE_LOG2NWAY' - specifica asociativitatea cache-ului. Exista 2 valori posibile: 0 si 2 (2 fiind valoarea implicita).
  • 'CACHE_LOG2NSETS' - log2(numarul_de_seturi_din_cache). Valorile posibile sunt cuprinse intre 0 si 12. Valoarea implicita este 6 (2^6 = 64 seturi).
  • 'CACHE_TYPE' - tipul de acces la cache: read-only (0) sau read-write (1 - implicit)
  • 'CACHE_SET_TAGID(set)' - specifica tag-ID-ul unui anumit set. Valorile posibile sunt cuprinse intre 0 si 31. Implicit se defineste ca set % 32.
spu1.c
  1. /* definitii obligatorii */
  2. #define CACHE_NAME my_cache
  3. #define CACHED_TYPE my_type_t
  4.  
  5. /* definitii optionale; daca o definitie lipseste se foloseste o valoare implicita */
  6. #define CACHE_LOG2NWAY 2 /* 4-way */
  7. #define CACHE_LOG2NSETS 3 /* 8 set-uri */
  8. #define CACHE_TYPE 1 /* RW */
  9. #define CACHELINE_LOG2SIZE 9 /* 512b */
  10. #define CACHE_STATS /* activare stats */
  11.  
  12. /* in mod obligatoriu <cache-api.h> trebuie inclus dupa definirea variabilelor CACHE_* */
  13. /* "cache-api.h" foloseste aceste definitii pentru a crea tipuri de date noi care implementeaza cache-ul */
  14. #include <cache-api.h>

Pentru a defini mai multe cache-uri se redefinesc variabilele CACHE_* si se include din nou “cache-api.h”.

Software cache-ul poate fi operat in mod sincron sau asincron. In modul sincron, accesul la datele din cache se face doar prin adrese din spatiul de adrese al PPE-ului (adica din memoria principala sau eventual memoria video). Desi datele din memoria principala sunt aduse in LS-ul SPE-ului, folosind cache-ul implementat software, programatorul nu va folosi adresele locale pentru a accesa datele.

spu2.c
  1. #define CACHE_NAME MY_CACHE /* numele cache-ului */
  2. #define CACHED_TYPE int /* tipul elementului de baza al cache-ului */
  3.  
  4. /* atribute optionale */
  5. #define CACHE_TYPE CACHE_TYPE_RW /* acces de scriere si citire */
  6. #define CACHELINE_LOG2SIZE 11 /* 2^11 = lungimea unei linii de cache de 2048 bytes */
  7. #define CACHE_LOG2NWAY 2 /* 2^2 = 4-way cache */
  8. #define CACHE_LOG2NSETS 4 /* 2^4 = 16 seturi */
  9.  
  10. #include <cache-api.h>
  11.  
  12. int main(unsigned long long spu_id, unsigned long long parm){
  13. int a, b;
  14. unsigned eaddr_a, eaddr_b;
  15.  
  16. /* initializeaza adresele efective cu o adresa din memoria principala */
  17. eaddr_a = parm;
  18. eaddr_b = parm + sizeof(int);
  19.  
  20. /* citeste a si b din memoria principala (folosind adresa efectiva) */
  21. a = cache_rd(MY_CACHE, eaddr_a);
  22. b = cache_rd(MY_CACHE, eaddr_b);
  23.  
  24. /* modifica valorile locale */
  25. a++;
  26. b++;
  27.  
  28. /* scrie valorile modificate in cache. */
  29. /* nu se face imediat scriere in memoria principala (nu e un cache write-through) */
  30. /* se actualizeaza doar copiile din LS si se marcheaza ca "dirty" liniile corespunzatoare */
  31. cache_wr(MY_CACHE, eaddr_b, a);
  32. cache_wr(MY_CACHE, eaddr_a, b);
  33.  
  34.  
  35. /* scrie toate liniile modificate (dirty) inapoi in memoria principala */
  36. cache_flush(MY_CACHE);
  37. return 0;
  38. }

In cazul cache-ului controlat in mod asincron, programatorul foloseste adresele din LS pentru a accesa datele pentru citire sau scriere.

spu3.c
  1. unsigned int tag_base;
  2.  
  3. #define CACHE_NAME MY_CACHE /* numele cache-ului */
  4. #define CACHED_TYPE int /* type of elementului de baza al cache-ului */
  5.  
  6. /* atribute optionale */
  7. #define CACHE_TYPE CACHE_TYPE_RW /* acces de scriere si citire */
  8. #define CACHELINE_LOG2SIZE 7 /* 2^7 = linii de cache de 128 bytes */
  9. #define CACHE_LOG2NWAY 2 /* 2^2 = 4-way cache */
  10. #define CACHE_LOG2NSETS 4 /* 2^4 = 16 seturi */
  11. #define CACHE_SET_TAGID(set) (tag_base + (set & 7)) /* use 8 tag Ids */
  12. #include <cache-api.h>
  13.  
  14. int main(unsigned long long spu_id, unsigned long long parm){
  15. /* rezerva un grup de 8 tag-uri consecutive exclusiv pentru cache */
  16. if((tag_base = mfc_multi_tag_reserve(8)) == MFC_TAG_INVALID){
  17. printf("ERROR: can't reserve a tags\n"); return 1;
  18. }
  19.  
  20. int a, b;
  21. unsigned eaddr_a, eaddr_b;
  22.  
  23.  
  24. /* initializeaza adresele efective cu o adresa din memoria principala */
  25. eaddr_a = parm;
  26. eaddr_b = parm + sizeof(int);
  27.  
  28. int *a_ptr, *b_ptr;
  29.  
  30.  
  31. /* "atinge" asincron date de la adresa eaddr_b */
  32. /* cache-ul va initia o comanda de prefetch */
  33. b_ptr = cache_touch(MY_CACHE, eaddr_b);
  34.  
  35.  
  36. /* citeste in mod sincron datele de la eaddr_a */
  37. /* functia este blocanta si asteapta ca datele sa fie transferate din memoria principala in LS */
  38. a_ptr = cache_rw(MY_CACHE, eaddr_a);
  39.  
  40. /* blocheaza adresa a_ptr in cache*/
  41. /* in acest fel, se asigura ca valoarea nu este evacuata din cache */
  42. cache_lock(MY_CACHE, a_ptr);
  43.  
  44. *a_ptr = *a_ptr + 10;
  45.  
  46. /* functie blocanta care asteapta ca valoarea de la eaddr_b sa ajunga in cache */
  47. cache_wait(MY_CACHE, b_ptr);
  48.  
  49. /* blocheaza adresa b_ptr in cache */
  50. cache_lock(MY_CACHE, b_ptr);
  51.  
  52. /* valoarea de la eaddr_b este in cache si poate fi modificata */
  53. *b_ptr = *b_ptr + 20;
  54.  
  55. /* in acest moment modificarile sunt realizate la nivelul cache-ului */
  56. /* scrie liniile de cache dirty in memoria principala */
  57. cache_flush(MY_CACHE);
  58.  
  59. /* afiseaza statistici despre utilizarea cache-ului */
  60. cache_pr_stats(MY_CACHE);
  61. mfc_multi_tag_release(tag_base, 8);
  62. return (0);
  63. }

Overlay-uri SPE

Ce se intampla atunci cand un program nu incape in LS? Overlay-urile SPE adreseaza exact aceasta problema. In cazul in care codul unui program ajunge la dimensiuni apropiate de dimensiunea LS-ului, sau cand programul are nevoie de buffere de date de dimensiuni mari, este utila spargerea programului in mai multe segmente si pastrarea in LS doar a acelor segmente ce sunt utilizate in momentul curent, sau ce vor fi utilizate in viitorul apropiat.

Definirea structurii unui program

Un segment este definit ca cea mai mica unitate care poate fi incarcata pentru executie. Un segment contine una sau mai multe sectiuni de program (de ex. zone de cod ale unor functii sau zone de date). Folosind software overlay, imaginea unui program este impartita in mai multe segmente:

  • segmentul radacina, un segment care nu poate fi evacuat din LS
  • mai multe segmente suprapuse care pot fi incarcate si descarcate dinamic. Un segment este intotdeauna incarcat in aceeasi regiune, iar o regiune poate contine la un moment dat un singur segment. Un astfel de segment poate fi pastrat in memoria principala cat timp nu este nevoie de el si poate fi adus in LS sau eliminat din LS, in masura in care este sau nu este nevoie de el.

Pentru date pot fi utilizate doua strategii:

  1. datele globale sunt stocate in regiunea radacina
  2. datele globale sunt tinute aproape de codul care le acceseaza. Daca anumite date sunt folosite de mai multe segmente, atunci sunt stocate in regiunea radacina.

Este important a se mentiona ca atunci cand un segment este eliminat din LS, el nu este scris inapoi in memoria principala. Din aceasta cauza, se pot mapa intr-un segment doar datele nepersistente, care din punct de vedere logic intra in existenta numai atunci cand se executa cod din acel segment si dispar cand segmentul este inlocuit cu un altul (de ex. buffere temporare utilizate in functii din acel segment).

Functionare

La rulare, cand se face o referinta dintr-un segment intr-altul, sistemul determina daca codul respectiv se gaseste sau nu in LS. Daca codul ce urmeaza a fi executat este in LS, se trece la executia acelui cod. Daca nu, sistemul suprascrie regiunea corespunzatoare segmentului cu codul acestuia din memorie iar, dupa scriere, controlul este transferat codului incarcat.

Pentru activarea overlay-ului software linker-ul genereaza: cod specific, care va fi executat atunci cand se fac apeluri intre module; niste tabele pentru managementul sistemului de overlay. Toate acestea sunt stocate in segmentul radacina.

Linkerul va mapa toate segmentele corespunzatoare unei aceleiasi regiuni peste aceeasi adresa din LS si va inlocui apelurile intre segmente cu apeluri catre codul sistemului de overlay, care la randul sau va intermedia apelul catre segmentul destinatie.

La executie, codul sistemului de overlay determina din tabelele proprii daca segmentul destinatie este prezent in LS. Daca da, se sare direct la acel cod. Daca nu, overlay-ul initiaza un transfer DMA pentru a aduce datele din memoria principala in LS, marcheaza in tabelele proprii faptul ca noul segment se afla acum in LS si asteapta incheierea tranferului DMA, dupa care efectueaza saltul in noul segment. Daca vechiul segment continea si sectiuni de date, orice modificari efectuate asupra acestora vor fi pierdute.

Un exemplu de impartire a codului unui program in segmente

Fie programul urmator:

Cu SA, SB, SC, SD, SE, SF si SG au fost notate cele sapte functii din care este format programul (consideram ca programul nu foloseste date globale). Dimensiunea fiecarei functii din cadrul programului se considera a fi cea din tabelul urmator:

SA SB SC SD SE SF SG
30 KB 20 KB 60 KB 40 KB 30 KB 60 KB 80 KB

Fara overlay acest program nu poate fi rulat in mod normal, intreaga sa imagine ocupand 320 KB. O solutie de impartire in segmente si regiuni este data in figura urmatoare:

Desi exista alte configuratii care ocupa spatiu mai putin (lasand mai mult spatiu din LS pentru datele programului: stack, heap, global data), trebuie sa tinem cont si de impactul asupra performantei. In programul luat ca exemplu aici, nu e niciodata nevoie in acelasi timp si de SG si de oricare din SC, SD, SE, SF. Mai mult, daca SG este o cale rar urmarita, aceasta poate fi pastrata in memoria principala si adusa in LS doar in cazurile speciale, cand este nevoie de ea.

Script-ul pentru link-are

Implementarea software overlay se face cu ajutorul unor scripturi de linker. In Makefile-ul corespunzator SPU-ului trebuie inclusa urmatoarea definitie: LDFLAGS = -Wl,-T,linker.script

Fisierul linker.script va contine urmatorul text:

linker.script
  1. SECTIONS
  2. {
  3. OVERLAY :
  4. {
  5. .segment1 {sc.o(.text)}
  6. .segment4 {sg.o(.text) }
  7. }
  8. OVERLAY :
  9. {
  10. .segment2 {sd.o(.text) se.o(.text)}
  11. .segment3 {sf.o(.text)}
  12. }
  13. }
  14. INSERT AFTER .text;

Fisierele obiect sc.o si sg.o sunt grupate in segmentele 1 si 4 care sunt mapate peste aceeasi regiune 1. Codul din fisierele sd.o si se.o este grupat in acelasi segment, iar acest segmentul este mapat in cea de-a doua regiune impreuna cu segmentul alcatuit din fisierul sf.o. Implicit sa.o si sb.o vor fi mapate in sectiunea .text. Sectiunea .text contine segmentul radacina care este intotdeauna prezent in LS.

Predictia branch-urilor

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-small-functions, -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:

  1. /* bucla initiala */
  2. for(i = 0; i < 3; i++)
  3. x[i] = y[i];
  1. /* bucla initiala se poate inlocui cu: */
  2. x[0] = y[0];
  3. x[1] = y[1];
  4. 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:

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

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.
  1. /* if-else-ul original */
  2. if (a > b)
  3. c += 1;
  4. else
  5. d = a + b;
  1. /* cod optimizat care elimina branch-ul folosind spu_sel */
  2. select = spu_cmpgt(a, b);
  3. c_plus_1 = spu_add(c, 1);
  4. a_plus_b = spu_add(a, b);
  5. c = spu_sel(c, c_plus_1, select);
  6. 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:

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

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

  1. /* programatorul indica x == 0 */
  2. if(__builtin_expect(x, 0)) {
  3. foo();
  4. }

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:

  1. cond2 = ... /* prezice cond2 */
  2. ...
  3. cond1 = ...
  4. if(__builtin_expect(cond1, cond2)) { /* programatorul indica cond1 == cond2 */
  5. foo();
  6. }

Activitate practica

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 la altele (un nod din drum contine ca informatie urmatorul nod la care trebuie sa se sara). Stim ca am ajuns la comoara cand trebuie sa sarim la nodul (0, 0). Mai jos aveti un program PPU care scrie drumul în labirint si trimite SPU-ului adresa catre începutul matricii. SPU-ul va trebui sa gaseasca coordonatele comorii si sa le scrie în prima celula a labirintului (0, 0). Programul de mai jos verifica daca in celula (0, 0) se gasesc coordonatele comorii.

ppu.c
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <errno.h>
  4. #include <libspe2.h>
  5. #include <pthread.h>
  6.  
  7. extern spe_program_handle_t find;
  8. #define N 400
  9. #define M 200
  10. #define NR_JUMPS 10
  11. struct f {
  12. int x, y;
  13. };
  14.  
  15. typedef struct f coord_t;
  16. coord_t v[N][M] __attribute__ ((aligned(16)));
  17. coord_t destination; // coordonatele comorii
  18.  
  19. // construieste drumul in labirint
  20. static void init_matrix()
  21. {
  22. int k;
  23. coord_t c, newc;
  24. c.x = c.y = 0;
  25.  
  26. for(k = 0; k < NR_JUMPS; k ++) {
  27. newc.x = rand() % N;
  28. newc.y = rand() % M;
  29. if ( (v[c.x][c.y].x == 0) && (v[c.x][c.y].y == 0) ) {
  30. v[c.x][c.y] = newc;
  31. printf("newc:x=%d, y=%d\n", newc.x, newc.y);
  32. c = newc;
  33. }
  34. }
  35. destination = newc;
  36. }
  37.  
  38.  
  39. int main()
  40. {
  41. spe_context_ptr_t ctx;
  42. unsigned int entry = SPE_DEFAULT_ENTRY;
  43. init_matrix();
  44.  
  45. if ((ctx = spe_context_create(0, NULL)) == NULL) {
  46. perror ("Failed creating context");
  47. exit (1);
  48. }
  49.  
  50. if (spe_program_load(ctx, &find)) {
  51. perror ("Failed loading program");
  52. exit (1);
  53. }
  54.  
  55. printf("SPU:\n");
  56. if (spe_context_run(ctx, &entry, 0, &v, M, NULL) < 0) {
  57. perror ("Failed running context");
  58. exit (1);
  59. }
  60.  
  61. if (spe_context_destroy (ctx) != 0) {
  62. perror("Failed destroying context");
  63. exit (1);
  64. }
  65.  
  66. printf("PPU:\n");
  67. printf("%d %d \n", v[0][0].x, v[0][0].y);
  68. printf("correct: %d\n", (destination.x == v[0][0].x) && (destination.y == v[0][0].y));
  69.  
  70. return 0;
  71. }

Concluzii

Pentru a facilita programarea aplicatiilor pentru Cell/B.E. pot fi folosite tehnici precum software caching sau overlay-uri SPE. Software caching-ul este recomandat mai ales in acele situatii in care datele necesare unui program sunt prea mari pentru LS. Overlay-urile SPE raspund unei probleme asemanatoare, si anume cand codul este prea mare pentru a incapea in memoria SPE. In cadrul unui script pentru linker se definesc segmente alcatuite din fisiere obiect si grupate in regiuni disjuncte mapate peste LS.

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/lab10/index.txt · Last modified: 2013/02/07 12:41 (external edit)
CC Attribution-Share Alike 3.0 Unported
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