Cutie cu nisip

mreana amuzantă 25 iulie 2011 la ora 00:59

Înmulțirea matricei paralele sau magie cache. Puțină cercetare

Introducere

Acest articol este despre un mic studiu care a fost realizat din pură curiozitate. Dar pentru că rezultatele au fost interesante, am decis să le public. Elementele de bază ale calculului paralel au fost discutate folosind o sarcină simplă și convenabilă: înmulțirea matricelor.

Sunt mai multe poze sub tăietură!

În mod formal, sarcina este stabilită după cum urmează:
Având în vedere două matrice A și B de dimensiunea NxN. Este necesar să se calculeze produsul lor: matricea C.
C[i][j] = suma peste k de la 1 la N A[i][k]*B[k][j].

Soluție fără calcul paralel

Cel mai simplu algoritm pentru rezolvarea acestei probleme cu asimptotice este următorul:

pentru (int i = 0; i< n; ++i)
pentru (int j = 0; j< n; ++j){
c[i][j] = 0;
pentru (int k = 0; k< n; ++k)
c[i][j] = a[i][k]*b[k][j];
}

Există un truc binecunoscut care vă permite să accelerați codul de mai sus de 4-5 ori. Aceasta este înlocuirea matricei b cu matricea bt, care conține matricea transpusă B:

pentru (int i = 0; i< n; ++i)
pentru (int j = 0; j< n; ++j)
bt[i][j] = b[j][i];
pentru (int i = 0; i< n; ++i)
pentru (int j = 0; j< n; ++j){
c[i][j] = 0;
pentru (int k = 0; k< n; ++k)
c[i][j] = a[i][k]*bt[j][k];
}

* Acest cod sursă a fost evidențiat cu Sursa de evidențiere a codului .

Accelerația în acest caz este legată de designul cache-ului procesorului. Când accesați o celulă de memorie, nu numai aceasta, ci și câteva celule învecinate sunt scrise în cache. În primul caz, elementele matricei b, pe care le accesăm în buclă prin k, sunt în rânduri diferite, dar în aceeași coloană și, prin urmare, în RAM sunt situate la o distanță egală cu dimensiunea unui rând al matricei. În cel de-al doilea caz, accesăm secvențial elementele unei linii ale matricei bt, care sunt situate în memorie într-un rând.

Soluție de calcul paralel

Deoarece fiecare element al matricei C este calculat independent de celelalte și matricele A și B nu se modifică, pentru a calcula produsul în paralel, este suficient să indicați pur și simplu ce elemente din C la care fir să se calculeze.
În acest scop, a fost creată o funcție care primește 2 numere: lf și rg. Funcția calculează rândurile matricei C de la lf la rg inclusiv, folosind matricea originală B:

#definiți forn(i, n) pentru (int i = 0; i< int (n); ++i)

struct matrixMulParam(
int lf, rg;
matrixMulParam(int cLf = 0, int cRg = 0) : lf(cLf), rg(cRg)()
};

DWORD matrixMulNoHack(LPVOID p)(
pentru (int i = ((matrixMulParam*)p)->lf; i<= ((matrixMulParam*)p)->rg; ++i)
forn(j, n)(
c[i][j] = 0;
forn(k, n)
c[i][j] += a[i][k] * b[k][j];
}

Delete ((matrixMulParam*)p);
întoarce 0;
}

* Acest cod sursă a fost evidențiat cu Sursa de evidențiere a codului .

În același mod, o funcție a fost scrisă folosind o matrice transpusă.

Colectarea datelor privind timpul de funcționare

Calculele au fost efectuate pe 4 diferite calculatoare cu procesoare diferite:

1. Intel Atom N550
   • Frecvența ceasului: 1,5 GHz
   • Număr de nuclee: 2
   • Numar de fire: 4
     Aceasta nu este o greșeală de tipar. Aici este un link către site-ul web Intel și aici sunt capturi de ecran ale Managerului de activități și Managerului de dispozitive al netbook-ului meu
   • Dimensiunea cache L2: 1 MB
2. Intel Core2Duo P8600
   • Frecvența ceasului: 2,4 GHz
   • Număr de nuclee: 2
   • Numar de fire: 2
   • Dimensiunea cache L2: 3 MB
3. Intel Core2Quad Q6600
   • Frecvența ceasului: 2,4 GHz
   • Număr de nuclee: 4
   • Numar de fire: 4
   • Dimensiunea cache L2: 8 MB
4. Amazon EC2 High-CPU Extra Large Instanță,
   aproximativ egală ca putere cu cel de-al doilea Intel Xeon E5410
   • Frecvența ceasului: 2,33 GHz
   • Număr de nuclee: 4 (8 în total)
   • Număr de fluxuri: 4 (8 în total)
   • Dimensiunea memoriei cache L2: 12 (24 în total) MB

Pentru a obține statistici, au fost variați următorii parametri:

• Dimensiunea matricei: 1000x1000 sau 2000x2000.
  Matricele au fost umplute cu numere întregi pseudoaleatoare de la 1 la 1000.
• Număr de fire de la 1 la 16.
• Folosind matricea B originală sau una transpusă.

Pentru fiecare combinație a parametrilor specificați, calculele au fost efectuate de cel puțin 5 ori, iar ca rezultat a fost utilizată media aritmetică a timpilor de rulare a programului.

Rezultate

Din moment ce mă uitam la diferite procesoare cu parametri diferiți, apoi pentru comparație nu puteți utiliza timpul absolut de rulare al programului în milisecunde. Pentru aceasta, introducem timpul relativ de funcționare: raportul, în procente, dintre timpul de calcul al produsului matricelor cu anumiți parametri și timpul de calcul al produsului acelorași matrice cu aceiași parametri într-un fir.

Să ne uităm la graficele dependenței timpului relativ de operare de numărul de fire pentru algoritmul folosind matricea originală:

Acest grafic îndeplinește toate așteptările: timpul de rulare scade pe măsură ce numărul de fire crește până la numărul de nuclee și apoi rămâne aproximativ constant. Cu toate acestea, dacă rezultatele pentru Core2Quad și Xeon diferă de cele ideale cu mai puțin de 1%, atunci pentru Core2Duo și Atom rezultatele sunt mai rele.

Când dimensiunea datelor crește de 4 ori, decalajul devine și mai puternic. În special pe Atom N550 (netbook-urile nu sunt în mod clar concepute pentru a multiplica matrice de 2000x2000 per ). Acest lucru este explicat exact în același mod ca și reducerea timpului atunci când se utilizează o matrice transpusă. Când există mai multe fire de execuție care accesează diferite zone de memorie, fiecare fir individual va funcționa mai lent decât un fir care traversează memoria în ordine. Dar, în ciuda acestui fapt, mai multe fire vor funcționa mai repede decât unul.

Următoarele grafice reprezintă timpul relativ de rulare în raport cu numărul de fire pentru algoritm folosind o matrice transpusă:


Deoarece accelerarea la utilizarea unei matrice transpuse este asociată cu mai mult utilizare eficientă cache, atunci începe să funcționeze mai rău dacă numărul de fire este crescut și secvența de acces la memorie este întreruptă. Atom și Core2Quad se comportă interesant: graficul Atom a rămas practic neschimbat, în timp ce performanța Core2Quad s-a deteriorat brusc la trecerea de la 1000x1000 la 2000x2000.
Acest lucru se explică după cum urmează: cu o dimensiune a matricei de 1000x1000, avem 2 tablouri (a și b) cu 1000*1000 elemente de 4 octeți (int). Adică aproximativ 8 megaocteți. Cache-ul de 1 MB al Atom N550 conține doar 1/8 din toate datele, când memoria cache Core2Quad se potrivește tuturor datelor. Când extindem matricele la 2000x2000, creștem cantitatea de date de 4 ori. Astfel, doar 1/4 din date se potrivesc acum în memoria cache Core2Quad și trucul de transpunere devine mai puțin eficient și nu a funcționat pe procesorul Atom și continuă să nu funcționeze.
Pentru a ilustra efectul descris mai sus, luați în considerare încă două grafice.
Să numim eficiența utilizării unei matrice transpuse raportul dintre timpul de rulare al algoritmului folosind matricea transpusă sub anumiți parametri și timpul de rulare al algoritmului folosind matricea originală sub aceiași parametri.


Acest grafic ilustrează bine toate cele de mai sus. Eficiența Core2Quad și Xeon scade din cauza numărului mare de fire concurente care accesează diferite zone de memorie și rup memoria cache. Eficiența Core2Duo este aproape neschimbată datorită faptului că are doar 2 fire de execuție care rulează o dată și pentru că dimensiunea cache-ului nu este la fel de mare ca la procesoarele anterioare.
Următoarea figură conține același grafic, doar cu adăugarea indicatorilor Atom N550.


Nu am reușit niciodată să înțeleg această creștere a eficienței trucului de cache și transpunere. Sper că putem ajunge la fundul adevărului în comentarii.

Concluzie

În primul rând, Cache-ul procesorului afectează semnificativ viteza de execuție a programului, deși în majoritatea cazurilor nici nu ne gândim la asta.
În al doilea rând, codul sursă și, în general, tot ceea ce am folosit în acest articol, pot fi descărcate din linkul dintr-o arhivă.
În al treilea rând, compilatorul a folosit g++ 4.5.2, linie de compilare g++ -Wall -O,
Windows 7 și Windows Server 2008 R2 pe Amazon.
Vă mulțumim pentru atenție.
Salutări, Ivan.

P.S. Așa arăta procesul de colectare a datelor

Etichete: calcul paralel, înmulțire, matrice, c plus plus

Acest articol nu este supus comentariilor, deoarece autorul său nu este încă un membru cu drepturi depline al comunității. Veți putea contacta autorul numai după ce acesta va primi o invitație de la cineva din comunitate. Până în acest moment, numele lui de utilizator va fi ascuns de un alias.

Acest articol va discuta Standardele POSIX Fire și OpenMP. Și anume, multiplicarea paralelă a matricelor NxN folosind aceste standarde și compararea lor.

1) Cod de multiplicare matrice folosind OpenMP.

#include #include #include #include #include #include #include #include #include #include #include #include int *alloc_matrix(int ​​​​size)( int *matrix = (int*)malloc(size * size * sizeof(int)); printf("matrice %dx%d alocată\n", dimensiune, dimensiune); return matrice ; ) void del_matrix(int ​​​​*matrix)( free(matrix); ) double dtime())( struct timeval tv; struct timezone tz; double t; gettimeofday(&tv, &tz); t = (double)tv.tv_sec + (double)tv .tv_usec*1e-6 return(t int main() ( int N = 50; int THR = 2; int i, j, k; printf("Introduceți numărul de fire\n"); ); scanf("% i",&THR); omp_set_threads(THR); ); int *B = alloc_matrix(N) *C = alloc_matrix(N) ;

2) Cod pentru multiplicarea matricei folosind Pthread.

#include #include #include #include #include #include #include #include #include #include #define SIZE 50 int *alloc_matrix(int ​​​​size)( int *matrix = (int*)malloc(size * size * sizeof(int)); printf("matrice %dx%d alocată\n" , size , size); return matrice; ) void del_matrix(int ​​​​*matrix)( free(matrix); ) double dtime())( struct timeval tv; struct timezone tz; gettimeofday(&tv, &tz); t = (double) tv.tv_sec + (double)tv.tv_usec*1e-6 return(t struct matrix_args( int *m1; int *m2; int *ans; int size; int start; int end; ) ARG; void *multiply_matrix(void *pargs)( struct matrix_args *args = (struct matrix_args *) pargs; int i, j, k, l, m, tmp = 0; double t0 = dtime(); int *m1 = args-> m1; int *m2 = args->ans;< end; i++){ m = i * size; for(j = 0; j < size; j++){ l = 0; for(k = 0; k < size; k++){ tmp += m1 * m2; l += size; } ans = tmp; tmp = 0; } } printf("thread works %fs\n", dtime() - t0); pthread_exit(NULL); } main(int argc, char** argv){ int i, j, size, k, step, pos, res; int THR_NUM,THR,N; printf("Введите число потоков\n"); scanf("%i",&THR); printf("Введите размер матрици\n"); scanf("%i",&N); THR_NUM = THR; size = N; pthread_t threads; pthread_attr_t attr; printf("allocating\n"); int *m1 = alloc_matrix(size); int *m2 = alloc_matrix(size); int *ans = alloc_matrix(size); srand(time(NULL)); for(int i=0; i

3) Testare

Înmulțirea matricilor de 1000x1000 de elemente pe un procesor Intel Atom

Pe baza datelor obținute, este clar că pe 2 fire se produce o ușoară creștere a performanței datorită tehnologiei de hyper threading pe care o suportă procesorul. Creșterea ulterioară a numărului de fire nu a dus la o creștere a performanței, ci mai degrabă a încetinit-o. De asemenea, este clar că paralelizarea manuală folosind Pthread este mai eficientă decât paralelizarea automată folosind OpenMP.

Înmulțirea matricilor de 1000x1000 de elemente pe un procesor Intel Xeon

Pe baza datelor obținute, este clar că performanța crește pe 2 și 4 fire, deoarece procesorul este capabil să aloce un nucleu separat pentru fiecare thread. Dar performanța începe să scadă atunci când încercăm să rulăm un program cu 10 fire de execuție, acest lucru se întâmplă și din cauza timpului petrecut cu cuantizarea dintre fire. Din acest tabel putem presupune că este cel mai eficient să rulați un fir pe nucleu (aplicația a arătat cea mai bună performanță pe 4 fire). De asemenea, este clar că paralelizarea manuală prin Pthread s-a dovedit a fi mai eficientă decât paralelizarea automată prin OpenMP.

Problema dvs. se datorează unei condiții de cursă pe variabila buclă interioară j . Trebuie să fie privat.

În C89 aș face ceva de genul acesta:

#pragma omp paralel ( int i, j, k; #pragma omp pentru for(i=0; ...

Pentru C++ sau C99, utilizați declarații mixte

#pragma omp paralel pentru for(int i=0; ...

Făcând acest lucru, nu trebuie să declarați în mod explicit nimic public sau privat.

Câteva comentarii suplimentare la codul dvs. Când utilizați B[k][j], codul dvs. cu un singur thread nu se păstrează în cache. Aceasta citește caju, apoi trece la următoarea linie de cache și așa mai departe până când produsul punctual este executat, moment în care ceilalți pini vor fi fost evacuați. În schimb, transpunerea trebuie mai întâi transferată și accesată ca BT[j][k] . De asemenea, ați alocat matrice de matrice, nu o matrice 2D contiguă. Ți-am corectat codul pentru a utiliza transpunerea și o matrice 2D învecinată.

Iată timpul pe care îl primesc pentru dimensiunea = 512.

Fără transpunere fără openmp 0,94 s fără transpunere, openmp 0,23 s transpunere, fără openmp 0,27 s transpunere, openmp 0,08 s #include #include #include void transpose(dublu *A, dublu *B, int n) ( int i,j; for(i=0; i