Comment paralléliser faire alors que et tandis que la boucle en openmp?

Je suis en train d'apprendre la programmation parallèle avec OpenMP et je suis intéressé par la parallélisation de l'suivantes do while boucle avec plusieurs while boucle à l'intérieur:

do {
        while(left < (length - 1) && data[left] <= pivot) left++;
        while(right > 0 && data[right] >= pivot) right--;

        /* swap elements */
        if(left < right){
            temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }

    } while(left < right);

Je n'ai pas réellement compris comment paralléliser while et do while boucles, je ne trouve pas d'où il est spécifiquement décrit comment paralléliser while et do while boucles. J'ai trouvé des instructions pour for boucles, mais je ne pouvais pas faire d'hypothèse pour while et do while boucles. Donc, pourriez-vous décrire comment je peut paralléliser cette boucle que je fournis ici?

MODIFIER

J'ai transformé le do while boucle pour le code suivant où seulement for boucle est utilisée.

for(i = 1; i<length-1; i++)
{
if(data[left] > pivot)
{
i = length;
}
else
{
left = i;
}
}
for(j=length-1; j > 0; j--)
{
if(data[right] < pivot)
{
j = 0;
}
else
{
right = j;
}
}
/* swap elements */
if(left < right)
{
temp = data[left];
data[left] = data[right];
data[right] = temp;
}
int leftCopy = left;
int rightCopy = right;
for(int leftCopy = left; leftCopy<right;leftCopy++)
{
for(int new_i = left; new_i<length-1; new_i++)
{
if(data[left] > pivot)
{
new_i = length;
}
else
{
left = new_i;
}
}
for(int new_j=right; new_j > 0; new_j--)
{
if(data[right] < pivot)
{
new_j = 0;
}
else
{
right = new_j;
}
}
leftCopy = left;
/* swap elements */
if(left < right)
{
temp = data[left];
data[left] = data[right];
data[right] = temp;
}
}

Ce code fonctionne très bien et produit un résultat correct, mais quand j'ai essayé de paralléliser les parties de ci-dessus indiqué de code, en changeant les deux premiers for boucles à la suivante:

#pragma omp parallel default(none) firstprivate(left) private(i,tid) shared(length, pivot, data)
{
#pragma omp for
for(i = 1; i<length-1; i++)
{
if(data[left] > pivot)
{
i = length;
}
else
{
left = i;
}
}
}
#pragma omp parallel default(none) firstprivate(right) private(j) shared(length, pivot, data)
{
#pragma omp for
for(j=length-1; j > 0; j--)
{
if(data[right] < pivot)
{
j = 0;
}
else
{
right = j;
}
}
}

La vitesse est pire que le non-code parallélisé. Merci de m'aider à identifier mon problème.

Grâce

Quelle est la valeur typique pour length?
Avant d'utiliser OpenMP, il suffit de penser à la façon dont la tâche peut être effectuée en parallèle à tous. Pensez-vous avoir plusieurs gars qui vous pouvez confier des tâches à votre fils. Maintenant, que faites-vous avec? Qu'est-ce exactement peut être effectuée en parallèle dans un certain temps? Avec un pour la, vous pouvez facilement dire "pour s'exécute sur un indice, pour chaque indice, le calcul peut être fait en parallèle". En remettant à chaque gars un index, ou de leur dire de poisson d'un index d'un seau, de la gérer et puis obtenir la suivante. Mais dans quelque chose comme un while(true){ if(condition){break;} do_stuff; } ? Je ne vois pas un concept en général ici.
Comme pour le tri, faire avec de fusion de tri? Prendre le tableau, de le diviser en T intervalles de T threads, le faire en parallèle et ensuite les fusionner de manière séquentielle. La fusion prend O(N), de Fusion et le tri des intervalles prend l'habitude O(NlogN), mais elle est indépendante et peut donc être effectué en parallèle. Pour un grand N, le processus de fusion est dominé par la séparation de tri dans les intervalles. C'est, si vous voulez vraiment faire cela comme un exercice. Si vous voulez juste quelque chose pour être triés en parallèle, vous obtenez une bibliothèque qui le fait. Vous ne serez pas en mesure de rivaliser avec une bonne bibliothèque.
(Notez que "qui peut être fait en parallèle" est un concept théorique - pour les gros tableaux, vous rencontrerez le problème qu'ils partagent le même cache. C'est grande raison pourquoi vous voulez les bibliothèques, le gars qui a écrit ces connaissait ce problème et ce sera probablement le même état combien de fils que vous devez utiliser, probablement pas le montant maximal que votre ordinateur peut créer et dépend de votre processeur et des caches.)

OriginalL'auteur the_naive | 2014-11-03

c++openmp parallel-processing

5

Tout d'abord, les algorithmes de tri sont très dur à la parallélisation avec OpenMP boucles parallèles. C'est parce que la boucle de voyage comptage n'est pas déterministe, mais dépend de la contribution de définir des valeurs qui sont lus à chaque itération.

Je ne pense pas avoir de boucle conditions telles que data[left] <= pivot va bien fonctionner, puisque la bibliothèque OpenMP ne sais pas exactement comment partition de l'itération de l'espace entre les threads.

Si vous êtes toujours intéressé en parallèle des algorithmes de tri, je vous suggère de lire la littérature d'abord, pour voir ces algorithmes qui vaut vraiment la peine de la mise en œuvre en raison de leur évolutivité. Si vous voulez juste en savoir OpenMP, je vous suggère de commencer avec le plus simple des algorithmes tels que seau-tri, où le nombre de compartiments est bien connu et n'est pas souvent le changement.

À propos de l'exemple que vous essayez de paralléliser, while les boucles ne sont pas directement pris en charge par OpenMP, parce que le nombre d'itérations de la boucle (boucle de voyage count) n'est pas déterministe (sinon, il est facile de les transformer en boucles for). Par conséquent, il n'est pas possible de distribuer les itérations entre les threads. En outre, il est commun pour les boucles while pour vérifier une condition à l'aide de la dernière itération. Ceci est appelé Lecture après Écriture ou vrai-dépendance et ne peut être parallélisée.

Votre ralentissement problème pourrait être atténué si vous essayez de réduire le nombre de omp parallel clauses. En outre, essayez de les déplacer hors de tous vos boucles. Ces clauses peuvent créer et de rejoindre les autres threads qui sont utilisés en parallèle, certaines parties du code, ce qui est coûteux.

Vous pouvez toujours synchroniser les threads à l'intérieur de blocs parallèles, de sorte que le résultat est similaire. En fait, tous les threads en attente pour l'autre à la fin d'une omp for clause par défaut, de sorte que ce qui rend les choses encore plus facile.
```
#pragma omp parallel default(none) firstprivate(right,left) private(i,j) shared(length, pivot, data)
{
#pragma omp for
for(i = 1; i<length-1; i++)
{
if(data[left] > pivot)
{
i = length;
}
else
{
left = i;
}
}
#pragma omp for 
for(j=length-1; j > 0; j--)
{
if(data[right] < pivot)
{
j = 0;
}
else
{
right = j;
}
}
} //end omp parallel 
```
OriginalL'auteur Jorge Bellon

Vous devez vous connecter pour publier un commentaire.