在OpenMP中插入排序

Question

我正在尝试为Insertion排序编写OpenMP解决方案,但是我遇到问题要让它并行运行并给出正确的结果:).有没有办法让Insertion排序并行运行.

这是我的代码:

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

Answer 1

您不能以这种方式并行化插入排序算法.从内部循环条件可以看出A[k-1]> key;,该算法假设对于数组key位置k中的给定,如果实际键大于存储在数组前一个位置的键,则swap应该停止.因此,该算法是假设下面的位置的按键k都已经排序.

例如,当您引入并行化时,使用两个线程,线程0将从数组的开头开始,而线程1将从一半开始.根据算法的假设,问题是前半部分没有排序,因此这将导致问题.

让我举个例子,array = [-1,2,-3,4,-5,6,-7,8]用2个线程排序:让我们修复一个给定的执行顺序(实际上是非确定性的)

• 1)线程0取k = 1且key = 2; 数组状态[-1,2,-3,4,-5,6,-7,8]
• 2)线程1取k = 5且key = 6; 数组状态[-1,2,-3,4,-5,6,-7,8]
• 3)线程0取k = 2且key = -3; 数组状态[-3,-1,2,4,-5,6,-7,8]
• 4)线程1取k = 6且key = -7; 数组状态[-7,-3,-1,2,4,-5,6,8]
• 5)线程0取k = 3且key = 2; 数组状态[-7,-3,-1,2,4,-5,6,8]
• 6)线程1取k = 7且key = 8; 数组状态[-7,-3,-1,2,4,-5,6,8]
• 7)线程0取k = 4且key = 4; 数组状态[-7,-3,-1,2,4,-5,6,8]

最后结果 : [-7,-3,-1,2,4,-5,6,8]

在第4行上,线程1 -7从位置获取键6并放置在数组的末尾,从位置1 to 6(包括)向右移动所有元素,因此现在-5位于旧位置-7.因为,-7(6)的旧位置永远不会被再次比较-5将留在那里不可触及.因此,使算法不排序.

一个简单但很差的解决方案是将OpenMP ordered子句添加到parallel for构造中.但是,使用它会使您的代码基本上是顺序代码.

另一个可能的解决方案,虽然我不是100%确定它可以适合您的情况,但是通过常规采样使您的算法并行.你可以在这里看到后一种技术适用的例子quicksort.

算法的结构不是直接并行化并实现加速的最佳结构.由于内循环的每次迭代都是相互依赖的,因此需要使用方法来确保互斥,从而导致开销.你有更好的排序算法可以直接并行化,通常是那些使用分而治之策略的算法,如Radix Sort或Quick Sort等.