c++ - tbb：最初の要素を並列検索

Question

私はこの問題を抱えています：

特定の条件が当てはまるリストの最初の要素を見つけます。

残念ながら、リストは非常に長く（100.000要素）、各要素の条件の評価には、1つのスレッドを使用して合計で約30秒かかります。

この問題をきれいに並列化する方法はありますか？すべてのtbbパターンを調べましたが、適切なものが見つかりませんでした。

更新：パフォーマンス上の理由から、アイテムが見つかったらできるだけ早く停止し、リストの残りの処理を停止したいと思います。だから私は使用できないと信じていparallel_whileますparallel_do。

score 1 · Accepted Answer

私はこのためのライブラリにあまり精通していませんが、声を出して考えるだけで、異なる開始点から同じストライドで異なるスレッドのグループを反復することはできませんか？

スレッド（=コアの数など）を使用することにした場合n、各スレッドには最大で特定の開始点を指定する必要があるnため、最初のスレッドはから始まりbegin()、次に比較する項目はbegin() + nなどです。2番目のスレッドはから始まりbegin()+1、次の比較も入っていnます。

このようにして、スレッドのグループをリスト全体で並行して反復することができます。反復自体はおそらくコストがかからず、比較だけです。ノードは複数回比較されることはなく、いずれかのスレッドによって一致が行われたときに設定される条件を設定できます。反復/比較する前に、すべてのノードがこの条件を確認する必要があります。

実装するのはかなり簡単だと思います（？）

score 1 · Accepted Answer

TBBでこの問題を解決する最善の方法はparallel_pipelineです。

パイプラインには（少なくとも）2つのステージが必要です。第1段階はシリアルです。リストから次の要素を読み取り、それを第2ステージに渡します。この第2段階は並行しています。特定の要素の対象となる状態を評価します。条件が満たされるとすぐに、第2ステージは、解決策が見つかったことを示すフラグ（アトミックであるか、ロックで保護されている必要があります）を設定します。最初の段階では、このフラグを確認し、解決策が見つかったらリストの読み取りを停止する必要があります。

条件評価はいくつかの要素に対して並行して実行されるため、見つかった要素がリストの最初の適切な要素ではない場合があります。これが重要な場合は、要素のインデックスも保持する必要があります。適切なソリューションが見つかったら、そのインデックスが既知のソリューション（存在する場合）のインデックスよりも小さいかどうかを検出します。

HTH。

score 1 · Accepted Answer

わかりました、私はそれをこのようにしました：

すべての要素をに入れますtbb::concurrent_bounded_queue<Element> elements。
空のを作成しますtbb::concurrent_vector<Element> results。
を作成しboost::thread_group、このロジックを実行するいくつかのスレッドを作成します。

並列実行するロジック：

Element e;
while (results.empty() && elements.try_pop(e) {
    if (slow_and_painfull_check(e)) {
         results.push_back(e);
    }
}

したがって、最初の要素が見つかると、他のすべてのスレッドは次にチェックするときに処理を停止しますresults.empty()。

2つ以上のスレッドがslow_and_painfull_checktrueを返す要素で動作している可能性があるため、結果をベクトルに入れて、並列ループの外側でこれを処理します。

スレッドグループ内のすべてのスレッドが終了したら、内のすべての要素をチェックして、results最初に来るものを使用します。

score 0 · Accepted Answer

リンクリストの場合、並列検索ではそれほど速度は上がりません。ただし、リンクリストはキャッシュを使用するとパフォーマンスが低下する傾向があります。2つのスレッドがある場合、パフォーマンスがわずかに向上する可能性があります。1つはfind_first_elementを実行し、もう1つはリストを繰り返し実行して、最初のスレッドの前にX（100？）を超えないようにします。2番目のスレッドは比較を行いませんが、最初のスレッドで可能な限りアイテムがキャッシュされることを保証します。これはあなたの時間を助けるかもしれません、あるいはそれはほとんど違いをもたらさないかもしれません、あるいはそれは妨げるかもしれません。すべてをテストします。

score 0 · Accepted Answer

並列アルゴリズムの実装については、http：//gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.htmlを参照してください。特に、find_ifアルゴリズムが必要ですhttp://www.cplusplus.com/reference/algorithm/find_if/

score 0 · Accepted Answer

0

GCCを使用している場合、GNUOpenMPは並列std関数リンクを提供します

于 2011-10-11T14:38:15.143 に答える

score 0 · Accepted Answer

ここでは、並列処理の2つの機会があります。複数のスレッドで1つの要素を評価するか、異なるスレッドで複数の要素を一度に評価するかです。

複数のスレッドで1つの要素を評価することの難しさや有効性を判断するのに十分な情報がありません。これが簡単な場合は、要素あたり30秒の時間を短縮できます。

この問題がTBBに完全に適合しているとは思えません。ランダムアクセスイテレータがないリスト、停止するタイミングの決定、および最初の要素の検出の保証には問題があります。ただし、範囲を使用してプレイできるゲームがいくつかある場合があります。

いくつかの低レベルのスレッド構造を使用してこれを自分で実装することもできますが、誤った結果が返される場所がいくつかあります。このようなエラーを防ぐために、既存のアルゴリズムを使用することをお勧めします。リストを配列（またはランダムアクセスイテレータを備えた他の構造）に変換し、参照されている実験的なlibstdc++並列モードfind_ifアルゴリズムuser383522を使用できます。

score 0 · Accepted Answer

リストをバランスの取れたツリーなどに変換できませんか？このようなデータ構造は、並列処理が簡単です。通常、最初にバランスをとるために支払ったオーバーヘッドを取り戻します。たとえば、機能スタイルのコードを作成する場合は、次のペーパーを確認してください。並列プログラミング

score -1 · Accepted Answer

Intel tbbライブラリのことは聞いたことがありませんが、チュートリアルをすばやく開いてスキャンすると、parallel_forうまくいくようです。

c++ - tbb：最初の要素を並列検索

9 に答える 9

Related

Reference