ペアでの並列ループ

Question

C++ 11では、複数のスレッドでペアワイズ計算を実行する最も良い方法は何ですか？私が意味することは、私は要素のvectorを持っています、そして、私は別個の要素の各ペアのための関数を計算したいと思います。注意は、同じ要素を複数のスレッドで同時に使用することができないことです。要素は計算中に進化する状態を持ち、計算はそれに依存します。

Answer 1

簡単な方法は、オフセットでペアをグループ化することです。

vがベクトルの場合、要素N apart（mod v.size（））は2つのペアの集合を形成します。これらのペアのコレクションのそれぞれには、内部に重複が含まれていません。

10エレメントベクター0 1 2 3 4 5 6 7 8 9を調べる。離れてペア1は、以下のとおりです。

0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 0 

あなたは私たちが得る2つのコレクションの中に、「パリティ」によってこれらを分割した場合：

0 1, 2 3, 4 5, 6 7, 8 9 
1 2, 3 4, 5 6, 7 8, 9 0 

あなたは上記のコレクションのそれぞれに、並行して、作業することができます。コレクションが終了したら、同期してから次のコレクションを操作します。

同様のトリックは2つの別々の作業です。残り物と

0 2, 1 3, 4 6, 5 7 
2 4, 3 5, 6 8, 7 9 

：すべてについて

8 0, 9 1 

N/2に1からのオフセットがある2 "コレクション" と残り物です。ここで

は4のオフセットされています

0 4, 1 5, 2 6, 3 7 
4 8, 5 9, 6 0, 7 1 

及びこれらのコレクション（および計算残り物

8 2, 9 3 

（私は単純に残り物の大きさは、オフセットベクトルの大きさのMODだと思う）

残り物）は難しくありません。スレッドをキューに入れ、正しいスレッドを効率的に正しいスレッドに配置するように調整するのは難しいです。

Nは2、または（n^2 + n）/ 2のペアを選択します。この分割により、最大でn/2のO（1.5n）のコレクションと残り物、および各コレクション内の完全な並列性が得られます。あなたには、いくつかの要素がはるかに高価な他のものよりも状況があるので、仕上げに各コレクションを待っていることは、あまりにも多くのスレッドをアイドル状態にした場合

---

、あなたはきめの細かい同期を追加することができます。

アトミックboolのベクターを維持します。これを使用して、現在要素を処理中であることを示します。上の方の前にある低い方のインデックスを常にロックする（trueに設定し、それを真に設定する前にfalseであることを確認する）。

両方をロックすると、処理が中断されます。次に両方をクリアします。

失敗した場合は、後で作業を覚えておき、他の作業を行います。待機しているタスクが多すぎる場合は、条件変数を待って、スピンラムダでロックしたいアトミックブールをチェックして設定します。

ロックをクリアすると、定期的に条件変数がキックされます。どのくらいの頻度でこれを行うかは、プロファイリングに依存します。あなたはmutex mayhapを得ることなく蹴ることができます（しかしスレッドを飢えさせる可能性のある競合状態に対処するために、boolをクリアした後にmutexを取得する必要があるかもしれません）。

上記の収集システムで示された順序でタスクをキューに入れると、スレッドが衝突する可能性が少なくなります。しかし、このシステムでは、1つのタスクが遅れていても、作業はまだ進行しています。

複雑さと同期性が向上し、純粋なコレクション/コホートより簡単に遅くなる可能性があります。