Cilk のワーク スティール スケジューリング パフォーマンスについて説明している論文を読んでいます。
1) 私の理解では、スケジューラはクリティカル パスのタスクを認識していませんが、タスク グラフの「深く」ないタスクを盗むことによって、いずれにしてもその実行を維持しようとします。あれは正しいですか？
2) また、Cilk のワーク スチール スケジューラは、すべてのタスクが同様の複雑さであると想定していますか? タスクの複雑さが一様でない場合、スケジューラは最高のパフォーマンス、つまり最高の負荷分散を実現する上で柔軟性が低下するのではないでしょうか?
おそらく (1) に答える最良の方法は、Cilk スケジューリングは、タスクをスチールするときは幅優先ですが、そうでない場合は深さ優先であるということです。
(2) に対する答えは、Cilk タスク スケジューラがタスクの複雑さを認識していないということです。
理解すべき重要な原則は、「ブレントの補題」(Graham によって以前に発見された) です。レンマは、(PRAM の仮定の下で) 貪欲なスケジューラ (やるべき仕事がある場合にワーカーを決してアイドル状態にしないもの) が与えられた場合、可能な限り最高のスケジュールは、可能な限り最悪のスケジュールよりも 2 倍以上速くならないことを示しています。タスクの複雑さ。
2x is limit の背後にある直感は、実行中にクリティカル パス上のタスクに取り組んでいるワーカーがいない場合 (クリティカル パスをむしゃむしゃ食べている場合)、すべてのワーカーがビジー状態である (合計作業をむしゃむしゃ食べている) ということです。クリティカル パスと総作業量は、アルゴリズムの総作業量の 2 倍を超えることはできません。
PRAM の仮定は、キャッシュ ミスがキャッシュ ヒットよりも 100 倍の時間かかる可能性がある実際のマシンへのおそらく最も弱いリンクです。したがって、タスクの複雑さについて心配することは、キャッシュに関する考慮事項ほど重要ではありません。Cilk の使用方法に応じて、キャッシュ (再帰的プログラム) でうまく機能するか、うまく機能しません (連続する cilk_for ループ)。