parallel_scan

[algorithms.parallel_scan]

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


// <oneapi/tbb/parallel_scan.h> ヘッダーで定義 

template<typename Range, typename Body> 
void parallel_scan( const Range& range, Body& body ); 
template<typename Range, typename Body> 
void parallel_scan( const Range& range, Body& body, /* see-below */ 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 ); 
template<typename Range, typename Value, typename Scan, typename Combine> 
Value parallel_scan( const Range& range, const Value& identity, const Scan& scan, const Combine& combine, /* see-below */ partitioner );

partitioner タイプは、次のいずれかのエンティティーになります:

  • const auto_partitioner&

  • const simple_partitioner&

要件:

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

並列プリフィクスの数学的な定義は以下のとおりです。× を左単位元が id× の結合操作であるとします。シーケンス z0, z1, ...*z*n-1 の × の並列プリフィックスはシーケンス y0, y1, y2, ...*y*n-1 です。 説明:

  • y0 = id× × z0

  • yi = yi-1 × zi

例えば、 x が加算である場合、並列プリフィクスが sum (累積) の実行に相当します。並列プリフィクスのシリアル実装は以下のようになります:


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) は、並列プレフィクスを汎用的に実装しています。

サマリー (ParallelScanBody の要件を参照) には十分な情報が含まれているため、2 つの連続するサブ範囲 r と s に対し次のことが可能です。

  • r の前にサブ範囲がない場合、s のスキャン結果は s と r のサマリーから計算できます。

  • s と連結された r のサマリーは、r と s のサマリーから計算できます。

関数 parallel_scan(range, identity, scan, combine) は関数とラムダ式が利用できるように設計されており、命令形式の複雑性を隠匿します。両方のパスで scan ファンクターを使用してブール・パラメーターによってそれらを区別し、サマリーを combine ファンクターと結合することで range 全体で計算されたサマリーを返します。identity 引数は Scan::operator() の左側の同一性要素です。

pre_scan と final_scan クラス

parallel_scan テンプレートは、可能であれば事前スキャンの回避を試みます。シリアルに実行される場合、parallel_scan はファイナルスキャンを使用してサブ範囲を左から右へ処理することで、事前スキャンなしでサブ範囲を処理します。そのためはファイナルスキャンでは、サマリーとファイナルスキャンの結果を計算する必要があります。他のスレッドが事前スキャンを行っていない場合、次の サブ範囲を処理するためサマリーが必要になることがあります。

例 (Imperative 形式)

次のコードは、Body を parallel_scan に実装して、前述のシリアルの例と同じ結果を計算する方法を示します。


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 oneapi::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, oneapi::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); 
    oneapi::tbb::parallel_scan( oneapi::tbb::blocked_range<int>(0,n), body ); 
    return body.get_sum(); 
}

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

  • 1 つのテンプレートで両方のバージョンを定義します。これは必須ではありませんが、2 つのバージョンは通常類似しているためコーディングの重複を省くことができ。ライブラリーは、バージョンを区別できるようにスタティック・メソッド is_final_scan を定義します。

  • 事前スキャンのバリアントは、× リダクションを計算しますが y を更新しません。プリスキャンは、先読みの部分削除を生成するため parallel_scan によって使用されます。

  • ファイナルスキャンのバリアントは × リダクションを計算して y を更新します。

reverse_join 操作は、引数が逆であることを除けば parallel_reduce の join 操作に似ています。this は × の right の引数になります。parallel_scan テンプレート関数は、並列ワークを生成するかどうか、そしていつ生成するかを決定します。したがって、× が結合操作で Body のメソッドがそれを正確に表現することが重要です。浮動小数点加算などある程度関連性がある操作は、parallel_scan で使用される関連性に応じて結果が異なって丸められる場合があることを理解する必要があります。たとえ同じマシン上であっても実行ごとに関連付けが異なることがあります。ただし、シリアル実行されると 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 oneapi::tbb::parallel_scan( 
        oneapi::tbb::blocked_range<int>(0,n), 
        id, 
        [](const oneapi::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; 
        } 
    ); 
}

参照: