时间戳

首页 > 解决方案 > OpenMP 中树结构的线程安全

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

问题描述

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

因为我的程序使用Barnes-Hut 算法，所以它的核心是一个树结构，在二维中这是一个四叉树，在我的例子中是一个八叉树。我在多线程填充树的过程中遇到了麻烦。将此步骤设为单线程会阻止程序充分利用我的处理器。我添加的主体越多，我的 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节点细分的部分。我没有尝试阻止立即发生段错误。

我还构建了一个批量添加主体的方法。它接收身体对象的向量，根据它们适合的细分将它们分类为向量，然后将这些向量传递到它们各自的细分中。每个细分都有自己的线程，并且该过程是递归的。这运行并使用了我所有的核心，但速度明显较慢。我认为将身体放入向量中会增加大量开销。

我对 OpenMP 很陌生，甚至对线程安全的概念也很陌生。解决这个问题的最佳方法是什么？我似乎无法在网上找到很多线程安全树结构的示例，也没有使用 OpenMP。使用多线程填充树的理想方法是什么？至少，您认为哪些工具可以使这种事情发挥作用？

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

标签： c++multithreadingtreethread-safetyopenmp

解决方案

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

再多评论几句。@Joseph Franciscus 的意思是并行进行大部分计算，然后按顺序将所有节点添加到树中，如果您不期望节点数量达到数十亿，应该可以正常工作。

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

PS。之后的障碍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属性来控制它。我能想到的唯一警告是如何使线程将节点放入树端。您可以将一个特殊节点放入队列中，表示不再添加节点。

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

标准库队列/双端队列不是线程安全的，因此请确保实现您自己的或使用在并行场景中使用的库。希望能成功！

推荐阅读