実装しているスレッドプールのさまざまなスケジューリングアルゴリズムを調査してきました。私が解決している問題の性質上、並行して実行されているタスクは独立しており、新しいタスクを生成しないと想定できます。タスクのサイズはさまざまです。
私はすぐに、ローカルジョブキューにロックフリーの両端キューを使用する最も一般的なスケジューリングアルゴリズム「ワークスティーリング」に行きました。このアプローチには比較的満足しています。しかし、仕事を盗むことが最善のアプローチではない一般的なケースがあるかどうか疑問に思います。
この特定の問題について、私は個々のタスクのサイズを適切に見積もっています。ワークスティーリングはこの情報を利用しません。この情報を使用したワークスティーリングよりも優れた負荷分散を提供するスケジューラーがあるかどうか疑問に思います（明らかに同じ効率で）。
NB。この質問は前の質問と結びついています。
事前にタスクを分散します。推定実行時間の情報を使用して、スレッドごとに個別のキューに分散できます。
タスクの分散は基本的にナップザックの問題であり、各キューには同じ時間がかかるはずです。
実行中にキューを変更するには、いくつかのロジックを追加する必要があります。たとえば、再配布は、推定実行時間が実際の実行時間と一定量異なる場合に発生する必要があります。
ワークスティーリング スケジューラがその情報を使用しないのは事実ですが、理論上の制限 (たとえば、使用するメモリ、ワーカー間の予想される合計通信量、および予想されるここで読むことができるように、完全に厳密な計算を実行する時間: http://supertech.csail.mit.edu/papers/steal.pdf )
興味深い論文の 1 つ ( http://dl.acm.org/citation.cfm?id=2442538にアクセスしていただければ幸いです) では、実際に有限実行時間を使用して正式な証明を提供しています (元の研究にできるだけ近づけようとしていますが、可能な限り境界を盗む）。
はい、ワーク スティールが最適に実行されない場合があります (たとえば、不均衡なツリー検索やその他の特定のケース)。ただし、そのような場合のために、最適化が行われています (たとえば、1 つのタスクのみを取得するのではなく、被害者の両端キューの半分を盗むことを許可する: http://dl.acm.org/citation.cfm?id=571876 )。