Implémentation du classement des listes en C avec OpenMP - Erreur de sortie

Question

Le code suivant montre ma mise en œuvre de l'algorithme de classement de liste avec OpenMP. Quand j'exécute ce code sans les pragmas, j'obtiens les bons résultats, mais quand j'inclus les pragmas, j'obtiens des erreurs (occasionnellement) dans la sortie. Les sorties sont affichées en bas. Vous pouvez voir que la deuxième fois la sortie était erronée. Cela se produit au hasard. Lorsque je supprime les pragmas, ma sortie est toujours correcte. Y at-il une erreur dans la façon dont j'ai utilisé les pragmas ou y a-t-il une dépendance qui me manque? (La sortie séquentielle est la sortie attendue Lorsque la sortie parallèle correspond à la sortie séquentielle des estampes de programme DATA OK.)

longueur

et nombre de fils sont 16.

#define NSIZE 1 
#define NMAX 16 
int Ns[NSIZE] = {16}; 
int A[NMAX] = {14,13,5,16,11,10,9,12,0,8,7,15,4,3,2,1}; 
int B[NMAX + 1] = {0}; 

int S[NMAX + 1] = {0}; 

int Rp[NMAX + 1] = {0}; 
int next[NMAX+1] = {0}; 

for(int i = 1, j=0; i <= n; i++, j++) 
{ 
    B[i] = A[j]; 

} 

int chunk = ceil(length/nthreads); 
int i, j; 
int tid; 
//#pragma omp parallel num_threads(nthreads) 
//{ 
//#pragma omp for schedule(dynamic, chunk) private(i) 
for(i = 1; i <= length; i++) 
{ 

    Rp[i] = 1; 
    next[i] = S[i]; 
} 


for(i = 1; i<=log2(length); i++) 
{ 
#pragma omp parallel num_threads(nthreads) shared(Rp,next,chunk) private(j) 
{ 
    #pragma omp for schedule(dynamic,chunk) 
    for(j = 1; j <= length; j++) 
    { 
     if(next[j]!=0) 
     { 
      Rp[j] = Rp[j] + Rp[next[j]]; 

      next[j] = next[next[j]]; 
     } 
    } 

} 
} 

SORTIE:

./ a.out - (Ce fut la sortie quand je courais le programme pour la première fois)

à partir des données parallèles
OK
Inpu t: 14 13 5 16 11 10 9 12 0 8 7 15 4 3 2 1
Séquentiel: 6 10 4 8 3 15 1 13 0 14 2 12 9 5 11 7
Parallèle: 6 10 4 8 3 15 1 13 0 14 2 12 9 5 11 7

./a.out - (sortie lorsque je me suis le programme pour la deuxième fois) de parallèle
MISMATCH de données !!!
entrée: 14 13 5 16 11 10 9 12 0 8 7 15 4 3 2 1
séquentielle: 6 10 4 8 3 15 1 13 0 14 2 12 9 5 11 7
parallèle: 6 10 4 8 3 15 1 13 0 10 2 12 9 5 11 7

./a.out - (sortie lorsque je me suis le programme pour la troisième fois)

de données parallèles

OK entrée: 14 13 16 5 11 10 9 12 0 8 7 15 4 3 2 1
Séquentiel: 6 10 4 8 3 15 1 13 0 14 2 12 9 5 11 7
Parallèle : 6 10 4 8 3 15 1 13 0 14 2 12 9 5 11 7

Answer 1

Je pense que cela devrait être possible avec un deuxième ensemble de tableaux. Corrigez-moi si je me trompe.

Lorsque vous prenez deux tableaux et deux pointeurs next_new et next_old et deux tableaux et deux pointeurs Rp_new et Rp_old, il devrait faire l'affaire.

Vous écrivez les nouveaux tableaux, en lisant de la vieille et échangeant des pointeurs après chaque tour.

Rp_new[j] = Rp_old[j] + Rp_old[next_old[j]]; 

next_new[j] = next_old[next_old[j]];