c - OpenMP 中的插入排序

Question

我正在尝试为插入排序编写 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;
}

Answer 1

您不应以这种方式并行化插入排序算法。从内部循环条件 A[k-1]> key; 可以看出，该算法假设对于位置 k 的给定 key > 数组，如果实际键大于存储在数组先前位置的键，则元素的交换停止。因此，该算法假定 k 之前位置上的键已经排序。

当您引入并行性时，例如，对于两个线程，线程 0 和 1 分别从数组的开头和中间开始。但是，根据算法做出的(错误)假设，数组的前半部分未排序，因此会导致问题。

让我来说明这个问题，让我们用 2 个线程对 array = [-1,2,-3,4,-5,6,-7,8] 进行排序:让我们修复一个给定的执行顺序(在现实中它是不确定的)

• >
  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 获取键 -7 并将其放在数组的末尾，筛选其所有元素从位置 1 到 6(包括)向右移动一个位置，所以现在 -5 位于 -7 的旧位置。因为，-7 (6) 的旧位置将永远不会再被比较，-5 将保持在那里不可触及。因此，使数组未排序。

一个简单但很差的解决方案是将 OpenMP ordered 子句添加到 parallel for 结构中。但是，使用此构造函数基本上会顺序化您的代码。

尽管我不能 100% 确定它符合您的需求，但另一种可能的解决方案是通过常规采样使您的算法并行。可以看到here后一种技术的示例适用于 quicksort。

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