yohhoyの日記

技術的メモをしていきたい日記

（翻訳）Intel Threading Building Blocks フローグラフを用いたウェーブフロント計算の実装

C++ TBB

元記事:Implementing a wave-front computation using the Intel® Threading Building Blocks flow graph | Intel® Software, Michael Voss氏, 2011/9/9

自分自身の理解のために日本語訳を行ったIntel TBB フローグラフ解説記事。

Intel® Threading Building Blocks フローグラフを用いたウェーブフロント計算の実装*1

Intel® Threading Building Blocks (Intel® TBB) フローグラフ(flow graph)はIntel® TBB 4.0でフルサポートされました。フローグラフについて馴染みがなければ、こちら（訳注：同記事の拙訳）の紹介を参照してください。

今回のフローグラフ中で用いる1種類のノードタイプは continue_node<T> です。このノードタイプは依存性グラフの実装向けに設計されており、先行ノード群が完了するまで自ノードの処理開始を待機します。continue_nodeは先行ノードからデータメッセージを受信しない代わりに、受信したcontinue_msgの個数を数えます。各先行ノードから1個づつ計P個のメッセージを受信すると、ノード本体を実行して型Tの出力メセージを生成します。多くの場合、出力の型もまたcontinue_msgを用います。

ここではcontinue_nodeを次のように図示します。
cnode

このシンボルはcontinue_nodeに関する重要な性質を伝えようとしたものです。入力辺の上に数本の線がありますが、これは受信メッセージの個数を数えることを意味します。また、円の内側にあるf()はノード本体が引数をとらないファンクタであることを意味します。

図1は、continue_nodeオブジェクトの集合を用いてウェーブフロント計算を実装するアプローチを示しています。この例では、各計算の実行開始前に上および左側の計算完了を待たなければいけません。大半のノードは2つの先行ノードを持つため、2個のcontinue_msgメッセージを受信するまでは計算を開始しません。上段と左列に位置するノードでは1つの先行ノードしか持たないため、1個のcontinue_msgメッセージ到着を待ちます。

図1
図1: ウェーブフロント計算のIntel® Threading Building Blocks フローグラフによる表現

今回はIntel® TBBフローグラフを用いてウェーブフロント計算を行う、完全なコードを示します。今回の例では、各ノードにおける計算は二次元行列のブロックの更新です。行列要素の左隣と上隣の要素値が等しいならば、該当の要素値は隣接値を2倍した値に設定されます。そうでなければ、要素値には2つのうち最大値が設定されます。また、左上要素は値1で初期化します。例えば5x5行列の場合、計算結果は次の通りです：

1 1 1 1 1
1 2 2 2 2
1 2 4 4 4
1 2 4 8 8
1 2 4 8 16

下記コードでは必要ヘッダのinclude、いくつかのパラメータ定義、および行列要素の計算を行う関数calcの定義を行います。定数M, Nは行列のサイズを定義します。各ノードで計算されるブロックの次元はブロックサイズBで与えられ、各次元のブロック個数はMB, NBへ格納されます。計算結果は二次元行列valueへ格納されます。

#include <algorithm> // for std::max
#include <cstdio>

#include "tbb/flow_graph.h"

using namespace tbb;
using namespace tbb::flow;

int M=1000, N=1000;
int B = 100;
int MB = (M/B) + (M%B>0);
int NB = (M/B) + (M%B>0);

double **value;

inline double calc( double v0, double v1 ) {
  if ( v0 == v1 )
    return 2*v0;
  else
    return std::max(v0,v1);
}

次のコードは、図1に示した依存性に従い行列ブロックに対して関数calcを適用するフローグラフを構築します。二次元配列nodeは、continue_nodeオブジェクトへのポインタ保持に用います。関数BuildGraphでは、二重forループによりcontinue_nodeオブジェクトを割り当てます。各ノードはグラフオブジェクトgへの参照と、該当ブロック行列に対し関数calcの適用を行うラムダ式とを与えて構築します。各ノードを作成した後、自身から後続ノードへのエッジ/辺(edge)を作成して依存性グラフを構築します。ループでは図1の右下から左上へ走査するため、各ノードの後続ノードは作成済みであることに留意してください。

continue_node<continue_msg> ***node;

void BuildGraph( graph &g ) {
  value[M-1][N-1] = 0;
  for( int i=MB; --i>=0; )
    for( int j=NB; --j>=0; ) {
      node[i][j] =
        new continue_node<continue_msg>( g,
                         [=]( const continue_msg& ) {
                           int start_i = i*B;
                           int end_i = (i*B+B > M) ? M : i*B+B;
                           int start_j = j*B;
                           int end_j = (j*B+B > N) ? N : j*B+B;
                           for ( int ii = start_i; ii < end_i; ++ii ) {
                             for ( int jj = start_j; jj < end_j; ++jj ) {
                               double v0 = ii == 0 ? 0 : value[ii-1][jj];
                               double v1 = jj == 0 ? 0 : value[ii][jj-1];
                               value[ii][jj] = ii==0 && jj==0 ? 1 : calc(v0,v1);
                             }
                           }
                         } );
      if ( i + 1 < MB ) make_edge( *node[i][j], *node[i+1][j] );
      if ( j + 1 < NB ) make_edge( *node[i][j], *node[i][j+1] );
    }
}

関数EvaluateGraphはフローグラフを実行します。グラフ実行は左上ノードにcontinue_msgを発行(put)することで行い、グラフ上の処理が停止するまで待機します。g.wait_for_all()呼び出しが返ってくると、全ノードの評価が完了し最終結果が生成されています。（訳注：最終結果とは行列の右下要素value[M-1][N-1]のこと。）

double EvaluateGraph( graph &g ) {
  node[0][0]->try_put(continue_msg());
  g.wait_for_all();
  return value[M-1][N-1];
}

continue_nodeオブジェクトの行列を作成したので、削除も行わないといけません。

void CleanupGraph() {
  for( int i=0; i<MB; ++i )
    for( int j=0; j<NB; ++j )
     delete node[i][j];
}

最後に、フローグラフを構築・評価・後始末する関数を呼び出すmain関数を示します。

int main(int argc, char *argv[]) {
  value = new double *[M];
  for ( int i = 0; i < M; ++i ) value[i] = new double [N];

  node = new continue_node<continue_msg> **[MB];
  for ( int i = 0; i < MB; ++i ) node[i] = new continue_node<continue_msg> *[NB];

  graph g;
  BuildGraph(g);
  double result = EvaluateGraph(g);
  CleanupGraph();
  printf("%g\n", result);

  for ( int i = 0; i < M; ++i ) delete [] value[i];
  for ( int i = 0; i < MB; ++i ) delete [] node[i];
  delete [] value;
  delete [] node;

  return 0;
}

このサンプルが、フローグラフで依存性グラフを簡易に表現できる例示となることを望みます。基本ステップは、(1) continue_nodeオブジェクトの集合を作成し、(2) make_edge関数呼び出しによりノード間を接続、(3) 先行ノードを持たないノードにcontinue_msgを送信することでグラフ実行を開始する となります。

もしIntel® Threading Building Blocks (Intel® TBB) フローグラフについて興味があれば、http://software.intel.com/en-us/blogs/tag/flow_graph にある他のブログ記事をチェックするか、http://www.threadingbuildingblocks.org を訪れてみてください。

*1:ウェーブフロント(Wavefront)計算は並列処理パターンの一種。