C OpenMP paralelo quickSort
Uma vez mais, eu estou preso ao usar o openMP em C ++. Desta vez, estou tentando implementar uma classificação rápida paralela.
Código
#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;
}
Algoritmo
Para usar o openMP para uma função recursiva, usei uma pilha para acompanhar os próximos intervalos nos quais a função qs deve ser executada. Eu adiciono manualmente o 1º intervalo [0, tamanho] e deixo os threads começarem a funcionar quando um novo intervalo é adicionado à pilh
O problema
O programa termina muito cedo, sem ordenar a matriz depois de criar o primeiro conjunto de intervalos ([q, i - 1], [i + 1, r] se você olhar no código. Meu palpite é que os threads que recebem o work, considera as variáveis locais da função quicksort (qs no código) compartilhadas por padrão, para que elas estraguem e não adicionem intervalo na pilh
Como eu compilar:
g++ -o qs qs.cc -Wall -fopenmp
Como eu corro:
./qs < in_100000 > out_100000
where in_100000 é um arquivo que contém 100000 na 1ª linha, seguido por 100k intergers na próxima linha, separados por espaço
Estou usando o gcc 4.5.2 no linux
Obrigado pela ajuda
Dan