parallel_scan テンプレート関数

概要

並列プリフィクスを計算するテンプレート関数。

ヘッダー

#include "tbb/parallel_scan.h"

構文

template<typename Range, typename Body> 
void parallel_scan( const Range& range, Body& body [, partitioner] );

template<typename Range, typename Value, typename Scan, typename Combine>
Value parallel_scan( const Range& range, const Value& identity,
                     const Scan& scan, const Combine& combine
                     [, partitioner] );

オプションの partitioner は、「パーティショナー」セクションのパーティショナー表の列 1 にある auto_partitioner または simple_partitioner を宣言します。

説明

parallel_scan テンプレート関数は、並列プリフィクス (並列スキャンとも呼ばれる) を計算します。この計算は、並列計算における高度なコンセプトで、シリアルな依存性があるように見えるシナリオで役立つことがあります。

並列プリフィクスの数学的な定義は以下のとおりです。× を左単位元が id× の結合操作にします。シーケンス z0, z1, ...zn-1 の × の並列プリフィクスはシーケンス y0, y1, y2, ...yn-1 です。

例えば、× が加算の場合、並列プリフィクスは合計と一致します。並列プリフィクスのシリアル実装は以下のようになります。

T temp = id×;
for( int i=1; i<=n; ++i ) {
    temp = temp × z[i];
    y[i] = temp;
}
    

並列プリフィクスは、× のアプリケーションを再構築して 2 つのパスにすることで、この処理を並列実行します。シリアル・プリフィクス・プログラムの 2 倍まで × を呼び出す可能性があります。より多くの処理を行っているにもかかわらず、適切な粒度が指定されると、並列アルゴリズムは複数のハードウェア・スレッドにわたってワークを分散できるため、シリアル・プリフィクスより性能が優れています。妥当なスピードアップを得るため、マルチコアシステムの使用を推奨します。

parallel_scan テンプレートには 2 つの形式があります。命令形式 parallel_scan(range, body) は、並列プリフィクスを汎用的に実装します。Range 型は、Range コンセプトをモデル化しなければなりません。ボディーは、以下の表の要件をモデル化しなければなりません。

parallel_scan の Body の要件

擬似署名

意味

void Body::operator()( const Range& r, pre_scan_tag )

範囲 r のサマリーを累積します。

void Body::operator()( const Range& r, final_scan_tag )

範囲 r のスキャン結果とサマリーを計算します。

Body::Body( Body& b, split )

thisb のサマリーを別々に累積できるように b を分割します。

void Body::reverse_join( Body& b )

b によって累積されたサマリーを this によって累積されたサマリーにマージします。this は以前に分割コンストラクターによって b から作成されました。

void Body::assign( Body& b )

b のサマリーを this に代入します。

サマリーには、十分な情報が含まれているため、2 つの連続するサブ範囲 rs について、次のことが可能です。

例えば、配列の合計を計算する場合、範囲 r のサマリーは r に対応する配列要素の合計です。

関数形式 parallel_scan(range, identity, scan, combine) は、ファンクターおよびラムダ式と使用するように設計されており、命令形式ほど複雑ではありません。両方のパスで同じ scan ファンクターを使用し、Boolean パラメーターでパスを区別して、combine ファンクターでサマリーを結合し、range 全体で計算されたサマリーを返します。以下の表は、identityscan、および combine の型要件を要約したものです。

scan および combine の要件

擬似署名

意味

Value identity

Scan::operator() の左単位元。

Value Scan::operator()(const Range& r, const Value& sum, bool is_final) const

sum から開始して、サマリーと is_final == true の場合は範囲 r のスキャン結果を計算します。計算したサマリーを返します。

Value Combine::operator()(const Value& left, const Value& right) const

サマリー leftright を結合して結果を返します。

以下の図は、parallel_scan が整数 1 ~ 16 を含む配列の合計を計算する 1 つの方法を示しています。この図では、時間は下方向に経過します。色分けは、各 Body オブジェクトを示します。サマリーは角括弧で示されています。

  1. 最初の 2 つのステップは、オリジナルの青のボディーをピンクと黄色のボディーに分割します。各ボディーは入力配列の 1/4 を並列に処理します。最後の 1/4 はステップ 5 で処理されます。
  2. 青のボディーは、最後のスキャンと 1 ~ 4 のサマリーを計算します。ピンクと黄色のボディーは、それぞれ 5 ~ 8 と 9 ~ 12 のプリスキャンを行い、サマリーを計算します。
  3. ピンクのボディーは、青のボディーと reverse_join を行い、1 ~ 8 のサマリーを計算します。
  4. 黄色のボディーは、ピンクのボディーと reverse_join を行い、1 ~ 12 のサマリーを計算します。
  5. 青、ピンク、黄色のボディーは、最後のスキャンと配列のそれぞれの部分のサマリーを計算します。
  6. 黄色のサマリーが青のボディーに代入されます。ピンクと黄色のボディーは破棄されます。

配列の最初と最後の 1/4 はプリスキャンされていません。ワーカースレッドが少数の場合や余分なワーカースレッドがない場合、パフォーマンスを向上するため、parallel_scan テンプレートは、可能であればプリスキャンを回避しようとします。利用可能なワーカースレッドがない場合、parallel_scan は、最後のスキャンを使用してサブ範囲を左から右に処理することで、プリスキャンなしでサブ範囲を処理します。そのため、最後のスキャンは、サマリーと最後のスキャン結果を計算する必要があります。サマリーは、次のサブ範囲がワーカースレッドによってプリスキャンされていない場合に必要になります。

parallel_scan の実行例

サンプル (命令形式)

次のコードは、前述の × を使用したシーケンシャルの例と同じ結果を計算するため、parallel_scan に対する Body の実装方法を示します。

class Body {
    T sum;
    T* const y;
    const T* const z;
public:
    Body( T y_[], const T z_[] ) : sum(id×), z(z_), y(y_) {}
    T get_sum() const { return sum; }

    template<typename Tag>
    void operator()( const tbb::blocked_range<int>& r, Tag ) {
        T temp = sum;
        for( int i=r.begin(); i<r.end(); ++i ) {
            temp = temp × z[i];
            if( Tag::is_final_scan() )
                y[i] = temp;
        }
        sum = temp;
    }
    Body( Body& b, tbb::split ) : z(b.z), y(b.y), sum(id×) {}
    void reverse_join( Body& a ) { sum = a.sum × sum; }
    void assign( Body& b ) { sum = b.sum; }
};

T DoParallelScan( T y[], const T z[], int n ) {
    Body body(y,z);
    tbb::parallel_scan( tbb::blocked_range<int>(0,n), body );
    return body.get_sum();
}
    

operator() の定義は、parallel_scan を使用するときの典型的なパターンを説明します。

reverse_join 操作は、引数が逆であることを除けば、parallel_reduce によって使用される join 操作に似ています。つまり、this は × のの引数です。parallel_scan テンプレート関数は、並列のワークを生成するかどうか、そしていつ生成するかを決定します。したがって、× が結合操作で Body のメソッドがそれを正確に表現することは重要です。浮動小数点加算のような結合操作は、parallel_scan で使用される結合則に依存して結果が異なって丸められる場合があることを理解して使用する必要があります。再結合は、たとえ同じマシン上であっても実行ごとに異なることがあります。しかし、ワーカースレッドが利用可能でない場合、このセクションのはじめに示されているシリアル形式に関連付けられて実行されます。

simple_partitioner を使用するようにコードを変更した場合は、必ず粒度を指定してください。粒度は次のように指定します。ここでは、粒度を 1000 に指定しています。

parallel_scan(blocked_range<int>(0,n,1000), total, simple_partitioner() );
    

ラムダ式のサンプル

次のサンプルは、前述のサンプルに似ていますが、ラムダ式と parallel_scan の関数形式を使用して記述されています。

T DoParallelScan( T y[], const T z[], int n ) {
    return tbb::parallel_scan( 
        tbb::blocked_range<int>(0,n), 
        id×, 
        [](const tbb::blocked_range<int>& r, T sum, bool is_final_scan)->T {
            T temp = sum;
            for( int i=r.begin(); i<r.end(); ++i ) {
                temp = temp × z[i];
                if( is_final_scan )
                    y[i] = temp;
            }
            return temp;
        },
        []( T left, T right ) {
            return left × right;
        }
    );
}
    

関連情報