要素単位

問題

データセットの各アイテムで同様の独立した計算が開始され、すべて完了するまで待機する。

コンテキスト

多くのシリアル・アルゴリズムは、アイテムのセットを走査して各アイテムの独立した計算を行います。ただし、ある種のサマリー情報が収集される場合は、代わりにリダクション・パターンを使用します。

影響

計算中に情報が伝えられません (またはマージされません)。

ソリューション

アイテム数があらかじめ分かっている場合は、tbb::parallel_for を使用します。分かっていない場合は、tbb::parallel_do を使用します。

個々の計算がスケジューラーのオーバーヘッドよりも相対的に小さい場合は、凝集化を使用します。

同じデータに対するリダクションがパターンに続く場合は、リダクションの一部として要素単位の操作を行う (2 つのパターンの組み合わせを 2 回の走査ではなく 1 回の走査で行う) ことを検討してみてください。メモリー階層間のトラフィックが減ることでパフォーマンスが向上する可能性があります。

サンプル

畳み込みは信号処理でよく使用されます。フィルター c と信号 x の畳み込みは次のように計算されます。

この計算のシリアルコードは次のようになります。

// c[0..clen-1] と x[1-clen..xlen-1] が定義されていると仮定します
for( int i=0; i<xlen+clen-1; ++i ) {
   float tmp = 0;
   for( int j=0; j<clen; ++j )
       tmp += c[j]*x[i-j];
   y[i] = tmp;
}

簡潔に表記するため、x は x[k] (k<0 または k≥xlen の場合にゼロを返す) のようにゼロでパディングされる配列のポインターであると仮定しています。

各反復は前の反復に依存するため、内部ループは要素単位パターンに自然に適合しませんが、外部ループは要素単位パターンに適合します。上記のコードは、tbb::parallel_for を使用して次のように表現できます。

tbb::parallel_for( 0, xlen+clen-1, [=]( int i ) { 
   float tmp = 0;
   for( int j=0; j<clen; ++j )
       tmp += c[j]*x[i-j];
   y[i] = tmp;
});

tbb::parallel_for は、その実装で暗黙的に tbb::auto_partitioner を使用して自動で凝集化を行います。明示的に凝集化を行う理由がある場合は、明示的な範囲引数を指定できる tbb::parallel_for のオーバーロードを使用します。オーバーロードを使用するように変更したサンプルを次に示します。

tbb::parallel_for(
   tbb::blocked_range<int>(0,xlen+clen-1,1000),
   [=]( tbb::blocked_range<int> r ) { 
		 int end = r.end();
       for( int i=r.begin(); i!=end; ++i ) {
           float tmp = 0;
           for( int j=0; j<clen; ++j )
               tmp += c[j]*x[i-j];
           y[i] = tmp;
       }
   }
);