OpenMP 中的插入排序 [英] Insertion Sort in OpenMP
问题描述
我正在尝试为插入排序编写 OpenMP 解决方案，但我在使其并行运行并给出正确结果时遇到问题:).有什么办法可以让插入排序并行运行.
I'm trying to write OpenMP solution for Insertion sort but I'm having problems to make it run in parallel and give correct results :). Is there any way to make Insertion sort it run in parallel.
这是我的代码:
void insertionsort(int *A, int num)
{
// clock_t start, stop;
//
// start=clock();
int k;
#pragma omp parallel for shared(A) private(k)
for(int n = 1; n < num; n++)
{
int key = A[n];
k = n;
#pragma omp critical
for(;k>0 && A[k-1]> key;k--)
{
A[k] = A[k-1];
}
A[k] = key;
}
// stop=clock();
// cas = (double)(stop-start)/CLOCKS_PER_SEC;
}
推荐答案
您不应该以这种方式并行化插入排序算法.从内循环条件 A[k-1]>key; 可以看出，该算法假设对于给定的 key 在数组的位置 k 中，如果实际的密钥大于存储的密钥在数组的前一个位置，元素的交换停止.因此，该算法假设 k 之前位置的键已经排序.
You should not parallelize the Insertion Sort algorithm in this manner. From the inner loop condition A[k-1]> key; one can see that this algorithm assumes that for a given key in the position k of the array, if the actual key is bigger than the keys stored on the previous position of the array the swapping of elements stops. Hence, this algorithm assumes that the keys on the positions before k are already sorted.
当你引入并行性时，例如，有两个线程，线程 0 和 1 分别从数组的开头和中间开始.但是，根据算法做出的(错误)假设，数组的前半部分没有排序，因此会导致问题.
When you introduce parallelism, for instance, with two threads, threads 0 and 1 start from the beginning and middle of the array, respectively. However, the first half of the array is not sorted, according to the (wrong) assumption made by the algorithm, which consequently, leads to issues.
让我说明问题，让我们用2个线程对array = [-1,2,-3,4,-5,6,-7,8]进行排序:让我们修复一个给定的执行顺序(实际上它是不确定的)
Let me illustrate the problem, let us sort the array = [-1,2,-3,4,-5,6,-7,8] with 2 threads:
Let us fix a given execution ordered (in reality it is non-deterministic)
- 线程 0 取 k = 1 和 key = 2；数组状态
[-1,2,-3,4,-5,6,-7,8]
- 线程 1 取 k = 5 和 key = 6；数组状态
[-1,2,-3,4,-5,6,-7,8]
- 线程 0 取 k = 2 和 key = -3；数组状态
[-3,-1,2,4,-5,6,-7,8]
- 线程 1 需要 k = 6 和 key = -7；数组状态
[-7,-3,-1,2,4,-5,6,8]
- 线程 0 取 k = 3 和 key = 2；数组状态
[-7,-3,-1,2,4,-5,6,8]
- 线程 1 取 k = 7 和 key = 8；数组状态
[-7,-3,-1,2,4,-5,6,8]
- 线程 0 需要 k = 4 和 key = 4；数组状态
[-7,-3,-1,2,4,-5,6,8]
最终结果:[-7,-3,-1,2,4,-5,6,8]
在第 4 行线程 1 从位置 6 获取键 -7 并将其放在数组的末尾，筛选其所有元素从位置1到6(包括)向右一个位置，所以现在-5在-7的旧位置.因为， -7 (6) 的旧位置将永远不会再次比较 -5 将保持在那里不可触及.因此，使数组未排序.
On line 4 thread 1 takes the key -7 from position 6 and puts it in the end of the array sifting all its elements from positions 1 to 6 (included) one position to the right, so now -5 is on the old position of -7. Since, the old position of -7 (6) will never be compared again -5 will stay there untouchable. Therefore, making the array unsorted.
一个简单但差的解决方案是将 OpenMP ordered 子句添加到 parallel for 结构中.但是，使用此构造函数基本上可以对您的代码进行顺序化.
An easy, albeit poor solution, would be to add the OpenMP ordered clause to the parallel for construct. However, using this constructor would basically sequentialize your code.
另一种可能的解决方案，虽然我不是 100% 确定它符合您的需求，但通过常规采样使您的算法并行.您可以在此处查看后一种技术的示例应用于 quicksort.
Another possible solution, although I am not 100% sure it fits your needs, would be to make your algorithm parallel by Regular Sampling. You can see here an example of this latter technique apply on quicksort.
您的算法结构不是最适合直接并行化并实现良好加速的.由于内循环的每次迭代都是相互依赖的，这就需要使用不确定互斥的方法，从而导致同步开销.您有更好的排序算法可以直接并行化，通常是使用分治策略的排序算法，例如基数排序或快速排序等.
The struct of your algorithm is not the most suitable to be parallelize directly and achieve a good speedups. Since each iteration of the inner loop is interdependent, this will required the use of methods to unsure mutual exclusion, thus resulting in synchronization overhead. You have far better sorting algorithm that you can directly parallelize, typically the ones that use a divide-and-conquer strategy, for instance Radix Sort or Quick Sort, among others.
这篇关于OpenMP 中的插入排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
