并行处理数组索引的最佳方法？

我有以下情况：我有一个大小为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

并行处理数组索引的最佳方法？

回答

相关问题