parallel_reduce

[algorithms.parallel_reduce]

範囲全体のリダクションを計算する関数テンプレート。

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

namespace oneapi { 
    namespace tbb { 

        template<typename Range, typename Value, typename Func, typename Reduction> 
        Value parallel_reduce(const Range& range, const Value& identity, const Func& func, const Reduction& reduction, /* see-below */ partitioner, task_group_context& context); 
        template<typename Range, typename Value, typename Func, typename Reduction> 
        Value parallel_reduce(const Range& range, const Value& identity, const Func& func, const Reduction& reduction, /* see-below */ partitioner); 
        template<typename Range, typename Value, typename Func, typename Reduction> 
        Value parallel_reduce(const Range& range, const Value& identity, const Func& func, const Reduction& reduction, task_group_context& context); 
        template<typename Range, typename Value, typename Func, typename Reduction> 
        Value parallel_reduce(const Range& range, const Value& identity, const Func& func, const Reduction& reduction); 

        template<typename Range, typename Body> 
        void parallel_reduce(const Range& range, Body& body, /* see-below */ partitioner, task_group_context& context); 
        template<typename Range, typename Body> 
        void parallel_reduce(const Range& range, Body& body, /* see-below */ partitioner); 
        template<typename Range, typename Body> 
        void parallel_reduce(const Range& range, Body& body, task_group_context& context); 
        template<typename Range, typename Body> 
        void parallel_reduce(const Range& range, Body& body); 
    } // namespace tbb 
} // namespace oneapi

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

• const auto_partitioner&

• const simple_partitioner&

• const static_partitioner&

• affinity_partitioner&

要件:

• Range タイプは、Range 要件を満たしている必要があります。

• Body タイプは、ParallelReduceBody 要件を満たしている必要があります。

• Func タイプは、ParallelReduceFunc 要件を満たしている必要があります。

• Reduction タイプは、ParallelReduceReduction 要件を満たしている必要があります。

関数テンプレート parallel_reduce には次の 2 つの形式があります: 関数は簡単にラムダ式と組み合わせて使用できるように設計されています。命令はデータのコピーを最小限に抑えるように設計されています。

関数 parallel_reduce(range, identity, func, reduction) は、range 内のサブ範囲に func を適用し、2 項演算子 reduction を使用して結果をリデュースすることで並列リダクションを行います。リダクションの結果を返します。identity パラメーターは、func の operator() の左側の同一性要素を指定します。func と reduction パラメーターにはラムダ式を指定することができます。

命令形式 parallel_reduce(range,body) は、range の各値に対して body の並列リダクションを実行します。

parallel_reduceは、is_divisible() が各サブ範囲で false になるポイントまで、範囲をサブ範囲に再帰的に分割します。parallel_reduce は分割コンストラクターを使用して、各スレッドのボディーの 1 つ以上のコピーを作成します。ボディーの operator() または join メソッドが同時に実行されているとボディーをコピーすることがあります。プログラマーは、この並行処理の安全性を保証する責任を負います。通常の使用方法では、安全性に特別な労力を費やす必要ありません。

parallel_reduce はボディーの分割コンストラクターを呼び出すことがあります。そのようなボディーの分割ごとに、ボディーからの結果をマージするために join メソッドを呼び出します。this と rhs の累積された結果を表すように join を定義します。リダクション操作は結合でなければなりませんが、可換的である必要はありません。非可換演算 op では、left.join(right) は left を left op right の結果になるように更新します。

ボディーは、範囲が分割される場合にのみ分割されますが、その逆は必ずしもそうではありません。プログラマーは、ボディー分割の際に特定のサブ範囲が選択されることや、ボディー・オブジェクトによって処理されるサブ範囲が連続していることを想定してはなりません。parallel_reduce は非決定論的にボディーを分割します。

シリアルに実行される場合、parallel_reduce は parallel_for と同様の解釈で左から右へ順番に実行されます。シーケンシャル実行では、分割コンストラクターや join メソッドは呼び出されません。

すべてのオーバーロードは task_group_context オブジェクトを受け入れることが可能であるため、アルゴリズムのタスクはこのコンテキストで実行されます。デフォルトでは、アルゴリズムは自身がバインドされているコンテキストで実行されます。

複雑性

範囲とボディーが O(1) 空間を使用して範囲をほぼ等しい断片に分割する場合、空間計算量は O(P log(N)) です。ここで、N は範囲のサイズ、P はスレッド数です。

#include 
"oneapi/tbb/parallel_reduce.h" 
#include "oneapi/tbb/blocked_range.h" 

using namespace oneapi::tbb;
 
struct Sum { 
    float value; 
    Sum() : value(0) {} 
    Sum( Sum& s, split ) {value = 0;} 
    void operator()( const blocked_range<float*>& r ) { 
        float temp = value; 
        for( float* a=r.begin(); a!=r.end(); ++a ) { 
            temp += *a; 
        } 
        value = temp; 
    } 
    void join( Sum& rhs ) {value += rhs.value;} 
}; 

float ParallelSum( float array[], size_t n ) { 
    Sum total; 
    parallel_reduce( blocked_range<float*>( array, array+n ), total ); 
    return total.value; 
}

#include 
"oneapi/tbb/parallel_reduce.h" 
#include "oneapi/tbb/blocked_range.h" 

using namespace oneapi::tbb; 

float ParallelSum( float array[], size_t n ) { 
    return parallel_reduce( 
        blocked_range<float*>( array, array+n ), 
        0.f, 
        [](const blocked_range<float*>& r, float init)->float { 
            for( float* a=r.begin(); a!=r.end(); ++a ) 
                init += *a; 
            return init; 
        }, []( float x, float y )->float { 
            return x+y; 
        } 
    ); 
}