parallel_deterministic_reduce テンプレート関数

概要

決定性のある分割/結合動作を使用して、範囲のリダクションを計算します。

ヘッダー

#include "tbb/parallel_reduce.h"

構文

template<typename Range, typename Value, typename Func, typename Reduction>
Value parallel_deterministic_reduce( const Range& range, const Value& identity,
                                     const Func& func, const Reduction& reduction,
                                     [, partitioner [, task_group_context& group]] );

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

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

説明

parallel_deterministic_reduce テンプレートは、parallel_reduce テンプレートによく似ています。関数形式と命令形式があり、Func と Reduction の要件も似ています。

parallel_reduce とは異なり、parallel_deterministic_reduce は、Body と Range の分割動作およびボディーの結合動作に関して決定性があります。関数形式では、Func は決定性のある Range のセットに適用され、Reduction は決定性のある順序で部分的な結果のマージを行います。parallel_deterministic_reduce は、simple_partitioner または static_partitioner のみを使用します。ほかのパーティショナーはランダムなワークスチール動作に反応するためです。

注意

simple_partitioner は自動的に範囲を粗くしないため、適切な粒度を指定していることを確認してください。詳細は、「パーティショナー」セクションを参照してください。

parallel_deterministic_reduce は常に、各範囲分割に対して Body 分割コンストラクターを呼び出します。

blocked_range<int>(0,20,5) での parallel_deterministic_reduce の実行

その結果、parallel_deterministic_reduce は、範囲が分割できなくなるまで再帰的に範囲を分割し、各サブ範囲に対して (Body 分割コンストラクターを呼び出して) 新しいボディーを作成します。parallel_reduce と同様に、各ボディー分割に対してボディーから結果をマージするために join メソッドが呼び出されます。上記の図は、サンプル範囲での parallel_deterministic_reduce の実行を示しています。斜線 (/) は、どこでボディーの新しいインスタンスが作成されたかを示します。

指定された引数に対して、parallel_deterministic_reduce は、実行スレッド数やスレッドへのタスクの割り当て方法に関係なく、同じ分割および結合操作のセットを実行します。ユーザー定義関数に決定性がある場合 (つまり、同じ入力データで実行したときに毎回同じ結果が出力される場合)、parallel_deterministic_reduce の複数の呼び出しは同じ結果になります。ただし、等価なシーケンシャル・アルゴリズムの結果 k とは異なる場合があります。

計算量

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

サンプル

parallel_reduce の代わりに parallel_deterministic_reduce を使用するプログラムの変更は、いくつかのステップで行うことができます。最初に、関数名を変更します。次に、使用されるパーティショナーが parallel_deterministic_reduce でサポートされない場合はパーティショナーを変更します。最後に、パフォーマンスが低下した場合は、blocked_range の粒度を指定するか、調整する必要があります。

次の例は、「parallel_reduce テンプレート関数」セクションにあるサンプルを parallel_deterministic_reduce を使用するように変更したものです。

#include <numeric>
#include <functional>
#include "tbb/parallel_reduce.h"
#include "tbb/blocked_range.h"

float ParallelSum( float array[], size_t n ) {
    size_t grain_size = 1000;
    return tbb::parallel_deterministic_reduce(
        tbb::blocked_range<float*>( array, array+n, grain_size[ ),
        0.f,
        [](const tbb::blocked_range<float*>& r, float value)->float {
            return std::accumulate(r.begin(),r.end(),value);
        },
        std::plus<float>());
}

関連情報