配列のインデックス付けを並列で処理する最適な方法は？

Question

私は次のような状況に陥っています。サイズLのボックスにパーティクルのリストがあります。ここで、Lは辺の長さです。

次に、ボックスをセルに分割します（L/cell_dim = 7）。したがって、7 * 7 * 7セルがあります。

最後に、私は、それらの位置に注意し、全ての粒子を読んで、それらがに記載されていたセル計算する。

---

IはループのOpenMPの並列に上記を達成します。しかし、スレッドセーフな方法で情報をキャプチャする必要があり、各セルのすべてのパーティクルをループする必要はありません。ですから、粒子の任意の部分集合を各セルに並列に記録する方法が必要です。

---

私は現在、OpenMPクリティカルコードブ​​ロックを使用しています。私は配列サイズ[7] [7] [max_パーティクル]を持っています。ここでmax_particlesはセルあたりのパーティクルの最大数ですが、パーティクルの総数よりもはるかに少ないです。 、これは動作しますが

int cube[7][7][7][10]; 
int cube_counts[7][7][7]={0}; 

#pragma omp parallel for num_threads(a lot) 
for (int i = 0; i < num_particles; i++){ 
    cell_x = //cell calculation; 
    cell_y = //ditto; 
    cell_z = //...; 

#pragma omp critical 
    { 
     cube_counts[cell_x][cell_y][cell_z] += 1; 

     // for readability 
     int index = cube_counts[cell_x][cell_y][cell_z]; 

     cube[cell_x][cell_y][cell_z][index] = i; 
    } 
} 

// rest in pseudo code: 

foreach cell: 
    adjacent_cell = cell2 

    particle_countA = cube_counts[cellx][celly][cellz] 
    particle_countB = cube_counts[cell2x][cell2y][cell2z] 

    // these two for loops will cover ~2-4 particles, 
    // so super small...as a result of the cell analysis above. 
    for particle in cell: 
     for particle in cell2: 
      ...do stuff 

：私はカウンターのアレイサイズに追加された最後のパーティクルのインデックス[7] [7] [7]を記録し、私の並列ループの最新のカウント数に応じてセル配列を更新します私は重要なブロック（私は60の物理的な、240論理的なインテルコプロセッサ上にある）を排除することができるときに2倍以上の速度で増加します。

クリティカルブロックを必要としないでこれをどのように達成できますか？私は大規模な配列を考えていましたが、7 * 7 * 7 * 257（257はパーティクル数）の配列を反復するときに得たすべてを失います。リンクされたリストには依然として競合条件があります。

多分、何らかの種類の順序付けられていないスレッドセーフリスト...？

Answer 1

ロックを使用する代わりに、クリティカルセクションをさらに駆動することができます。

あなたはコンパイラが正しいのx86特定のアセンブラ命令に変換することアトミックインクリメントとアトミック割り当て擬似コール（「組み込み関数」）を使用することができます。しかしこれはプラットフォームやコンパイラに依存しています。

最新のC++コンパイラ（C++ 11）を使用している場合は、std :: atomic_ *を使用するのが最善の方法かもしれません。