时间戳

首页 > 解决方案 > 使用openmp实现并行广度优先搜索

c++ - 使用openmp实现并行广度优先搜索

问题描述

我想使用openmp实现并行广度优先遍历。

我阅读了 Parallelizing a Breadth-First Search。我只是想打印广度优先遍历。但是上面提供的链接中的代码几乎包含了临界区的所有遍历代码。

如果没有两个线程可以同时处于临界区，那么它将花费与顺序程序相同的时间（可能需要更多时间）。如何使用 OpenMP 并行运行算法？

标签： c++openmpbreadth-first-search

解决方案

您的前提具有误导性：

代码 [...] 几乎包含关键部分中的所有遍历代码。

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);
  }
}

当然，遍历本身实际上是在一个关键部分，如果您使用的是非线程安全的数据结构，则必须如此。但是，这个问题的前提是：

处理功能doStuff()相当昂贵

只要这成立，剩余代码位于临界区就不是问题。例如，您可以使用阿姆达尔定律来计算理论上可实现的加速。

综上所述，如果您doStuff的价格非常便宜，那么您的观察当然是正确的。然后，我建议使用不需要共享队列的搜索，例如深度优先搜索或迭代深化深度优先搜索。

推荐阅读