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したがって、このアルゴリズムは、前の位置のキーがすでにソートされていることを前提としています。

たとえば、並列処理を導入する場合、2つのスレッド、スレッド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はキー-7を位置から6取得し、配列の最後に配置して、すべての要素を位置1 to 6（含まれている）から1つ右の位置にシフトします。これ-5で、の古い位置になり-7ます。（6）の古い位置は-7二度と比較されないので、-5そこに触れられないままになります。したがって、配列をソート解除します。

貧弱な解決策ではありますが、簡単な解決策は、OpenMPordered句をparallel for構成に追加することです。ただし、このコンストラクターを使用すると、基本的にコードがシーケンシャルになります。

もう1つの可能な解決策は、ニーズに100％適合するかどうかはわかりませんが、通常のサンプリングによってアルゴリズムを並列化することです。この後者の手法の例がに適用されていることがわかりますquicksort。

アルゴリズムの構造体は、直接並列化して優れた高速化を実現するのに最適ではありません。内部ループの各反復は相互に依存しているため、相互排除を不確実にするためのメソッドを使用する必要があり、同期のオーバーヘッドが発生します。直接並列化できるはるかに優れたソートアルゴリズムがあります。通常は、分割統治法を使用するものです。たとえば、基数ソートやクイックソートなどです。

于 2012-12-17T06:36:21.247 に答える