APD - Lab1
2007 programare (impartire problema in subprobleme) Firele de executie se creeaza in cadrul unui proces si se creeaza mai repede decat procesele. Algoritmi paraleli si distribuiti, curs an 5 Corina Stratan: corina@cs.pub.ro Limbaje pentru prelucrare paralela: SR, Paralaxis, biblioteci pentru programe C Ex: - OpenMP: creare de fire de executie; OpenMP e portabil (pthreads din C e specific Linux) - MPI: message passing interface: pe sisteme distribuite, intre care se schimba mesaje - Java: suporta nativ fire de executie Comunicarea se poare face: - In fire de executie separate, cu resurse partajate Prin mesaje, intre procese, eventual chiar intre masini separate - Open MP Compilator: Omni Open MP Comanda: ompcc (similar gcc): ex "ompcc -o program program.c" De inclus header: #include <omp.h> De setat o variabila de mediu: "export OMPC_NUM_PROCS = 5" Numarul de fire de executie nu trebuie sa fie fix, depinzand de masina pe care ruleaza. Open MP incearca sa aloce automat firele de executie. Program OpenMP: fork-join Pretate la cicluri mari. Fork la creare de fire, join la terminarea calculelor. Directive pragma: pentru compilator, optiuni specifice date de programator; compilatorul ce nu recunoaste pragma-urile le ignora Directivele actioneaza asupra unei regiuni de cod, intre {}. Pentru o linie de cod sau o singura instructiune compusa nu e nevoie de {}. #pragma omp <directiva> [clauze] Directiva de creare a unei regiuni paralele: #pragma omp parallel //cod { } #pragma omp parallel num_threads(5) Sau: Apelata inaintea crearii regiunii paralele. La directiva parallel se creeaza automat 5 threaduri. omp_set_num_threads(5); 1: dinamic, 0: static Setarea din variabila de mediu il face sa considere automat ca are atatea procesoare cate s-au specificat, nu mai e nevoie de dynamic omp_set_dynamic(0); Cate threaduri sunt in mod curent Rulat in regiune paralela, arata cate threaduri ruleaza acolo; in afara regiunii paralele (ar trebui sa arate) numarul definit la set_num_threads() int omp_get_num_threads(); Ce id are thradul curent int omp_get_thread_num(); Program OpenMP de adunare a doi vectori: Primul thread aduna primele x elemente, al doilea urmatoarele y, etc… vectorul A+B=C #pragma omp parallel Int id, I, Nthreads, istart, iend; //indici intre care ruleaza fiecare thread Id = omp_get_thread_num(); Nthreads = omp_get_num_threads(); Istart = id * N / Nthreads; Iend = (id+1) * N / Nthreads; c[i]=a[i]+b[i]; For(i=istart, i<iend;i++) { } Clauze: optiuni la directive Va incepe sa execute in paralel cu toate threadurile disponibile zona de cod. Forteaza 5 threaduri. De fapt va aloca atatea threaduri cate procesoare are, deci poate sa aloca mai putine (5 e un maxim). a b c N elemente Pot fi impartite in mod egal intre threaduri istart iend A Alta directiva, for, generaaza threadurile automat: #pragma omp parallel #pragma omp for c[i]=a[i]+b[i]; For(i=0, i<N, i++) Race condition: rezultat nedeterminist Diferenta fata de cod in afara "parallel": executata de mai multe threaduri, dar nu simultan Codul din afara "parallel" este executat o singura data doar de threadul master. Regiune critica: secventa de cod care nu poate fi executata la un moment dat decat de un singur thread La sfarsitul regiunii paralele este o bariera implicita; nu se iese din directiva parallel sau for pana cand n-au ajuns toate threadurile acolo Bariera: punct In program la care se asteapta toate threadurile sa ajunga inainte de a se trece mai departe #pragma omp critical { { #pragma omp barrier { } Obs: #pragma omp parallel for Iterativ: #include<stdio.h> #include<stdlib.h> #include <omp.h> static long num_steps = 10000; double step; void main() int I; double x,pi,sum=0.0; step = 1.0/(double)num_steps; for(i=1;i<num_steps;i++) x=(i-0.5)*step; sum=sum+4.0/(1.0+x*x); { } pi=step*sum; { } pentru paralelizare, s-ar putea pune sum= intr-o regiune critica altfel, un vector de sume si fiecare thread calculeaza suma lui sau, ce operatie se face la reducere (adunare) si cu ce variabila (sum) #pragma parallel for reduction(+:sum) Reducere = operatia de reunire a threadurilor Paralelizare: (in shell: ) export OMPC_NUM_PROCS=4 (fara export-ul de mai sus, programul da eroare la rulare spunand ca nu poate aloca 4 threaduri, conform lui opm_set_num_threads(), ci doar unul) #include<stdio.h> #include<stdlib.h> #include <omp.h> static long num_steps = 10000; double step; int main() int i; double x,pi,sum=0.0; step = 1.0/(double)num_steps; omp_set_num_threads(4) { #pragma omp parallel for reduction (+:sum) for(i=1;i<num_steps;i++) x=(i-0.5)*step; sum=sum+4.0/(1.0+x*x); { } { pi=step*sum; } } ....................................
Salut, am nevoie de putin ajutor cu un program in C. Am scris varianta secventiala si acum vreau sa il fac in paralel cu openmp. Codul arata ceva de genul.Am nevoie de o marire dependenta de numarul de threaduri, spre ex pt 2 threaduri sa ruleze de 2 ori mai repede,cum e si normal. Aceasta este doar bucata de cod din main care conteaza , mai sus am doar declaratii si citire din fisier. Daca se pricepe cineva si ma poate ajuta cu scrierea lui corecta, nu ma pricep asa bine cu openmp.Thx
Cod:
int an_curent=1;
#pragma omp parallel shared(resurse,preturi,buget,cost_minim,costres_minim) private(i,j,k,l)
while(an_curent <= nr_ani){
//resetare valori ce tin costul,contorii resurselor
for(i=0;i<nr_ani;i++){
resurseA[i]=0;
resurseB[i]=0;
pretmaxA[i]=0;
pretmaxB[i]=0;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++){
cost_minim[i][j]=50000;
costres_minim[i][j]=50000;
}
//activitati anuale
#pragma omp for
for(i=0;i<n;i++)
for(j=0;j<n;j++){
//int cost_minim=100; //pastrez costul cel mai mic al resurselor complementare gasite
int cost_curent=0; //costul resursei gasite la pasul curent
int resursa_complement;
if(resurse[i][j] == 0)
resursa_complement=1;
if(resurse[i][j] == 1)
resursa_complement=0;
//caut printre colonisti cine are resursa de tipul resursa_complement
for(k=0;k<n;k++)
for(l=0;l<n;l++){
//caut cost complementar minim
if(resurse[k][l] == resursa_complement){ //am gasit un colonist cu resursa necesara
cost_curent=preturi[k][l] + dist(i,k,j,l);
if(cost_curent < cost_minim[i][j]){
//printf("fost cost=%d,nou cost=%d\n",cost_minim,cost_curent);
cost_minim[i][j]=cost_curent;
}
}
//caut costRes minim
if(resurse[k][l] ==(1- resursa_complement)){ //am gasit un colonist cu resursa necesara
cost_curent=preturi[k][l] + dist(i,k,j,l);
if(cost_curent < costres_minim[i][j]){
//printf("fost cost=%d,nou cost=%d\n",cost_minim,cost_curent);
costres_minim[i][j]=cost_curent;
}
}
}//end for k
}//end for i
//verific cost vs buget pentru colonistul curent
#pragma omp for
for(i=0;i<n;i++)
for(j=0;j<n;j++){
int buget_curent=buget[i][j];
if(cost_minim[i][j] > buget_curent){
preturi[i][j]=preturi[i][j]+cost_minim[i][j] - buget[i][j];
buget[i][j]=cost_minim[i][j];
if(preturi[i][j] > pmax){
resurse[i][j]=1-resurse[i][j];
buget[i][j]=pmax;
preturi[i][j]=(pmin + pmax)/2;
}
}
if(cost_minim[i][j] < buget_curent){
preturi[i][j]+=(cost_minim[i][j]-buget[i][j])/2;
buget[i][j]=cost_minim[i][j];
if(preturi[i][j] < pmin)
preturi[i][j] = pmin;
}
if(cost_minim[i][j] == buget_curent){
preturi[i][j]=costres_minim[i][j]+1;
if(preturi[i][j] > pmax){
resurse[i][j]=1-resurse[i][j];
buget[i][j]=pmax;
preturi[i][j]=(pmin + pmax)/2;
}
}
}
//numar colonistii cu resurseA ,resp resurseB
#pragma omp for
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(resurse[i][j] == 0){
#pragma omp atomic
resurseA[an_curent-1]+=1;
}
if(resurse[i][j] == 1)
#pragma omp atomic
resurseB[an_curent-1]+=1;
}
//caut pretul maxim al resursei A resp al resurseiB
#pragma omp for
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(resurse[i][j] == 0){
if(preturi[i][j] > pretmaxA[an_curent-1])
pretmaxA[an_curent-1]=preturi[i][j];
}
if(resurse[i][j] == 1){
if(preturi[i][j] > pretmaxB[an_curent-1])
pretmaxB[an_curent-1]=preturi[i][j];
}
}
char line[128];
sprintf(line,"%d %d %d %d\n",resurseA[an_curent-1],pretmaxA[an_curent-1],resurseB[an_curent-1],pretmaxB[an_curent-1]);
writeToFile(out,line);
if(an_curent==nr_ani)
#pragma omp for
for(i=0;i<n;i++){
for(j=0;j<n;j++){
sprintf(line,"(%d,%d,%d) ",resurse[i][j],preturi[i][j],buget[i][j]);
writeToFile(out,line);
}
writeToFile(out,"\n");
}
an_curent++;
}
| |
 |   |
 03.11.2012, 22:45 | #2 |
Senior Member
Locație: Iasi
Posturi: 430
Putere Rep: 12
Reputație: 351  |
Nou
Ok, să-ți scriu câteva idei. Începem cu începutul, și anume:
1. Executarea în paralel a unui set de operații pe n thread-uri nu va fi niciodată de n ori mai rapidă; aceasta findcă crearea acestor thread-uri consumă și ea timp. Astfel, un spor de performanță se poate observa doar pentru thread-uri cu un număr mare/foarte mare de pași. În cazul în care se crează tread-uri separate pentru un număr mic de operații, se vor înregistra scăderi de performanță. 2. Codul de mai sus... nu e foarte ordonat; iar variabilele nu au nume foarte sugestive. Încearcă, în primul rând, să-l grupezi în câteva funcții separate; e destul de greu datorită operațiilor și for-urilor paralele, dar măcar pașii principali ai algoritmului. 3. Strâns legat de (2), cred că tu scrii cod C, iar în exemplul tău ai câteva artificii care sunt permise doar în C++, și anume declararea unor variabile locale în corpul funcției, dar nu la începutul acesteia. 4. Ne-ar ajuta enunțul problemei (cel puțin pentru a înțelege denumirile variabilelor). De obicei funcționează varianta cu rezolvarea problemei inițial secvențial și-apoi modificare în paralel. 1. Nu prea ajută creare de operații paralele în interiorul altor operații paralele; trebuie ținut oarecum cont și de faptul că un procesor are un număr limitat de nuclee și thread-uri (fizice). Astfel un număr foarte mare de thread-uri în paralel nu prea ajută; mai mult, trebuiesc evitate operațiile de creare și distrugere ale acestora. Ca și obiectiv/mod de rezolvare: atunci când ai un număr de câteva for-uri (sau alte instrucțiuni repetitive) imbricate, trebuie să-ncerci să faci paralel doar for-ul de la exterior (sau cât mai la exterior posibil, în funcție de algoritm). 2. Trebuiesc identificate resursele (variabilele) folosite în operațiile executate în paralel și clasificarea acestora în funcție de modul în care acestea sunt folosite: - resurse folosite individual (private) pe fiecare thread în parte, de exemplu contorii (i, j) folositi pentru parcurgerea unui tablou; - resurse comune (de obicei shared) pe mai multe thread-uri, de exemplu un tablou parcurs în paralel. 3. Se pune întrebarea: rezultatele obținute pe un thread sunt direct influențabile de operațiile executate pe alt thread? Se pot obține astfel rezultate false? Mi-e greu să fac această întrebare clară. Ține în primul rând de variabilele shared; dacă acestea sunt modificate pe un thread, rezultatele calculelor efectuate pe un al doilea thread vor mai fi corecte, presupunând că acesta a luat valorile modificate? În plus, dacă nu se specifică (prin niște directive mai pompoase) ordinea în care se vor executa thread-urile, aceasta va fi aleatoare/necunoscută. * De menționat că este de preferat folosirea #parallel for în locul unui simplu #parallel, acolo unde este posibil; în cazul #parallel for, contorul din interiorul forului este implicit variabilă private. Sunt sigur că am menționat mai multe lucruri pe care, de voie, de nevoie, le știai deja, dar e bine să le ai notate undeva, să fie clare, să nu le uiți.
__________________
HARDWARE = Parte a unui calculator pe care o lovesti cand apar probleme de software. |
No comments:
Post a Comment