入れ子になったループを減らすためにompを使う

Question

入れ子のforループを並列化するのに問題があります。コードは、この

for(k = 0; k < m; k++) { 
    for(i = 0; i < k; i++) { 
     s = 0.0; 
#pragma omp parallel for default(none) shared(i, k, q, m, n) private(j) reduction(+:s) 
     for(j = 0; j < n; j++) { 
     s += q[ i ][ j ] * q[ k ][ j ]; 
     } 
    } 
    } 

このコードの作品のようになりますが、「K」と「I」のループの下に何回ものスレッドを作成し、破棄する際によるオーバーヘッドのために非常に遅い実行されます。

理想的には私は、並列領域は一度だけ作成され、この

#pragma omp parallel default(none) shared(i, k, q, m, n, s) private(j) 
    for(k = 0; k < m; k++) { 
    for(i = 0; i < k; i++) { 
     s = 0.0; 
#pragma omp for reduction(+:s) 
     for(j = 0; j < n; j++) { 
     s += q[ i ][ j ] * q[ k ][ j ]; 
     } 
    } 
    } 

ような何かをしたいです。しかし、私は間違った結果を得ています。私はこれが変数 's'が共有されているためだと思います。

's'を共有して引き続き削減を行う方法はありますか？

ありがとうございます！

P.S.以前の反復に依存するので、私は 'k'または 'i'ループを並列化できません。

Answer 1

あなたが省略したiのループ内にコードがありますか、それともありますか？そのコードは多くのドット積を計算するだけなので、最後にq[m-1][]とq[m-2][]のドット積がsに格納されます。また、与えられたように、あなたのコードはループ反復間のデータ依存性を持たないが、静的スケジューリングを使用して他のループを並列化すると、むしろ負荷不均衡を示すだろう。

#pragma omp parallel default(none) shared(q, m, n) \ 
      private(i, k, j) lastprivate(s) schedule(dynamic,1) 
for(k = 0; k < m; k++) { 
    for(i = 0; i < k; i++) { 
    s = 0.0; 
    for(j = 0; j < n; j++) { 
     s += q[ i ][ j ] * q[ k ][ j ]; 
    } 
    } 
} 

コンパイラがバージョン3.0以上の標準をサポートしている場合は、OpenMPタスクを使用することもできます。

@Zhenyaの場合、jループが最も外側にある場合、q[i][j]とq[i+1][j]はC/C++のメモリ内に隣接していないため、キャッシュの利点は失われます。