L2_Aplicatii_Pthread

Felicia Ionescu, Valentin Pupezescu Laborator de Calcul paralel

Lucrarea 2 - APLICATII PTHREAD

Thread-urile reprezint o modalitate software de a mbunti performanele sistemelor de calcul prin reducerea timpului de comutare a proceselor. Un thread este un fir de executie n cadrul unui proces; n fiecare proces se pot defini mai multe thread-uri.

Fiecare thread are o stare mai redusa (constituita din starea registrelor si a flag-urilor procesorului si stiva proprie) si toate thread-urile unui proces partajeaza resursele de calcul ale acestuia (ca de exemplu, memoria i fiierele).

n sistemele bazate pe thread-uri, thread-ul devine cea mai mic entitate de planificare, iar procesul servete ca un mediu de execuie a thread-urilor. n astfel de sisteme, un proces cu un singur thread este identic cu un proces clasic.

De vreme ce toate celelalte resurse, cu excepia procesorului, sunt gestionate de ctre procesul care le nglobeaz, comutarea ntre thread-urile care aparin aceluiai proces, care implic doar salvarea, respectiv restaurarea, strii hardware (nu si a stivei, care este separata, proprie fiecarui thread), este rapid i eficient. Totui, comutarea ntre thread-urile care aparin unor procese diferite implic tot costul de comutare a proceselor.

Thread-urile sunt un mecanism eficient de exploatare a concurenei programelor. Un program poate fi mprit n mai multe thread-uri, fiecare cu o execuie mai mult sau mai puin independent, i pot comunica ntre ele prin accesul la spaiul de adres a memoriei procesului, pe care l partajeaz ntre ele.

Toate thread-urile unui proces partajeaz segmentul de cod i segmentul de date al procesului care le-a creeat. Fiecare thread are propriul segment de stiv care nu este partajat cu alte thread-uri.

Dac thread-urile aparin unor procese diferite, trebuie s fie definit n mod explicit un segment de memorie partajat ntre procese, la fel cum se procedeaz pentru partajarea memoriei ntre procese.

2.1 Biblioteca PTHREAD n sistemele de operare Unix/Linux, dezvoltate pentru multiprocesoare i multicalculatoare,

s-au implementat diferite faciliti pentru controlul i partajarea resurselor multiple (procesoare, memorie), inclusiv thread-uri. Cea mai utilizat modalitate de implementare a thread-urilor n astfel de sisteme este aceea definit n standardul POSIX (IEEE POSIX Standard 1003.4), care asigur portabilitatea ntre platforme hardware diferite. Thread-ul POSIX este denumit pthread.

Biblioteca Pthread este folosit pentru programarea paralel prin memorie partajat. O aplicaie cu pthread-uri este un program C care utilizeaz diferite funcii POSIX pentru

crearea thread-urilor, definirea atributelor, controlul strilor (terminare, detaare) thread-urilor. Aceste funcii sunt definite n biblioteca PTHREAD (libpthread.so), care trebuie s fie adugat (la link-are) programului apelant (prin opiunea de compilare lpthread).

Un thread POSIX este caracterizat printr-un identificator de tipul opac pthread_t si o colectie de atribute grupate ntr-o structura de tipul pthread_attr_t.

La lansarea in executie a unui program, sistemul de operare creeaza un proces care contine un singur thread, numit thread-ul principal (thread-ul master).

In cursul executiei (n mod dinamic) un thread poate crea alt thread prin apelul funciei: int pthread_create (pthread_t *pth, pthread_attr_t *attr, void *(functie_thread)(void*), void* param);

1

Lucrarea 2 Aplicaii Pthread

Identificatorul thread-ului creat (de tipul pthread_t) este returnat thread-ului apelant n argumentul pth (de tip pointer). n structura de date de tip pthread_attr_t sunt grupate atributele de creare ale pthread-ului, ca, de exemplu, prioritatea, politica de planificare, dimensiunea i adresa stivei, etc. Valoarea NULL pasat ca pointer la atribute are ca efect crearea unui thread cu atribute implicite. Thread-ul nou creat execut funcia: void * functie_thread (void* param)

Parametrul care se transmite functiei thread-ului la creare (param) trebuie sa fie de tip pointer la void (void *) si acesta se obtine prin conversia unui pointer la o variabila care contine propiu-zis valoarea transmisa sau la o structura care poate grupa mai multe valori.

Dat fiind ca thread-urile aceluiasi proces partajeaza doar segmentul de cod si de date (nu si stiva, care este proprie fiecarui thread si nu poate fi partajata), este necesar ca parametrul transmis ca argument al functiei thread-ului sa se afle in segmentul de date si nu in stiva. Deci el poate fi definit intr-unul din urmatoarele moduri:

Ca variabila globala (statica sau nu) Ca variabila locala statica Ca variabila in memoria libera (heap) alocata cu functia malloc; Un thread se termin automat atunci cnd revine din funcia executat. Un thread se poate de

asemenea termina prin apelul funciei pthread_exit(), aa cum un proces se termin prin apelul funciei exit(). Apelul funciei exit() termin ntreg procesul, inclusiv toate thread-urile sale, de aceea aceast funcie se apeleaz numai de ctre thread-ul principal, sau de ctre orice alt thread n cazul aperiiei unei erori care nu permite continuarea execuiei. Ieirea din thread-ul principal prin apelul funciei phtread_exit din funcia main nu termin ntreg procesul ci numai thread-ul principal, iar procesul se termin atunci cnd se termina toate thread-urile create.

Pentru sincronizarea la terminarea executiei thread-urilor se apeleza functia: int pthread_join(pthread_t th, int *status );

care oblig thread-ul apelant (master) s ateapte terminarea thread-ului cu identificatorul th; starea cu care se termin thread-ul se recupereaz n locaia dat prin pointerul status.

Exemplu Programul Hello_Pthread.c

#include #include #include void *Hello (void *param); // Prototip functie thread int p = 2; // Numar de thread-uri implicit int main (int argc, char *argv[]) {

int q; int *params; // Parametrii transmisi thread-urilor pthread_t *ids; // Identificatorii thread-urilor // Citirea parametrilor de lansare a programului

if (argc >= 2) p = atoi(argv[1]); // Alocarea dinamica (in heap) a datelor params = (int*)malloc(sizeof(int)*p); ids = (pthread_t*)malloc(sizeof(pthread_t)*p); 2


// Thread-ul master creeaza p thread-uri for (q = 0; q < p; q++){ params[q]=q; pthread_create(&ids[q], 0, Hello, &params[q]); } // Thread-ul master asteapta terminarea thread-urilor create for (q = 0; q < p; q++) pthread_join (ids[q], 0); exit (0); } // Functia thread-ului void *Hello (void *param){ int id = *(int*)param; printf ("Hello Pthread %d !\n",id); return 0; } Programele Pthread trebuie s includ header-ul bibliotecii: #include Se compileaz cu compilatorul gcc (sau g++) i se link-eaz cu biblioteca pthread: $ gcc Hello_Pthread.c o Hello_Pthread lpthread Se lanseaz cu comanda Hello_Pthread, urmat de parametrul p (care modific valoarea implicit) : $ ./Hello_Pthread 4 Hello Pthread 1 ! Hello Pthread 0 ! Hello Pthread 2 ! Hello Pthread 3 !

La execuia acestui program fiecare thread afieaz valoarea parametrului primit, care este chiar indicele thread-ului (0, 1, 2, 3). Ordinea de execuie a thread-urilor (i deci ordinea de afiare a mesajelor) este impredictibil, depinde de planificarea executat de sistemul de operare.

Exerciiul E2.1. Compilai i executai programul Hello_Pthread.c, pentru diferite valori ale parametrilor.

2.2. Inmulirea a dou matrice Pentru programarea paralel n multiprocesoare (cu memorie partajat) se creeaz mai multe

thread-uri care se execut concurent, fiecare thread pe un procesor diferit, i fiecare executnd pri (partiii) ale algoritmului. Dac se folosesc mai multe procesoare, este de ateptat ca timpul de execuie s scad, adic s se observe o accelerare a execuiei.

Fie algoritmul de nmulire a dou matrice a i b de dimensiuni n x n cu rezultat matricea c: 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]; }

3


Algoritmul conine o bucl imbricat pe 3 niveluri i are timpul de execuie secvenial TS = 2n3 = O(n3) dac se consider ca operaie de baz orice operaie aritmetic cu numere reale.

Se observ uor c iteraiile buclei exterioare (contor i) sunt independente, deoarece fiecare iteraie i scrie numai n linia c[i], deci nu exist dou iteraii diferite care s scrie n aceeai linie a matricei c. La fel, si iteraiile celei de-a doua bucle (contor j) sunt independente.

Deci primele dou bucle sunt perfect paralelizabile (paralelizabile fr dependene ntre ele). n schimb, ntre iteraiile buclei interioare (contor k) exist dependente de date, bucla nu poate fi paralelizat direct (ci numai cu mecanisme de sioncronizare).

Algoritmul se poate paraleliza prin partiionarea (distribuirea iteraiilor) celor dou bucle perfect paralelizabile:

Partiionare unidimensional, cu partiii continue (linii sau coloane consecutive) sau ntreesute: partiionare pe linii prin distribuirea iteraiilor buclei exterioare (contor i) (a) partiionare pe coloane prin distr iteraiilor celei de-a doua bucle (contor j) (b)

Partiionare bidimensional n blocuri, prin distr. iteraiilor ambelor bucle (i, j) (c)

Matricea a Matricea b Matricea c

0

q ...

...

p = 4

Matricea a Matricea c Matricea b

0 r .... ....p = 4

0 r ... ...

Partiionarea matricelor n algoritmul de nmulire a dou matrice

(a)

(b)

Matricea a

0

q

..

..

q

0 T00

T10

T20

T30

T01

T11

T21

T31

T02

T12

T22

T32

T03

T13

T23

T33

0 r ... ... p = 16 0 r ... ...

(c)

Matricea b Matricea c

4


2.2.1. nmulirea a dou matrice cu partiionare pe linii Programul Matrix_Mult_Pthread.c dat n continuare implementeaz mai multe moduri de

partiionare, dintre care mod = 0 reprezint patiionarea pe linii, cu partiii continue a algoritmului de nmulire a dou matrice folosind biblioteca Pthread. /* Matrix_Mult_Pthread.c Inmultirea Pthread a doua matrice Partitionare pe linii n partitii continue */ #include void *Matrix_Mult_line (void *); // Prototip functia thread-ului // Variabile globale partajate int n = 1024; // Dimensiune matrice int p = 2; // Numar thread-uri int mod = 0; // Mod part. pe linii cu partiii continue int max_rep = 1; // Numar de repetari ale executiei float **a, **b, **c; // Matricele int main(int argc, char *argv[]){ int i, j, k, q; int* params; // Parametri thread-uri pthread_t *ids; // Identificatori thread-uri struct timeval t1, t2; // Citire parametri if (argc >= 2) n = atoi(argv[1]); if (argc >= 3) p = atoi(argv[2]); if (argc >= 4) mod = atoi(argv[3]); if (argc >= 5) max_rep = atoi(argv[4]); // Verificarea parametrilor introdusi ... // Alocarea dinamica a datelor (n heap, deci partajate) 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); } params = (int*)malloc(sizeof(int)*p); ids = (pthread_t*)malloc(sizeof(pthread_t)*p); // Initializarea matricelor de intrare a, b if (n


for (rep = 0; rep < max_rep; rep++) { // Executia se repeta de max_rep if (p == 1) { // Inmultirea secventiala a matricelor for (i = 0; i < n; i++) for (j = 0; j < n; j++){ c[i][] = 0; for (k = 0; k < n; k++) c[i][j] += a[i][k]*b[k][j]; } } else if (mod == 0) { // Imnultirea paralela a matricelor cu part. pe linii for (q = 0; q < p; q++) { params[q] = q; pthread_create(&ids[q],0,Matrix_Mult_line,(void*)&params[q]); } for (q = 0; q < p; q++) pthread_join (ids[q],0); } else { /* Celelate moduri de partitionare ... */ } } // end for (rep...) gettimeofday(&t2, NULL); tp = (t2.tv_sec-t1.tv_sec+0.000001*(t2.tv_usec-t1.tv_usec))/max_rep; // Afisare timp de executie si scriere in fisier ... // Afiare rezultate ... return 0; } // Functia thread-ului void *Matrix_Mult_line (void *param) { int i, j, k, first, last; int q = *(int*)param; int s = (int) n/p; int kp = n%p; // Calcul first, last limitele partitiei if (kp == 0) { // n divizibil cu p first = q*s; last = first + s; } else if (q < kp) { // primele kp partitii au dimensiunea s+1 first = q*(s+1); last = first + s+1; } else { // ultimele (p-kp) partitii au dimens s first = q*s + kp; last = first + s; } for (i = first; i < last; 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]; } return 0; } 6


Compilare: $ gcc Matrix_Mult_Pthread.c o Matrix_Mult_Pthread lpthread Executie; $ ./Matrix_Mult_Pthread_1 1024 2 Afiseaza: n = 1024, p = 2, t = 9.771097 sec

Acest program conine mai multe tehnici de programare paralel folosind biblioteca Pthread pe care le vei regsi n majoritatea algoritmilor din acest laborator.

(a) Thread-ul master (creat la lansarea programului, care execut funcia main() ) creeaz p thread-uri de lucru, care execut nmulirea matricelor. Numrul de thread-uri care se creeaz (p), ca i dimensiunea matricelor (n), au valori implicite, dar pot fi modificate prin parametrii introdui n linia de comand la lansarea programului.

Dac numrul de thread-uri (p) este mai mic, cel mult egal cu numrul de procesoare ale nodului de calcul (P), atunci se vor folosi p doi cele P procesoare i accelerarea se calculeaz pentru p procesoare. Dac numrul de thread-uri create p > P, se vor folosi numai P procesoare (attea procesoare are nodul de calcul), deci timpul de execuie paralel va fi acelai ca i pentru p = P thread-uri. Dac totui, pentru p > P se obine un timp de cexecuie paralel mai mic dect pentru p = P, aceast mbuntire este nesemnificativ i se obine doar pentru c sistemul de operare planific mai multe cuante de timp de execuie al procesoarelor, fiind mai multe thread-uri n competiie cu celelalte procese care se execut pe sistem.

Programul conine att versiunea secvenial (pentru p = 1), ct i versiunea paralel (p > 1) i se execut de max_rep ori, pentru msurarea mai exact a timpului de execuie prin medierea valorilor obinute. Parametrul max_rep are valoarea implicit 1, dar se poate seta n linia de comand.

(b) Matricele a, b, c se aloc dinamic (cu funcia malloc). Pointerii float **a, float **b, float **c sunt variabile globale pentru a putea fi accesate partajat att de thread-ul master (din funcia main()) ct i din toate celelalte thread-uri (din funcia thread-ului) fr s fie transmii ca parametri funciei thread. Datele propiu-zise (vectorii de date) alocate n heap (cu funcia malloc) sunt de asemernea partajate de thread-ul principal i thread-urile create.

Datele din matricele de intrare a i b se iniializeaz. Pentru n 16 se iniializeaz cu valori cunoscute (a[i][j] = i, b[i][j] = 1), astfel c rezultatul ateptat este cunoscut i se afieaz automat dup execuia algoritmului. Dac algoritmul funcioneaz corect pentru n 16, i rezultatele pentru varianta secvenial sunt identice cu rezultatele pentru varianta paralel cu valori ale lui p = 2, p = 4, etc., cel mai probabil algoritmul este corect i nu mai sunt necesare alte verificri (care se pot face bineneles). Pentru n > 16 datele se iniializeaz cu valori aleatoare scalate ntre 0 i 1: rand()/(float)RAND_MAX;

(c) Fiecare thread primete ca parametru indicele thread-ului (valori de la 0 la p-1), care trebuie s fie dat printr-un pointer la o variabil partajat. Pentru aceasta se definete un vector cu p numere ntregi (params), alocat n memoria heap cu funcia malloc(). n fiecare element al vectorului params se nscrie indicele thread-ului: params[q] = q; iar funciei thread-ului i se transmite pointerul la aceast locaie (convertit n pointer la void - void*). n funcia thread-ului se face conversia invers (n pointer la ntreg - int*) i se citete valoarea parametrului, care este indicele thread-ului i a partiiei de date.

(d) n funcia thread-ului (Matrix_Mult) se oine indicele thread-ului i al partiiei de linii (q) din argumentul funciei (void *param). Distribuirea uniform a celor n iteraii ntre p thread-uri se face astfel: dac n este divizilbil cu p, fiecrui thread i se aloc s = n / p iteraii; dac n nu este divizibil cu p se aloc s = (int) n / p iteraii primelor k = n%p thread-uri i s+1 iteraii celorlalte (p k) thread-uri.

(e) Petru msurarea timpului de execuie a programului se introduc funcii de msurare a timpului (gettimeofday() ) nainte i dup execuie, se calculeaz diferena (n secunde), iar valoarea rezultat (tp) se afieaz pe ecran i se insereaz (append) ntr-un fiier de rezultate.

7


Dezvoltarea programului, compilarea, testarea funcionrii corecte secveniale i paralele se pot face local, pe staiile din clusterele Linux din laboratorul B125 sau B138. Pe aceste staii se poate vedea c, n general (dar nu chiar la toi algoritmii), timpul de execuie paralel (cu p > 1) este mai mic dect timpul de execuie secvenial (cu p = 1).

Pentru msurarea performanelor i ntocmirea graficelor de performane se va folosi unul din nodurile clusterului HPC Dell-PowerEdge, fiecare din cele 4 noduri avnd P = 16 cores (procesoare).

Msurarea i reprezentarea grafic a performanelor algoritmului. Se copiaz fiierele surs pe HPC n directorul propriu i se recompileaz, tot cu gcc, dar pe 64 biti, folosind biobliotecile corespunztoare. Se realizeaz conectarea ca terminal n HPC, se lanseaz comenzi de execuie i se poate observa cum se modific timpul de execuie paralel atunci cnd crete numrul de procesoare (p =1, 2, 4, 8, 12, 16). Este recomandabil s se realizeze nc o conexiune la HPC, pe care s observai ct din puterea de calcul de 1600% (ale celor 16 cores) se folosete pentru fiecare proces lansnd utilitarul top, care afieaz informaii de execuie ale fiecrui proces activ.

n screenshot-ul de mai sus n primul terminal se vede utilizarea de 399.6 % din puterea de

calcul de procesul Matrix_Mult_Pthread_1 (o variant a programului Matrix_Mult_Pthread), id = 2646 lansat n al doilea terminal.

Pentru reprezentarea graficelor de performane ale algoritmului se execut programul Matrix_Mult_Pthread pentru diferite valori ale dimensiunii matricelor (n) i ale numrului de thread-uri p P (numrul de thread-uri mai mic sau egal cu numrul de procesoare ale nodului de calcul) i la fiecare execuie valorile timpului de execuie paralel se nscriu n fiierul de rezultate.

Pentru execuii repetate se nscriu comenzile ntr-un script bash i se execut. Scriptul de execuie poate fi o simpl niruire de comenzi sau se pot folosi expresii i variabile de scripting care fac modificarea ulterioar mult mai simpl. Exemplu de script simplu pentru execuia repetat: #!/bin/bash rm Res_Matrix_Mult_Pthread_1.txt ./Matrix_Mult_Pthread 16 1 ./Matrix_Mult_Pthread 16 2 ./Matrix_Mult_Pthread 16 4 ./Matrix_Mult_Pthread 16 8

8


./Matrix_Mult_Pthread 16 12


..............................







La execuia acestui script se obine un fiier de rezultate Res_Matrix_Mult_Pthread.txt care conine o matrice de valori ale timpului de execuie: fiecare linie conine valorile pentru un n dat (16, 32, 64, 256, 1024, 4096): n prima coloan p =1, a doua p = 2 etc. 0.000059 0.000211 0.000236 0.000328 0.000396 0.000536 0.000640 0.000649 0.000674 0.000444 0.000329 0.000344 0.000322 0.000460 0.000481 0.000549 0.000702 0.000737 0.003501 0.001889 0.001160 0.000824 0.000811 0.000755 0.000807 0.000838 0.000945 0.209388 0.158418 0.078934 0.051449 0.037777 0.032007 0.027080 0.023197 0.023285 10.431087 5.137667 3.045718 2.150795 1.650737 1.740569 1.200131 0.899486 0.947437 2394.60131 1472.83142 709.23321 551.18817 414.03732 331.57760 276.41073 235.28324 216.63024

Aceste valori pot fi folosite pentru reprezentarea graficelor: TP (p), S(p), E(p), cu parametru n, n Excel, Matlab sau limbajul R. Accelerarea msurat este: S = TP=1/TP, Eficiena: E = S/p

Se poate defini scriptul bash Exec_Matrix_Mult_Pthread mai concis astfel:

#!/bin/bash ########################################################## Exec_file=Matrix_Mult_Pthread Antet_grafic="Program Pthread de inmultire a doua matrice" LISTN="16 32 64 256 1024 4096" LISTP="1 2 4 8 12 16" MOD=0 # Partitionare pe linii MAX_REP=4096 # Numar max repetari executie ########################################################## Source_file="$Exec_file"".c" Exec_command=./$Exec_file Res_file="Res_""$Exec_file"".txt" rm $Exec_file gcc $Source_file -o $Exec_file -lpthread lm echo $Antet_grafic > $Res_file echo $LISTN >> $Res_file echo $LISTP >> $Res_file for i in $LISTN do REP=`expr $MAX_REP / $i` for j in $LISTP do $Exec_command $i $j $MOD $REP done done

La execuia acestui script se terge mai nti fiierul executabil (Matrix_Mult_Pthread), se compileaz programul surs se scrie un antet n fiierul de rezultate Res_Matrix_Mult_Pthread.txt, apoi se lanseaz aceeai secven de execuii ale programului i la fiecare execuie se nscrie valoarea

9


timpului de execuie n fiierul de rezultate. Se obine acelai fiier de rezultate (timpii pot avea, totui unele variaii datorit condiiilor de msur) care conine n plus un antet care cu numele programului programului, o linie cu lista valorilor lui n i o linie cu lista valorilor lui p: Program Pthread de inmultire a doua matrice 16 32 64 256 1024 4096 1 2 4 6 8 10 12 14 16

0.000059 0.000211 0.000236 0.000328 0.000396 0.000536 0.000640 0.000649 0.000674 0.000444 0.000329 0.000344 0.000322 0.000460 0.000481 0.000549 0.000702 0.000737 0.003501 0.001889 0.001160 0.000824 0.000811 0.000755 0.000807 0.000838 0.000945 0.209388 0.158418 0.078934 0.051449 0.037777 0.032007 0.027080 0.023197 0.023285 10.431087 5.137667 3.045718 2.150795 1.650737 1.740569 1.200131 0.899486 0.947437 2394.60131 1472.83142 709.23321 551.18817 414.03732 331.57760 276.41073 235.28324 216.63024

Programul R care poate realiza graficele pornind de la acest fiier este dat n subdir. Grafice.

b) Se lanseaza rstudio din directorul n care se afl fiierul de rezultate (Matrix_Mult).

c) Se incarc (cu FileOpen) fisierul Grafice.R din directorul Grafice e) n programul surs (fereastra stnga sus din mediul Rstudio) se seteaz numele fisierului de

rezultate prin instruciunea (de exemplu): rn


11


Interpretarea rezultatelor. Graficele TP: Pentru o valoare constant a lui n, TP scade atunci cnd crete p, ceea ce este normal; pentru o valoare constant a lui p, TP crete atunci cnd crete n. Graficul este scalat pe valorile maxime (pentru n = 4096) i celelalte curbe au valori mult mai mici i nu se poate urmri forma exact. Pentru detalieri se pot extrage valorile de interes din matricea de valori din fiierul de rezultate. Graficele S: Pentru n mic (16, 32) timpul de execuie paralel este mai mare dect timpul de execuie secvenoial i se vede c accelerarea este subunitar. Cnd n este suficient de mare (n > 256), accelerarea este foarte bun, se apropie de accelerarea ideal S = p (linia punctat n grafic). n general, pentru n constant, accelerarea are un maxim, la valori care cresc cu creterea lui n. Pentru p constant, accelerarea crete atunci cnd crete n (cu unele imprecizii de msur). Graficele E: Pentru n constant, eficiena scade atunci cnd p crete; pentru p constant eficiena crete atunci cnd crete n.

Exerciiul E2.2.a. Parcurgei toate etapele de dezvoltare a algoritmului de nmulire a dou

matrice cu partiionare pe linii cu partiii continue descrise n aceast seciune i executai pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind scriptul Exec_Matrix_Mult_Pthread i reprezentai graficele TP (p), S(p), E(p) folosind programul Grafice.R .

2.2.2. nmulirea a dou matrice cu alte partiionri Algoritmii care pot fi descompui n task-uri independente (ntre care nu exist dependene) se

numesc algoritmi perfect paraleli (embarasing parallelism) i se paralelizeaz prin partiionarea sarcinii de calcul ntre mai multe thread-uri, fr mecanisme de sincronizare ntre ele. Exemple de algoritmi perfect paraleli: nmulirea matricelor, adunarea matricelor, adunarea a doi vectori etc.

n seciunea precedent a fost studiat algoritmul de nmulire a dou matrice cu partiionare pe linii cu partiii continue. Mai exist i alte posibiliti de partiionare care sunt implementate tot n fiierul Matrix_Mult_Pthread.c.

Pentru diferite moduri de partiionare, partea de program de definire a datelor, msurare a timpului etc. este comun, difer funcia thread-ului.

nmulirea a dou matrice cu partiionare pe linii ntreesute (mod = 1). n acest mod de partiionare cu p thread-uri, thread-ului 0 revin iteraiile: 0, p, 2p...; thread-ului 1 i revin iteraiile 1, (1+p), (1+2p)...; n general thread-ului q i revin iteraiile: q, (q+p), (q+2p)... Funcia thread-ului este: // Mod 1 - Inmultire paralela cu partitionare pe linii intretesute void *Matrix_Mult_line_interlaced (void *param) { int i, j, k, q = *(int*)param; for(i = q; i < n; i+=p) 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]; } return 0; }

Inmulirea a dou matrice cu partiionare pe coloane dup interschimb bucle (mod = 2). Cea mai simpl modalitate de nmulire a dou matrice cu partiionare pe coloane se obine dup interschimbarea primelor dou bucle ntre ele, posibil deoarece buclele sunt perfect imbricate i fr dependene ntre iteraii.

Dup interschimb, bucla (j) de coloane este exterioar i distribuirea iteraiilor ei ntre p thread-uri produce un algoritm cu o singur regiune paralel, asemntor cu algoritmul cu partiionare pe linii.

12


Inmultirea a dou matrice cu partitionare pe coloane cu n regiuni paralele (mod = 3). O alt modalitate de partiionare pe coloane: se distribuie iteraiile buclei de parcurgere a coloanelor (j), care este o bucl imbricat n bucla exterioar. n implementarea cu thread-uri POSIX, thread-ul principal parcurge n iteraii (pe linii) i n fiecare iteraie creeaz o regiune paralel de p thread-uri;

Ca parametri ai funciei thread-ului se transmit linia i (n data membr line) i partiia q (n data membr col) a unei structuri de tip group: typedef struct _group{ int line; int col; } group;

Inmultirea a dou matrice cu partitionare pe coloane cu 1 regiune paralel (mod = 4). Pentru transformarea algoritmului cu n regiuni paralele n algoritm cu 1 regiune paralel se reunesc cele n iteraii pentru fiecare partiie de coloane: funcia thread-ului parcurge n iteraii (pe linii) i n fiecare iteraie calculeaz s elemente ale celor s coloane j (q*s j < (q+1)*s) ale partiiei (q) din linia curent (i). Buclele fiind independente, nu sunt necesare bariere de sincronizare

n acest caz, thread-ul principal (main) creeaz o singur regiune paralel, cu p thread-uri, la fel ca la algoritmii precedeni.

Inmultirea a dou matrice cu partitionare n blocuri cu 1 regiune paralel (mod = 5). Pentru proiectarea unui algoritm de nmulire a dou matrice cu partiionare in blocuri:

Se definesc p blocuri ale matricei c, organizate ca o matrice cu p1/2 x p1/2 blocuri-uri, numerotate cu doi indici q i r; fie p ptrat perfect, f = p1/2, n divizibil cu p1/2, d = n/ p1/2

Se creeaz p thread-uri; thread-ul Tt (0 t < p) calculeaz blocul corespunztor partiiei q de linii i partiiei r de coloane

Exerciiul E2.2.b. Studiai programul folosind textul surs Matrix_Mult_Pthread.c, executai pentru fiecare mod de partiionare pe staia Linux i pe HPC i comparai rezultatele. n scriptul de execuie Exec_Matrix_Mult_Pthread 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.

2.3. Adunarea a doi vectori Algoritmul secvenial de adunare a doi vectori x i y de dimensiune n, cu rezultat n y:

for (i = 0; i < n; i++) y[i] = y[i] + x[i]; Algoritmul const dintr-o bucl simpl i are timpul de execuie secvenial TS = n = O(n). S-a demonstrat c iteraiile sunt independente, paralelizarea se poate face prin distribuirea

iteraiilor buclei: se distribuie sarcina de calcul n p n task-uri, fiecare task Tq este asignat thread-ului Thq care execut operaiile partiiei (q), 0 q < p.

Pentru n divizibil cu p i o partiionare cu partiii continue (elemente consecutive), fiecare thread Thq va calcula s = n / p elemente, ncepnd cu elemente q*s pn la (q+1)*s (exclusiv acesta din urm). n cazul general se testeaz divizibilitatea lui n cu p i, dac n nu este divizibil cu p se aloc s = (int) n / p iteraii primelor k = n%p thread-uri i s+1 iteraii celorlalte (p k) thread-uri.

Variabilele globale i funciile thread-ului pentru partiionare cu partiii continue i ntreesute:

#include // Variabile globale partajate int n = 1024; // Dimensiune vectori int p = 2; // Numar thread-uri float *x, *y; // Vectorii de date 13


void *Vector_Add(void *param) { // partitii continue int first, last; int i, q = *(int*)param; int s = (int) n/p; int k = n%p; // Calcul first, last limitele partiiei ... for (i = first; i < last; i++) y[i] = y[i] + x[i]; return 0; } void *Vector_Add_interlaced (void *param){ // partitii intretesute int i, q = *(int*)param; for (i = q; i < n; i+=p) y[i] = y[i] + x[i]; return 0; }

Exerciiul E2.3. Dezvoltai programul Vector_Add_Pthread.c, executai pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind scriptul un script (Exec_Vector_Add_Pthread) asemntor cu scriptul pentru nmulire, 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.

2.4. Adunarea a dou matrice Algoritmul secvenial de adunare a dou matrice ptrate a i b de dimensiuni n x n:

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

Algoritmul const dintr-o bucl imbricat pe dou niveluri i are timpul de execuie secvenial (complexitatea) TS = n2 = O(n2).

Se demonstreaz uor c iteraiile acestor bucle sunt independente, de aceea paralelizarea se poate face prin distribuirea iteraiilor primei bucle, a celei de-a doua bucle sau a ambelor bucle, la fel ca la algoritmul de nmulire a dou matrice. Totui, partiiile matricelor difer fa de partiiile de la nmulire. n figura de mai jos este reprezentat partiionare pe linii cu partiii continue pentru adunarea paralel a dou matrice.

Programul Matrix_Add_Pthread.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, funcia thread-ului pentru partiionare orientat pe linii ntreesute (mod 1): // Mod 1 - Adunare paralela cu partitionare pe linii intretesute void *Matrix_Add_line_interlaced(void *param) { int i, j, q = *(int*)param; for(i = q; i < n; i+=p) for (j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j]; return 0; }

14


Matricea a Matricea b Matricea c

0

q ...

...

p = 4

Adunarea a dou matrice cu partiionare pe linii, cu partiii continue

Exerciiul E2.4. Dezvoltai programul de adunare a dou matrice Matrix_Add_Pthread.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_Pthread 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

2.5. Excluderea mutual mutex-uri n sistemele cu memorie partajat nu sunt admise scrieri concurente nesincronizate n variabile

partajate. Dac se ncearc scrierea concurent (n acelai ciclu instruciune) ntr-o variabil partajat, circuitele de arbitrare ale memoriei serializeaz accesele ntr-o ordine de execuie impredictibil i deci cu valoare rezultat impredictibil.

De aceea accesul nesincronizat la variabile partajate a dou sau mai multe procese (thread-uri) concurente poate produce erori de execuie, dac exist dependene ntre task-urile implementate prin procesele (thread-urile) concurente (Anexa Sincronizarea ntre procese). Sincronizarea ntre procese (thread-uri) se poate face n mai multe moduri:

Excludere mutual (mutex-uri) - rezolv dependenele prin ieire (Anexa Sincronizarea ntre procese)

Bariere de sincronizare - rezolv dependenele prin succesiune ntre procesele (thread-urile) unei regiuni paralele: orice proces (thread) care a ajuns la bariera de sincronizare este blocat i ateapt pn cnd ce ajung toate procesele (thread-urile) la barier, i numai dup aceea poate continua execuia.

Semafoare - rezolv dependenele prin resurse sau de control. Astfel de mecanisme de sincronizare sunt implementate eficient cu suport hardware:

instruciuni atomice (nentreruptibile) ale procesoarelor cum sunt: Test-And-Set, Compare-And-Swap, Fetch-And-Add.

Mutex-ul (contragere - mutual exclusion), sau lock-ul (zvor), este un mecanism de excludere mutual, care controleaz accesul la o variabil partajat. Un mutex este compus (principial) dintr-o variabil partajat (mutex), i funcii care permit executarea urmtoarelor operaii:

lock - este operaia de obinere a mutex-ului, executat de un thread care dorete s execute seciunea critic de acces la variabila partajata corespunztoare.

unlock - este operaia de eliberare a mutex-ului, executat de thread-ul care deine mutex-ul, dup terminarea seciunii critice .

15


La execuia unei operaii de lock de ctre un thread, pot s apar dou situaii: (a) Dac mutex-ul este liber, thread-ul apelant ocup mutex-ul i se revine din funcia lock

imediat, ntr-o operaie atomic.

(b) Dac mutex-ul este ocupat, thread-ul apelant ateapt pn cnd mutex-ul este eliberat (de un alt thread, care l deinea), dup care l ocup.

Pentru serializarea accesului thread-urilor la variabila partajat v, prin execuia seciunii critice controlat de un mutex m, trebuie respectat protocolul: lock (m) Executie sectiune critic de acces la variabila v unlock (m)

n biblioteca Pthread un mutex se definete prin: Variabila de tipul opac: pthread_mutex_t Atribute, date printr-o structur de tipul: pthread_mutexattr_t Funcii: int pthread_mutex_init (pthread_mutex_t *m, pthread_mutexattr_t *atr) int pthread_mutex_lock (pthread_mutex_t *m) int pthread_mutex_unlock (pthread_mutex_t *m)

Algoritmul de reducere paralel. Algoritmul secvenial: fiind date n valori ca elemente ale vectorului a[n] i operatorul asociativ de adunare, rezultatul reducerii se obtine n variabila sum astfel: sum = 0; for (i = 0; i < n; i++) sum += a[i];

Timpul de execuie secvenial este TS = n = O(n) - se consider ca operaie de baz adunarea a dou nrumere reale, se neglijeaz indexrile, asignrile, control bucle.

Fiecare iteraie scrie n aceeai variabil (sum) deci exist dependene prin ieire ntre iteraii. Algoritmul nu poate fi paralelizat direct (prin distribuirea iteraiilor), de aceea se modific astfel nct s se poat obine un algoritm paralel adaptiv cu p task-uri.

Deoarece dependena ntre iteraii este cauzat de faptul c toate task-urile scriu n aceeai variabil de ieire (sum), se mrete dimensiunea datelor de ieire, definind o variabil n care se calculeaz rezultate pariale (psum). Se obine astfel un algoritm secvenial de reducere paralelizabil: sum = 0; for (q = 0; q < p; q++) { // Etapa 1 : reducere partiala (locala) in partitia q psum = 0; for (m = 0; m < s; m++) psum += a[q*s + m]; // Etapa 2 : acumulare suma partiala la rezultatul global sum += psum; }

Pentru paralelizarea acestui algoritm se mparte vectorul a n p partiii i fiecrei partiii q (0 q < p) i se atribuie un task Tq compus din subtask-uri Tq,1 i Tq,2 care parcurg cele dou etape.

n implementarea Pthread (Reduction_Pthread.c), cele p task-uri se atribuie la p thread-uri de lucru, care execut funcia thread-ului cu cele dou etape:

n prima etap fiecare thread execut o reducere parial n variabila local psum. n etapa a doua se execut reducerea global: fiecare thread Tq adun suma parial proprie

(din psum) la rezultatul total (sum) folosind un mutex care serializeaz operaiile de scriere.

16


Variabilele globale partajate i funcia thread-ului sunt: // Reduction_Pthread.c #include // Variabile globale partajate int n = 1024; // Dimensiune matrice int p = 2; // Numar thread-uri float *a; // Vectorul de date double sum = 0.0; // Suma globala pthread_mutex_t mutex; // Mutex-ul // Functia thread-ului void * Reduction(void *param) { double psum = 0; // Suma partiala (locala) int i, first, last; int q = *(int*)param; int s = (int) n/p; int k = n%p; // Calcul first, last limitele partitiei ... // Etapa 1 : reducerea partiala (in partitie) for(i = first; i < last; i++) psum += a[i]; // Etapa 2: reducere globala folosind un mutex pthread_mutex_lock(&mutex); sum += psum; pthread_mutex_unlock(&mutex); return 0; }

n funcia main() se aloc i se iniializeaz datele, se iniializeaz mutex-ul prin apelul funciei: pthread_mutex_init(&mutex,0); unde argumentul 0 pentru atributele mutex-ului nseamn atribute implicite, apoi se creeaz thread-urile, la fel ca n toate celelalte programe.

nsumarea (acumularea) datelor se face n variabile de tip double (sum i psum), pentru a nu se pierde din precizia de calcul.

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

2.6. Bariere de sincronizare O barier de sincronizare ntre p task-uri paralele este un mecanism prin care, atunci cnd un

task ajunge n punctul de barier, este blocat i trebuie s atepte pn cnd toate celelalte (p -1) task-uri au ajuns i ele la barier. Ultimul task ajuns la barier le deblocheaz pe toate celelalte, aflate n ateptare.

Majoritatea bibliotecilor de programare paralel, att cele prin memorie partajat ct i cele prin transfer de mesaje, includ bariere de sincronizare.

n biblioteca Pthread o barier ntre p thread-uri se definete prin:

17


Variabila de tipul: pthread_barrier_t Atributele barierei structura de tipul: pthread_barrierattr_t Funcii pentru o barier ntre p thread-uri: int pthread_barrier_init(pthread_barrier_t *b, pthread_barrierattr_t *atr, int p); int pthread_barirer_wait(pthread_barrier_t *b); nmulirea succesiv a matricelor. Un exemplu de folosire a unei bariere de sincronizare este nmulirea succesiv a matricelor: c = a x b; e = d x c , cu algoritmul secvenial: 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]; } for (i = 0; i < n; i++) for (j = 0; j < n; j++){ e[i][j] = 0; for (k = 0; k < n; k++) e[i][j] += d[i][k] * c[k][j]; }

Algoritmul este compus din dou bucle succesive; se paralelizeaz fiecare bucl ca o nmulire a dou matrice cu partiionarea orientat pe linii; se obin p task-uri T0,q, pentru prima bucl i p task-uri T1,q pentru a doua bucl (0 q < p). ntre cele dou bucle exist dependene prin succesiune: trebuie ca prima bucl s se termine i matricea c s fie complet calculat pentru ca s poat s nceap cea dea-a doua operaie de nmulire.

n implementarea Pthread cu o singur regiune paralel a nmulirii succesive a matricelor se introduce o barier de sincronizare ntre cele dou operaii de nmulire.

Variabilele partajate i funcia thread-ului sunt: // Many_Matrix_Mult_Pthread.c #include // Variabile globale partajate int n = 1024; // Dimensiune matrice int p = 2; // Numar thread-uri float **a, **b, **c, **d, **e; // Matricele pthread_barrier_t bariera; // Bariera de sincronizare

// Functia thread-ului void * Many_Matrix_Mult (void *param) { int i, first, last; int q = *(int*)param; int s = (int) n/p; int k = n%p; // Calcul first, last limitele partitiei ... for (i = first; i < last; 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]; } pthread_barrier_wait(&bariera)

18


for (i = first; i < last; i++) for (j = 0; j < n; j++){ e[i][j] = 0; for (k = 0; k < n; k++) e[i][j] += d[i][k] * c[k][j]; } return 0; }

n funcia main() se aloc i se iniializeaz datele, se iniializeaz bariera prin apelul funciei: pthread_barrier_init(&bariera,0, p); unde argumentul 0 pentru atributele barierei nseamn atribute implicite, apoi se creeaz thread-urile, la fel ca n toate celelalte programe.

Exerciiul E2.6. Implementai algoritmul de nmulire succesiv a matricelor folosind

biblioteca Pthread, n mod asemntor cu inmulirea a dou matrice. Executai programul pe staia Linux i pe HPC. Generai matricea de valori ale timpului de execuie folosind un script Exec_Many_Matrix_Mult_Pthread pentru aceleai valori ale lui p (1, 2, 4, 8, 12, 16) i n = (16, 32, 64, 256, 1024, 4096). Reprezentai graficele performanelor TP (p), S(p), E(p) folosind Grafice.R.

Bibliografie 1. Felicia Ionescu, Calcul paralel, 2014, slide-uri publicate pe site-ul moodle ETTI. 2. Felicia Ionescu, Calcul paralel, Anexe, publicate pe site-ul moodle ETTI. 3. B. Barney, POSIX Threads Programming, Lawrence Livermore National Laboratory, 2013, https://computing.llnl.gov/tutorials/pthreads/ 4. W.N.Venables, An Introduction to R, R Core Team

19

L2_Aplicatii_Pthread

Documents

Transcript of L2_Aplicatii_Pthread