問題
プレデセッサー・アイテムの計算結果を使用してデータセットのアイテムの計算を行う。
コンテキスト
計算間の依存関係により閉路のないグラフが形成されます。
影響
-
アイテム間の依存関係の制約により閉路のないグラフが形成されます。
-
グラフの直前のプレデセッサーの数はあらかじめ分かっているか、最後のプレデセッサーが完了する前に決定されます。
ソリューション
アイテムの処理に tbb::parallel_do を使用して、トポロジカル・ソートを並列に行います。各アイテムにアトミックカウンターを関連付けます。各カウンターをプレデセッサーの数に初期化します。tbb::parallel_do を呼び出してプレデセッサーのないアイテム (カウントがゼロ) を処理します。アイテムが処理されたら、そのサクセサーのカウンターをデクリメントします。サクセサーのカウンターがゼロになったら、「feeder」によりサクセサーを tbb::parallel_do に追加します。
プレデセッサーの数があらかじめ決定できない場合、「既知のプレデセッサーの数 (know number of predecessors)」をプレデセッサー項目として扱います。プレデセッサーの数が分かったら、この概念的なプレデセッサーを完了したとして扱います。
個々のアイテムをカウントするオーバーヘッドが大きい場合、複数のアイテムを凝集化して、そのブロックに対してウェーブフロントを行います。
サンプル
最長共通部分列アルゴリズムのシリアルカーネルを次に示します。引数は文字列 x と y (長さは xlen と ylen) です。
int F[MAX_LEN+1][MAX_LEN+1];
void SerialLCS( const char* x, size_t xlen, const char* y, size_t ylen )
{
for( size_t i=1; i<=xlen; ++i )
for( size_t j=1; j<=ylen; ++j )
F[i][j] = x[i-1]==y[j-1] ? F[i-1][j-1]+1:
max(F[i][j-1],F[i-1][j]);
}
カーネルは、x[0..i-1] および y[0..j-1] で共有される最長共通部分列の長さに F[i][j] をセットします。F[0][0..ylen] および F[0..xlen][0] はすでにゼロに初期化されていると仮定します。
次の図は、F[i][j] 計算のデータの依存関係を示しています。
次の図で示されているように、灰色の対角線の依存関係はほかの依存関係の推移閉鎖です。このため、並列化に際しこの依存関係を無視できます。
アトミックカウントは依存関係を考慮するコストがかかるため、冗長な依存関係を考慮しないようにすることは一般に良い方法です。
もう 1 つ考慮すべき点は粒度です。F[i][j] の要素計算を別々にスケジュールするのはコストがかかりすぎます。複数の要素を連続するブロックに擬集化して、ブロックのコンテンツを連続して処理するほうが適切です。ブロックの依存関係のパターンは同じですが、ブロックはスケールします。このため、スケジュールのオーバーヘッドを考慮してもメリットがあります。
並列コードを次に示します。各ブロックは N×N の要素で構成されます。各ブロックにはアトミックカウンターが関連付けられています。配列 Count は、簡単に調査するためこれらのカウンターを構成します。コードはカウンターを初期化した後、parallel_do を使用して、ウェーブフロントを処理します (predecessor がないため最初のブロックから開始)。
const int N = 64;
tbb::atomic<char> Count[MAX_LEN/N+1][MAX_LEN/N+1];
void ParallelLCS( const char* x, size_t xlen, const char* y, size_t ylen ) {
// ブロックの predecessor カウントを初期化
size_t m = (xlen+N-1)/N;
size_t n = (ylen+N-1)/N;
for( int i=0; i<m; ++i )
for( int j=0; j<n; ++j )
Count[i][j] = (i>0)+(j>0);
// ウェーブフロントを原点から回転
typedef pair<size_t,size_t> block;
block origin(0,0);
tbb::parallel_do( &origin, &origin+1,
[=]( const block& b, tbb::parallel_do_feeder<block>&feeder ) {
// ブロックの境界を抽出
size_t bi = b.first;
size_t bj = b.second;
size_t xl = N*bi+1;
size_t xu = min(xl+N,xlen+1);
size_t yl = N*bj+1;
size_t yu = min(yl+N,ylen+1);
// ブロックを処理
for( size_t i=xl; i<xu; ++i )
for( size_t j=yl; j<yu; ++j )
F[i][j] = x[i-1]==y[j-1] ? F[i-1][j-1]+1:
max(F[i][j-1],F[i-1][j]);
// successor を考慮
if( bj+1<n && ‐‐Count[bi][bj+1]==0 )
feeder.add( block(bi,bj+1) );
if( bi+1<m && ‐‐Count[bi+1][bj]==0 )
feeder.add( block(bi+1,bj) ); }
);
}
規則的な構造はウェーブフロントの実装を単純化しますが、必須ではありません。examples/parallel_do/parallel_preorder の並列前順走査では、predecessor が走査された後にノードが走査されるという制約に従って、ウェーブフロント・パターンをグラフの各ノードの走査を並列に処理します。このサンプルで、グラフ中の各ノードは predecessor のカウントを格納します。
参考資料
Eun-Gyu Kim および Mark Snir、"Wavefront Pattern"、http://web.engr.illinois.edu/~snir/patterns/wavefront.pdf