2017-10-21 46 views
1

J'essaye de paralléliser une fonction de codage, j'ai essayé d'ajouter un simple pragma autour du pour mais le résultat était faux. J'ai supposé que les itérations dépendent (par code variable) et donc elles ne peuvent pas être directement parallélisées.OpenMP | Paralléliser une boucle avec des itérations dépendantes

int encodePrimeFactorization(int number){ 
    int code = 0; 
    for (int i=PF_NUMBER-1; i>=0 ; i--){ 
     code = code * 2; 
     int f = prime_factors[i]; 
     if (number % f == 0){ 
     code = code + 1; 
     } 
    } 
    return code; 
} 

Y at-il un moyen de rendre variable indépendante code pour chaque itération?

Répondre

1

Oui. Au moins pour moi, il est plus facile de penser que si vous regardez l'algorithme de cette façon:

int code = 0; 
for (int i=PF_NUMBER-1; i>=0 ; i--) { 
    code = code << 1; 
    int f = prime_factors[i]; 
    if (number % f == 0){ 
    // The last bit of code is never set here, 
    // because it has been just shifted to the left 
    code = code | 1; 
    } 
} 

Vous pouvez maintenant déplacer l'ensemble bits déjà lors de la configuration:

int code = 0; 
for (int i=PF_NUMBER-1; i>=0 ; i--) { 
    int f = prime_factors[i]; 
    if (number % f == 0){ 
    code = code | (1 << i); 
    } 
} 

Maintenant, il devient réduction triviale. Maintenant vous pouvez déjà décaler le set-bit lors du réglage:

int code = 0; 
#pragma omp parallel for reduction(|,code) 
for (int i=PF_NUMBER-1; i>=0 ; i--) { 
    int f = prime_factors[i]; 
    if (number % f == 0){ 
    code |= (1 << i); 
    } 
} 

Cela dit, vous n'obtiendrez aucun gain de performance. Cela ne fonctionne que jusqu'à 31 bits, ce qui est beaucoup trop peu de travail pour bénéficier des frais généraux de parallélisation. S'il s'agit d'une partie importante de votre code, vous devez trouver quelque chose autour de lui pour appliquer la parallélisation.