forループで1つの関数だけを並列化するようにOpenMPに指示するにはどうすればよいですか？

Question

私は自分自身にいくつかの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が処理される前にすべて処理されているためです）。

どうすればこの問題を回避できますか？

Answer 1

解決方法は、クリティカルセクションでキューへのアクセスを保護することです。

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がグローバルまたは共有状態を変更しないようにする必要があります。