ウェーブフロント

問題

データセット内の項目に対して計算を実行します。項目の計算では、先行する項目の計算の結果が使用されます。

コンテキスト

計算間の依存関係は非巡回グラフを形成します。

強制

• 項目間の依存制約は非巡回グラフを形成します。

• グラフ内の直前の先行タスクの数は事前にわかっているか、最後の先行タスクが完了する直前に決定できます。

解決方法

解決策は、oneapi::tbb::parallel_for_each を使用して項目を処理する、トポロジカル・ソートの並列バリアントです。各項目にアトミックカウンターを関連付けます。各カウンターを先行数に初期化します。oneapi::tbb::parallel_for_each を呼び出して、先行する項目がない (カウントが 0 である) 項目を処理します。項目が処理された後、後続の項目のカウンターをデクリメントします。後続のカウンターがゼロに達した場合、「フィーダー」を介してその後続を oneapi::tbb::parallel_for_each に追加します。

項目の先行タスクの数が不明である場合、「先行タスクの数を認識 (know number of predecessors)」という情報を追加の先行タスクとして扱います。先行タスクの数が判明したら、概念上の先行タスクを完了したものとして扱います。

個々の項目をカウントするオーバーヘッドが大きすぎる場合、項目をブロックに集約し、ブロックに対してウェーブフロントを実行します。

例

以下は、最長の共通部分列アルゴリズムのシリアルカーネルです。パラメーターは、それぞれ長さが xlen と ylen である文字列 x と y です。

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]); 
}

カーネルは F[i][j] を x[0..i-1] と y[0..j-1] が共有する最長共通部分列の長さに設定します。F[0][0..ylen] と F[0..xlen][0] はすでにゼロに初期化されていると想定しています。

次の図は F[i][j] を計算するデータの依存関係を示しています。

最長共通部分文字列計算におけるデータ依存関係。

次の図は、灰色の対角線の依存関係が、他の依存関係の推移閉包であることを示しています。したがって、並列化では、これは無視できる冗長な依存関係です。

対角依存関係は冗長です。

アトミックカウントでは依存関係ごとにコストが発生するため、通常は冗長な依存関係を考慮から除外するのが適切です。

もう一つの考慮事項は粒度です。各 F[i][j] 要素の計算を個別にスケジュールすると、非常にコストが高くなります。 良い解決策は、要素を連続したブロックに集約し、ブロックの内容を順番に処理することです。ブロックは同じ依存関係パターンを持ちますが、ブロック単位です。したがって、スケジュールのオーバーヘッドはブロック全体で償却できます。

並列コードは以下のとおりです。各ブロックは N×N 要素で構成されます。各ブロックには関連するアトミックカウンターがあります。Count 配列はこれらのカウンターを整理して簡単に検索できるようにします。コードはカウンターを初期化し、先行がないため原点のブロックから始めて、parallel_for_each を使用してウェーブフロントをロールします。

const int N = 64; 
std::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 ) { 
    // ブロックの先行カウントを初期化 
    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); 
    oneapi::tbb::parallel_for_each( &origin, &origin+1, 
        [=]( const block& b, oneapi::tbb::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]); 
            // 後続を考慮する 
            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) ); } 
    ); 
}

参考資料

Eun-Gyu Kim and Mark Snir, “Wavefront Pattern”, http://snir.cs.illinois.edu/patterns/wavefront.pdf