元記事:How to make a pipeline with an Intel® Threading Building Blocks flow graph | Intel® Software, Michael Voss氏, 2011/9/14
自分自身の理解のために日本語訳を行ったIntel TBB フローグラフ解説記事。
Intel® Threading Building Blocks フローグラフによるパイプライン構成方法
Intel® Threading Building Blocks (Intel® TBB) フローグラフ(flow graph)はIntel® TBB 4.0でフルサポートされました。フローグラフについて馴染みがなければこちら（訳注：同記事の拙訳）の紹介を参照してください。
最近、フローグラフを用いたパイプラインの実装方法に関する質問が投稿されました。この質問により、Intel TBB パイプライン(pipeline)とIntel TBB フローグラフとの微妙な差異を明らかにすることでユーザの混乱を防げるのでは、と気づかされました。
実例として、Intel TBB配布パッケージに含まれるパイプラインの例examples/pipeline/squareを変換していきます。この例では図1に示す3段のパイプラインを用いています。
図1: examples/pipeline/squareで用いられている3段のパイプライン
squareの例では、inputフィルタが入力ファイルから文字列ブロックを読み込みます。各ブロックは固定長からなり、ブロックの読込みが完了すると次のtransfromフィルタへ送られます。2番目のフィルタは出力バッファを割当てる並列(parallel)フィルタであり、入力バッファ中の文字列をlong型に変換し、その値を二乗した結果を出力バッファに書き込みます。値は出力バッファから最後のフィルタ、逐次順序(serial-in-order)なoutputフィルタに渡されます。outputフィルタは同時に1個のバッファを、inputフィルタが作成した順序にて処理します。同フィルタは二乗した結果を出力ファイルへダンプします。バッファ処理は順序付け(in-order)されるため、出力ファイルに書き出される値は入力ファイル中での順序と一致します。
図2にフローグラフへの素直な変換結果を示します。それぞれinputフィルタはsource_nodeへ、2個目のフィルタは無制限の並列度を持つfunction_nodeへ、最後のフィルタは並列度1のfunction_nodeへと変換しています。大部分は長方形を円形に替えただけです:)。ただし、残念ながらこの実装は誤った結果を生成し、かつ不十分なパフォーマンスを示すでしょう。
図2: 素直な（しかし間違った）フローグラフへの変換
最初に不正確さの問題から片付けましょう。先のフローグラフ中の最終ノードは、並列度1のため逐次処理されますが、ノードはバッファをFIFO(first-in-first-out)順で扱います。一方で、serial-in-orderなフィルタを用いるパイプライン版は、inputフィルタにより生成されたアイテムの再順序付けを許容します。図3に示す通り、この振る舞いはsequencer_nodeを追加することで模倣できます。（訳注：データがフローグラフ上を流れる順序はout-of-orderであり、最終ノードがアイテムを受け取る順序は保証されない。一方、パイプライン版はserial-in-orderを指定するため、最終フィルタでのアイテム処理順序は入力フィルタのアイテム出力順序と一致することが保証される。）
図3: 正しい（ただし遅い）フローグラフへの変換
フローグラフへsequencer_nodeを追加したことで、各バッファに対してinputフィルタで確保した順序通りのシーケンス番号を割り当てることが要求されます。与えられたバッファに対するシーケンス番号を返す関数を記述し、sequencer_nodeへ設定しなければいけません。
図3のフローグラフはまだ問題を抱えています。source_nodeノードinputは、無制限の並列度を持つfunction_nodeノードtransformに直結しています。これは、inputノードが送信したアイテムをtransformノードが全て受け入れることを意味します。inputノードは何も考えずに新しいバッファを確保し続け、フローグラフを入力データで溢れてさせてしまいます。最良のケースでは、酷いパフォーマンスでシステムを立ち往生させるでしょうし、最悪のケースでは、アプリケーションはメモリを消費し尽くしてクラッシュさせるでしょう。
このような状況は、トークンベーススケジューリング機構をもつIntel TBB パイプラインでは生じません。パイプラインを実行するときに、ユーザは固定数のトークンをパイプラインに与えます。パイプライン中では1トークンあたり1アイテムしか存在しません。squareの例では、パイプラインへ1コアあたり4個のトークンを与えて実行しています:
pipeline.run( nthreads*4 );
フローグラフはトークンベースのスケジューリングを行いません。フローグラフ中のノードは複数出力の生成やメッセージの統合・分割を行なうことが出来るため、トークンベースシステムの実現が不可能でなかったとしても、デッドロックの危険性を回避するのは困難です。しかし、フローグラフではメモリ使用量を制限する別の方法を提供します。その方法の1つに、図4に示すlimiter_nodeの利用があげられます。
図4: 正しくかつ効率的なフローグラフへの変換
図4では、limiter_nodeをinputフィルタとtransformフィルタとの間に挿入しました。limiter_nodeはユーザ指定のしきい値を持ち、その個数以下のメッセージを受け付けて通過させます。第2の入力ポートはノード内部の転送メッセージカウントを減算するために用いられます。もし図4のlimiter_nodeに閾値 4*nthreads を与えて構築すれば、そのメモリ使用量はパイプライン版の実装と同程度に抑えられるでしょう。outputフィルタからlimiter_nodeに戻るエッジ/辺(edge)で、（訳注：limiter_node内部カウンタを減らすことにより）inputフィルタからの追加入力の許可を通知します。
squareの例では示されていませんが、パイプラインは並列入力フィルタを持つことが可能です。一方でsource_nodeは常に逐次処理されます。この制限は、フローグラフにトークンベーススケジューリングが無いためにもたらされます。パイプライン中での入力フィルタのコピー個数は、有効トークン数によって制限されます。フローグラフにはそのような上限は無く、並列実行されるsource_node本体の個数を決める実用的な方法もありません。フローフラフ中で並列入力フィルタの振る舞いを模倣する方法は存在しますが、その議論は今後のブログ記事へ譲ることとします。
下記コードはexamples/pipeline/squareにある、図1に示したIntel TBB パイプライン構造を構築している部分です。3個のフィルタがそれぞれ構築されてパイプラインに追加されます。最後にパイプラインを 4*nthreads 個のトークンで実行します。
tbb::pipeline pipeline;
MyInputFilter input_filter( input_file );
pipeline.add_filter( input_filter );
MyTransformFilter transform_filter;
pipeline.add_filter( transform_filter );
MyOutputFilter output_filter( output_file );
pipeline.add_filter( output_filter );
pipeline.run( nthreads*4 );
図4のIntel TBB フローグラフ構造を構築するコードを下記に示します。各ノードが構築され、エッジ/辺がノード間に追加されます。しきい値 4*nthreads を持つlimiter_nodeが渡され、sequencer_nodeがoutputノードの前に配置されます。最後にsource_nodeがactivateされて、フローグラフの完了を待機するwait_for_allが呼ばれます。
tbb::flow::graph g; tbb::flow::limiter_node limiter( g, nthreads*4 ); tbb::flow::sequencer_node< TextSlice * > sequencer(g, sequencer_body() ); tbb::flow::source_node input( g, MyInputFilter(input_file), false ); tbb::flow::function_node transform( g, tbb::flow::unlimited, MyTransformFilter() ); tbb::flow::function_node output( g, tbb::flow::serial, MyOutputFilter( output_file ) ); tbb::flow::make_edge( input, limiter ); tbb::flow::make_edge( limiter, transform ); tbb::flow::make_edge( transform, sequencer ); tbb::flow::make_edge( sequencer, output ); tbb::flow::make_edge( output, limiter.decrement ); input.activate(); g.wait_for_all();
フローグラフのコードはパイプライン版よりも明らかに冗長ですが、そのパフォーマンスは同程度になるでしょう。このように、パイプライン構造をもつアプリケーションはIntel TBB パイプラインを用いた方が簡単に表現できますが、Intel TBB フローグラフはより柔軟なAPIであり非線形パイプラインのアプリケーションを表現することができます。
結論として、Intel TBB パイプラインとIntel TBB フローグラフとの間には些細ですが重要な差異が存在します。まず、パイプラインはserial-in-orderノードをサポートしますが、フローグラフで同様の振る舞いをさせるにはsequencer_nodeが必要です。次に、より重要なことに、パイプラインはトークンベーススケジューリングを用いますが、フローグラフはそうではありません。フローグラフAPIには、本記事で議論したlimiter_nodeといったトークンベーススケジューリングを行なう代替手段があります。また以前のブログ記事Intel® Threading Building Blocks フローグラフを用いた特徴検出の例（訳注：同記事の拙訳）では、reserving joinノードによるメモリ使用量の管理手法を説明しました。そして最後に、トークンベーススケジューリングでないためにsource_nodeは常に逐次処理され、パイプラインでの並列入力フィルタを模倣するにはより複雑な方式が必要となります。
Intel® Threading Building Blocks 4.0の新機能については http://www.threadingbuildingblocks.org を、またIntel® TBB フローグラフについては http://software.intel.com/en-us/blogs/tag/flow_graph/ にあるブログ記事をチェックしてください。
