parallel_reduce

parallel_reduce#

ループでは、次の合計計算のようにリダクションを行うことができます。

float SerialSumFoo( float a[], size_t n ) { 
    float sum = 0; 
    for( size_t i=0; i!=n; ++i ) 
        sum += Foo(a[i]); 
    return sum; 
}

反復が独立している場合、次のように parallel_reduce テンプレート・クラスを使用してループを並列化できます。

float ParallelSumFoo( const float a[], size_t n ) { 
    SumFoo sf(a); 
    parallel_reduce( blocked_range<size_t>(0,n), sf ); 
    return sf.my_sum; 
}

SumFoo クラスは、部分和を累積して結合する方法など、リダクションの詳細を指定します。SumFoo クラスの定義は次のとおりです。

class SumFoo { 
    float* my_a; 
public: 
    float my_sum; 
    void operator()( const blocked_range<size_t>& r ) { 
        float *a = my_a; 
        float sum = my_sum; 
        size_t end = r.end(); 
        for( size_t i=r.begin(); i!=end; ++i ) 
            sum += Foo(a[i]); 
        my_sum = sum; 
    } 

    SumFoo( SumFoo& x, split ) : my_a(x.my_a), my_sum(0) {} 

    void join( const SumFoo& y ) {my_sum+=y.my_sum;} 

    SumFoo(float a[] ) : 
        my_a(a), my_sum(0) 
    {} 
};

parallel_for の ApplyFoo クラスとの違いに注意してください。まず、operator() は const ではありません。これは、SumFoo::my_sum を更新する必要があるためです。2 番目に、SumFoo には、parallel_reduce が機能するために必要な分割コンストラクターと join メソッドがあります。分割コンストラクターの引数は、オリジナル・オブジェクトへの参照と、ライブラリーによって定義されるタイプ split の仮引数です。この仮引数によって、分割コンストラクターとコピー・コンストラクターが区別されます。

ヒント

この例では、operator() の定義は、ループ内でアクセスされるスカラー値にローカル一時変数 (a、sum、end) を使用します。この手法は、値をメモリーではなくレジスターに保持できることをコンパイラーに通知することで、パフォーマンスの向上に役立ちます。値が大きすぎてレジスターに収まらない、またはコンパイラーが追跡できない方法でアドレスが取得される場合、この手法は役に立たない可能性があります。一般的な最適化コンパイラーでは、書き込み対象の変数 (例の sum など) にのみローカル一時変数を使用すれば十分です。その理由は、コンパイラーはループが他の場所に書き込まないことを推測でき、他の読み取りをループの外側に移動できるためです。

タスク・スケジューラーでワーカースレッドが利用できると判断された場合、分割コンストラクターを呼び出すことでプロセッサーのサブタスクを作成し、parallel_reduce がそのワーカースレッドにワークを供給します。サブタスクが完了すると、parallel_reduce は join メソッドを使用してサブタスクの結果を蓄積します。次の図の上部のグラフは、ワーカーが利用可能な場合に発生する分割結合シーケンスを示しています。

分割結合シーケンスのグラフ image0

図中の矢印は時間的な順序を示しています。前半のリダクションでオブジェクト x が使用される間に、分割コンストラクターが同時に実行される可能性があります。そのため、y を作成する分割コンストラクターのすべての動作が、x に関してスレッドセーフである必要があります。分割コンストラクターで他のオブジェクトと共有のカウンターをインクリメントする場合は、アトミック・インクリメントを使用しなければなりません。

ワーカーが利用できない場合は、反復の後半は、前半をリデュースしたのと同じボディ・オブジェクトを使用してリデュースされます。つまり、前半のリデュースが終了したところから後半のリデュースが始まります。

警告

ワーカーが利用できない場合、分割/結合は使用されないため、parallel_reduce は必ずしも再帰的な分割を行うわけではありません。

警告

同じボディーが複数のサブレンジを累積するのに使用される可能性があるため、operator() が以前の累積を破棄しないことが重要です。以下のコードは、SumFoo::operator() の誤った定義を示しています。

class SumFoo { 
    ... 
public: 
    float my_sum; 
    void operator()( const blocked_range<size_t>& r ) { 
        ... 
        float sum = 0; // 間違い – sum = my_sum とすべき 
        ... 
        for( ... ) 
            sum += Foo(a[i]); 
        my_sum = sum; 
    } 
    ... 
};

この誤りにより、ボディーは parallel_reduce が適用するすべてのサブレンジではなく、最後のサブレンジの部分合計を返します。

parallel_reduce のパーティショナーと粒度のルールは、parallel_for と同じです。

parallel_reduce は、任意の結合演算に一般化されます。一般に、分割コンストラクターは次の 2 つを行います。

  • ループボディーを実行するのに必要な読み取り専用情報をコピーする。

  • リダクション変数を初期化して操作要素を特定する。

join メソッドは、対応するマージ操作を行います。複数のリダクションを同時に行うことが可能です。単一の parallel_reduce で最小値と最大値を同時に求めることができます。

注

リダクション操作は非可換になる場合があります。浮動小数点の加算を文字列の連結に置き換えても、この例は機能します。