のOpenMP：ループは、私は次のようにC++で簡単な累積和コードを実装しようとしています依存

Question

持ち越さ：このsiteオン

x[0] = 0; 
for (k=1;k<100; k++) 
    x[k] = x[k-1] + x[k]; 

を、実装は、依存関係を超えるループキャリーを排除するために書き留めています。コードは2つのスレッドのために、次のようになります。

x[0] = 0; 
x[49] = 74; //pre calculated 
//the outer loop is parallelized (two instances) 
#pragma omp parallel for private(m,k) 
    for(m=0;m<2;m++) { 
    for (k=m*49+1; k<m*50+50; k++) { 
     x[k] = x[k-1] + x[k]; 
    } 
    } 

問題、私はまだここに（平行に走る2つのスレッドが、1から別のデータを必要とする）ループキャリー依存関係を参照してくださいです。

ここで説明を加えてください。そのような依存関係を排除する最良の方法は何ですか？

Answer 1

x[49]の値が既に存在するため、再度計算する必要はありません。k = 0とk = 49の繰り返しをスキップできます。そのため、ループは2つのネストされたループで展開されます。

ただし、エラーがあるようです。内側ループのためのループキャリー依存性のみが存在し、外側ループの反復にわたって伝搬するはずです。

• m = 0、k = 1 .. 48で（すでに0と49を得た）：制限が適切に定義されていないためです。
• m = 1とk = 50 ..99（もう、すでに49があります！）

したがって、ループは次のように左にする必要があります。

for(m = 0; m < 2; m++) { 
    for (k=m*49+1; k<m*51+49; k++) { 
    x[k] = x[k-1] + x[k]; 
    } 
} 

あなたはほかのことを変更した場合：

x[k+1] = x[k] + x[k+1]; 

それは下位ビットあなたのバウンドを簡素化することができます。 ..

for(m = 0; m < 2; m++) { 
    for (k=m*50; k < m*51+48; k++) { 
    x[k+1] = x[k] + x[k+1]; 
    } 
}