并行化广度优先搜索
Parallelizing a Breadth-First Search
我刚刚自学了一些 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()开销很大,想并行处理。但是,如果我通过在 for 行之前放置 #pragma omp parallel 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);
}
}
这类似于拥有一个公共互斥体并将其锁定。
此版本在效率方面存在一些限制:在 for 循环结束时,一些线程可能空闲,尽管队列中有工作。就处理队列为空但某些线程仍在计算的情况而言,制作一个线程在队列中有内容时持续工作的版本有点棘手。
根据节点中涉及的数据大小,缓存效应和错误共享也可能对性能产生重大影响。但这不能用具体的例子来讨论。在许多情况下,简单版本可能足够高效,但获得最佳性能可能会变得任意复杂。
无论如何,您必须确保doStuff
不会修改任何全局或共享状态。
我刚刚自学了一些 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()开销很大,想并行处理。但是,如果我通过在 for 行之前放置 #pragma omp parallel 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);
}
}
这类似于拥有一个公共互斥体并将其锁定。
此版本在效率方面存在一些限制:在 for 循环结束时,一些线程可能空闲,尽管队列中有工作。就处理队列为空但某些线程仍在计算的情况而言,制作一个线程在队列中有内容时持续工作的版本有点棘手。
根据节点中涉及的数据大小,缓存效应和错误共享也可能对性能产生重大影响。但这不能用具体的例子来讨论。在许多情况下,简单版本可能足够高效,但获得最佳性能可能会变得任意复杂。
无论如何,您必须确保doStuff
不会修改任何全局或共享状态。