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

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

グラフ並列処理を使用すると、計算はノードによって表され、これらの計算間の通信チャネルはエッジによって表されます。グラフ内のノードがメッセージを受信すると、受信メッセージに対してそのボディー・オブジェクトを実行するタスクが生成されます。メッセージは、ノードを接続するエッジを経由してグラフを流れます。以下では、グラフとして表現できるアプリケーションの例を 2 つ示します。

次の図は、各値がグラフ内のノードを通過するときに値のシーケンスが処理されるストリーミングまたはデータ・フロー・アプリケーションを示しています。この例では、シーケンスは関数 F によって作成されます。シーケンス内の各値に対して、G は値を 2 乗し、H は値を 3 乗します。次に、J は各平方値と立方値を合計し、グローバルの合計を計算します。シーケンス内のすべての値が完全に処理された後、合計は 1 から 10 までの平方数と立方数のシーケンスの合計に等しくなります。ストリーミング・グラフまたはデータ・フロー・グラフでは、値は実際にエッジ間を流れ、1 つのノードの出力が後続ノードの入力になります。

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

以下の図は、異なる形式のグラフ・アプリケーションを示しています。この例では、依存関係グラフを使用して、ピーナッツバターとジャムのサンドイッチを作る手順の部分的な順序付けを確立します。この部分的な順序では、まずパンを手に入れ、その後でパンにピーナッツバターやジャムを塗る必要があります。ピーナッツバターの瓶をしまう前にピーナッツバターを塗っておく必要があります。同様に、ジャムの瓶をしまう前にジャムを塗っておく必要があります。そして、2 枚のパンを重ねる前に、ピーナッツバターとジャムを両方塗り終える必要があります。これは部分的な順序付けです。例えば、最初にピーナッツバターを塗るか、ジャムを塗るかは関係ありません。瓶を片付ける前にサンドイッチを作り終えても問題ありません。

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

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

oneTBB ライブラリーのフロー・グラフ・インターフェイスを使用すると、このようなデータ・フロー・グラフや依存関係グラフだけでなく、サイクル、条件、バッファリングなどを含む複雑なグラフも表現できます。フロー・グラフ・インターフェイスを使用してアプリケーションを表現する場合、ランタイム・ライブラリーはタスクを生成し、グラフ内にある並列処理を活用します。例えば、上記の最初の例では、おそらく 2 つの異なる値が並行して 2 乗されるか、同じ値が並行して 2 乗および 3 乗される可能性があります。同様に、2 番目の例では、ピーナッツバターが 1 枚のパンに塗られ、並行して、もう 1 枚のパンにジャムが塗られる場合があります。インターフェースは、並列実行が許可される処理を定義しますが、ランタイム・ライブラリーが実行時に並列実行する処理を選択できるようにしています。

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