1

アルゴリズムを並列化しようとして、いくつかの問題が発生しました。意図は、100x100 マトリックスにいくつかの変更を加えることです。openMPなしでアルゴリズムを実行すると、すべてが約34〜35秒でスムーズに実行されます.2つのスレッドで並列化すると（2つのスレッドのみである必要があります）、22秒程度になりますが、出力は間違っています。修正できない同期の問題。

コードは次のとおりです。

for (p = 0; p < sapt; p++){

    memset(count,0,Nc*sizeof(int));

    for (i = 0; i < N; i ++){
        for (j = 0; j < N; j++){

            for( m = 0; m < Nc; m++)
                dist[m] = N+1;

            omp_set_num_threads(2); 
            #pragma omp parallel for shared(configurationMatrix, dist) private(k,m) schedule(static,chunk)
            for (k = 0; k < N; k++){
                for (m = 0; m < N; m++){        

                    if (i == k && j == m)
                        continue;

                    if (MAX(abs(i-k),abs(j-m)) < dist[configurationMatrix[k][m]])
                        dist[configurationMatrix[k][m]] = MAX(abs(i-k),abs(j-m));       
                }
            }   


        int max = -1;

        for(m = 0; m < Nc; m++){

            if (dist[m] == N+1)
                continue;

            if (dist[m] > max){
                max = dist[m];
                configurationMatrix2[i][j] = m;
                }
            }           
        }
    }

    memcpy(configurationMatrix, configurationMatrix2, N*N*sizeof(int));


    #pragma omp parallel for shared(count, configurationMatrix) private(i,j)
    for (i = 0; i < N; i ++)
        for (j = 0; j < N; j++)
            count[configurationMatrix[i][j]] ++;

    for (i = 0; i < Nc; i ++)
        fprintf(out,"%i ", count[i]);
    fprintf(out, "\n"); 
}

その中で：sapt = 100; count -> 各ステップで行列の各要素がいくつあるかを保持するベクトルです。

(例: count[1] = 60--> 要素 '1' が行列に 60 回あるなど)

dist --> vectorこれは、たとえば値Kの要素i、jから同じ値Kの要素k、mまでの最大距離を保持します。

(例: dist[1] = 10--> 値 1 の要素から値 1 の最も遠い要素までの距離)

次に、出力ファイルに書き留めますが、やはり間違った出力です。

4

1 に答える 1

1

あなたのコードを正しく理解していれば、この行

count[configurationMatrix[i][j]] ++;

countインデックスが である要素でインクリメントしますconfigurationMatrix[i][j]。スレッドが の同じ要素を同時にインクリメントしようとしていないことを確認するために、コードが何らかの措置を講じているようには見えませんcount。configurationMatrixの 2 つの異なる要素が同じインデックスを提供し、countそれらの 2 つの要素が異なるスレッドによって処理されることは完全に可能です。++はアトミック操作ではないため、コードにはデータ競合があります。複数のスレッドが同じ変数への更新アクセスをめぐって競合する可能性があり、その結果、正確性または決定論の保証が失われます。

コードの他の部分にも同じ問題の他の例があると思います。逐次プログラムの結果と比較して、並列プログラムの結果に見られるエラーについては言及していませんが、これらのエラーは多くの場合、問題の診断に非常に役立ちます。たとえば、並列プログラムの結果が実行するたびに同じでない場合は、コードのどこかでデータ競合が発生している可能性が非常に高くなります。

これを修正するには？スレッドが 2 つしかないため、最も簡単な修正は、プログラムのこの部分を並列化しないことです。データ競合を OpenMP セクション内にラップすることもできますがcritical、それはコードをシリアライズする別の方法にすぎません。最後に、アルゴリズムとデータ構造を変更して、この問題を完全に回避することができます。

于 2013-11-10T21:04:28.920 に答える