moltiplicazione della matrice parallelizzazione OpenMP da un ciclo triplo (problema di prestazioni)

Question

Sto scrivendo un programma per la moltiplicazione di matrici con OpenMP, che, per convenienza della cache, implementa le righe X di moltiplicazione A x B (trasposizione) invece del classico A x B righe x colonne, per una migliore efficienza della cache. Facendo questo ho affrontato un fatto interessante che per me è illogico: se in questo codice parallelizzo il ciclo esterno il programma è più lento di se metto le direttive OpenMP nel ciclo più interno, nel mio computer i tempi sono 10.9 vs 8.1 secondi.

//A and B are double* allocated with malloc, Nu is the lenght of the matrixes 
//which are square 

//#pragma omp parallel for 
for (i=0; i<Nu; i++){ 
    for (j=0; j<Nu; j++){ 
    *(C+(i*Nu+j)) = 0.; 
#pragma omp parallel for 
    for(k=0;k<Nu ;k++){ 
     *(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    } 
} 

Answer 1

provare a colpire il risultato meno spesso. Ciò induce la condivisione della cache e impedisce l'esecuzione dell'operazione in parallelo. L'utilizzo di una variabile locale consente invece di eseguire la maggior parte delle scritture nella cache L1 di ciascun core.

Inoltre, l'utilizzo di restrict può essere d'aiuto. In caso contrario, il compilatore non può garantire che le scritture su C non vengano modificate A e B.

Prova:

for (i=0; i<Nu; i++){ 
    const double* const Arow = A + i*Nu; 
    double* const Crow = C + i*Nu; 
#pragma omp parallel for 
    for (j=0; j<Nu; j++){ 
    const double* const Bcol = B + j*Nu; 
    double sum = 0.0; 
    for(k=0;k<Nu ;k++){ 
     sum += Arow[k] * Bcol[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    Crow[j] = sum; 
    } 
} 

Inoltre, penso che Elalfer è giusto circa la necessità di riduzione se si parallelizzare il ciclo più interno.

Answer 2

Probabilmente si potrebbe avere alcune dipendenze nel data quando si parallelizzare il ciclo esterno ed il compilatore non è in grado di capirlo e aggiunge ulteriori chiavistelli.

Molto probabilmente decide che diverse iterazioni del ciclo esterno potrebbero scrivere nello stesso (C+(i*Nu+j)) e aggiunge i blocchi di accesso per proteggerlo.

Il compilatore potrebbe probabilmente capire che non ci sono dipendenze se si parallelizza il 2 ° ciclo. Ma capire che non ci sono dipendenze parallelizzando il ciclo esterno non è così banale per un compilatore.

UPDATE

Alcune misurazioni delle prestazioni.

Ciao di nuovo. Sembra 1000 doppio * e + non è sufficiente per coprire il costo della sincronizzazione dei thread.

Ho eseguito alcuni test di piccole dimensioni e la moltiplicazione scalare vettoriale semplice non è efficace con openmp a meno che il numero di elementi sia inferiore a ~ 10.000. Fondamentalmente, più grande è il tuo array, più prestazioni otterrai dall'uso di openmp.

Quindi, parallelizzando il ciclo più interno, dovrai separare l'attività tra diversi thread e raccogliere i dati indietro di 1'000'000 volte.

PS. Prova Intel ICC, è abbastanza gratuito da usare per studenti e progetti open source. Ricordo di aver usato openmp per i più piccoli array di 10'000 elementi.

UPDATE 2: Riduzione esempio

double sum = 0.0; 
    int k=0; 
    double *al = A+i*Nu; 
    double *bl = A+j*Nu; 
    #pragma omp parallel for shared(al, bl) reduction(+:sum) 
    for(k=0;k<Nu ;k++){ 
     sum +=al[k] * bl[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    C[i*Nu+j] = sum;