問題タブ [work-stealing]

C/CPP でワーク スティーリング キューの適切な実装を探しています。Google を見回しましたが、役立つものは何も見つかりませんでした。

おそらく、誰かが優れたオープンソースの実装に精通しているでしょうか? (元の学術論文から取った疑似コードを実装したくない)。

実装しているスレッドプールのさまざまなスケジューリングアルゴリズムを調査してきました。私が解決している問題の性質上、並行して実行されているタスクは独立しており、新しいタスクを生成しないと想定できます。タスクのサイズはさまざまです。

私はすぐに、ローカルジョブキューにロックフリーの両端キューを使用する最も一般的なスケジューリングアルゴリズム「ワークスティーリング」に行きました。このアプローチには比較的満足しています。しかし、仕事を盗むことが最善のアプローチではない一般的なケースがあるかどうか疑問に思います。

この特定の問題について、私は個々のタスクのサイズを適切に見積もっています。ワークスティーリングはこの情報を利用しません。この情報を使用したワークスティーリングよりも優れた負荷分散を提供するスケジューラーがあるかどうか疑問に思います（明らかに同じ効率で）。

NB。この質問は前の質問と結びついています。

Concurrency Runtimeに関する記事を読んでいますがwork stealing、この記事に名前が付けられているアルゴリズムがあります。しかし、私はこのアルゴリズムが何であるかわかりません！ですから、このアルゴリズムについてのプレゼンテーションを行うのに役立つ、少しの説明またはいくつかの良いリンクが必要です。

私のプロジェクトでは、クライアントから作業要求を受け取る Java 実行フレームワークを構築しています。作業 (さまざまなサイズ) は一連のタスクに分割され、処理のためにキューに入れられます。各タイプのタスクを処理する個別のキューがあり、各キューは ThreadPool に関連付けられています。ThreadPools は、エンジンの全体的なパフォーマンスが最適になるように構成されています。

この設計は、リクエストの負荷を効果的に分散するのに役立ち、大きなリクエストがシステム リソースを占有することはありません。ただし、一部のキューが空で、それぞれのスレッド プールがアイドル状態の場合、ソリューションが無効になることがあります。

これを改善するために、負荷の高いキューが他の ThreadPools から助けを得ることができるように、作業/タスクを盗む手法を実装することを考えていました。ただし、Java では複数のキューを ThreadPool に関連付けることができず、ワーク スティーリングの概念をサポートしていないため、独自の Executor を実装する必要がある場合があります。

Fork/Join について読んでください。しかし、それは私のニーズに合わないようです。このソリューションを構築するための提案や代替方法は非常に役立ちます。

ありがとうアンディ

私のプログラムでは、カーネルラウチで発行された各ブロックの両端キューがあります。各ブロックはループ内にとどまり、両端キューで作業をポップし、処理して動的に生成された作業をプッシュバックします。dequeフラグの配列が維持され、アクティブなdeque、つまり動作しているdequeを示します。dequeが空の場合、カーネルは別のループに入り、別のブロックのdequeから作業を盗もうとします。停止条件は、アクティブな両端キューがなくなると達成されます。

テストでは、1つの作業項目から始まるすべての両端キューを設定しました。私の問題は、いくつかのブロックがまったく実行されていないように見えることです。それらのいくつかは実行されていないので、それらはアクティブなままであり、私のプログラムは無限ループに入ります。

次に、コードについて説明します。カーネルお​​よび補助ポップおよびプッシュ機能：

そしてこれがテストです：

NSightを使用してこのコードをデバッグする最初の8ブロックだけが実行されていることを確認しました。これがスケジュールの問題であり、popWorkポーリングがすべてのリソースを消費しているのか、それともプログラムのバグにすぎないのか疑問に思います。どんな助けでも大歓迎です。

私のfork/joinの小さな例を改善して、Java Fork/Joinフレームワークの実行中に作業の盗用が発生することを示したいと思います。

次のコードにどのような変更を加える必要がありますか？例の目的：複数のスレッド間で作業を分割する値の線形調査を行うだけです。

まず、コンテキスト化を行います。CUDA で deques を使用して非ブロッキング ワーク スチール メソッドを実装しようとしています。deques (aDeques) は、グローバル メモリ内のブロック セグメント化された配列内にあり、popWork() デバイス関数には、作業をポップしてスレッドにフィードするという目的があります。グローバル deques に加えて、各ブロックには共有メモリ (aLocalStack) にスタックがあり、ローカルで動作できます。ポップは 3 レベルで発生します。最初の試行は共有スタックで、2 回目の試行はブロックが所有する両端キューで、3 回目の試行は他の両端キューのワーク スチールです。各両端キューには、グローバル メモリ配列 (aiDequesBottoms および auiDequesAges) にあるグローバル ボトム ポインターとポップ ポインターがあります。私の問題は、ブロックがグローバル deque ポインターを変更すると、GTS450 でコードをテストするときに、変更が他のブロックから見えなくなることです。キャッシュが更新されていないようです。問題が発生しない GT520 カードでもテストしました。aiDequeFlags 配列で同様の問題が発生しました。これらの問題は、揮発性を宣言することで解決されます。残念ながら、後でアトミック関数を使用する必要があるため、deque ポインター配列に対して同じことを行うことはできません。問題をより単純な例に入れずに申し訳ありませんが、この動作を再現できませんでした。この最初のスニペットには popWork() インターフェイスの説明があります。問題をより単純な例で説明できなくて申し訳ありませんが、この動作を再現できませんでした。この最初のスニペットには popWork() インターフェイスの説明があります。問題をより単純な例で説明できなくて申し訳ありませんが、この動作を再現できませんでした。この最初のスニペットには popWork() インターフェイスの説明があります。

この 2 番目のスニペットには、関数全体が含まれています。この関数を使用するカーネルは 8 ブロック、64 スレッドで起動され、最初は deque 0 だけで 1 つの作業が行われ、他のすべての deque は空です。ログを生成するための debug printf 呼び出しがいくつかあります。これは次のスニペットに表示されます。

}

この最後のスニペットは、生成されたログです。プッシュ ライン ("Block X push. Bottom=Y") は、ここには示されていなかったプッシュ関数によって生成されました。最初は、ブロック 0 だけに 1 つの作業があることに注意してください。

ご覧のとおり、ブロック 4 のみがブロック 0 の両端キューのボトム ポインターの変更を確認できます。ポインターの変更後に __threadfence() 呼び出しをいくつか追加しようとしましたが、成功しませんでした。注目してくれてありがとう！

次は正しいですか？

• 各エントリを複数の方法（io操作またはアノテーション）で処理する必要がある場合、ディスラプターパターンは、競合することなく複数のコンシューマーを使用して並列化できるため、並列パフォーマンスとスケーラビリティが向上します。
• 逆に、ワークスティーリング（つまり、エントリをローカルに保存し、他のスレッドからエントリを盗む）は、各エントリを単一の方法でのみ処理する必要がある場合、ディスラプターパターンでエントリを複数のスレッドにばらばらに分散すると競合が発生するため、並列パフォーマンスとスケーラビリティが向上します。

（そして、複数のプロデューサー（つまりCAS操作）が関与している場合、ディスラプターパターンは他のロックレスマルチプロデューサーマルチコンシューマーキュー（ブーストなど）よりもはるかに高速ですか？）

私の状況の詳細：

エントリを処理すると、いくつかの新しいエントリが生成される可能性があり、それらも最終的に処理する必要があります。パフォーマンスが最優先され、FIFO順に処理されるエントリが2番目に優先されます。

現在の実装では、各スレッドはローカルFIFOを使用し、そこで新しいエントリを追加します。アイドルスレッドは、他のスレッドのローカルFIFOから作業を盗みます。スレッドの処理間の依存関係は、ロックレスで機械的に同情的なハッシュテーブル（書き込み時のCAS、バケットの粒度）を使用して解決されます。これにより、競合はかなり少なくなりますが、FIFOの順序が崩れることがあります。

ディスラプタパターンを使用すると、FIFOの順序が保証されます。しかし、エントリをスレッドに分散すると、作業を盗むローカルFIFO（各スレッドのスループットはほぼ同じ）よりもはるかに高い競合（読み取りカーソルでのCASなど）が発生しませんか？

私が見つけた参考文献

ディスラプターに関する標準テクニカルペーパー（第5章+第6章）のパフォーマンステストは、ばらばらの作業分散をカバーしていません。

https://groups.google.com/forum/?fromgroups=#!topic/lmax-disruptor/tt3wQthBYd0は、ディスラプターとワークスティーリングについて私が見つけた唯一のリファレンスです。共有状態がある場合、スレッドごとのキューは劇的に遅くなると述べていますが、詳細や理由については説明していません。この文が私の状況に当てはまるとは思えません。

• ロックレスハッシュテーブルで解決されている共有状態。
• 消費者間でエントリをばらばらに配布する必要があります。
• 作業の盗用を除いて、各スレッドはローカルキューでのみ読み取りと書き込みを行います。

私は cilk++ を初めて使用し、cilk のワーク スチール スケジューラを使用したいと考えています。これについてはあまり情報が見つかりませんでした。誰でもこれに関して私を助けることができますか? ありがとう。

私は CLR 4.0 の詳細を学ぼうとしています。ThreadPool と Microsoft が推奨するさまざまな戦略。私はこれらのトピックの多くについてかなり最新であると考えており、日常的にスレッド化と並行コードを使用しています。

私は最近、並列パターンと実践に戻ってきましたが、「ワーク スティーリング」とローカル スレッド キューとグローバル スレッド キューの簡単な概要を説明している分散スケジューリング手法のセクションに少し引っかかっています。

私が持っている質問は次のとおりです。

1)ワークスティールはオプトインかオプトアウトか? ローカルスレッドキューを使用するのと同じですか? それとも、これは CLR 4.0 では既定で発生しますか?

2) ローカル スレッド キューとグローバル スレッド キューのどちらを使用しているかを制御できますか? もしそうなら、どの API 呼び出しを介して?