parallel_deterministic_reduce

[algorithms.parallel_deterministic_reduce]

決定論的な分割/結合動作を使用して、範囲全体のリダクションを計算するテンプレート。

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

namespace oneapi { 
    namespace tbb { 

        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, /* see-below */ partitioner, task_group_context& context); 
        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, /* see-below */ partitioner); 
        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, task_group_context& context); 
        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); 

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

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

const simple_partitioner&
const static_partitioner&

関数テンプレート parallel_deterministic_reduce は、parallel_reduce テンプレートに似ています。また、関数および命令形式があり、同様の要件が求められます。

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

警告

simple_partitioner は自動的に範囲を粗くしないため、適切な粒度を指定する必要があります。詳細は、パーティショナーのセクションを参照してください。

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

その結果、parallel_deterministic_reduce は、範囲が分割できなくなるまで再帰的に範囲を分割し、サブ範囲ごとに (Body 分割コンストラクターを呼び出して) 新しいボディーを作成します。parallel_reduce と同様に、ボディー分割ごとにボディーから結果をマージするため join メソッドが呼び出されます。

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

複雑性

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

参照: