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;可以看出，该算法假定对于数组k位置中的给定key，如果实际键大于存储在数组前一个位置的键，数组swap应该停止.因此，该算法假定k以下位置的键已已排序.

You can not parallelize the Insertion Sort algorithm this way. As you can see from the inner loop condition A[k-1]> key;, this algorithm is assuming 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 swap should stop. Therefore, the algorithm is assuming that the keys on the positions below k are already sorted.

例如，当您使用两个线程引入并行化时，线程0将从数组的开头开始，线程1将从一半开始.问题在于，根据算法的假设，前半部分没有排序，因此会出现问题.

When you introduce parallelization, with two thread, for example, thread 0 will start from the beginning of the array, and thread 1 will start from the half. The problem is that the first half is not sorted, according to the assumption made by the algorithm, thus this will lead to problems.

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

Let me give you an example, sorting an array = [-1,2,-3,4,-5,6,-7,8] with 2 threads: Let's fix a given execution ordered (in reality is non-deterministic)

• 1)线程0的k = 1，密钥= 2；阵列状态[-1,2,-3,4,-5,6,-7,8]
• 2)线程1的k = 5，密钥= 6；阵列状态[-1,2,-3,4,-5,6,-7,8]
• 3)线程0取k = 2，键= -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，密钥= 2；阵列状态[-7,-3,-1,2,4,-5,6,8]
• 6)线程1的k = 7，密钥= 8；阵列状态[-7,-3,-1,2,4,-5,6,8]
• 7)线程0的k = 4，密钥= 4；阵列状态[-7,-3,-1,2,4,-5,6,8]

• 1) Thread 0 takes k = 1 and key = 2; array status [-1,2,-3,4,-5,6,-7,8]
• 2) Thread 1 takes k = 5 and key = 6; array status [-1,2,-3,4,-5,6,-7,8]
• 3) Thread 0 takes k = 2 and key = -3; array status [-3,-1,2,4,-5,6,-7,8]
• 4) Thread 1 takes k = 6 and key = -7; array status [-7,-3,-1,2,4,-5,6,8]
• 5) Thread 0 takes k = 3 and key = 2; array status [-7,-3,-1,2,4,-5,6,8]
• 6) Thread 1 takes k = 7 and key = 8; array status [-7,-3,-1,2,4,-5,6,8]
• 7) Thread 0 takes k = 4 and key = 4; array status [-7,-3,-1,2,4,-5,6,8]

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

在第4行上，线程1从位置6取出键-7并将其放在数组的末尾，将位置1 to 6(包括)的所有元素筛选到右侧一个位置，所以现在-5在-7的旧位置上.由于-7(6)的旧位置将不再被比较，-5将保持不变.因此，使算法无法排序.

On line 4 thread 1 takes the key -7 from position 6 and puts at the end of the array sifting all the 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. Hence, making the algorithm not sorted.

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

An easy but a poor solution would be to add the OpenMP ordered clause to the parallel for construct. But, using this would make your code basically a sequential one.

另一种可能的解决方案，尽管我不是100％确信它可以适合您的情况，但可以通过常规采样"使您的算法并行化.您可以在此处看到后一种技术的示例适用于quicksort.

Another possible solution, although I am not 100% sure it can fit on your case, would be making your algorithm parallel by Regular Sampling. You can see here an example of this latter technique apply on quicksort.

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

The struct of your algorithm is not the best one to be parallelize directly and achieve speedup it. Since each iteration of the inner loop is interdependent, this will required the use of methods to unsure mutual exclusion, thus resulting in overhead. You have far better sorting algorithm that you can directly parallelize, typically the ones that use an divide and conquer strategy such as Radix Sort or Quick Sort among others.

这篇关于OpenMP中的插入排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！