C OpenMP quickSort parallèle

une fois de plus je suis bloqué en utilisant openMP en C++. Cette fois, j'essaie d'implémenter un quicksort parallèle.

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:

pour utiliser openMP pour une fonction récursive, j'ai utilisé une pile pour garder la trace des intervalles suivants sur lesquels la fonction qs devrait s'exécuter. J'ajoute manuellement le 1er intervalle [0, taille] et puis laisse les threads fonctionner quand un nouvel intervalle est ajouté dans le pile.

Le problème:

le programme se termine trop tôt, ne triant pas le tableau après avoir créé le premier ensemble d'intervalles ([q, i - 1], [i+1, r] Si vous regardez le code. Mon avis est que les threads qui obtiennent le travail, considère les variables locales de la fonction quicksort(qs dans le code) partagés par défaut, de sorte qu'ils les gâchent et ajouter aucun intervalle dans la pile.

Comment puis-je compiler:

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

Comment Puis-Je exécuter:

./qs < in_100000 > out_100000

où in_100000 est un fichier contenant 100000 sur la première ligne suivi de 100k sur la ligne suivante séparé par des espaces.

j'utilise gcc 4.5.2 sous linux

Merci pour votre aide,

Dan