3

我正在尝试为插入排序编写 OpenMP 解决方案，但在使其并行运行并给出正确结果时遇到了问题:)。有什么方法可以让插入排序并行运行。

这是我的代码：

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

1 回答 1

7

您不应该Insertion Sort algorithm以这种方式并行化。从内部循环条件A[k-1]> key;可以看出，该算法假设对于给定的数组key位置k，如果实际键大于存储在数组前一个位置上的键，则元素交换停止。因此，该算法假设之前位置上的键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]
    1. 线程 1 需要 k = 5 和 key = 6；阵列状态[-1,2,-3,4,-5,6,-7,8]
    1. 线程 0 需要 k = 2 和 key = -3；阵列状态[-3,-1,2,4,-5,6,-7,8]
    1. 线程 1 需要 k = 6 和 key = -7；阵列状态[-7,-3,-1,2,4,-5,6,8]
    1. 线程 0 需要 k = 3 和 key = 2；阵列状态[-7,-3,-1,2,4,-5,6,8]
    1. 线程 1 需要 k = 7 和 key = 8；阵列状态[-7,-3,-1,2,4,-5,6,8]
    1. 线程 0 需要 k = 4 和 key = 4；阵列状态[-7,-3,-1,2,4,-5,6,8]

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

在第 4 行，线程从位置1获取键并将其放在数组的末尾，从位置（包括）向右一个位置筛选其所有元素，所以现在位于. 既然，（6）的旧位置将永远不会再被比较，将保持不变。因此，使数组未排序。-761 to 6-5-7-7-5

一个简单但较差的解决方案是将 OpenMPordered子句添加到parallel for构造中。但是，使用此构造函数基本上会按顺序排列您的代码。

另一种可能的解决方案，虽然我不是 100% 确定它是否符合您的需求，但将通过常规采样使您的算法并行。您可以在此处看到后一种技术应用的示例quicksort。

您的算法结构不是最适合直接并行化并实现良好的加速。由于内部循环的每次迭代都是相互依赖的，这将需要使用不确定互斥的方法，从而导致同步开销。您拥有可以直接并行化的更好的排序算法，通常是使用分治策略的算法，例如基数排序或快速排序等。

于 2012-12-17T06:36:21.247 回答