C parallèle OpenMP quickSort

Une fois de plus, je suis coincé lors de l'utilisation d'openMP en C++. Cette fois, je suis en train de mettre en œuvre un parallèle quicksort.

Code:

#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <omp.h>
#include <stdio.h>
#define SWITCH_LIMIT 1000
using namespace std;
template <typename T>
void insertionSort(std::vector<T> &v, int q, int r)
{
int key, i;
for(int j = q + 1; j <= r; ++j)
{
key = v[j];
i = j - 1;
while( i >= q && v[i] > key )
{
v[i+1] = v[i];
--i;
}
v[i+1] = key;
}
}
stack<pair<int,int> > s;
template <typename T>
void qs(vector<T> &v, int q, int r)
{
T pivot;
int i = q - 1, j = r;
//switch to insertion sort for small data
if(r - q < SWITCH_LIMIT) 
{
insertionSort(v, q, r);
return;
}
pivot = v[r];
while(true)
{
while(v[++i] < pivot);
while(v[--j] > pivot);
if(i >= j) break;
std::swap(v[i], v[j]); 
}
std::swap(v[i], v[r]);
#pragma omp critical
{
s.push(make_pair(q, i - 1));
s.push(make_pair(i + 1, r));        
}
}
int main()
{
int n, x;
int numThreads = 4, numBusyThreads = 0;
bool *idle = new bool[numThreads];
for(int i = 0; i < numThreads; ++i)
idle[i] = true;
pair<int, int> p;
vector<int> v;
cin >> n;
for(int i = 0; i < n; ++i)
{
cin >> x;
v.push_back(x);
}
cout << v.size() << endl;
s.push(make_pair(0, v.size()));
#pragma omp parallel shared(s, v, idle, numThreads, numBusyThreads, p) 
{
bool done = false;
while(!done) 
{
int id = omp_get_thread_num();
#pragma omp critical
{
if(s.empty() == false && numBusyThreads < numThreads) 
{
++numBusyThreads;
//the current thread is not idle anymore
//it will get the interval [q, r] from stack
//and run qs on it
idle[id] = false;
p = s.top();                    
s.pop();
}
if(numBusyThreads == 0)
{
done = true;
}
}
if(idle[id] == false)
{
qs(v, p.first, p.second);
idle[id] = true;
#pragma omp critical 
--numBusyThreads;
}
}
}
return 0;
}

Algorithme:

À utiliser openMP pour une fonction récursive, j'ai utilisé une pile de garder une trace de la prochaine intervalles sur lesquels la qs de la fonction doit être exécutée. J'ai ajouter manuellement le 1er intervalle [0, la taille], puis laissez-les fils se rendre au travail lorsque l'intervalle est ajouté à la pile.

Le problème:

Le programme se termine trop tôt, de ne pas trier le tableau après la création de la 1ère série d'intervalles ([q, i - 1] [i+1, r] si vous regardez sur le code. Ma conjecture est que les threads qui obtiennent le travail, considère les variables locales de la fonction quicksort(qs dans le code) partagé par défaut, de sorte qu'ils désordre et de ne pas ajouter de l'intervalle dans la pile.

Comment je compile:

g++ -o qs qs.cc -Wall -fopenmp

Comment je cours:

./qs < in_100000 > out_100000

où in_100000 est un fichier contenant 100000 sur la 1ère ligne suivie par 100k entier sur la ligne suivante séparés par des espaces.

Je suis en utilisant gcc 4.5.2 sur linux

Merci pour votre aide,

Dan

La dernière fois je n'ai omp (ou même pthread) tri parallèle, il a été plus lente que la série + récursive. Sauf si vous êtes sûr que le serialness de la sorte est le goulot d'étranglement, vous êtes en train de faire l'optimisation prématurée.
Je suis sûr que la solution parallèle devrait mieux fonctionner. Cependant, je suis en train d'apprendre à utiliser openMP et je n'ai pas de connaissances approfondies sur ce qui se passe réellement dans les coulisses.
Sur une sorte de fusion de 1 000 000 d'éléments, le parallélisme avait trop haut dans le ciel. Et vous ne pouvez pas être sûr à 100%, sans un générateur de profils et de chiffres. Cela dit, ce n'est pas mauvais d'un exercice pour l'apprentissage de l'omp, ou pthreads. Pthreads va être un peu plus facile, car il est plus facile de faire récursive threads. Cela étant dit, vous devez utiliser un pool de threads et d'allouer des aides à la piscine. N'oubliez pas d'utiliser le verrouillage de la globals pour éviter des conditions de course, les blocages et autres ignominies.
Aussi, c'est une Bonne Pratique pour l'entourer d'en-tête C comprend avec extern "C" { ... }.
Eh bien, je veux savoir quel est le problème avec cette mise en œuvre le 1er.

OriginalL'auteur Dan Lincan | 2011-11-05

c c++openmp quicksort

17

Je n'ai pas fait exécuter votre code, mais je vois une erreur immédiate sur p, qui devrait être private pas shared. Le parallèle invocation de qs: qs(v, p.first, p.second); aura des courses sur p, entraînant un comportement imprévisible. Les variables locales à qs devrait être d'accord parce que tous les threads ont leur propre pile. Toutefois, l'approche globale est bonne. Vous êtes sur la bonne voie.

Voici mes commentaires généraux pour la mise en œuvre du parallèle de quicksort. Quicksort lui-même est parallèle gênant, ce qui signifie aucune synchronisation n'est nécessaire. Les appels récursifs de qs sur une matrice partitionnée est parallèle gênant.

Cependant, le parallélisme est exposée dans un récursive forme. Si vous utilisez simplement la imbriquée parallélisme dans OpenMP, vous finirez par avoir des milliers de threads dans une seconde. Pas d'accélération va être gagnée. Ainsi, le plus souvent, vous devez activer l'algorithme récursif dans un interative. Ensuite, vous avez besoin pour mettre en œuvre une sorte de travail de la file d'attente. C'est votre approche. Et, il n'est pas facile.

Pour votre approche, il est un bon repère: OmpSCR. Vous pouvez le télécharger à l' http://sourceforge.net/projects/ompscr/

Dans l'indice de référence, il existe plusieurs versions de OpenMP-fonction quicksort. La plupart d'entre eux sont similaires à la vôtre. Cependant, afin d'augmenter le parallélisme, on doit minimiser le conflit mondial de la file d'attente (dans votre code, il est s). Donc, il pourrait y avoir quelques optimisations telles que locaux les files d'attente. Bien que l'algorithme lui-même est purement parallèle, la mise en œuvre peut nécessiter de synchronisation des artefacts. Et, plus que tout, c'est très dur pour gagner de la vitesse.

Toutefois, vous devez toujours utiliser directement récursive parallélisme dans OpenMP de deux façons: (1) la Limitation du nombre total de threads, et (2) en Utilisant OpenMP 3.0 task.

Voici le pseudo-code pour la première approche (C'est uniquement basée sur OmpSCR de référence):
```
void qsort_omp_recursive(int* begin, int* end)
{
if (begin != end) {
//Partition ...
//Throttling
if (...)  {
qsort_omp_recursive(begin, middle);
qsort_omp_recursive(++middle, ++end);
} else {
#pragma omp parallel sections nowait
{
#pragma omp section
qsort_omp_recursive(begin, middle);
#pragma omp section
qsort_omp_recursive(++middle, ++end);
}
}
}
}
```
Afin d'exécuter ce code, vous devez appeler omp_set_nested(1) et omp_set_num_threads(2). Le code est très simple. Nous avons simplement frayer les deux fils sur la division du travail. Cependant, nous insérons une simple limitation de la logique pour prévenir l'excès de threads. Notez que mon expérimentation a montré décent accélérations pour cette approche.

Enfin, vous pouvez utiliser OpenMP 3.0 task, où une tâche est une logique simultanées de travail. Au-dessus de tous les OpenMP approches, chaque structure parallèle engendre deux physique threads. Vous pouvez dire qu'il est dur de 1-à-1 mappage entre une tâche à un thread de travail. Cependant, task sépare la logique des tâches et des travailleurs.

Parce que OpenMP 3.0 n'est pas populaire encore, je vais utiliser Cilk Plus, ce qui est excellent pour exprimer ce genre de imbriquées et récursive parallélismes. Dans Cilk Plus, la parallélisation est extrêmement facile:
```
void qsort(int* begin, int* end)
{
if (begin != end) {
--end;
int* middle = std::partition(begin, end,
std::bind2nd(std::less<int>(), *end));
std::swap(*end, *middle);
cilk_spawn qsort(begin, middle);
qsort(++middle, ++end);
//cilk_sync; Only necessay at the final stage.
}
}
```
J'ai copié ce code de Cilk Plus l'exemple de code. Vous pourrez voir d'un seul mot-clé cilk_spawn est tout à paralléliser quicksort. Je ne m'attarde pas sur les explications de Cilk Plus et frayer un mot clé. Cependant, il est facile à comprendre: les deux appels récursifs sont déclarées en tant que logiquement des tâches simultanées. Chaque fois que la récursivité a lieu, la logique des tâches sont créées. Mais, le Cilk Plus runtime (qui met en œuvre efficace de vol de travail du planificateur) se charge de toutes sortes de sale boulot. De façon optimale les files d'attente de tâches parallèles et des cartes pour les threads de travail.

Noter que OpenMP 3.0 task est essentiellement similaire à la Cilk Plus de l'approche. Mon expérimentation montre que de très jolies accélérations sont réalisables. J'ai eu un 3~4x plus rapide sur un 8-core de la machine. Et, l'accélération a été à l'échelle. Cilk Plus absolue accélérations sont plus grandes que celles d'OpenMP 3.0.

L'approche de Cilk Plus (et OpenMP 3.0) et votre approche sont essentiellement les mêmes: la séparation de l'parallèle des tâches et de la charge de travail d'affectation. Cependant, il est très difficile de mettre en œuvre efficacement. Par exemple, vous devez réduire la contention et à l'utilisation sans verrouillage des structures de données.

C'est pas mal. L'article de Nice. Pas sûr que cela répond à la question, mais j'aime bien les réponses de ce genre 🙂 +1
C'est exactement ce que j'attendais, en plus de quelque chose de plus. Je vous remercie beaucoup.
+1, l'un gentil, j'ai été chercher cette.

OriginalL'auteur minjang

Vous devez vous connecter pour publier un commentaire.