Prezentare WHC NCIT

Optimizari

Asa cum am relatat in postarea precedenta, algoritmul paralel implementat se dovedeste a fi foarte ineficient (cel putin la prima vedere).

Pentru a-l imbunatati, primii pasi vor fi sa:

• - elimin recrearea contextului de fiecare data
• - elimin recompilarea programului de fiecare data (+ 0.1-0.3 la fiecare apelare)
• - incearc sa inlantuiesc mai multe seturi de kernel-uri in acelasi context (folosind event)
• - evit daca pot interschimbarea haotica de date (e rau mai ales pe GPU)
• - bitonic sort e un mod de a sorta datele foarte potrivit pentru arhitecturi paralele (inclusiv GPU-uri), sugestie in loc de bubble sort in kernel-uri
• - incearc sa elimin/reduc acele loop-uri din kernel cumva (cu cat sunt mai multe branch-uri conditionale cu atat e mai rau)
• - reduc alocarile/eliberarile de memorie, folosind eventual o memorie tampon prealocata.

Cod: se poate gasi aici: http://dl.dropbox.com/u/24465060/K_elem_v3.zip

Observatii: timpul de executie s-a imbunatatit considerabil doar urmand cateva dintre sugestii, desi sortarile in kernels au ramas bubble sort (= multe bucle, multe ramificatii, interschimbari haotice).

------------------------- Teste -----------------------------------------------

n = 2400

k = 2000

[0] Intel(R) Core(TM)2 Duo CPU = 0.10s

[1] GeForce 8600 GT (4 cu) = 0.50s

[2] GeForce 210 (2 cu) = 0.91s

[3] Cedar Radeon 5470 (2 cu) = 0.57s

[4] Intel(R) Core(TM) i3 CPU = 0.14s

[5] ATI RV730 (8 cu) = 0.69s

==================

n = 2000

k = 1282

[0] Intel(R) Core(TM)2 Duo CPU = 0.09s

[1] GeForce 8600 GT (4 cu) = 0.34s

[2] GeForce 210 (2 cu) = 0.65s

[3] Cedar Radeon 5470 (2 cu) = 0.54s

[4] Intel(R) Core(TM) i3 CPU = 0.13s

[5] ATI RV730 (8 cu) = 0.69s

==================

n = 1000

k = 333

[0] Intel(R) Core(TM)2 Duo CPU = 0.09s

[1] GeForce 8600 GT (4 cu) = 0.14s

[2] GeForce 210 (2 cu) = 0.32s

[3] Cedar Radeon 5470 (2 cu) = 0.56s

[4] Intel(R) Core(TM) i3 CPU = 0.13s

[5] ATI RV730 (8 cu) = 0.71s

==================

n = 443

k = 89

[0] Intel(R) Core(TM)2 Duo CPU = 0.10s

[1] GeForce 8600 GT (4 cu) = 0.14s

[2] GeForce 210 (2 cu) = 0.17s

[3] Cedar Radeon 5470 (2 cu) = 0.55s

[4] Intel(R) Core(TM) i3 CPU = 0.12s

[5] ATI RV730 (8 cu) = 0.67s

Concluzii:

•

• nu este un algoritm care sa demonstreze eficienta calculului pe GPU comparativ cu calculul pe CPU – ceea ce intareste ideea ca DOAR anumite probleme pot fi executate mai rapid pe placa grafica si anume cele pe seturi mari de date cu aplicarea unor operatii repetitive (specific SIMD)
• principale dezavantaje GPU: latenta mare de transfer a datelor din RAM catre VRAM (memoria placii grafice) si invers; aceasta poate fi acoperita prin executia rapida si repetata a unor task-uri
• in cazul de fata, datorita memoriei locale limitate de pe GPU si a structurii algoritmului, valoarea lui n nu poate trece de un prag (aici, 2500) – posibil ca programul sa dea rezultate foarte bune in favoarea GPU pentru valori mult mai mari ale lui n
• algoritmul a trebuit regandit de mai multe ori pentru a da rezultate cat mai bune atat pe CPU cat si pe GPU – programarea in OpenCL cere totusi cunoasterea arhitecturii platformelor

Days 5+

Implementarea unui algoritm in OpenCL si analiza performantei (rapiditate, scalabilitate, etc... )

Am ales sa implementez "aflarea celui de-al K-lea element dintr-un vector" - variantele banala, recursiva & paralela .

Banala -- sortarea vectorului si afisarea celui de-al K-lea element

Recursiva -- aflarea elementului, fara a sorta vectorul

Paralela -- se bazeaza pe varianta recursiva, cu paralelizarea unuia dintre pasi

Observatii:
- varianta banala tinde sa mearga mai bine decat cea recursiva pentru valori mari ale lui n (overhead la crearea stivelor pt varianta recursiva)
- aparent, varianta paralela merge de... numai paralela nu este . Se pare ca overhead-ul de creare a contextelor este imens... [in curand] optimizari.

Days 3, 4

In Day 3, s-a discutat structura generala a unui program openCL si s-au prezentat cateva exemple.

Pe scurt, o sursa se compune dintr-un program C/C++, un program de kernel plus alte surse auxiliare, biblioteci, etc.

Un program in OpenCL are 3 parti:

* initializari - aici se specifica platforma, device-ul, se creeaza contextul, queues (cozile), (+ se fac verificari)

* executia kernel-urilor

* finalizare

De initializari si finalizare se ocupa codul in C/C++, iar de treaba propriu-zisa se ocupa fisierele de kernel. Compilarea este doar a programelor C/C++, iar fisierul binar rezultat va fi cel care executa fisierul de kernel (daca doar acesta se modifica, nu trebuie recompilat totul).

/////////////////////////////////////////////////////

Un exemplu "simplu" cu filtre de imagini si unul "complex" cu histogram equalisation puteti gasi aici: http://dl.dropbox.com/u/24465060/image_processing_geo.zip

OpenCL Programming

Cateva idei din cartea "OpenCL Programming" de la FixStars:

* arhitecturi hardware care folosesc mai multe procesoare pentru implinirea unei singure sarcini:

- Grid computing - o combinatie de resurse din mai multe domenii administrative care realizeaza un singur task

- MPP = Massively Parallel Processor - "arhitectura super computer"

- Cluster server system - retea de calculatoare cu scop general

- SMP = Symmetric Multiprocessing system - un numar de 2^n procesoare identice conectate

- Multi-core processor - un chip cu mai multe nuclee de calcul

* Flynn

- pana in 2004 - SISD

- SIMD - instructiunea este difuzata la mai multe unitati de calcul - procesare vectoriala.

Recent, mai multe microprocesoare suporta instructiuni SIMD: SSE pe Intel CPU, si SPE pe un Cell BE.

- MISD - mai putine exemple, sistemele tolerante la defecte intra in categorie

- MIMD - clustere, sistem SMP

* Acceleratori:

GPU, Cell Broadband Engine - core-uri simple, care nu ocupa mult spatiu pe chip, deci pot fi incorporate mai multe

ex. GPU: Nvidia GPU chip (Tesla T10) = 30 de seturi de Streaming Processors (a cate 8 core-uri fiecare), in total 240 core-uri pe un chip

GPU-urile sunt superioare CPU-urilor pentru ca pot realiza intre 100 GFLOPS-1 TFLOPS, pe cand CPU-urile sunt limitate la 10 GFLOPS (giga floating operations per second)

OpenCL = framework pt scrierea de aplicatii in sisteme eterogene / hibride

"open computing language"

Implementarea unui program paralel:

* folosind apelurile de sistem ale SO : Posix threads

* folosind un framework: MPI pentru cluster servers, OpenMP pentru SMP, NUMA (sistemele cu memorie partajata), API-uri de paralelizare in Boost C++.

OpenMP - suportat de cele mai importante compilatoare: gcc, Intel C, Microsoft C

* prin compilare automata: Intel C/C++ , prin specificarea unor parametri de paralelizare in linia de comanda. Desi este mai comod asa, cu cat codul devine mai complex performanta are de suferit, compilatorul nestiind sa paralelizeze corespunzator.

OpenCL - pentru sisteme eterogene, dar si omogene (multi core: un core pentru control, restul pentru executii)

- scopul: un singur limbaj pentru a programa atat pe CPU-uri cat si pe GPU-uri, Cell BE, DSP-uri, .....

* Comparatie CUDA-Cell-lumea embedded

CPU = "host" - rol de management si control ---- "Host program"

GPU = "device" - rol de procesare data parallel -- "Kernel"

Kernelul trebuie scris in limbaj CUDA (extensie a lui C)

CUDA este asemanator cu Cell BE, CPU-ul fiind analog PPE, GPU-urile analoage SPU-urilor.

In domeniul embedded systems, modelul este asemanator: CPU dirijeaza DSP-urile (care au o functie primitiva - "digital signal processing")

Problema: toate cele 3 situatii (CUDA, Cell, sistemele embedded) cer folosirea unui API diferit. Solutia propusa este OpenCL.

Software de OpenCL = {compilator OpenCL, biblioteca runtime OpenCL}

Procesoarele implicate trebuie sa suporte insa OpenCL (vezi placa video)

Avantaje OpenCL:

- API pentru paralelizare standard

- optimizare: operatii vectoriale SIMD, copiere asincrona de memorie folosind DMA, transfer de memorie intre procesoare. OpenCL nu va limita niciodata performanta (in cazul unor functii nesuportate, se va folosi API-ul specific al procesorului)

Platforme: Host + Device

- Host: mediul in care se afla programul care controleaza device-urile, de obicei CPU-ul + memoria aferenta

- Device: GPU, DSP, Cell BE, alte CPU-uri + memoriile aferente

Un GPU este descris astfel: Device (GPU) + unitate de calcul (SM=streaming processor) + element de procesare (SP=scalar processor)

Programul care ruleaza pe device = kernel.

API-urile oferite de OpenCL se incadreaza pt urmatoarele modele de programare paralela:

* data parallel - un singur kernel este executat simultan in unitatile de calcul sau elementele de procesare, cu seturi diferite de date

* task parallel - mai multe kernel-uri....

Daca pe fiecare unitate de calcul ruleaza un grup kernel-uri , grupul primeste un ID unic (Work group ID). Fiecare kernel din grup primeste si el un ID (Work item ID). Utilizatorul specifica numarul total de work items si numarul de work items care sa ruleze pe fiecare unitate de calcul.

ID-ul poate avea pana la 3 dimensiuni.

* Modelul de memorie, contine memorie:

- globala: poate fi citita de toti work items, fizic rezidua in memoria principala a device-ului

- constanta: idem cea globala, doar ca poate fi folosita mai eficient dar unitatile de calcul contin hardware ce suporta constant memory cache

- locala: poate fi citita de toti work items din work group-ul respectiv. Fizic este memoria partajata de pe fiecare unitate de calcul

- privata: accesata doar de un singur work item. Fizic, corespunde registrilor fiecarui element de procesare.

Host : poate manipula memoria globala, constanta si memoria proprie

Device : memoria sa este accesata exclusiv de catre kernel

Continuarea acestei carti arata modul de instalare , exemple de utilizare si alte detalii utile.