openmp parallélisé code en C++ est plus lente que la série une

Question

je voudrais paralléliser le code suivant

for (i=0; i<M; i++){ 
    temp = 0. 
    for (j=0; j<N; j++){ 
     temp += A[i][j]*v[j]; 
    u[i] = temp; 
} 

où différent u [i] peut être calculé de façon indépendante. Donc j'ai essayé de faire

#pragma omp parallel for private (j,temp) 
for (i=0; i<M; i++){ 
    temp = 0. 
    for (j=0; j<N; j++){ 
     temp += A[i][j]*v[j]; 
    u[i] = temp; 
} 

et je trouve que le deuxième cas est plus lent que le premier. Une idée de pourquoi c'est ainsi? ici M ~ 100 et N ~ 2.

Answer 1

Il n'y a aucun avantage à paralléliser ceci parce que les données sont si petites: le surdébit de l'établissement et de la coordination d'un calcul parallèle l'emporte sur n'importe quel avantage de l'exécution parallèle.

De plus, le calcul est facilement optimisé.

Votre compilateur certainement déroulez la boucle interne (N = 2), de sorte qu'il devient:

u[i] = A[i][0]*v[0] + A[i][1] * v[1] 

Même si nous supposons A est un type de 64 bits (comme double), puis la boucle extérieure over je peux être déroulé 4 fois, de sorte que chaque accès à A utilise une seule ligne de cache de 64 octets (pour les 8 entrées A [i] [0] à A [i + 3] [1]).

Le résultat est une simple boucle avec seulement 25 itérations (pour M = 100):

for (i=0; i<M; i+= 4) 
{ 
    u[i] = A[i][0]*v[0] + A[i][1] * v[1]; 
    u[i+1] = A[i+1][0]*v[0] + A[i+1][1] * v[1]; 
    u[i+2] = A[i+2][0]*v[0] + A[i+2][1] * v[1]; 
    u[i+3] = A[i+3][0]*v[0] + A[i+3][1] * v[1]; 
} 

Avec préchargement, tous les accès sont essentiellement déjà dans le cache.

Vous auriez besoin de données beaucoup plus importantes pour voir aucun avantage de cette parallélisation :)