我想用openmp实现并行广度优先遍历。
我读了Parallelizing a Breadth-First Search .我只是想打印广度优先遍历。但是上面提供的链接中的代码几乎包含了临界区中的所有遍历代码。
如果没有两个线程可以同时在临界区中,那么它将花费与顺序程序相同的时间(可能需要更多时间)。如何使用 OpenMP 并行运行算法?
最佳答案
您的前提具有误导性:
the code [...] has almost all the traversal code in the critical section.
std::queue<node*> q;
q.push(head);
while (!q.empty()) {
qSize = q.size();
#pragma omp parallel for
for (int i = 0; i < qSize; i++) {
node* currNode;
#pragma omp critical
{
currNode = q.front();
q.pop();
}
doStuff(currNode);
#pragma omp critical
q.push(currNode);
}
}
当然,遍历本身实际上是在临界区中,如果您使用的是非线程安全的数据结构,则必须如此。但是,这个问题的前提是:
The processing function
doStuff()
is quite expensive
只要这成立,剩下的代码在临界区就不是问题。例如你可以使用 Amdahl's law计算理论上可实现的加速比。
综上所述,如果您的 doStuff
非常便宜,那么您的观察当然是正确的。然后我建议使用不需要共享队列的搜索,例如深度优先搜索或迭代加深深度优先搜索。
关于c++ - 使用 openmp 实现并行广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58722950/