OpenMP并行快速排序
我尝试使用OpenMP在分区部分和快速排序部分中并行快速排序。 我的C代码如下：
#include "stdlib.h" #include "stdio.h" #include "omp.h" // parallel partition int ParPartition(int *a, int p, int r) { int b[rp]; int key = *(a+r); // use the last element in the array as the pivot int lt[rp]; // mark 1 at the position where its element is smaller than the key, else 0 int gt[rp]; // 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[jp] = *(a+j); if (*(a+j) < key) { lt[jp] = 1; gt[jp] = 0; } else { lt[jp] = 0; gt[jp] = 1; } } // calculate the new position of the elements for ( j=0; j<(rp); ++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[rp-1]; *(a+p+k) = key; // move elements to their new positon #pragma omp parallel for for ( j=p; j<r; ++j) { if (b[jp] key) *(a+k+gt[jp]) = b[jp]; } 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; } 我是OpenMG和并行编程的新手。 对于main函数中的示例，排序结果为：
0 9 9 2 2 2 6 7 7 7
我用gdb来调试。 在早期的递归中，一切顺利。 但在一些递归中，它突然搞砸了，开始重复元素。 然后生成上述结果。
有人可以帮我找出问题所在吗？ 非常感谢你！
我为我的第一条评论感到抱歉。这与你的问题没关系。我没有找到你问题的真正问题（也许你的移动元素有问题）。根据你的意见，我写了一个类似的程序，它工作正常（我也是OpenMP的新成员）。
#include #include int partition(int * a, int p, int r) { int lt[rp]; int gt[rp]; int i; int j; int key = a[r]; int lt_n = 0; int gt_n = 0; #pragma omp parallel for for(i = p; i < r; i++){ if(a[i] < a[r]){ lt[lt_n++] = a[i]; }else{ gt[gt_n++] = a[i]; } } for(i = 0; i < lt_n; i++){ a[p + i] = lt[i]; } a[p + lt_n] = key; for(j = 0; j < gt_n; j++){ a[p + lt_n + j + 1] = gt[j]; } return p + lt_n; } void quicksort(int * a, int p, int r) { int div; if(p < r){ div = partition(a, p, r); #pragma omp parallel sections { #pragma omp section quicksort(a, p, div - 1); #pragma omp section quicksort(a, div + 1, r); } } } int main(void) { int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6}; int i; quicksort(a, 0, 9); for(i = 0;i < 10; i++){ printf("%d\t", a[i]); } printf("\n"); return 0; }
我已经在生产环境中实现了并行快速排序，尽管使用并发进程（即fork（）和join（））而不是OpenMP。 我还发现了一个非常好的pthread解决方案，但就最坏情况运行时而言，并发流程解决方案是最好的。 首先我要说的是，您似乎并没有为每个线程复制输入数组，因此您肯定会遇到可能损坏数据的竞争条件。
基本上，正在发生的事情是你在共享内存中创建了一个数组N ，当你执行一个#pragma omp parallel sections ，你产生的工作线程与#pragma omp section一样多。 每次工作线程尝试访问和修改a的元素时，它将执行一系列指令：“从给定地址读取N的第n个值”，“修改N的第n个值”，“写入N的第n个值回到给定的地址“。 由于您有多个线程没有锁定或同步，因此读取，修改和写入指令可以由多个处理器以任何顺序执行，因此线程可以覆盖彼此的修改或读取未更新的值。
我找到的最佳解决方案（经过数周的测试和基准测试，我提出了许多解决方案）是将列表log（n）次细分，其中n是处理器的数量。 例如，如果您有四核机器（n = 4），请将列表细分2次（log（4）= 2），选择作为数据集中位数的枢轴。 重要的是枢轴是中位数，因为否则你最终可能会遇到一个错误选择的枢轴导致列表在过程中不均匀分布的情况。 然后，每个进程对其本地子数组进行快速排序，然后将其结果与其他进程的结果合并。 这被称为“hyperquicksort”，从最初的github搜索，我发现了这一点 。 我不能保证那里的代码，并且不能发布我写的任何代码，因为它受NDA保护。
顺便说一句，最好的并行排序算法之一是PSRS（通过常规采样进行并行排序），它可以使进程之间的列表大小更加平衡，不会在进程之间不必要地传递密钥，并且可以处理任意数量的并发进程（他们不一定必须是2）的力量。
这似乎是错误的，我的操作看起来像这样
[student@localhost ~]$ g++ -openmp QuickSort1.cpp [student@localhost ~]$ ./a.out Enter the size of array:8 Enter element at 0:77 Enter element at 1:99 Enter element at 2:22 Enter element at 3:44 Enter element at 4:11 Enter element at 5:66 Enter element at 6:88 Enter element at 7:55 =====================After Sorting=================== 11 22 44 99 55 66 77 88