固定分配でCPUが待機する理由
4個のワーカーに作業を固定分配し、1個だけが大きな部分問題を持つと、他の3個は自分の仕事を終えた後、実行できる仕事がなく待機します。Work stealingは、空いたワーカーが別のワーカーのキューから仕事を取り出す方式です。タスクが実行中に新しいタスクを生む、木構造の分割統治などに向きます。仕事の依存関係を消す仕組みではないので、まだ前提が終わらないタスクを勝手に実行することはできません。
8、1、1、1の例
仕事の長さが8、1、1、1という4個のタスクしかなければ、長さ8の仕事を盗んでもそれ自体は短くなりません。8を独立した小さな仕事へ分割できることが、均等化の条件です。分割後の総仕事量が11、最長の依存鎖が8なら、CPUを増やしても8未満にはできません。総仕事量と依存鎖の長さを区別すると、タスク数だけ増やしても速くならない理由を説明できます。
キュー操作と局所性の費用
ワーカーごとの両端キューを使い、自分の仕事と盗む仕事で異なる端を使う実装があります。ただし具体的な順序や公平性はランタイムの契約によります。仕事を移すと、そのデータが盗んだ側のキャッシュにないことがあります。NUMA環境では別ノードのメモリに触れる費用も増えます。キューの競合を減らせても、データ移動まで無料になるわけではありません。タスクは十分大きく、しかし偏りを分散できる粒度にします。
ブロックする処理を混ぜるとき
CPU計算向けのプールに、長時間の通信待ちをそのまま混ぜると、ワーカーがすべて待って仕事が進まない場合があります。JavaのForkJoinPoolにもブロッキングへの補助機構はありますが、任意のI/Oで自動調整が保証されるわけではありません。用途ごとのプールや非同期I/Oを検討します。盗んだ回数が多いこと自体を成功とせず、完了時間、CPU利用率、待機時間から実際の効果を判断します。
処理の依存関係を表すDAGを先に描くと、盗める仕事と、まだ開始できない仕事を分けられます。完了した親が子を公開する順序や、子の結果を読むタイミングも同期の一部です。仕事の移動は、共有データの競合を自動で解決するものではありません。