OpenMP中树结构的线程安全
我有一个基于Barnes-Hut算法的N体模拟器，我已经使用OpenMP进行了多线程处理。大多数程序是通过简单地在几个关键位置添加#pragma omp parallel for来实现并行的。这提供了一个健康的加速，当引力体的数量低于几千时，它与核的数量有很好的比例。
因为我的程序使用的是Barnes-Hut算法，它的核心是树结构，在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;
}这在串联调用时工作得很好，但是当我试图同时向同一个根节点添加多个主体时，自然会崩溃。此代码不包括任何措施来确保octant对象线程的安全。
理想情况下，我希望能够使用这样的方法并行调用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中的树，我也主要感兴趣的是如何以线程安全的方式将树添加/生成/填充。
回答 2
Stack Overflow用户
发布于 2019-01-20 16:18:10
要使树线程安全用于写操作(比如在示例中添加一个节点)，我只能考虑锁定算法，例如两相锁定。例如，在数据库中使用这些结构。这样做的想法是沿着树走下去，找出节点需要添加到哪里，它将影响到哪些(所有)其他父节点，等待这些节点的锁，锁定它们，执行添加操作并解锁。这将始终保持树的一致状态，同时允许在树的不同部分进行并发添加操作。因此，在考虑实现这一点之前，先看看如何将数据添加到树中。如果大多数的增加都是相互冲突的，那么锁定的开销就不会超过加速的收益。
再评论几句。如果您不期望节点的数量按数十亿的顺序排列，那么@在并行执行大量计算，然后依次将所有节点添加到树中时，应该工作得很好。
不过，你可以扩展他的想法。您可以实现类似于并行生产-消费模式的东西。任意数量的工作线程将用于创建主体，并将结果放入线程安全队列和一个仅(!)线程中。就会加进去。这样你就可以使两个工作相互交织，同时完成更多的工作。
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属性来控制该线程。这里我能想到的唯一警告是如何使线程将节点放入树的末尾。您可以像一个特殊节点一样将其放入队列中，这意味着不会添加更多的节点。
我编写的伪代码也称为活动等待。它总是询问队列是否为空。您可以通过用信号量向使用者线程发送信号来摆脱它。取决于线程需要等待多少数据。你也可以试一试。
标准库队列/deques不是线程安全的，所以要确保要么实现自己的库，要么使用在并行场景中使用的库。希望能成功！
Stack Overflow用户
发布于 2019-01-15 01:59:37
这只是一个关于如何实现这一点的建议。我相信解决这个问题有多种方法。
void octant::addBody(Body);
Body octant::create_body(vec3 newPosition, float newMass);
int main() {
int thread_count = omp_get_num_threads();
std::vector<std::vector<Body>> body_list(thread_count); //each thread gets its own list of bodies
#pragma omp parallel for
for (int b = 0; b < bodies.size(); ++b) {
int index = omp_get_thread_num();
Body tmp = octant::create_body(bodies[b]->getPosition(), bodies[b]->getMass());
body_list[index].push_back(tmp);
}
#pragma omp barrier //make sure to add barrier (as openmp is asynchronous to host thread)
for (int i = 0; i < thread_count; ++i) {
for (int j = 0; j < body_list[i].size(); ++j)
bodies.add_body(body_list[i][j]);
}
}基本上，你首先创建身体，然后在平行部分之后添加它们。这确保您不会分段错误，并给出一个近似的速度线性速度(假设大部分的成本是创造身体，而不是添加它们)。
https://stackoverflow.com/questions/54190567
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号