Mnożenie macierzy OpenMP równolegle przez potrójną pętlę (problem wydajności)

Question

Piszę program do mnożenia macierzy z OpenMP, który dla wygody cache implementuje mnożenie A x B (transpozycja) wiersze X wiersze zamiast klasycznego A x B wiersze x kolumny, dla lepszej wydajności pamięci podręcznej. Robiąc to spotkałem się z interesującym faktem, który dla mnie jest nielogiczny: jeśli w tym kodzie zrównaję się z zewnętrzną pętlą program jest wolniejszy, niż gdybym umieścił dyrektywy OpenMP w najbardziej wewnętrznej pętli, w moim komputerze czasy wynoszą 10,9 vs 8,1 sekundy.

//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

Spróbuj uderzenie wynik rzadziej. To wywołuje udostępnianie w pamięci podręcznej i uniemożliwia równoległe działanie operacji. Użycie zmiennej lokalnej pozwala na zapisanie większości zapisów w pamięci podręcznej L1 każdego rdzenia.

Pomocne może być również użycie . W przeciwnym razie kompilator nie może zagwarantować, że zapisy do C nie ulegną zmianie A i B.

Spróbuj:

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; 
    } 
} 

Także myślę, że Elalfer jest prawo o konieczności redukcji jeśli parallelize wewnętrznej pętli.

Answer 2

Można prawdopodobnie mają pewne zależności w danych podczas parallelize zewnętrzną pętlę i kompilator nie jest w stanie zrozumieć to i dodaje dodatkowe zamki.

Najprawdopodobniej decyduje, że różne iteracje pętli zewnętrznej mogą zapisać w tym samym (C+(i*Nu+j)) i dodaje blokady dostępu w celu ich ochrony.

Kompilator mógłby prawdopodobnie stwierdzić, że nie ma zależności, jeśli zrównoważysz drugą pętlę. Ale zorientowanie się, że nie ma zależności równoległych do zewnętrznej pętli, nie jest tak proste dla kompilatora.

UPDATE

Niektóre pomiary wydajności.

Cześć jeszcze raz. Wygląda na to, że 1000 podwójnych * i + nie wystarcza na pokrycie kosztów synchronizacji wątków.

Zrobiłem kilka małych testów i proste mnożenie wektorów nie działa z openmp, chyba że liczba elementów jest mniejsza niż ~ 10'000. Zasadniczo, większa jest twoja tablica, większa wydajność uzyskasz dzięki wykorzystaniu OpenMP.

Równolegle do najbardziej wewnętrznej pętli musisz oddzielić zadanie pomiędzy różne wątki i zebrać dane z powrotem 1 000 000 razy.

PS. Wypróbuj Intel ICC, można go używać do studentów i projektów Open Source. Pamiętam, że używam openmp dla mniejszych niż 10'000 tablic elementów.

UPDATE 2: przykład Redukcja

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;