タスクグラフはこれまで、各タスクに完了を待っている 1 つのサクセサー task::parent() があるツリー構造であると考えられていました。1 つのタスクに複数のサクセサーがある、より複雑なグラフを扱えるように、インテル® スレッディング・ビルディング・ブロック (インテル® TBB) 2.2 以降には、タスクの参照カウントを直接操作できるメソッドが用意されています。
例えば、タスクが左と上のタスクに依存する MxN 配列のタスクを考えてみます。次の図は、この例を示しています。
次のコードは、各タスクで左からの入力と上からの入力の合計を計算するタスクグラフを評価します。
const int M=3, N=4;
class DagTask: public tbb::task {
public:
const int i, j;
// input[0] = 上からの合計、input[1] = 左からの合計
double input[2];
double sum;
// successor[0] = 下のサクセサー、successor[1] = 右のサクセサー
DagTask* successor[2];
DagTask( int i_, int j_ ) : i(i_), j(j_) {
input[0] = input[1] = 0;
}
task* execute() {
__TBB_ASSERT( ref_count()==0, NULL );
sum = i==0 && j==0 ? 1 : input[0]+input[1];
for( int k=0; k<2; ++k )
if( DagTask* t = successor[k] ) {
t->input[k] = sum;
if( t->decrement_ref_count()==0 )
spawn( *t );
}
return NULL;
}
};
double BuildAndEvaluateDAG() {
DagTask* x[M][N];
for( int i=M; --i>=0; )
for( int j=N; --j>=0; ) {
x[i][j] = new( tbb::task::allocate_root() ) DagTask(i,j);
x[i][j]->successor[0] = i+1<M ? x[i+1][j] : NULL;
x[i][j]->successor[1] = j+1<N ? x[i][j+1] : NULL;
x[i][j]->set_ref_count((i>0)+(j>0));
}
// 最後のタスクは spawn_and_wait_for_all で待機するため
// 追加の参照を追加
x[M-1][N-1]->increment_ref_count();
// 最後のタスク以外のすべてのタスクが完了するのを待つ
x[M-1][N-1]->spawn_and_wait_for_all(*x[0][0]);
// 最後のタスクは暗黙的に実行されないため明示的に実行
x[M-1][N-1]->execute();
double result = x[M-1][N-1]->sum;
// 最後のタスクを破棄
task::destroy(*x[M-1][N-1]);
return result;
}
BuildAndEvaluateDAG 関数は、DagTask の配列を最初に作成します。task::parent() はサクセサーとの関係の記録に使用しないため、各タスクをルートタスクとして割り当てます。各タスクの参照カウントは、プレデセッサー・タスクの数に初期化します。初期タスク x[0][0] を作成し、x[M-1][N-1] が完了するのを待つことで、グラフを評価します。各タスクが完了すると、サクセサーの参照カウントをデクリメントして、カウントがゼロになるサクセサーを作成します。十分な数のプロセッサーが提供されると、グラフの左上から右下に向かって、波のように対角線上に実行されます。
BuildAndEvaluateDAG で特別な処理を行うため、最後のタスク x[M-1][N-1] は特別な制御が必要です。
-
最後のタスクは、ほかのタスクが完了するのを明示的に待つために使用されます。wait_for_all メソッドでは、最後のタスクの参照カウントをプレデセッサー・タスクの数よりも 1 つ多く設定します。このため、最後のタスクはプレデセッサー・タスクが完了しても暗黙で実行されません。
-
sum の値は、最後のタスクが破棄される前に取得する必要があります。
例では、最後のタスクを明示的に実行し、sum を取得した後で、最後のタスクを破棄しています。