c++ - 并行化广度优先搜索

我只是自学了一些 OpenMP，这可能很愚蠢。基本上，我试图在 C++ 中并行化广度优先搜索程序，每个节点都需要很长时间来处理。这是一个示例代码:

queue<node*> q;
q.push(head);
while (!q.empty()) {
  qSize = q.size();
  for (int i = 0; i < qSize; i++) {
    node* currNode = q.front();
    q.pop();
    doStuff(currNode);
    q.push(currNode);
  }
}

处理函数 doStuff() 非常昂贵，我想对其进行并行化。但是，如果我通过将 #pragma omp parallel for 放在 for 行之前来并行化 for 循环，则在运行时会弹出各种奇怪的错误。我猜原因是这样 q.front() 和 q.push() 也将被并行化，并且多个线程可能会通过 q.front() 获得相同的节点(因为它们都在处理任何 q.push 之前得到了处理)。

我怎样才能解决这个问题？

最佳答案

解决方案是使用临界区来保护对队列的访问。

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

这类似于拥有一个公共(public)互斥锁并将其锁定。

这个版本的效率有一些限制:在 for 循环结束时，尽管有工作在队列中，但一些线程可能空闲。就处理队列为空但某些线程仍在计算的情况而言，制作一个线程在队列中有东西时连续工作的版本有点棘手。

根据节点中涉及的数据大小，缓存效应和错误共享可能还会对性能产生重大影响。但这不能用具体的例子来讨论。在许多情况下，简单版本可能足够高效，但获得最佳性能可能变得任意复杂。

在任何情况下，您都必须确保 doStuff 不会修改任何全局或共享状态。

关于c++ - 并行化广度优先搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44082755/