在OpenMP中插入排序
我正在尝试为插入排序编写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 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;可以看出A[k-1]> key; ，该算法假设对于arrays位置k中的给定key ，如果实际键大于存储在arrays的先前位置上的键，则swap应该停止。 因此，该算法假设已经对 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] - 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从位置6获取键-7并且在arrays的末尾放置从位置1 to 6 （包括）向右移动一个位置的所有元素，所以现在-5位于旧位置-7 。 因为，-7（6）的旧位置将永远不会再次比较-5将保持在那里不可触及。 因此，使算法不排序。
一个简单但很差的解决方案是将OpenMP ordered子句添加到parallel for construct中。 但是，使用它会使您的代码基本上是顺序代码。
另一种可能的解决方案，虽然我不是100％确定它可以适合您的情况，但是通过常规采样可以使您的算法并行。 你可以在这里看到后一种技术适用于quicksort一个例子。
算法的结构不是直接并行化并实现加速的最佳结构。 由于内循环的每次迭代都是相互依赖的，因此需要使用方法来确保互斥，从而导致开销。 你有更好的排序算法可以直接并行化，通常是那些使用分而治之策略的算法，如Radix Sort或Quick Sort等。