Parallèle OpenMP quicksort
J'essaie d'utiliser OpenMP parallèle quicksort dans la partition de la partie et quicksort partie. Mon code C est comme suit:
#include "stdlib.h"
#include "stdio.h"
#include "omp.h"
//parallel partition
int ParPartition(int *a, int p, int r) {
int b[r-p];
int key = *(a+r); //use the last element in the array as the pivot
int lt[r-p]; //mark 1 at the position where its element is smaller than the key, else 0
int gt[r-p]; //mark 1 at the position where its element is bigger than the key, else 0
int cnt_lt = 0; //count 1 in the lt array
int cnt_gt = 0; //count 1 in the gt array
int j=p;
int k = 0; //the position of the pivot
//deal with gt and lt array
#pragma omp parallel for
for ( j=p; j<r; ++j) {
b[j-p] = *(a+j);
if (*(a+j) < key) {
lt[j-p] = 1;
gt[j-p] = 0;
} else {
lt[j-p] = 0;
gt[j-p] = 1;
}
}
//calculate the new position of the elements
for ( j=0; j<(r-p); ++j) {
if (lt[j]) {
++cnt_lt;
lt[j] = cnt_lt;
} else
lt[j] = cnt_lt;
if (gt[j]) {
++cnt_gt;
gt[j] = cnt_gt;
} else
gt[j] = cnt_gt;
}
//move the pivot
k = lt[r-p-1];
*(a+p+k) = key;
//move elements to their new positon
#pragma omp parallel for
for ( j=p; j<r; ++j) {
if (b[j-p] < key)
*(a+p+lt[j-p]-1) = b[j-p];
else if (b[j-p] > key)
*(a+k+gt[j-p]) = b[j-p];
}
return (k+p);
}
void ParQuickSort(int *a, int p, int r) {
int q;
if (p<r) {
q = ParPartition(a, p, r);
#pragma omp parallel sections
{
#pragma omp section
ParQuickSort(a, p, q-1);
#pragma omp section
ParQuickSort(a, q+1, r);
}
}
}
int main() {
int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6};
ParQuickSort(a, 0, 9);
int i=0;
for (; i!=10; ++i)
printf("%d\t", a[i]);
printf("\n");
return 0;
}
Je suis nouveau sur OpenMG et de la programmation parallèle. Pour l'exemple dans la fonction principale, le tri résultat est:
0 9 9 2 2 2 6 7 7 7
J'ai utilisé gdb pour déboguer. Dans le début de la récursivité, tout s'est bien passé. Mais dans certaines récurrences, il a soudainement foiré pour commencer les éléments en double. Ensuite générer le résultat ci-dessus.
Quelqu'un peut-il m'aider à comprendre où est le problème? Merci beaucoup!
AFAK, OpenMP
Tu veux dire que la boucle dans la partition de la partie ou de la partition, tri rapide, tri rapide boucle?
for
peut ne pas s'appliquer au contexte de la déclaration. Dans quicksort
, une nouvelle boucle dépend de la précédente boucle, de sorte qu'il ne peut pas facilement utiliser openMP, je pense.Tu veux dire que la boucle dans la partition de la partie ou de la partition, tri rapide, tri rapide boucle?
OriginalL'auteur randomp | 2013-04-15
Vous devez vous connecter pour publier un commentaire.
Je suis désolé pour mon premier commentaire.Il n'a pas d'importance avec votre problème.Je n'ai pas trouvé le vrai problème de votre question(Peut-être que votre déménagement élément a le problème).Selon votre opinion, j'ai écrit un programme similaire, il fonctionne
des beaux.(Je suis également nouveau sur OpenMP).
Je peux juste dire "peut-être".: -)
Je ne vois pas pourquoi ce serait jamais travailler. Dans le
parallel for
,lt_n
etgt_n
sont éventuellement modifié par plus d'un fils sans aucune synchronisation. Peut-être que le tableau est tellement petite qu'un seul thread est de travailler sur cet article.mise à Jour: j'ai couru plusieurs fois, et en effet, vu le mauvais résultat:
0 1 2 3 5 6 6 7 8 9
. Donc le code est mal. @randompOriginalL'auteur MYMNeo
J'ai mis en œuvre parallèlement quicksort dans un environnement de production, mais avec des processus simultanés (c'est à dire fork() et join()) et pas d'OpenMP. J'ai aussi trouvé une assez bonne pthread solution, mais un processus concurrent de la solution en termes de pire cas d'exécution. Permettez-moi de commencer par dire qu'il ne semble pas comme vous faites des copies de votre tableau d'entrée pour chaque thread, vous allez certainement rencontrer des conditions de course qui peuvent corrompre vos données.
Essentiellement, ce qui se passe est que vous avez créé un tableau N dans la mémoire partagée, et quand vous faites un
#pragma omp parallel sections
, vous êtes frai autant de threads qu'il y a#pragma omp section
'. Chaque fois qu'un thread tente d'accéder et de modifier les éléments d'un, il va exécuter une série d'instructions: "lire le n-ième valeur de N à partir de l'adresse donnée", "modifier la n-ième valeur de N", "écriture de la n-ième valeur de N de retour à l'adresse donnée". Puisque vous avez plusieurs threads sans verrouillage ou de synchronisation, le lire, le modifier, et d'écrire des instructions peuvent être exécutées dans n'importe quel ordre par plusieurs processeurs, de sorte que le fils peut écraser les uns les autres modifications ou de lire une non-valeur de mise à jour.La meilleure solution que j'ai trouvé (après plusieurs semaines de tests et d'analyse comparative de nombreuses solutions que j'ai trouvé) est la subdivision de la liste log(n) fois, où n est le nombre de processeurs. Par exemple, si vous avez un quad core de la machine (n = 4), subdivision de la liste 2 fois (log(4) = 2) choix des pivots que sont les médianes de l'ensemble de données. Il est important que les pivots sont les médianes, parce que sinon vous pouvez vous retrouver avec un cas où un mal choisi pivot causes les listes pour être distribué de manière inégale entre les processus. Ensuite, chaque processus ne quicksort locaux de subarray, puis fusionne ses résultats avec les résultats d'autres processus. Ceci est appelé "hyperquicksort", et d'une initiale github de recherche, j'ai trouvé cette. Je ne peux pas se porter garant pour le code, et ne peut pas publier le code que j'ai écrit car il est protégé en vertu d'un accord de confidentialité.
Par la voie, l'un des meilleurs parallèle algorithme de tri est SRFP (Parallèle Tri par Échantillonnage Régulier) qui tient à jour la liste des tailles plus équilibrée entre les processus, n'est-ce pas inutilement communiquer les clés entre les processus, et peuvent travailler sur un nombre arbitraire de processus simultanés (ils n'ont pas nécessairement à être une puissance de 2).
OriginalL'auteur Keshav Saharia
Cela semble mal mon op est à la recherche comme cette
OriginalL'auteur MITian