依存関係グラフ

依存関係グラフ#

依存関係グラフでは、ノードはボディー・オブジェクトを呼び出して計算を実行し、エッジはこれらの計算の部分的な順序付けを作成します。実行時に、ライブラリーは、指定された部分的な順序に従って実行が可能なであれば、ボディー・オブジェクトを実行するタスクを生成してスケジュールします。次の図は、依存関係グラフを使用して表現できるアプリケーションの例を示しています。

サンドイッチを作る依存関係グラフ

image0

依存関係グラフはデータ・フロー・グラフの特殊なケースであり、ノード間で渡されるデータは oneapi::tbb::flow::continue_msg タイプになります。一般的なデータ・フロー・グラフとは異なり、依存関係グラフ内のノードは受信するメッセージごとにタスクを生成しません。代わりに、待機している先行処理の数を認識し、受信したメッセージをカウントし、この数が先行処理の合計数と等しい場合にのみ、ボディーを実行するタスクを生成します。

次の図は別の依存関係グラフ例を示しています。これは上図と同じトポロジーですが、サンドイッチの作成手順を単純な関数に置き換えたものです。この部分的な順序付けでは、関数 A は他の計算の実行が開始される前に実行を完了する必要があります。関数 B は、関数 C と D の実行が開始される前に完了する必要があり、関数 E は関数 D と F の実行が開始される前に完了する必要があります。これは部分的な順序付けです。例えば、B と E の間、または C と F の間には明示的な順序付けの要件がないためです。

単純な依存関係グラフ

イメージ1

これをフローグラフとして実装するには、ノードとして continue_node オブジェクトを使用し、メッセージとして continue_msg オブジェクトを使用します。continue_node コンストラクターは 2 つの引数を受け取ります。

template< typename Body > continue_node( graph &g, Body body)

最初の引数はそれが属するグラフであり、2 番目の引数は関数オブジェクトまたはラムダ式です。function_node とは異なり、continue_node は常に無制限の同時実行性を持つと想定され、依存関係が満たされるたびにすぐにタスクを生成します。

次のコードは、この図の例の実装です。

typedef continue_node< continue_msg > node_t; 
typedef const continue_msg & msg_t; 

int main() { 
  oneapi::tbb::flow::graph g; 
  node_t A(g, [](msg_t){ a(); } ); 
  node_t B(g, [](msg_t){ b(); } ); 
  node_t C(g, [](msg_t){ c(); } ); 
  node_t D(g, [](msg_t){ d(); } ); 
  node_t E(g, [](msg_t){ e(); } ); 
  node_t F(g, [](msg_t){ f(); } ); 
  make_edge(A, B); 
  make_edge(B, C); 
  make_edge(B, D); 
  make_edge(A, E); 
  make_edge(E, D); 
  make_edge(E, F); 
  A.try_put( continue_msg() ); 
  g.wait_for_all(); 
  return 0; 
}

このグラフで可能な実行例の 1 つを以下に示します。D の実行は、B と E の両方が終了するまで開始されません。タスクが wait_for_all で待機している間、そのスレッドは oneTBB ワークプールからの他のタスクの実行に参加できます。

依存関係グラフの実行タイムライン

イメージ2

繰り返しになりますが、フローグラフ内のすべての実行は非同期的であることに注意することが重要です。A.try_put の呼び出しは、カウンターをインクリメントし、A のボディーを実行するタスクを生成した後、呼び出し元のスレッドに制御をすばやく返します。同様に、ボディータスクはラムダ式を実行し、その後、存在する場合はすべての後続ノードに continue_msg を送信します。当然のことながら、wait_for_all の呼び出しのみがブロックされ、この場合でも、呼び出しスレッドは待機中に oneTBB のワークプールのタスクを実行するのに使用される可能性があります。

上記のタイムラインは、並列実行できるすべてのタスクを実行するのに十分なスレッドがある場合のシーケンスを示しています。スレッド数が少ない場合、生成されたタスクの一部は、実行できるスレッドが利用可能になるまで待機します。