c++ - OpenMP 中树结构的线程安全

Question

我有一个基于 Barnes-Hut 算法的 N 体模拟器，我使用 OpenMP 对其进行了多线程处理。通过简单地在几个关键位置添加#pragma omp parallel for，大部分程序就可以实现并行化。这提供了一个健康的加速，当引力体的数量低于几千时，它可以很好地与核心数量成比例。

因为我的程序使用了 Barnes-Hut algorithm ，它的核心是一个树结构，在 2d 中这是一个四叉树，在我的例子中是一个八叉树。我在多线程填充树的过程中遇到了麻烦。使此步骤成为单线程可防止程序充分利用我的处理器。我的 CPU 使用率实际上随着我添加的主体越多而下降，因为更多的时间花费在仅使用一个内核将所有主体添加到八叉树上。

现在将单个主体添加到八叉树的方法如下所示:

void octant::addBody(vec3 newPosition, float newMass) {

    // Making room for new bodies by dividing if the node is a leaf
    if (isLeaf) {

        // Subdividing the octant
         divide();

        // Moving the body already contained
        subdivisionEnclosing(this->position)->addBody(this->position, this->mass);
    }

    // Adding the body to the appropriate subdivision if the node is divided
    if (divided) {

        // Adding the new body to the appropriate octant
        subdivisionEnclosing(newPosition)->addBody(newPosition, newMass);

        return;
    }

    // If the node doesnt yet contain any bodies at all, add the new one
    this->position = newPosition;
    this->mass = newMass;

    // This node only contains one body, so the center of mass is accurate
    isLeaf = true;
    calculatedCOM = true;
}

这在连续调用时工作得很好，但当我尝试同时将多个主体添加到同一个根节点时自然会崩溃。此代码不包括任何使八分圆对象线程安全的措施。

理想情况下，我希望能够使用如下方式并行调用 addBody 方法:

#pragma omp parallel for
for (int b = 0; b < bodies.size(); ++b) {
    octree->addBody(bodies[b]->getPosition(), bodies[b]->getMass());
}

我已经尝试将 #pragma omp critical(name) 添加到数据更改的方法部分，并将 #pragma omp single 添加到节点 segmentation 的位置。我尝试过的任何事情都无法阻止立即发生的段错误。

我还构建了一个批量添加实体的方法。它接受了 body 对象的 vector ，根据它们适合的 segmentation 将它们分类为 vector ，并将这些 vector 传递到它们各自的 segmentation 中。每个 segmentation 都有自己的线程，这个过程是递归的。这起作用并使用了我所有的核心，但速度明显较慢。我认为将物体放入 vector 中会增加大量开销。

我对 OpenMP 还很陌生，对线程安全的概念还比较陌生。解决这个问题的最佳方法是什么？我似乎无法在网上找到很多线程安全树结构的例子，而且没有一个使用 OpenMP。使用多线程填充树的理想方法是什么？最起码，您认为哪些工具有助于实现此类功能？

编辑: 有谁知道完全线程安全的树结构的示例吗？即使它不在 OpenMP 中，我主要对如何以线程安全的方式添加/生成/填充树感兴趣。

Answer 1

为了使树对写操作线程安全(比如在你的例子中添加一个节点)我只能想到锁定算法 - 例如Two-phase locking .例如，这些结构用于数据库。这个想法是沿着树向下走，找出需要添加节点的位置，它将影响哪些(所有)其他父节点，等待对这些节点的锁定，锁定它们，执行添加操作并解锁。这将始终保持树处于一致状态，同时允许在树的不同部分进行并发添加操作。因此，在您考虑实现它之前，先看看如何将数据添加到树中。如果大多数添加会发生冲突，那么锁定的开销不会超过加速的 yield 。

还有一些评论。 @Joseph Franciscus 的意思是并行执行大量计算，然后按顺序将所有节点添加到树中，如果您不期望节点数量达到数十亿，那么应该可以很好地工作。

但是，您可以扩展他的想法。您可以实现类似于并行 Produce-Consume 模式的东西。任意数量的工作线程将致力于创建主体并将结果放入线程安全队列中，并且只有一个线程(!)会添加它们。通过这种方式，您可以让这两项工作相互交织，并并行完成更多工作。

附言。 omp parallel for 之后的屏障是隐式的，您不需要将它放在那里 AFAIK。

编辑:我在想也许一些伪 C 代码可以提供帮助:

#pragma omp parallel sections num_threads(2)
{
  #pragma omp section
  {
    while (true) {
      if (queue_notEmpty()){
        if (node is last) break;
        node = queue_front(); queue_pop();
        tree->addNode(node);
      }
    }
  }
  #pragma omp section
  {
     #pragma omp parallel for
     for (int i = 0; i < N; ++i) {
        node = init_node(...);
        queue_push(node);
     }
  }
}

这将首先产生两个线程，每个线程占用其中一个部分。然后在第二部分将产生更多的线程，您也可以使用 num_thread 属性来控制它。我能想到的唯一警告是如何使线程将节点放入树端。您可以将一个特殊节点放入队列中，表示不会添加更多节点。

我写的伪代码也做了所谓的主动等待。它一直询问队列是否为空。您可以通过使用信号量向消费者线程发送信号来摆脱它。取决于线程需要等待数据的时间。您也可以尝试一下。

标准库队列/双端队列不是线程安全的，因此请确保实现您自己的或使用专为在并行场景中使用而制作的库。希望一切顺利!