Mecanisme avansate de folosire a operatiilor SIMD si a transferurilor DMA

In acest laborator este abordata o tematica mai avansata de programare Cell. Vom continua subiectul DMA inceput in laboratorul trecut, analizand de data aceasta mecanismul de double buffering folosit pentru optimizarea procesarii. De asemenea, vom revizui programarea Cell din perspectiva paradigmei SIMD si vom vedea importanta alinierii datelor si a instructiunilor native (intrinsics) pentru procesare de vectori.


SIMD

O modalitate accesibila de imbunatatire a performantelor unui procesor este de a adauga unitati de executie designului initial. Aceste unitati vor creste performanta, pentru un program cu setul de instrucituni limitat al SISD (Single Instruction, Single Data) doar in masura in care logica de scheduling a procesorului determina ca nu exista dependente de date intre doua instructiuni apropiate din flowul de instructiuni si le scheduleaza pentru executie pe unitati diferite, simultan.
Pentru o mai buna utilizare a acestor resurse de procesare, exista alternativa SIMD (Single Instruction, Multiple Data), care permite specificarea inca din setul de instructiuni ca o anumita operatie se va executa pe mai multe perechi (date de intrare , date de iesire).

SIMD se poate folosi si pentru procesoare vectoriale in mod nativ. De exemplu, pentru un vector de 4 elemente si presupunand 4 unitati de executie, in loc sa fie necesare patru instructiuni inc(a[i]) pentru incrementarea elementelor vectorului, se va putea scrie simd_inc(a).


Modele de utilizare a capacitatilor SIMD

Modalitatea de exploatare a acestor instructiuni SIMD poate fi:
  1. nativa
    • Programatorul foloseste instructiuni wrapper peste instructiunile native ale procesorului din limbajul folosit(C/C++) sau chiar scrie cod ASM corespunzator. (cazul Cell in laboratorul de azi)
  2. traditionala


SIMD folosind Cell

Arhitectura Cell a fost gandita pentru SIMD. Despre implicatiile acestei alegeri puteti citi pe ArsTehnica .
Pentru a utiliza SIMD, programatorul trebuie sa fie familiar cu modelul SIMD oferit prin extensiile de C ale Cell. Capabilitati SIMD sunt disponibile atat pentru SPE, cat si pentru PPE, cu mici diferente.


Alinierea datelor

SPE si PPE folosesc vectori de 128 de biti pentru instructiuni SIMD. Pentru a putea utiliza instructiunile SIMD (Single Instruction Multiple Data), arhitectura Cell are nevoie de o anumita pozitionare a datelor in memorie, si anume, acestea trebuie sa fie aliniate in memorie la o limita de 16 octeti (quadword) sau multiplu de 16 octeti.
alocare statica

Pentru alinierea unui tip de date in memorie exista atributul aligned care se foloseste astfel:

float input[MAX_LEN] __attribute__ ((aligned(128)));

Alternativ, se poate scrie urmatorul macro:

#define MY_ALIGN(_my_var_def_, _my_al_)  _my_var_def_  \
 __attribute__((__aligned__(_my_al_)))

si utilizarea arata in felul urmator:

MY_ALIGN(float input[MAX_LEN],128);

Ca alinierea sa functioneze variabila trebuie sa fie globala sau locala functiei, dar statica, deoarece alocarea pe stiva se face la runtime.

alocare dinamica

Pentru date alocate dinamic, folosim functiile malloc_align si free_align din libmisc.h (+ libraria libmisc.a - trebuie inclus flagul -lmisc) pentru alocare aliniata, astfel:

input = (float*)malloc_align(N*sizeof(float),128);


Tipul vector

Implementarea SIMD pt Cell e bazeaza pe registrii de tip vector pentru a putea exploata paralelismul de date. Registrii de tip vector permit efectuarea usoara a instructiunilor SIMD. Pentru a reprezenta acest concept in C, a fost adaugat cuvantul cheie vector , care preceda o declaratie de tip si semnifica extinderea acelui tip pana ocupa un intreg registru vector SIMD:
vector unsigned int myvec = (vector unsigned int){1, 2, 3, 4};

Exemplul de mai sus declara un vector de 4 intregi, ale carui elemente vor fi incarcate, procesate si stocate impreuna, iar variabila myvec se refera la toate.


Intrinsics

Extensiile C pentru Cell ofera instructiuni wrapper peste instructiunile ASM-SIMD corespunzatoare SPU, de exemplu, pentru scadere SIMD:
  1. typedef vector unsigned int vi;
  2. ...
  3. cmp = spu_sub( *((vi*)one), *((vi*)two));

Instructiunea de mai sus, realizeaza scaderea fiecarui element din vectorul two din elementul corespunzator din vectorul one.

Observatie: specificarea signed/unsigned este obligatorie.

Apeluri care difera doar prin tipul operanzilor sunt reprezentate prin acelasi apel C/C++, care selecteaza instructiunea corespunzatoare ASM dupa tipul operanzilor. Pentru adunare, spu_add, cu parametru vector de tip unisnged int, va genera instructiunea 'a' (adunare pe 32 de biti), dar daca are parametru de tip vector float, va genera instructiunea 'fa' (float add).

Aceste operatii primesc parametru de tip vector si se numesc intrinsics. Sunt disponibile operatii aritmetice (scadere, adunare, inmultire, comparare) si operatii pe biti (shiftare, negare, etc) si altele mai avansate.

  1. #include <spu_intrinsics.h>
  2.  
  3. vector float vec1={8.0,8.0,8.0,8.0}, vec2={2.0,4.0,8.0,16.0};
  4.  
  5. vec1 = spu_sub( (vector float)spu_splats((float)3.5), vec1);
  6. vec1 = spu_mul( vec1, vec2);

O alternativa facila a intrinsics sunt operatorii suportati de compilator pentru operatii vectoriale (care pot fi folositi direct pe vectori in mod analog celor scalari):

  • Subscriptare vector: [ ]
  • Operatori unari: ++, –, +, -, ~
  • Operatori binari: +, -, *, /, unary minus, %, &, |, ^, «, »
  • Operatori relationali: ==, !=, <, >, ⇐, >=

De exemplu:

  1. #include <spu_intrinsics.h>
  2.  
  3. vector float vec1={8.0,8.0,8.0,8.0}, vec2={2.0,4.0,8.0,16.0};
  4.  
  5. vec1 = vec1 + vec2;
  6. vec1 = -vec1;

Mai multe despre intrinsics si exemple de folosire ale tuturor operatiile, gasiti in acest tutorial, sau in PPU & SPU C/C++ Language Extension Specification.

Observatie: SPE si PPE nu au aceleasi capabilitati privind SIMD; aceste diferente sunt documentate aici.


DMA - Transferarea de buffere mari din memoria principala in SPE

In laboratorul trecut am vazut modalitati de baza de folosire a DMA pentru transfer de date intre memoria locala a SPU si spatiul principal de stocare. Din cauza ca memoria locala este limitata, multe aplicatii vor avea nevoie sa transfere, pe rand, mai multe secvente de date catre SPE, spre procesare. Pentru acest scenariu se pot folosi mai multe metode, descrise in continuare.


Liste DMA

O lista DMA este o secventa de elemente de transferat, ce specifica o serie de transferuri DMA intre o singura zona din memoria locala si mai multe zone (posibil discontinue) din spatiul principal de stocare. Se pot construi astfel functii de tip scatter-gather intre memoria locala si spatiul principal de stocare. Toate transferurile initiate pe baza aceleiasi liste au acelasi tag id si folosesc comenzi de acelasi tip (getl, putl etc.). Lista DMA se stocheaza in memoria locala a aceluiasi SPE.

Crearea unei liste DMA

Fiecare element dintr-o lista DMA contine trei parametrii:

  • 'notify:' flag care, daca este setat, suspenda secventa de transferuri dupa transferul acestui element
  • 'size:' marimea transferului in octeti
  • 'eal:' adresa efectiva in spatiul principal de stocare (lower 32-bits)
  1. typedef struct mfc_list_element {
  2. uint64_t notify : 1; // optional stall-and-notify flag
  3. uint64_t reserved : 16; // the name speaks for itself
  4. uint64_t size : 15; // transfer size in bytes
  5. uint64_t eal : 32; // lower 32-bits of an EA in main storage
  6. } mfc_list_element_t;

Initierea transferurilor din lista DMA

Dupa ce lista este stocata in memoria locala a SPE, se apeleaza comenzi de transfer specifice (cele cu sufix “l”, dupa cum va reamintiti din laboratorul trecut):

  • mfc_getl implementeaza comanda getl
  • mfc_putl implementeaza comanda putl.

Aceste functii sunt non-blocante, iar SPU poate continua executarea programului, economisind timp pretios. Insa, desigur, daca ele nu au loc in MFC SPU command queue, vor avea caracter blocant pana la obtinerea unui slot.

Comenzile de transfer de tip lista folosesc parametri similari comenzilor de transfer obisnuite, cu mici mentiuni (Redbook):

  • parametrul adresa efectiva (eal) ar trebui sa specifice adresa listei in memoria locala (adresele efective individuale sunt precizate in structura listei)
  • parametrul marime a transferului (size) ar trebui sa specifice spatiul in octeti ocupa de lista DMA in memoria locala (marimile individuale ale fiecarui transfer sunt precizate in structura listei).


Ascunderea duratei transferurilor - DMA buffering

Workflow-ul normal pentru SPE este sa primeasca date de la PPE, sa la proceseze si sa trimita rezultatele inapoi in spatiul principal de stocare.

Single buffering

Single buffering este, in principiu, solutia folosita de noi pana acum in exemple precum cel cu DMA din laboratorul precedent (Prog Tutorial). Sa ne orientam atentia catre ceea ce se petrece la SPU:

SPU aloca un buffer local, aliniat la 128 de octeti, pentru stocarea datelor primite si a datelor de raspuns.
Rezerva un tag
Primeste primul bloc de date (de control), in care vede cate blocuri are de procesat
Pentru fiecare dintre blocurile de procesat:
	Transfera blocul in memoria locala (get) si asteapta ca transferul sa se finalizeze
	Proceseaza datele
	Transfera rezultatele in memoria sistemului (put) si asteapta ca transferul sa se finalizeze.\\

Daca aveti instalat SDK, puteti gasi un exemplu complet in:
/opt/cell/sdk/src/tutorial/dma/single_buffer/

Double buffering

Folosind solutia single buffering, se consuma foarte mult timp asteptand incheierea transferurilor DMA. O buna optimizare este alocarea de doua buffere de lucru in loc de unul si intercalarea alternativa a calculelor pe un buffer cu transferul in celalalt buffer (Prog Tutorial). Sa ne orientam atentia catre ceea ce se petrece la SPU:

Double buffering

Daca punem aceasta schema in pseudocod obtinem urmatoarele (transferul de primire GET este explicitat in doua operatii: cer si astept):

Aloc doua buffere de intrare si doua buffere de iesire, doua taguri etc.
Cer bloc de control (parameter context) de la PPU
Astept bloc de control de la PPU
Cer primul bloc (buffer) de date de la PPU
While nu s-au procesat toate datele:
	Cer bufferul urmator de date de la PPU 
		// Atentie la bariera in acest punct - desi folosim doua buffere, fara ea
		//  exista posibilitatea sa se faca suficiente GET si insuficiente procesari
		//  incat sa se suprascrie unul din bufferele de intrare
	Astept bufferul precedent de date de la PPU 
		// la fiecare iteratie se pun in alternativ in cele doua buffere de intrare
	Procesez bufferul precedent
		// rezultatul se pune in bufferul de iesire corespunzator celui de intrare
	Trimit bufferul precedent la PPU
Astept ultimul buffer de date de la PPU
Procesez ultimul buffer
Trimit ultimul buffer la PPU

Vom folosi urmatoarele headere:

  1. #include <spu_intrinsics.h>
  2. #include <spu_mfcio.h>

Pentru transmiterea parametrilor (blocul de control) folosim structura:

  1. typedef struct {
  2. uint32_t *in_data;
  3. uint32_t *out_data;
  4. uint32_t *status;
  5. int size;
  6. } parm_context;

De asemenea, vom folosi urmatoarele date:

  1. // ctx: contextul venit de la PPU, contine o serie de parametrii: adresa la in_data si out_data in main storage si status
  2. volatile parm_context ctx __attribute__ ((aligned(16)));
  3. // ls_in_data: doua buffere de intrare (avansat: double buffering se poate face si 'in-place'
  4. volatile uint32_t ls_in_data[2][ELEM_PER_BLOCK] __attribute__ ((aligned(128)));
  5. // ls_out_data: doua buffere de iesire
  6. volatile uint32_t ls_out_data[2][ELEM_PER_BLOCK] __attribute__ ((aligned(128)));
  7. // status
  8. volatile uint32_t status __attribute__ ((aligned(128)));
  9. // tag_id: doua tag groups
  10. uint32_t tag_id[2];

Expandam pseudocodul de mai sus si obtinem un schelet de cod (functia main):

  1. tag_id[0] = mfc_tag_reserve();
  2. tag_id[1] = mfc_tag_reserve();
  3. // ... alte declaratii de variabile
  4.  
  5. // Cer blocul de control de la PPU
  6. mfc_get((void*)(&ctx), (uint32_t)argv, sizeof(parm_context), tag_id[0], 0, 0);
  7. // Astept blocul de control de la PPU
  8. waitag(tag_id[0]);
  9.  
  10. // Initializare
  11. in_data = ctx.in_data;
  12. out_data = ctx.out_data;
  13. left = ctx.size;
  14. cnt = (left<ELEM_PER_BLOCK) ? left : ELEM_PER_BLOCK;
  15.  
  16. // Cer primul bloc (buffer) de date de la PPU
  17. buf = 0;
  18. mfc_getb((void *)(ls_in_data), (uint32_t)(in_data), cnt*sizeof(uint32_t), tag_id[0], 0, 0);
  19.  
  20. while (cnt < left) { // cat timp nu s-a terminat de procesat
  21.  
  22. left -= SPU_Mbox_Statnt;
  23. nxt_in_data = in_data + cnt;
  24. nxt_out_data = out_data + cnt;
  25. nxt_cnt = (left<ELEM_PER_BLOCK) ? left : ELEM_PER_BLOCK;
  26.  
  27. // Cer bufferul urmator de date de la PPU
  28. // Atentie la bariera!
  29. nxt_buf = buf^1;
  30. mfc_getb((void*)(&ls_in_data[nxt_buf][0]), (uint32_t)(nxt_in_data), nxt_cnt*sizeof(uint32_t), tag_id[nxt_buf], 0, 0);
  31.  
  32. // Astept bufferul precedent de date de la PPU
  33. waitag(tag_id[buf]);
  34.  
  35. // Procesez bufferul precedent
  36. for (i=0; i<ELEM_PER_BLOCK; i++){
  37. // ... whatever
  38. }
  39.  
  40. // Trimit bufferul precedent la PPU
  41. mfc_put((void*)(&ls_out_data[buf][0]), (uint32_t)(out_data),
  42. cnt*sizeof(uint32_t),tag_id[buf],0,0);
  43.  
  44. // Pregatim urmatoarea iteratie
  45. in_data = nxt_in_data;
  46. out_data = nxt_out_data;
  47. buf = nxt_buf;
  48. cnt = nxt_cnt;
  49. }
  50.  
  51. // Astept ultimul buffer de date de la PPU
  52. waitag(tag_id[buf]);
  53.  
  54. // Procesez ultimul buffer
  55. for (i=0; i<ELEM_PER_BLOCK; i++){
  56. // ... whatever
  57. }
  58.  
  59. // Trimit ultimul buffer la PPU
  60. // Punem bariera pentru a ne asigura ca s-a trimis si ultimul rezultat inainte de a confirma statusul
  61. mfc_putb((void*)(&ls_out_data[buf][0]), (uint32_t)(out_data), cnt*sizeof(uint32_t), tag_id[buf],0,0);
  62. waitag(tag_id[buf]);
  63.  
  64. // Actualizam status pentru PPU
  65. status = STATUS_DONE;
  66. mfc_put((void*)&status, (uint32_t)(ctx.status), sizeof(uint32_t), tag_id[buf],0,0);
  67. waitag(tag_id[buf]);
  68.  
  69. // Clean-up
  70. mfc_tag_release(tag_id[0]);
  71. mfc_tag_release(tag_id[1]);

La PPU vom folosi urmatoarele headere:

  1. #include <libspe2.h>
  2. #include <cbe_mfc.h>
  3. #include <pthread.h>

Codul PPU este mult mai simplu (schelet de cod pentru functia main):

  1. // Initializari (printre altele):
  2. status = STATUS_NO_DONE;
  3. ctx.in_data = in_data;
  4. ctx.out_data = out_data;
  5. ctx.size = NUM_OF_ELEM;
  6. ctx.status = &status;
  7. data.argp = &ctx;
  8.  
  9. // Creeaza context
  10. // Incarca program
  11. // Ruleaza threaduri SPE
  12. // Asteapta ca SPE sa finalizeze
  13.  
  14. // Asteapta sa se finalizeze scrierea datelor
  15. while (status != STATUS_DONE);
  16.  
  17. // Verificari si clean-up

Puteti descarca arhiva cu programul complet aici: spe_double_buffer.zip.

De asemenea, daca aveti instalat SDK, puteti gasi un exemplu complet in:
/opt/cell/sdk/src/tutorial/dma/double_buffer_in_out

Double buffering - last notes

Pentru folosirea double buffering eficient, luati in considerare urmatoarele aspecte:

  • folositi doua (sau mai multe) buffere in memoria locala
  • folositi tag id-uri unice, unul pentru fiecare buffer
  • folositi comenzi in forma cu fence pentru a ordona transferuri intr-un tag group
  • folositi comanda barrier pentru a ordona transferuri pentru intregul MFC

Scopul double buffering este de a maximiza timpul petrecut pentru calcule si a minimiza timpul petrecut asteptand finalizarea transferurilor. Fie Tt timpul petrecut cu transferul unui buffer si Tc timpul petrecut cu realizarea calculelor pentru acelasi buffer. In general, cu cat raportul Tt/Tc este mai mare, cu atat va avea mai mult de beneficiat aplicatia voastra de pe urma folosirii unei scheme double buffering.

Resurse: http://www.ibm.com/developerworks/library/pa-linuxps3-6/


Activitate practica - Folosirea eficienta a caracteristicilor arhitecturii Cell

Pana in laboratorul curent am descoperit cateva caracteristici ale arhitecturii Cell care permit, daca sunt folosite corect, obtinerea unei performante ridicate in anumite aplciatii. Acestea sunt:

  • multiprocesare folsind SPE
  • multiprocesare folosind SIMD
  • comunicare folosind mailboxuri
  • ascunderea duratei transferurilor folosind DMA.

Aplicatia realizata astazi va va ajuta sa invatati folositi corespunzator aceste caracteristici.

In programarea aplicatiilor 3D, multe din operatiile de baza folosesc vectori si matrice. Adunarea, produsul (cross-product), etc, sunt efecutate foarte des si de aceea sunt o tinta buna pentru optimiare. Scopul exercitiilor de astazi este sa aplicam cunostintele acumulate pentru optimizarea efectuarii acestor operatii pe Cell.

Etapele ce le vom urma sunt:

  1. Scrierea unui program ce va rula pe PPU pentru efectuarea a N(>8) adunari a doi vector de NR elemente de tip float.
    • din lipsa de timp, aceasta etapa se poate omite
  2. Modificarea acestuia pentru a folosi SPE.
    • Adunarile se aloca pentru efectuare pe cate un SPU, acelasi numar de vectori alocati fiecarui PPU (avand acelasi numar de elemente, vectorii se vor aduna in acelasi timp)
    • Pentru a face accesibili vectorii pe SPU, trebuie ca:
      • SPU sa cunoasca adresa acestora in memoria principala. Acest lucru se poate realiza prin una din urmatoarele alternative:
        • trimiterea de param. la inceperea rularii pe spu ( analizati documentatia pentru spe_context_run) . Se poate trimite un pointer la o zona de memorie unde se afla pointeri spre vectori.
        • folosind mailboxes, ca in laboratorul trecut, de la al carui cod puteti porni.
  3. Folosirea instructiunilor SIMD pentru a imbunatati performanta propriu-zisa a operatiilor matematice propriu-zise, efectuate pe SPE.
    • nu omiteti alinierea corecta a memoriei folosite pentru vectori
    • nu uitati ca NR poate sa nu fie divizibil cu 4
    • pentru bonus, implementati SIMD si pe PPE, ca acesta sa nu stea degeaba in timp ce SPE lucreaza.


Linkuri utile

asc/lab9/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