Workflow Heterogeneous Computing

GL, VS, GT

API pentru dezvoltarea programelor ce se executa pe multiple platforme eterogene

Initializare Executie efectiva Terminare

CPU CPUCPUGPU

__kernel ()

Filtre GaussFiltre GaussIdee:

• Pixelul rezultat este o medie ponderata a pixelilor vecini, cu ponderile:

• S-a folosit o singura functie de kernel, executata de catre toate unitatile de calcul

1 2 1

2 4 2

1 2 1

in.pgm out.pgm

Un usor efect de blur

Idee:

• S-au folosit doua functii de kernel, aplicate succesiv

• Se folosesc doua filtre, cu ponderile:

•Prima functie kernel aplica primul filtru asupra setului de date (afland Dx)

• A doua functie aplica al doilea filtru (afland Dy) si calculeaza valoarea unui pixel dupa formula:

1 2 1

0 0 0

-1 -2 -1

-1 0 1

-2 0 2

-1 0 1

Observatii:

- este avantajoasa executia pe GPU in cazul setului mare de date (imagini cu rezolutie mare)

Filtre SobelFiltre Sobel

Histogram Equalization• transformare prin care se obtine o imagine cu o

histograma distribuita uniform• utilizata pentru a creste vizibilitatea detaliilor

• rezultatul maximizeaza contrastul unei imagini fara a pierde informatii de tip structural

Histogram Equalization (implementare)

• Functii kernel:1. calculeaza numarul de pixeli din imagine cu

intensitatea <= I [0..255];2. calculeaza noua valoare a fiecarui pixel T: T = (n[valoare_pixel] - n[0]) * 255 / (nr_total_pixeli - n[0]);

• Rezultate obtinute:

Fractali• o figura geometrica care poate fi divizata in

parti, astfel incat fiecare din acestea sa fie o copie in miniatura a intregului

• dimensiune fractala – un exponent care indica cat de complet ocupa un fractal spatiul

• metode de determinare a Df:• Box Counting method;• Mass-Radius method;• the Cluster Growing method;

Dimensiune fractala• impartirea imaginii per thread-uri • binarizarea imaginii;• numararea box-urilor de diferite dimensiuni:

• E.g.: latura = 2, 4, 8, 11(pixeli);• calcularea pantei regresiei logaritmice

Aflarea celui de-al k-lea element dintr-un vectorAflarea celui de-al k-lea element dintr-un vector- idee -- idee -

• S-a pornit de la varianta recursiva a aflarii celui de-al k-lea element, paralelizandu-se un pas al acestui algoritm

• Exemplu:N = 12, K = 5 (aflarea celui de-a 5-lea element)V = {2, 15, 0, 9, 40, 11, 7, 3, 14, 6, 21, 5}

Presupunem ca avem Q = 3 unitati de calcul=> impart pe V in 3 subsecvente de dimensiune N/Q =>

V = {2, 15, 0, 9, 40, 11, 7, 3, 14, 6, 21, 5}In paralel, fiecare unitate de calcul afla mediana subsecventei aferente folosind sortare

=> M = {9, 7, 5}O unitate de calcul afla mediana medianelor => m = 7 si creeaza 3 subsecvente cu

elemente <, = respectiv > m, din v: s1 = {2, 0, 3, 6, 5} , s2 = {7} , s3 = {15, 9, 40, 11, 14, 21}

Se alege prin anumite criterii una din aceste subsecvente ca fiind noul vector V (in cazul in care subsecventa aleasa este s2, se poate furniza rezultatul).

In cazul de fata, se alege s1, V = s1 ……….Procedeul este repetitiv.

Aflarea celui de-al k-lea element dintr-un vectorAflarea celui de-al k-lea element dintr-un vector- implementare -- implementare -

• 2 functii de kernel:– Kelem

• executata in paralel de mai multe unitati de calcul• input: V, output: M (vectorul de mediane) – o unitate de calcul modifica

doar un element din M– Median

• Executata de o singura unitate de calcul• input: M, output: V (si alte flag-uri care spun daca s-a gasit elementul si

valoarea acestuia)• Functiile se apeleaza alternativ, rezultatul uneia devine intrarea celeilalte• Am evitat recursivitatea• Am facut o singura data mutarea datelor din RAM in VRAM (enqueue in buffere),

restul modificarilor petrecandu-se pe placa video (pentru economie de timp)• Din cand in cand, scot din anumite buffere flag-uri pentru a afla starea executiei

Aflarea celui de-al k-lea element dintr-un vectorAflarea celui de-al k-lea element dintr-un vector- statistici -- statistici -

n = 1000

k = 333

n = 2000

k = 1282

n = 2400

k = 2000

n = 443

k = 89

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

• Doar anumite probleme pot fi executate mai rapid pe placa grafica si anume cele pe seturi mari de date cu aplicarea unor operatii repetitive

• Latenta mare de transfer pentru GPU a datelor din RAM catre VRAM, acoperita prin executia rapida si repetata a unor task-uri

• Evitarea branch-urilor (if, while, for) intr-un kernel pe GPU• Anumiti algoritmi paraleli trebuie adaptati pentru a da rezultate cat mai bune atat

pe CPU cat si pe GPU – programarea in OpenCL cere totusi cunoasterea arhitecturii platformelor

• Algoritmi mai eficienti pe GPU (testati) : filtre simple ( Sobel/Gauss/Bitsplicing ), analiza fractala, procesare de imagini in general

• Algoritmi mai eficienti pe CPU (testati) : aflarea al K-lea element dintr-un sir

Concluzii