並行處理數組索引的最佳方法？

我有以下情況：我有一個大小爲L的框中的粒子列表，其中L是其中一個邊的長度。並行處理數組索引的最佳方法？

接下來，我將盒子拆分成單元格，其中L/cell_dim = 7。所以有7 * 7 * 7個單元格。

最後，我通過所有的顆粒讀，注意它們的位置，並計算出它們在哪個小區。

我實現上述在OpenMP並行for循環的。但是，我需要以線程安全的方式捕獲信息，以便我不必遍歷每個單元格的所有粒子。所以我需要一些方法來並行地將任意子集的粒子記錄到每個單元格中。

我現在使用的方法利用了OpenMP關鍵代碼塊。我有一個數組大小[7] [7] [7] [max_particles]，其中max_particles是每個單元中粒子數最多的粒子，但它比粒子總數要少得多。我記錄在一個計數器陣列尺寸增加[7] [7] [7]，並根據我的並行循環的最新統計更新單元陣列的最後一個粒子的指標：

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

雖然這個工程，當我能夠消除關鍵塊（我在具有60個物理，240個邏輯的Intel協處理器上）時，它的速度增加了2倍以上。

如何在不需要關鍵塊的情況下完成此操作？我想過做一個大陣列......但是當我迭代7 * 7 * 7 * 257（其中257是粒子數）陣列時，我失去了所有獲得的東西。鏈接列表仍然存在競爭條件。

也許某種無序的線程安全列表...？

來源

2016-09-17 bordeo

難道你不能只將粒子分成N個任意大致相等的大小集合，其中N是物理線程的數量？ –

@乾杯和hth。 - 阿爾弗我不這麼認爲......也許：粒子本身不是線程安全的 - 它們與所有其他粒子交互。所以真的，我只需要知道每個細胞中有哪些粒子......以及有多少粒子。我想我可以將它們分開...然後我將有60 * 7 * 7 * 7的鏈表，我必須將它們堆疊在一起形成7 * 7 * 7鏈表...它可能變得非常討厭...並結束了具有相似數量的關鍵操作... – bordeo

在打開mp的關鍵塊是一個相當沉重的構造，因爲它鎖定了一個完整的代碼片段。鎖可能工作得很好。 – Mehno

使用鎖代替臨界區可以進一步推動：

您可以使用原子增量和原子分配僞電話（「內在」），編譯器將轉化爲正確的x86特定的彙編指令。然而，這是平臺甚至編譯器的依賴。

如果您使用現代C++編譯器（C++ 11），那麼std :: atomic_ *可能是最好的方法。

來源

2016-09-20 07:57:42

並行處理數組索引的最佳方法？

回答

相關問題