C OpenMP并行quickSort

在C ++中使用openMP时，我再次陷入困境。 这次我正在尝试实现并行快速排序。

码：

#include  #include  #include  #include  #include  #include  #define SWITCH_LIMIT 1000 using namespace std; template  void insertionSort(std::vector &v, int q, int r) { int key, i; for(int j = q + 1; j = q && v[i] > key ) { v[i+1] = v[i]; --i; } v[i+1] = key; } } stack<pair > s; template  void qs(vector &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); 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 p; vector v; cin >> n; for(int i = 0; i > 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; } 

算法：

要将openMP用于递归函数，我使用堆栈来跟踪qs函数应运行的下一个时间间隔。 我手动添加第一个间隔[0，size]，然后在堆栈中添加新间隔时让线程开始工作。

问题：

程序结束得太早，没有在创建第一组间隔后对数组进行排序（[q，i – 1]，[i + 1，r]如果查看代码。我的猜测是获得工作的线程，考虑默认共享的quicksort函数的局部变量（代码中的qs），因此它们将它们弄乱并在堆栈中不添加间隔。

我如何编译：

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

我如何运行：

./qs out_100000

其中in_100000是第1行包含100000的文件，后面是以空格分隔的下一行的100k个整数。

我在linux上使用gcc 4.5.2

谢谢您的帮助，

担

Answer 1

我实际上并没有运行你的代码，但我发现p上有一个错误，它应该是private而不是shared 。 并行调用qs ： qs(v, p.first, p.second); 将在p上进行比赛，导致不可预测的行为。 qs的局部变量应该没问题，因为所有线程都有自己的堆栈。 但是，整体方法很好。 你走在正确的轨道上。

---

以下是我对并行快速排序实施的一般性评论。 Quicksort本身就是令人尴尬的并行 ，这意味着不需要同步。 qs在分区数组上的递归调用令人尴尬地并行。

但是，并行性以递归forms公开。 如果您只是在OpenMP中使用嵌套并行性，那么您将在一秒钟内拥有数千个线程。 不会加速。 因此，大多数情况下，您需要将递归算法转换为迭代算法。 然后，您需要实现一种工作队列。 这是你的方法。 而且，这并不容易。

对于您的方法，有一个很好的基准：OmpSCR。 您可以在http://sourceforge.net/projects/ompscr/下载

在基准测试中，有几个版本的基于OpenMP的快速排序。 他们中的大多数与你的相似。 但是，为了增加并行性，必须最小化全局队列上的争用（在代码中，它是s ）。 因此，可能会有一些优化，例如拥有本地队列。 虽然算法本身纯粹是并行的，但实现可能需要同步伪像。 而且，最重要的是，它很难获得加速。

---

但是，您仍然可以通过两种方式直接在OpenMP中使用递归并行：（1）限制线程总数，以及（2）使用OpenMP 3.0的task 。

这是第一种方法的伪代码（这仅基于OmpSCR的基准）：

 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); } } } } 

要运行此代码，您需要调用omp_set_nested(1)和omp_set_num_threads(2) 。 代码非常简单。 我们只是在工作的分工上产生两个线程。 但是，我们插入一个简单的限制逻辑来防止过多的线程。 请注意，我的实验显示了这种方法的体面加速。

---

最后，您可以使用OpenMP 3.0的task ，其中任务是逻辑上并发的工作。 在上面所有OpenMP的方法中，每个并行构造产生两个物理线程。 您可能会说任务与工作线程之间存在硬性的一对一映射。 但是， task将逻辑任务和工作者分开。

因为OpenMP 3.0还不流行，所以我将使用Cilk Plus ，它非常适合表达这种嵌套和递归的并行性。 在Cilk Plus中，并行化非常简单：

 void qsort(int* begin, int* end) { if (begin != end) { --end; int* middle = std::partition(begin, end, std::bind2nd(std::less(), *end)); std::swap(*end, *middle); cilk_spawn qsort(begin, middle); qsort(++middle, ++end); // cilk_sync; Only necessay at the final stage. } } 

我从Cilk Plus的示例代码中复制了这段代码。 您将看到一个关键字cilk_spawn是并行化快速排序的所有内容。 我正在跳过Cilk Plus的解释并生成关键字。 但是，它很容易理解：两个递归调用被声明为逻辑并发任务。 每当递归发生时，都会创建逻辑任务。 但是，Cilk Plus运行时（实现高效的工作窃取调度程序）将处理各种脏工作。 它最佳地将并行任务排队并映射到工作线程。

请注意，OpenMP 3.0的task基本上类似于Cilk Plus的方法。 我的实验表明，相当不错的加速是可行的。 我在8核机器上获得了3~4倍的加速。 而且，加速是规模。 Cilk Plus的绝对加速比OpenMP 3.0更高。

Cilk Plus（和OpenMP 3.0）的方法和您的方法基本相同：并行任务和工作负载分配的分离。 但是，有效实施起来非常困难。 例如，您必须减少争用并使用无锁数据结构。