The solution is to protect access to the queue with a critical section.
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);
}
}
This is similar to having a common mutex and locking it.
There are some limits in efficiency with this version: At the end of the for loop, some threads may idle, despite work being in the queue. Making a version where threads continuously work whenever there is something in the queue is a bit tricky in terms of handling the situations where the queue is empty but some threads are still computing.
Depending of the data size involved in a node, you may also have significant performance impact of cache-effects and false sharing. But that can't be discussed with a specific example. The simple version will probably be sufficiently efficient in many cases, but getting optimal performance may become arbitrarily complex.
In any case, you have to ensure that doStuff
does not do modify any global or shared state.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…