データフローと依存関係グラフの並列化

インテル® スレッディング・ビルディング・ブロック (インテル® TBB) ライブラリーはループの並列処理に加えて、グラフの並列処理もサポートしています。 高度にスケーラブルなグラフを作成したり、完全にシーケンシャルなグラフを作成することもできます。

グラフの並列処理では、計算はノードで表され、これらの計算の通信チャネルはエッジで表されます。 グラフのノードがメッセージを受け取ると、受け取ったメッセージでそのボディー・オブジェクトを実行するタスクがスポーンされます。 メッセージはノードを接続しているエッジを介してグラフを流れます。 次のセクションでは、グラフとして表現できるアプリケーションの例を 2 つ示します。 タスクについての詳細は、「タスクベースのプログラミング」を参照してください。

次の図は、グラフのノードを介して値のシーケンスを処理するストリーミング (データフロー) アプリケーションを示しています。 この例で、シーケンスは関数 F によって作成されます。 シーケンスの各値について、G は値の 2 乗を計算し、H は値の 3 乗を計算します。 次に、J は 2 乗された値と 3 乗された値を sum に追加します。 シーケンスの値がすべて完全に処理されると、sum は 1 から 10 までの 2 乗と 3 乗の合計になります。 ストリーミング (データフロー) グラフでは、値はエッジを介して実際に流れます。ノードの出力はその後継の入力になります。

単純なデータフロー・グラフ
単純なデータフロー・グラフ

次の図は、グラフ・アプリケーションの別の形式を示しています。この例では、依存関係グラフを使用し、ピーナッツバターとジャムを塗ってサンドイッチを作るステップの半順序を確立しています。 この半順序では、パンにピーナッツバターやジャムを塗る前に、まずパンを用意する必要があります。 ピーナッツバターの瓶を片付ける前にピーナッツバターを塗る必要があり、同様にジャムの瓶を片付ける前にジャムを塗る必要があります。 また、2 切れのパンを重ねる前にピーナッツバターとジャムを塗る必要があります。 ピーナッツバターとジャムを塗るのはどちらが先でもかまわないため、これは半順序です。 また、瓶を片付けるのとパンを重ねるのも、どちらが先でもかまいません。

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

パンやジャムの瓶のようなリソースは、順序付けされたステップ間で共有されると推測できますが、グラフで明示されていません。 代わりに、必要なステップの順序のみ依存関係グラフで明示されています。 例えば、「ジャムの瓶を片付ける」前に「パンにジャムを塗る」必要があります。

インテル® TBB ライブラリーのフローグラフのインターフェイスを使用すると、データフローや依存関係グラフだけでなく、サイクル、条件、バッファーなどを含むより複雑なグラフも表現できます。 フローグラフのインターフェイスを用いてアプリケーションを表現した場合、ランタイム・ライブラリーはグラフの並列処理を実行するタスクをスポーンします。 例えば、上記の最初の例では、2 つの異なる値の 2 乗の計算が並列に行われるか、同じ値の 2 乗の計算と 3 乗の計算が並列に行われます。 同様に、2 番目の例では、ピーナッツバターをパンに塗るステップとジャムを別のパンに塗るステップが並列に行われます。 インターフェイスは何が並列実行できるかを示し、ランタイム・ライブラリーは何を並列実行するかランタイムに決定します。

グラフの並列処理のサポートは tbb::flow 名前空間に含まれており、flow_graph.h ヘッダーファイルで定義されています。

関連情報