CPU 上的并行八叉树构造

Question

我做了一个八叉树的简单实现。现在我正在尝试在 CPU.

上并行构建树

首先，我尝试使向树的子节点添加点的步骤平行（这是构造中成本最高的步骤），但由于每次添加时都必须锁定 vector/list指出它没有获得任何性能优势。

现在我正在尝试并行构建树中的每个节点。这个想法很简单，应该是直截了当的，因为节点之间没有交集。我只需要为每个线程分配一个节点来处理。问题是它是一个嵌套的自上而下的实现，所以我不确定什么是最好的实现方式。

我正在使用 C++ 和 OpenMP。我试着在构建函数中写这个：

 omp_set_nested(1);
#pragma omp parallel for schedule(dynamic)
    for (int i = 0; i < child_count; i++) {
        _child[i]->build(threshold, maximumDepth, currentDepth + 1);
    }

但是性能变得比连续的差很多。

然后我尝试只并行化前 8 个节点（根节点）。这使我获得了 X2-X3 的性能增益。但是，这在很大程度上取决于场景。如果我的场景太不平衡，那么并行性将没有什么好处，因为前 8 个节点中的 7 个可能几乎是空的，而一个节点拥有所有其他点。

对如何正确执行此操作有任何想法吗？

Answer 1

使用任务而不是嵌套并行。试试这个代码：

#pragma omp parallel
#pragma omp single nowait
{       
            \ first call to build function       
}

内部构建函数使用以下代码。请注意，currentDepth> XXX 是停止创建更多任务的条件。

for (int i = 0; i < child_count; i++) 
{
   #pragma omp task final( currentDepth> XXX ) mergeable \
   default(none) firstprivate(threshold, maximumDepth, currentDepth)
     _child[i]->build(threshold, maximumDepth, currentDepth + 1);
}

如果 child_count > 1 下面的代码可能会更快：

for (int i = 0; i < child_count-1; i++) 
{
   #pragma omp task final( currentDepth> XXX ) mergeable \
   default(none) firstprivate(threshold, maximumDepth, currentDepth)
     _child[i]->build(threshold, maximumDepth, currentDepth + 1);
}
_child[child_count-1]->build(threshold, maximumDepth, currentDepth + 1);

CPU 上的并行八叉树构造

Parallel octree construction on the CPU

parallel-processing

cpu

graphics

octree