Comment paralléliser une boucle?

Question

J'utilise OpenMP sur C++ et je veux paralléliser une boucle très simple. Mais je ne peux pas le faire correctement. Tout le temps je me trompe de résultat.

for(i=2;i<N;i++) 
    for(j=2;j<N;j++) 
     A[i,j] =A[i-2,j] +A[i,j-2]; 

code:

int const N = 10; 
int arr[N][N]; 

#pragma omp parallel for 
for (int i = 0; i < N; i++) 
    for (int j = 0; j < N; j++) 
     arr[i][j] = 1; 

#pragma omp parallel for 
for (int i = 2; i < N; i++) 
    for (int j = 2; j < N; j++) 
    { 
     arr[i][j] = arr[i-2][j] +arr[i][j-2]; 
    } 

for (int i = 0; i < N; i++) 
{ 
    for (int j = 0; j < N; j++) 
     printf_s("%d  ",arr[i][j]); 
    printf("\n"); 
} 

Avez-vous des suggestions comment je peux le faire? Je vous remercie!

Answer 1

exécution en série et en parallèle donnera différent. résultat parce que dans

#pragma omp parallel for 
for (int i = 2; i < N; i++) 
    for (int j = 2; j < N; j++) 
    { 
     arr[i][j] = arr[i-2][j] +arr[i][j-2]; 
    } 
    ..... 

vous mettez à jour arr [i]. donc vous changez les données utilisées par l'autre thread. cela conduira à une course de données en lecture-écriture!

Answer 2

Ce

#pragma omp parallel for 
for (int i = 2; i < N; i++) 
    for (int j = 2; j < N; j++) 
    { 
     arr[i][j] = arr[i-2][j] +arr[i][j-2]; 
    } 

va toujours être une source de douleur et de sortie imprévisible. Le temps d'exécution OpenMP va remettre à chaque thread une plage de valeurs pour i et les laisser. Il n'y aura pas de déterminisme dans l'ordre relatif dans lequel les threads sont mis à jour arr. Par exemple, alors que le thread 1 met à jour les éléments avec i = 2,3,4,5,...,100 (ou autre) et le thread 2 met à jour les éléments avec i = 102,103,104,...,200, le programme ne détermine pas si le thread 1 met à jour arr[i,:] = 100 avant ou après que le thread 2 souhaite utiliser les valeurs mises à jour dans arr. Vous avez écrit un code avec une course de données classique .

Vous avez un certain nombre d'options pour résoudre ce problème:

Vous pourriez vous contorsionner en essayant de faire en sorte que les fils sont mis à jour arr dans l'ordre (ie séquentiel). Le résultat final serait un programme OpenMP qui s'exécute plus lentement que le programme séquentiel. NE PRENEZ PAS CETTE OPTION.

Vous pouvez faire 2 copies de arr et toujours mettre à jour de l'un à l'autre, puis de l'autre à l'un. Quelque chose comme (très pseudo-code)

for ... 
{ 
    old = 0 
    new = 1 

    arr[i][j][new] = arr[i-2][j][old] +arr[i][j-2][old]; 

    old = 1 
    new = 0 
} 

Bien sûr, cette seconde approche métiers espace pour le temps, mais qui est souvent un compromis raisonnable.

Vous pouvez constater qu'ajouter un plan supplémentaire à arr n'accélère pas immédiatement les choses car cela détruit la localité spatiale des valeurs tirées dans le cache. Expérimentez un peu avec ceci, faites peut-être [old] le premier élément d'index plutôt que le dernier.

Puisque la mise à jour de chaque élément de la matrice dépend des valeurs trouvées dans les éléments 2 lignes/colonnes, vous divisez efficacement la matrice comme un échiquier en éléments blancs et noirs. Vous pouvez utiliser 2 threads, un sur chaque «couleur», sans que les threads ne courent pour accéder aux mêmes données. Encore une fois, cependant, la perturbation de la localité spatiale dans le cache pourrait avoir un impact négatif sur la vitesse.

Si d'autres options se produisent à moi, je vais les modifier dans.

Answer 3

paralléliser le nid de boucle dans la question est délicate, mais faisable. Le document de Lamport "The Parallel Execution of DO Loops" couvre la technique. Fondamentalement, vous devez faire pivoter vos coordonnées (i, j) de 45 degrés dans un nouveau système de coordonnées (k, l), où k = i + j et l = i-j.

Bien que pour obtenir une accélération, les itérations doivent probablement être groupées en tuiles, ce qui rend le code encore plus laid (quatre boucles imbriquées).

Une approche complètement différente consiste à résoudre le problème de manière récursive, en utilisant OpenMP. La récursion est:

if(too small to be worth parallelizing) { 
    do serially 
} else { 
    // Recursively: 
    Do upper left quadrant 
    Do lower left and upper right quadrants in parallel 
    Do lower right quadrant 
} 

En pratique, le rapport des opérations arithmétiques à accès mémoire est si faible que cela va être difficile d'obtenir SpeedUp de l'exemple.

Answer 4

Si vous posez des questions sur le parallélisme en général, alors une réponse plus possible est la vectorisation. Vous pouvez obtenir un parallélisme vectoriel relativement pauvre (quelque chose comme 2x speedup ou plus) sans modifier la structure de données et la base de code. C'est possible en utilisant OpenMP4.0 ou CilkPlus pragma simd ou similaire (avec safelen/vectorlength (2))

Eh bien, vous avez vraiment une dépendance des données (les deux boucles internes et externes), mais il appartient à «WAR» [(write after read) sous-catégorie de dépendances, qui bloque l'utilisation de «omp parallel for» «tel quel», mais pas nécessairement un problème pour les boucles «pragma omp simd».

Pour que cela fonctionne, vous aurez besoin de compilateurs x86 supportant pragma simd via OpenMP4 ou via CilkPlus (compilateur gcc ou Intel très récent).