ループ内でシリアル化されたカウンタ変数を並列化する最良の方法

Question

"シリアル" counterの問題を含むこの4つのネストされたループを並列化しようとしています。

count = 0 
for (i = 0; i < vel; i++) 
    for (n = 0; n < dist; n++) 
     for (j = 1; j <= Y; j++) 
     for (k = 1; k <= Z; k++) { 

      index = index(X, j, k);   
      buffX[count] = array[index]; 

      index = index(Y, j, k);     
      buffY[count] = array[index]; 
      ++count; 
     } 

私は、次のような非常に単純なアイデア試してみた：

#pragma omp parallel for private(i,n,j,k,index) shared(count) 
    for (i = 0; i < vel; i++) 
     for (n = 0; n < dist; n++) 
      for (j = 1; j <= Y; j++) 
#pragma omp critical 
{ 
      for (k = 1; k <= Z; k++) { 

       index = index(X, j, k);   
       buffX[count] = array[index]; 
       index = index(Y, j, k);     
       buffY[count] = array[index]; 
       ++count; 
      } 
} 

をしかし、それは理由countでは動作しません。私はこの種のループを並列化するためのよく知られた技術があるのだろうかと思っていました。

Answer 1

まっすぐな方法は、ネストされたループ変数からのThreadLocal count変数を計算することである。

for (i = 0; i < vel; i++) 
    for (n = 0; n < dist; n++) 
    for (j = 1; j <= Y; j++) 
     for (k = 1; k <= Z; k++) { 
     int count = (k-1) + Z * ((j-1) + Y * (n + dist * i)); 
     ... 

あなたは余分なコストのために心配している場合は、間にあるいくつかの中間count_jを作ることができます。

代替手動ループを崩壊し、count一次ループインデックスを作ることである：これは正ループの並列性能（より多くの反復、より良いバランス）または負（悪い影響を与えることが

#pragma omp parallel for 
for (count = 0; count < vel * dist * Y * Z; count++) { 
    // declare locally to make sure they are threadlocal 
    int k = 1 + (count % Z); 
    ... 

注キャッシュ効果）。

ループ本体全体が重要なセクションに過ぎないソリューションはひどいでしょう。どのスレッドも並列に計算（またはメモリ転送）を行うことはできません。クリティカルな領域には順序保証が導入されておらず、コードが間違っています。