0

C++ で OpenMP を使用しており、非常に単純なループを並列化したい。しかし、私はそれを正しく行うことはできません。いつも間違った結果が出ます。

for(i=2;i<N;i++)
    for(j=2;j<N;j++)
         A[i,j] =A[i-2,j] +A[i,j-2];

コード：

int const N = 10;
int arr[N][N];

#pragma omp parallel for
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        arr[i][j] = 1;

#pragma omp parallel for 
for (int i = 2; i < N; i++)
    for (int j = 2; j < N; j++)
    {
        arr[i][j] = arr[i-2][j] +arr[i][j-2];
    }

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
        printf_s("%d     ",arr[i][j]);
    printf("\n");
}

どうすればそれができるか提案はありますか？ありがとうございました！

4

4 に答える 4

3

問題のループ ネストを並列化するのは難しいですが、実行可能です。Lamport の論文「The Parallel Execution of DO Loops」では、この手法について説明しています。基本的に、(i,j) 座標を新しい座標系 (k,l) に 45 度回転させる必要があります。ここで、k=i+j および l=ij です。

実際に高速化するには、反復をタイルにグループ化する必要がある可能性が高いため、コードはさらに醜くなります (4 つのネストされたループ)。

まったく異なるアプローチは、OpenMP タスクを使用して問題を再帰的に解決することです。再帰は次のとおりです。

if( too small to be worth parallelizing ) {
    do serially
} else {
    // Recursively:
    Do upper left quadrant
    Do lower left and upper right quadrants in parallel
    Do lower right quadrant
}

実際問題として、メモリ アクセスに対する算術演算の比率が非常に低いため、例から高速化を実現することは困難です。

于 2013-09-05T22:48:22.853 に答える
3

これ

#pragma omp parallel for 
for (int i = 2; i < N; i++)
    for (int j = 2; j < N; j++)
    {
        arr[i][j] = arr[i-2][j] +arr[i][j-2];
    }

常に悲しみと予測不可能なアウトプットの源になります。OpenMP ランタイムは、各スレッドに一連の値をi渡し、それらをそのままにします。スレッドが更新される相対的な順序に決定性はありませんarr。たとえば、スレッド 1 がi = 2,3,4,5,...,100(またはその他のもので) 要素を更新し、スレッド 2 がプログラムで要素を更新している間、スレッド 2 がで更新された値を使用する前に、または後にi = 102,103,104,...,200スレッド 1 が更新されるかどうかを判断しません。古典的なデータ競合でコードを書きました。arr[i,:] = 100arr

これを修正するには、いくつかのオプションがあります。

arrスレッドが正しい (つまり、シーケンシャルな) 順序で更新されるようにするために、結び目を作ることができます。最終結果は、シーケンシャル プログラムよりも実行速度の遅い OpenMP プログラムになります。このオプションを使用しないでください。

の 2 つのコピーを作成しarr、常に一方から他方に更新し、次に他方から他方に更新することができます。のようなもの（非常に疑似コード）

for ...
{
    old = 0
    new = 1

    arr[i][j][new] = arr[i-2][j][old] +arr[i][j-2][old];

    old = 1
    new = 0
}

もちろん、この 2 番目のアプローチはスペースと時間のトレードオフですが、多くの場合、これは妥当なトレードオフです。

余分なプレーンを追加しても、arrキャッシュに取り込まれた値の空間的局所性が損なわれるため、すぐには速度が向上しないことがあります。これを少し試してみてください。おそらく[old]、最後の要素ではなく最初のインデックス要素を作成してください。

配列内の各要素の更新は、2 行/列離れた要素の値に依存するため、配列をチェス盤のように白と黒の要素に効果的に分割しています。同じデータへのアクセスのためにスレッドが競合することなく、「色」ごとに 1 つずつ、2 つのスレッドを使用できます。繰り返しますが、キャッシュ内の空間的局所性の混乱は、速度に悪影響を与える可能性があります。

他のオプションが思い浮かんだ場合は、それらを編集します。

于 2013-09-05T11:02:22.617 に答える