c – 在OpenMP中插入排序

发布时间：2020-12-16 09:41:07 所属栏目：百科来源：网络整理

导读：我正在尝试为Insertion排序编写OpenMP解决方案,但是我遇到问题要让它并行运行并给出正确的结果:).有没有办法让Insertion排序并行运行. 这是我的代码： void insertionsort(int *A,int num){// clock_t start,stop;// // start=clock();int k;#pragma omp par

我正在尝试为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;
}

解决方法

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

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

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

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

最终结果：[ – 7,8]

在第4行,线程1从位置6获取键-7并且在阵列的末尾放置从位置1到6(包括)向右移动一个位置的所有元素,所以现在-5位于旧位置 – 7.因为,-7(6)的旧位置将永远不会再被比较-5将保持在那里不可触及.因此,使算法不排序.

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!