タスク・スケジューラーの動作#
タスク・スケジューラーは特定の種類の並列処理に拘束されませんが、多数のフォークによるフォークジョイン並列処理で効率良く動作するように設計されています。このタイプの並列処理は、oneapi::tbb::parallel_for などの並列アルゴリズムでは一般的です。
タスク・スケジューラーにおけるフォークジョイン並列処理のマッピングをさらに詳しく考えてみましょう。
- スケジューラーは、複数のターゲットを同時に達成するような方法でタスクを実行します。
可能な限り多くのスレッドを有効にし、十分なジョブを作成することで、実際の並列処理を実現します。
データの局所性を維持して、単一スレッドの実行をより効率的にします。
メモリーの要求とスレッド間通信を最小限に抑えてオーバーヘッドを削減します。
これを実現するには、深さ優先と幅優先のバランスをとる必要があります。タスクグラフが有限であると仮定すると、次の理由により深さ優先がシーケンシャル実行に適しています。
キャッシュは熱い (ホットな) うちに打つ。最も深いタスクは最も新しく生成されたタスクであるため、キャッシュ内で最もホットな状態です。また、完了できる場合、それに依存するタスクは実行を継続でき、キャッシュ内で最もホットなタスクではないものの、デキューの深くにある古いタスクよりもホットな状態になります。
スペースを最小限に抑えます。最も浅いタスクを実行すると、グラフは幅優先で展開されます。同時に共存する指数関数的な数のノードを作成します。一方、深さ優先実行では同じ数のノードが作成されますが、同時に存在できるノードの数は線形に制限されます。これは、他の実行可能なタスクのスタックを生成するためです。
各スレッドには、実行準備が整ったタスクのデックがあります。スレッドがタスクを生成すると、そのタスクはデックの一番下にプッシュされます。
スレッドがタスクの評価に参加する場合、そのスレッドは、ほぼ同等のルールセットから適用される最初のルールによって取得したタスクを継続的に実行します。
前のタスクによって返されたタスクを取得します (存在する場合)。
デックの一番下からタスクを取得します (存在する場合)。
ランダムに選択された別のデックの先頭からタスクをスチールします。選択されたデックが空の場合、スレッドは成功するまでこのルールの実行を再試行します。
ルール 1 については、タスク・スケジューラーのバイパスで説明されています。ルール 2 の全体の効果は、スレッドによって生成された最も新しいタスクを実行することです。これにより、スレッドのワークがなくなるまで深さ優先の実行が行われます。その場合はルール 3 が適用されます。これは、別のスレッドによって生成された最も古いタスクをスチールし、一時的な幅優先実行によって潜在的な並列性を実際の並列性に変換します。