l3_aplicatii_openmp

Felicia Ionescu, Valentin Pupezescu Laborator de Calcul paralel

Lucrarea 3 - APLICATII OpenMP

Se va studia implementarea OpenMP a algoritmilor paraleli n multiprocesoare cu memorie

partajat. Programele se pot dezvolta att pe calculatoarele desktop din laboratoarele B125a i B138 (ITEMS), ct i n nodurile sistemului HPC Dell PowerEdge, programele sunt compatibile datorit bibliotecii OpenMP care se poate instala pe oricare dintre sisteme. Calculatoarele desktop din laboratorul B125a au procesoare cu 2 core, cele din B138 au cte 4 cores, iar fiecare nod din HPC conine cte 2 procesoare cu cte 8 cores, n total 16 cores in fiecare nod. Biblioteca OpenMP trateaz fiecare nucleu (core) dintr-un sistem ca un procesor separat pe care poate lansa un thread de execuie.

3.1 Biblioteca OpenMP Biblioteca OpenMP este instalat implicit (la instalarea sistemului de operare) att n sistemele

Linux Ubuntu 12.04 (din laboratoarele B125a, B138), ct i n fiecare nod al sistemului HPC Dell PowerEdge.

Biblioteca OpenMP asigur interfaa (API-Application Program Interface) pentru exprimarea paralelismului ntr-un limbaj de baz (Fortan, C, C++) folosind thread-uri multiple care comunic prin variabile partajate. Exist implementri OpenMP att pentru Linux ct i pentru Windows [Gra03], [OMP08].

OpenMP folosete modelul fork-join de programare paralel: programul este compus dintr-o succesiune de regiuni secveniale i regiuni paralele; n regiunile paralele thread-urile multiple execut task-uri create implicit sau explicit care comunic ntre ele prin variabile partajate. Biblioteca OpenMP permite paralelizarea semi-automat a programelor:

Programatorul studiaz dependenele ntre task-uri i definete regiunile secveniale i paralele (compuse din thread-uri paralele) i modul de comunicaie i sincronizare ntre thread-uri prin intermediul unor directive de compilare.

Compilatoarele compatibile OpenMP interpreteaz directivele de compilare i genereaz codul paralel care conine thread-urile i mecanismele de comunicaie i sincronizare ntre thread-uri.

Sintaxa unei directive OpenMP pentru limbajele C, C ++ este: #pragma omp nume_directiva [clauze] { Bloc structurat }

OpenMP admite numai blocuri structurate: un bloc structurat are un singur punct de intrare i un singur punct de ieire i nu se admit salturi din bloc n afara lui sau din afar n interiorul blocului, cu excepia funciei exit() (pentru C, C++) sau a instruciunii STOP (pentru Fortran).

n continuare vor fi prezentate cele mai importante directive OpenMP, mpreun cu clauzele acestora i cu funciile de bibliotec necesare pentru limbajul C.

3.1.1 Crearea regiunilor paralele n OpenMP Regiunile paralele se creeaz cu directiva #pragma omp parallel. Atunci cnd un thread (n

general thread-ul master) execut directiva parallel, se creaz o regiune paralel compus dintr-un grup de thread-uri care se execut n paralel; aceast directiv are urmtoarea sintax:

1

Lucrarea 3 Aplicaii OpenMP

#pragma omp parallel \ num_threads(nr_intreg)\ shared (var1, var2, ) \ private (var1, var2, ) \ default(shared|none)\ reduction(operator:var1, var2, ) { .. bloc structurat de cod }

Numrul de thread-uri ale regiunii paralele create este controlat de valoarea variabilei de mediu OMP_NUM_THREADS, poate fi setat prin comanda sh/bash:

$ export OMP_NUM_THREADS=nr_thread-uri n program se poate seta numrul de thread-uri prin apelul funciei: void omp_set_num_threads (int num_threads); sau poate fi setat ca argument al clauzei num_threads. Dac nu a fost setat numrul de thread-uri prin program i OMP_NUM_THREADS nu este

definit, biblioteca OpenMP creeaz un numr de thread-uri egal cu numrul de procesoare (cores) ale nodului de calcul.

Fiecare thread execut blocul structurat inclus n regiunea paralel. n general, nu exist nici-o sincronizare ntre thread-urile unei regiuni paralele, adic fiecare thread execut o anumit instruciune din bloc ntr-un moment de timp independent de momentul n care acea instruciune este executat de alte thread-uri.

Fiecare thread are un numr (identificator), care este un ntreg de la 0 pn la numrul de thread-uri minus 1. Acest identificator poate fi aflat prin apelul funciei:

int omp_get_thread_num() Atunci cnd toate thread-urile ating sfritul regiunii paralele, ele sunt distruse (sau puse n

ateptare) i numai thread-ul master continu execuia regiunii secveniale urmtoare. Se poate considera c la terminarea unei regiuni paralele exist o bariera de sincronizare implicit.

Variabile folosite n thread-uri pot fi de tip private sau partajat (shared). Dac o variabil este

de tip private, atunci fiecare thread primete o copie local neiniializat a acestei variabile. Dac o variabil este de tip partajat (shared), atunci exist o singur copie a variabilei i toate thread-urile care se execut n paralel au acces la acea copie a variabilei. In mod implicit, variabilele globale sunt de tip shared, iar cele locale sunt de tip private.

Clauza default poate schimba aceasta, specificnd c tipul implicit al variabilelor este partajat (shared), sau nici un tip (none) nu este implicit, deci trebuie declarat explicit tipul fiecarei variabile.

Tipul variabilelor se poate specifica prin clauza shared (care specific lista variabilor partajate de toate thread-urile) sau prin clauza private (care specific lista variabilelor locale ale thread-urilor). Clauza firstprivate conine lista variabilelor private care se iniializeaz cu valorile pe care le au variabilele cu acelai nume nainte de nceperea regiunii paralele.

Clauza reduction definete o operatie de reducere paralel, pentru care se specific un operator asociativ i o list de variabile.

2


Exemplu Programul Hello_OpenMP.c /* Hello_OpenMP.c Compilare: gcc Hello_OpenMP.c -o Hello_OpenMP -fopenmp -lgomp Se executa cu argument p - nr de thread-uri, implicit p = 4 ./Hello_OpenMP p */ #include #include int main(int argc, char* argv[]) { int id, p = 4; if (argc >= 2) p = atoi(argv[1]); #pragma omp parallel num_threads(p) private(id) { id = omp_get_thread_num(); printf("Hello OpenMP thread %d !\n", id); } return 0; }

Execuia cu 4 thread-uri: $ ./Hello_OpenMP 4 Hello OpenMP thread 0 ! Hello OpenMP thread 1 ! Hello OpenMP thread 3 ! Hello OpenMP thread 2 !

Programele OpenMP trebuie s includ header-ul bibliotecii (#include ). Comanda de compilare trebuie s conin opiunea fopenmp (pentru interpretarea directivelor OpenMP) i s link-eze programul rezultat cu biblioteca OpenMP (opiunea lgomp din comanda de compilare gcc).

Exerciiul E3.1. Compilai i executai programul Hello_OpenMP.c, variind modul de setare a numrului de thread-uri (folosind variabila de mediu OMP_NUM_THREAD, sau prin program cu funcia omp_set_num_threads())

3.1.2 Directive OpenMP de execuie paralel n interiorul unei regiuni paralele se pot introduce directive de paralelizare a buclelor de calcul

(directiva for) i directive de sincronizare ntre thread-uri (directivele single, barrier i critical). Directiva #pragma omp for specific faptul c bucla for imediat urmtoare va fi executat n

paralel, prin distribuirea iteraiilor buclei ntre thread-urile regiunii paralele n care a fost introdus. Bucla trebuie s fie paralelizabil, adic fiecare iteraie a acesteia s poat fi executat independent de alte iteraii.

Sfrsitul buclei paralele for este un punct de sincronizare implicit (barier) ntre thread-uri: nici un thread nu continu execuia dup bucla for pn ce nu au terminat toate thread-urile de executat bucla respectiv. Exist o exceptie, dac se introduce clauza nowait in directiva #pragma omp for; n aceast situaie fiecare thread continu operaiile dup bucla for, fr s atepte ca i celelalte thread-uri s termine bucla.

Directiva #pragma omp for introduce o singur bucl paralel; dac ntr-o regiune paralel sunt mai multe bucle paralele, pentru fiecare dintre ele se folosete o astfel de directiv. Se pot combina directivele parallel i for:

3


#pragma omp parallel for [clauze] for(){ }

OpenMP permite setarea modului de distribuire i planificare a iteraiilor buclelor paralelizate cu directiva for, prin clauza schedule:

#pragma omp for schedule (kind [,chunk_size]) Planificare static: schedule (static [,chunk_size]): iteraiile buclei sunt mprite

static n grupuri de cte chunk_size iteraii, care se atribuie circular (robin-round), n ordine thread-urilor 0, 1,...(p-1), pn se epuizeaz toate grupurile; dac nu este dat parameetrul chunk_size, atunci cele n iteraii se mpart echilibrat n p partiii de iteraii consecutive: fie s = (int) n / p; primele k = n%p partiii au (s+1) iteraii, iar ultimele (p-k) partiii au s iteraii; se obine o partiionare n partiii continue, aa cum a fost definit n programele Pthread

Dac chunk_size = 1, se obine o partiionare ntreesut aa cum a fost folosit n programele Pthread.

Planificare dinamic: schedule (dynamic [,chunk_size]): iteraiile buclei sunt mprite n grupe de cte chunk_size iteraii care sunt distribuite dinamic thread-urilor din regiunea paralel, pe msur ce acestea cer un nou grup de iteraii.

Planificare automat: schedule (auto): distribuirea i planificarea iteraiilor este delegat compilatorului sau sistemului executiv (runtime), n funcie de implementarea bibliotecii

Directiva #pragma omp barrier introduce un punct de sincronizare explicit n interiorul unei regiuni paralele: nici un thread din regiunea paralel nu poate continua execuia instruciunii urmtoare directivei barrier dect dup ce toate thread-urile au ajuns la barier. #pragma omp parallel .... { .... #pragma omp barrier .... }

Directiva #pragma omp single, introdus ntr-o regiune paralel, are ca efect execuia instruciunii (sau a blocului de instruciuni) care urmeaz de ctre un singur thread. Thread-ul care ajunge primul la aceast directiv este ctigtorul pentru execuia blocului ei, iar toate celelalte thread-uri care ajung la ea ateapt pn cnd blocul este executat, dup care o depete i continu execuia. Directiva single introduce o barier de sincronizare implicit ntre thread-uri dac nu conine clauza nowait. #pragma omp parallel ... { ... #pragma omp single { bloc single } }

Directiva #pragma omp master, introdus ntr-o regiune paralel, are ca efect execuia instruciunii (sau a blocului de instruciuni) care urmeaz doar de ctre thread-ul master, fr barier de sincronizare ntre thread-uri.

Directiva #pragma omp critical este utilizat pentru serializarea acceselor mai multor thread-uri la o variabil partajat. Instruciunea (sau blocul de instruciuni) care urmeaz unei astfel de directive este o seciune critic i poate fi executat numai de un singur thread la un moment dat:

4


#pragma omp critical (nume_sect_critica) { bloc sectiune critica }

Argumentul acestei directive este opional dac toate seciunile critice dintr-o regiune paralel sunt independente unele de altele, sau trebuie introdus explicit, cu un anumit nume pentru toate directivele critical care se refer la controlul accesului la aceeai variabil partajat.

Directiva critical protejeaz, aadar, accesul mai multor thread-uri la o seciune critic (blocul directivei) i este echivalent cu utilizarea unui mecanism de sincronizare de tip mutex (lock).

3.2. Implementarea OpenMP a nmulirii matricelor

n OpenMP se pot implementa algoritmi paraleli folosind thread-uri care comunic prin

variabile partajate. Spre deosebire de biblioteca Pthread, n care variabilele partajate trebuie s fie definite obligatoriu n segmentul de date (ca variabile globale, statice sau alocate dinamic n heap, nu ca variabile locale alocate n stiv), n OpenMP programatorul poate defini variabilele ca n orice program secvenial (de regul locale, n funcia main() sau n alte funcii) i compilatorul OpenMP (gcc cu opiunea fopenmp) schimb categoria de memorare a variabilelor n conformitate cu clauzele de partajare din directive (shared, private, firstprivate, default).

Se implementeaz acelai algoritm de nmulire a dou matrice care a fost implementat i n

aplicaiile Pthread: for (i = 0; i < n; i++) for (j = 0; j < n; j++) { c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k]*b[k][j]; }

In fisierul Matrix_Mult_OpenMP.c sunt date mai multe versiuni de implementare OpenMP a algoritmului de nmulire a dou matrice, cu diferite moduri de partiionare.

Partea de citire a parametrilor din linia de comand, de alocare i iniializare a datelor este la fel ca n programul Pthread de nmulire a dou matrice, cu deosebirea c toate variabilele (inclusiv int n; int p; float **a, **b, **c;) sunt definite local n funcia main(), iar categoria de memorare este setat prin clauzele shared i private ale directivei #pragma omp parallel. // Matrix_Mult_OpenMP.c #include #include #include #include int main(int argc, char *argv[]){ int n = 1024; // dimensiunea implicita a matricelor int p = 2; // numarul implicit de thread-uri int mod = 0; // Mod 0: partitionare pe linii int max_rep = 1; // Numar de repetari ale executiei float **a, **b, **c; int i, j, k, rep; char *text_mod;

5


// Alocarea dinamica a matricelor a = (float**)malloc(sizeof(float*)*n); b = (float**)malloc(sizeof(float*)*n); c = (float**)malloc(sizeof(float*)*n); for (i = 0; i < n; i++){ a[i] = (float*)malloc(sizeof(float)*n); b[i] = (float*)malloc(sizeof(float)*n); c[i] = (float*)malloc(sizeof(float)*n); } // Initializarea matricelor a si b ... for (rep = 0; rep < max_rep; rep++){ if (p == 1) { // Inmultirea secventiala a doua matrice ... } // Inmultirea paralela a doua matrice else if (mod == 0) { text_mod = "mod 0: Inmultire paralela cu partitionare pe linii"; #pragma omp parallel num_threads(p) shared(a,b,c,n) private(i,j,k) { #pragma omp for for (i = 0; i < n; i++) for (j = 0; j < n; j++){ c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } } else if (mod == 1) { text_mod = "mod 1: Inmultire paralela cu partitionare pe linii \ intretesute"; #pragma omp parallel num_threads(p) shared(a,b,c,n) private(i,j,k) { #pragma omp for schedule (static, 1) for (i = 0; i < n; i++) for (j = 0; j < n; j++){ c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } } else if ... else { printf("Eroare: mod %d - inexistent\n", mod); exit (0); } } // end for (rep) // Masurare timp, afisare rezultate ... return 0; }

Dimensiunea matricelor (n) i numrul de thread-uri (p) se pot introduce ca parametri la lansarea n execuie (argv[1], argv[2]), iar implicit n = 1024, p = 2. Matricele a, b, c se aloc dinamic.

6


Modul de partiionare pe linii a matricelor. Pentru partiionarea pe linii (continue sau ntreesute) se paralelizeaz bucla exterioar (care parcurge liniile) prin aplicarea construciei #pragma omp for acestei bucle.

Variabilele i, j, k sunt private: variabile j, k parcurg integral buclele interne neparalelizate; variabila i este contorul buclei paralelizate: fiecare thread are propria variabil i, care nu parcurge toate iteraiile buclei de la 0 la (n-1), aa cum pare din sintaxa directivei, ci numai iteraiile care i revin, conform clauzei schedule:

partiii continue: #pragma omp for sau #pragma omp for schedule (static) partiii ntreesute: #pragma omp for schedule (static, 1) Modul de partiionare pe coloane dup nterschimbarea buclelor. Dac se interschimb

buclele i i j ntre ele, distribuirea iteraiilor buclei externe (de contor j) nseamn distribuirea coloanelor matricelor. Se obine un program cu o singur regiune paralel, asemntor cu cel cu partiionarea pe linii.

Variabilele i, j, k sunt private: variabilele i, k parcurg integral buclele interne neparalelizate; variabila j este contorul buclei paralelizate: fiecare thread parcurge numai iteraiile care i revin din cele n iteraii (conform clauzei schedule) #pragma omp parallel num_threads(p) shared(a,b,c,n) private(i,j,k) { #pragma omp for for (j = 0; j < n; j++) for (i = 0; i < n; i++){ c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } }

Modul de partiionare pe coloane cu n regiuni paralele. Pentru partiionarea pe coloane fr interschimbarea buclelor se paralelizeaz bucla intern (de contor j): se definete o regiune paralel n fiecare iteraie a buclei exterioare (de contor i), iar directiva #pragma omp for distribuie iteraiile buclei interne (de contor j) ntre p thread-uri.

Variabila i este partajat: toate thread-urile folosesc acelai contor de linii; variabilele j, k sunt private; variabila j este contorul buclei paralelizate, fiecare thread parcurge numai iteraiile care i revin conform clauzei schedule; variabila k parcurge integral bucla intern neparalelizat.

S-a obinut varianta cu n regiuni paralele a algoritmului, care are timpul de execuie paralel estimat i msurat mai mare dect cel al variantei cu o regiune paralel. for (i = 0; i < n; i++) #pragma omp parallel num_threads(p) shared(a,b,c,n,i) private(j,k) { #pragma omp for for (j = 0; j < n; j++){ c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } }

Se poate introduce clauza nowait in directiva for deoarece iteraiile sunt independente, dar nu are nici un efect deoarece terminarea buclei coincide cu terminarea regiunii paralele care introduce o bariera de sincronizare implicit.

7


Modul de partiionare pe coloane fr interschimbarea buclelor. Se transform programul de partiionare pe coloane cu n regiuni paralele n program cu 1 regiune paralel prin reunirea task-urilor asignate fiecrei partiii n cele n iteraii ale buclei i.

Variabilele i, j, k sunt private; variabila j este este contorul buclei paralelizate: fiecare thread parcurge numai iteraiile care i revin conform clauzei schedule; variabilele i i k parcurg integral buclele interne neparalelizate

Se introduce clauza nowait deoarece iteraiile sunt independente i thread-urile nu trebuie s se sincronizeze la fiecare linie. #pragma omp parallel num_threads(p) shared(a,b,c,n) private(i,j,k) { for (i = 0; i < n; i++) { #pragma omp for nowait for (j = 0; j < n; j++){ c[i][j] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } }

Compilarea programului se face pe calculatorul pe care se va executa (n clusterul B125 sau

HPC) i se link-eaz cu bibliotecile corespunztoare: $ gcc Matrix_Mult_OpenMP.c o Matrix_Mult -fopenmp -lgomp

La execuia programului rezultat (Matrix_Mult_OpenMP) pentru dimensiuni ale matricelor n = 1024 cu p = 16 thread-uri, cu partiionare pe linii (mod 0, implicit) n nodul hpc.intern al clusterului HPC Dell PowerEdge se obine: $ ./Matrix_Mult_OpenMP 1024 16 n = 1024, p =16, t = 1.337 sec Pentru msurarea performanelor se lanseaz fiierul de execuie repetat (Exec_Matrix_Mult_OpenMP), cu diferii parametri n i p a programului Matrix_Mult_OpenMP executabil pe multiprocesorul dorit.

La fiecare execuie, programul Matrix_Mult_OpenMP nscrie n fiierul de rezultate (Res_Matrix_Mult_OpenMP.txt) valoarea msurat a timpului de execuie. n final, n fisierul de rezultate se obine o matrice de valori ale timpului de execuie: pe o linie valorile pentru n dat (32, 512, 1024, 2048), pe o coloan valorile pentru un anumit numr de procesoare (p = 1, 2, 4, 8, 16).

Pentru reprezentarea grafic se lanseaz programulGrafice.R i se seteaz numele fiierului

rn


9


Pe grafice se observ diferite aspecte ale comportrii algoritmului: scderea timpului de execuie (TP) atunci cnd crete numrul de procesoare, creterea accelerrii (S) i a eficienei (E) pentru un p dat, atunci cnd crete dimensiunea n; scderea eficienei atunci cnd crete numrul de procesoare, dac dimensiunea n rmne constant, etc.

Modul de ncrcare a procesoarelor n cursul execuiei unui algoritm paralel se poate urmri cu toolset-ul System Monitor. De exemplu, dac lansm n execuie mai multe thread-uri n nodul hpc.intern din clusterul HPC se poate vedea cum sunt atribuite procesoarele.

.

(c)

(a)

(b)

(c)

10


n screenshot-ul (a) sunt lansate n execuie 4 thread-uri care sunt atribuite la 4 procesoare, care sunt ncrcate 100%, restul procesoarele avnd o ncrcare mult mai mic (execuia altor procese, de sistem sau utilizator). n screenshot-ul (b) sunt lansate 8 thread-uri, atribuite la 8 procesoare care sunt ncrcate 100%. n screenshot-ul (c) sunt lansate 16 thread-uri, toate cele 16 procesoare ale nodului hpc.intern sunt ocupate 100%.

Exerciiul E3.2. Studiai programul folosind textul surs Matrix_Mult_OpenMP.c, executai pentru fiecare mod de partiionare pe staia Linux i pe HPC i comparai rezultatele. n scriptul de execuie Exec_Matrix_Mult_OpenMP numrul de repetri ale execuiei (parametrul max_rep transmis la comanda ./Matrix_Mult_Pthread n p mod max_rep) este mai mare pentru n mic: max_rep = 4096 / n.

3.3. Program OpenMP de adunare a doi vectori Se implementeaz acelai algoritm de adunare a doi vectori x i y de dimensiune n, cu rezultat

n y folosit i n aplicaiile Pthread: for (i = 0; i < n; i++)

y[i] = y[i] + x[i]; Partea de calcul din programul OpenMP de adunare a doi vectori:

// Adunare paralela cu partitii continue (cu elemente adiacente) #pragma omp parallel num_threads(p) shared (x, y, n) private (i) { #pragma omp for schedule (static) for (i = 0; i < n; i++) y[i] = y[i] + x[i]; } // Adunare paralela cu partitii intretesute (cu elemente intretesute) #pragma omp parallel num_threads(p) shared (x, y, n) private (i) { #pragma omp for schedule (static,1) for (i = 0; i < n; i++) y[i] = y[i] + x[i]; }

Exerciiul E3.3. Dezvoltai programul Vector_Add_OpenMP.c, executai pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind un script Exec_Vector_Add_OpenMP asemntor cu cel pentru nmulie, pentru n = (4096, 32768, 262144, 16777216), p = (1, 2, 4, 8, 12, 16). Reprezentai graficele performanelor TP (p), S(p), E(p) cu parametru n, folosind programul R dat.

3.4. Program OpenMP de adunare a dou matrice Se implementeaz acelai algoritm de adunare a dou matrice ptrate a i b de dimensiuni n x n

folosit i n aplicaiile Pthread: for (i = 0; i < n; i++) for (j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j];

11


Programul Matrix_Add_OpenMP.c poate fi identic cu cel de nmulire a dou matrice, se nlocuiete numai partea de calcul a elementului c[i][j] al matricei de ieire; de exemplu, partea de program care realizeaz nmulirea a dou matrice cu partiionare orientat pe linii continue: #pragma omp parallel num_threads(p) shared(a,b,c,n) private(i,j,k) { #pragma omp for for (i = 0; i < n; i++) for (j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j]; }

Exerciiul E3.4. Implementai algoritmul de adunare a dou matrice Matrix_Add_OpenMP.c, n mod asemntor inmulirii a dou matrice. Executai programul pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind un script Exec_Matrix_Add_OpenMP pentru aceleai valori ale lui p (1, 2, 4, 8, 12, 16) i n = (64, 256, 512, 4096, 32768). Reprezentai graficele performanelor TP (p), S(p), E(p) folosind programul Grafice.R

3.5. Program OpenMP de reducere paralel Implementarea OpenMP a algoritmului de reducere paralel adaptiv (asemntoare cu varianta

Pthread) poate folosi clauza critical sau reduction pentru excluderea mutual din etapa 2.

n varianta cu directiva critical, bucla cu n iteraii de adunare a elementelor vectorului a[n] este descompus (distribuit) de directiva #pragma omp for celor p thread-uri ale regiunii paralele i fiecare thread acumuleaz rezultatul reducerii pariale din propria partiie ntr-o variabil local (private) (psum), iniializat cu 0.

Bucla for poate fi fr sincronizare la sfrit (cu nowait), dat fiind c fiecare thread i execut propria partiie apoi nsumeaz rezultatul n rezultatul final fr s atepte

Rezultatul final se obine prin nsumarea valorilor acestor variabile locale n variabila partajat sum folosind excluderea mutual prin clauza #pragma omp critical

n varianta cu clauza reduction(op:list), operaiile de calcul a rezultatelor partiale si a rezultatului global folosind excluderea mutual sunt introduse automat.

Standardul prevede iniializarea variabilei rezultat (sum n acest exemplu) n funcie de operatorul de reducere: cu 0 pentru operaia +, cu 1 pentru operaia * etc.), dar nu toate implementrile OpenMP respect aceast recomandare. Variabilele din list trebuie s fie shared (partajate).

Clauza reduction se aplic corect numai dac operaia de reducere se face n bucla for creia i aparine (nu ntr-o bucl imbricat n aceasta).

Exerciiul E3.5. Studiai i executai programul Reduction_OpenMP.c pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind scriptul Exec_Reduction_OpenMP. Reprezentai graficele performanelor TP (p), S(p), E(p) folosind programul R dat.

3.6 Program OpenMP de nmulire succesiv a matricelor Se implementeaz acelai algoritm de nmulire succesiv a matricelor : c = a x b; e = d x c ca

i cel implementat Pthread. Partea de calcul paralel a nmulirii succesive va arta astfel:

12

l3_aplicatii_openmp

Documents