parallel-processing - ワークスチールとデキュー

Question

ワークスティーリングに両端キューが必要なのはなぜですか? (例: Cilk) 所有者は上で働き、泥棒は下から盗みます。なぜ便利なのですか？

下から複数の泥棒が盗んでいる可能性があります。とにかく、ロックは必要ありませんか？大きなジョブ (たとえば、ツリーで作成されたもの) が下部に追加されることをどこかで読んだことがあります。したがって、下から盗む方が効率的です (泥棒が盗むことで忙しくなるため、コミュニケーションが少なくなります)。それですか？

Answer 1

ワークスティーリングには両端キューは必要ありません。並列データ構造を使用してタスクのプールを格納することは可能です (実際に実行されています)。しかし問題は、ワーカーからのプッシュ/ポップ操作とシーフからのスチール リクエストをすべて同期する必要があることです。

盗みは比較的まれなイベントであると予想されるため、盗みの試行中や、データ構造からアイテムをポップする際に競合が発生する可能性がある場合でも、同期が実行されるようにデータ構造を設計することができます。同期を最小限に抑えるために、Cilk で deque が使用されたのはまさにそのためです。ワーカーは自分自身の両端キューをスタックとして扱い、スレッドを下からプッシュおよびポップしますが、別のビジー ワーカーの両端キューをキューとして扱い、実行するローカル スレッドがないときは常に上からのみスレッドを盗みます。盗みの動作は同期しているため、複数の盗人が同じ被害者から盗もうとしても大丈夫です。

下位に追加されるより大きなジョブは、分割統治スタイルのアルゴリズムでは一般的ですが、すべてではありません。窃盗中に何をすべきかについては、さまざまな戦略が用意されています。タスクを 1 つ盗んだり、いくつかのタスクを盗んだり、タスクの半分を盗んだりします。これらのバリアントはそれぞれ、一部のアプリケーションではうまく機能しますが、他のアプリケーションではうまく機能しません。

Answer 2

THE プロトコルの詳細は、MIT から入手できる「Cilk-5 マルチスレッド言語の実装」のセクション 5 で説明されています。

Answer 3

ワークスチールには、実際には両端キューが必要です。元の論文では、P 個のプロセッサを搭載したシステムで使用されるメモリの最大値が証明されています。制限は、任意のスタックの最大サイズにプロセッサ数を掛けたものによって決まります。これは実際には、忙しい葉の定理に従うことによってのみ可能です。また、ワーク スティーリングのもう 1 つの重要な機能は次のとおりです。ワーカーがスポーンを行うと、すぐにスポーナーを両端キューに保存し、子の作業を開始します。彼らの証明に関する詳細については、私が言っていることをすべて説明している元の論文を読んでください。http://supertech.csail.mit.edu/papers/steal.pdf

ワーク スチール デキュー アクセスの同時実行制御は、ワーク スティーリング スケジューラとは関係ありません。実際、(ロック フリー構造を使用して) デキューからロックを削除し、可能な限りメモリ バリアを最小限に抑えるために、多くの研究が行われています。 . たとえば、この論文（アクセスできない場合は申し訳ありませんが、アイデアを得るために要約を読むことができます）：http://dl.acm.org/citation.cfm?id=1073974著者は新しい上記の側面を改善するためのdeque。

おそらくいくつかの理由で、ワーカーが作業していない側からスチールが行われます。論文を読めば理解できる）。私が大きいと言うとき、それらはおそらくより多くの計算を行うものであることを意味したいと思います. また、もう 1 つの重要な側面は、そうすることで (deque 所有者の反対側の作業側から盗むことによって) 競合が減少することです。これは、一部の新しい deque では、被害者と泥棒の両方が同じ deque で同時に作業している可能性があるためです。