並列アルゴリズム

並列パターン ライブラリ (PPL) は、データのコレクションに対して同時処理を実行するアルゴリズムを提供します。これらのアルゴリズムは、標準テンプレート ライブラリ (STL) で提供されるアルゴリズムと似ています。

並列アルゴリズムは、同時実行ランタイムの既存の機能から構成されます。たとえば、concurrency::parallel_for のアルゴリズムは、並列ループ反復を実行するために concurrency::structured_task_group のオブジェクトを使用します。parallel_for アルゴリズムは、使用できるコンピューティング リソース数に合わせて、最適な方法で作業を分割します。

セクション

• parallel_for アルゴリズム

• parallel_for_each アルゴリズム

• parallel_invoke アルゴリズム

• parallel_transform と parallel_reduce のアルゴリズム

  • parallel_transform のアルゴリズム

  • parallel_reduce のアルゴリズム

  • 例: マップ並列計算を実行

• 作業のパーティション分割

• 並列並べ替え

  • 並べ替えアルゴリズムの選択

parallel_for アルゴリズム

concurrency::parallel_for のアルゴリズムは、繰り返し同じタスクを並列に実行します。これらの各タスクは、反復値によってパラメーター化されます。このアルゴリズムは、ループのイテレーション間でリソースを共有しないループ ボディがある場合に有用です。

parallel_for アルゴリズムは、並列実行に最適となるようにタスクを分割します。これは、作業負荷のバランスが崩れたときにこれらのパーティションを分散させるために盗むワーク スティーリング アルゴリズムと範囲を使用します。1 つのループ反復が協調的にブロックした場合、ランタイムは現在のスレッドに割り当てられている反復範囲を他のスレッドまたはプロセッサに再分配します。同様に、スレッドが反復範囲を完了したとき、ランタイムは他のスレッドでの処理を該当スレッドに再分配します。parallel_for アルゴリズムでは、入れ子になった並列化もサポートされています。1 つの並列ループに別の並列ループが含まれている場合、ランタイムはループ本体間で処理リソースを調整し、並列実行が効率的に行われるようにします。

parallel_for のアルゴリズムに複数のオーバーロードされたバージョンがあります。1 つ目のバージョンは、開始値、終了値、および処理関数 (ラムダ式、関数オブジェクト、または関数ポインター) を受け取ります。2 つ目のバージョンは、開始値、終了値、およびステップ値、および処理関数を受け取ります。この関数の 1 つ目のバージョンは、ステップ値として 1 を使用します。残りのバージョンは parallel_for がスレッド間の範囲をどのように分割するかを指定できるようにするパーティショナーのオブジェクトを受け取ります。パーティショナーは、このドキュメントの 作業のパーティション分割 セクションで詳しく説明します。

複数の for ループを変換して parallel_for を使用できます。ただし、parallel_for アルゴリズムには、次のような for ステートメントとの相違があります。

• parallel_for アルゴリズムでは、タスクはあらかじめ決められた順序では実行されません。

• parallel_for アルゴリズムでは、任意の終了条件がサポートされません。parallel_for アルゴリズムは、反復変数の現在の値が _Last より 1 小さい値になると停止します。

• _Index_type 型パラメーターは、整数型である必要があります。この整数型は符号付きでも符号なしでもかまいません。

• ループ イテレーションは、順方向である必要があります。_Step パラメーターが 1 未満の場合、parallel_for アルゴリズムは、std::invalid_argument 型の例外をスローします。

• parallel_for アルゴリズムの例外処理機構は、for ループの例外処理機構とは異なります。並列ループの本体で複数の例外が同時に発生した場合、ランタイムはそのいずれか 1 つだけを parallel_for の呼び出し元スレッドに反映します。また、1 つのループ反復が例外をスローした場合、ランタイムはループ全体を即座に停止することはありません。代わりに、ループは取り消し済み状態になり、ランタイムはまだ開始されていないタスクをすべて破棄します。例外処理と並列アルゴリズムの詳細については、「同時実行ランタイムでの例外処理」を参照してください。

parallel_for アルゴリズムは任意の終了条件をサポートしていませんが、キャンセル処理を使用してすべてのタスクを中止できます。キャンセル処理の詳細については、「PPL における取り消し処理」を参照してください。

[!メモ]

ループ本体の並列実行のメリットの方が、キャンセル処理などの機能や負荷分散のサポートによって生じるスケジューリング コストよりも重視されることがあります (特に、ループ本体が比較的小さい場合など)。並列ループで独自のパーティショナーを使用してこのオーバーヘッドを最小限に抑えることができます。詳細については、このドキュメントの 作業のパーティション分割 を参照してください。

例

次の例では、parallel_for アルゴリズムの基本的な構造を示します。この例では、範囲 [1, 5] の各値を並列にコンソールに出力します。

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

この例では、次のサンプル出力が生成されます。

parallel_for アルゴリズムは各項目に並列に作用するため、値がコンソールに出力される順序は変わります。

parallel_for アルゴリズムの完全な使用例については、「方法: parallel_for ループを記述する」を参照してください。

[Top]

parallel_for_each アルゴリズム

concurrency::parallel_for_each のアルゴリズムは STL によって提供された反復コンテナーなどのタスクを並列に実行します。このアルゴリズムでは、parallel_for アルゴリズムで使用されるのと同じ分割ロジックが使用されます。

parallel_for_each アルゴリズムは STL std::for_each アルゴリズムと似ていますが、parallel_for_each アルゴリズムではタスクが同時に実行される点が異なります。他の並列アルゴリズムと同様、parallel_for_each では、タスクは特定の順序で実行されません。

parallel_for_each アルゴリズムは前方反復子とランダム アクセス反復子の両方に対して作用しますが、ランダム アクセス反復子を使用した場合の方が良いパフォーマンスが得られます。

例

次の例では、parallel_for_each アルゴリズムの基本的な構造を示します。この例では、std::array オブジェクトの各値を並列にコンソールに出力します。

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(begin(values), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

この例では、次のサンプル出力が生成されます。

parallel_for_each アルゴリズムは各項目に並列に作用するため、値がコンソールに出力される順序は変わります。

parallel_for_each アルゴリズムの完全な使用例については、「方法: parallel_for_each ループを記述する」を参照してください。

[Top]

parallel_invoke アルゴリズム

concurrency::parallel_invoke のアルゴリズムは、一連のタスクを並列に実行します。それぞれのタスクが終了するまで、制御は返されません。このアルゴリズムは、同時に実行する独立したタスクが複数ある場合に便利です。

parallel_invoke アルゴリズムは、パラメーターとして一連の処理関数 (ラムダ関数、関数オブジェクト、または関数ポインター) を受け取ります。parallel_invoke アルゴリズムは、オーバーロードされた場合、2 ～ 10 個のパラメーターを受け取ります。parallel_invoke に渡すすべての関数が、パラメーターを受け取らないようにしてください。

他の並列アルゴリズムと同様、parallel_invoke では、タスクは特定の順序で実行されません。parallel_invoke アルゴリズムとタスクおよびタスク グループの関連性については、「タスクの並列化 (同時実行ランタイム)」を参照してください。

例

次の例では、parallel_invoke アルゴリズムの基本的な構造を示します。この例では、3 つのローカル変数で twice 関数を同時に呼び出し、結果をコンソールに出力します。

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

この例を実行すると、次の出力が生成されます。

parallel_invoke アルゴリズムの完全な使用例については、「方法: 並列呼び出しを使用して並列並べ替えルーチンを記述する」および「方法: 並列呼び出しを使用して並列操作を実行する」を参照してください。

[Top]

parallel_transform と parallel_reduce のアルゴリズム

concurrency::parallel_transform と concurrency::parallel_reduce のアルゴリズムは STL アルゴリズム std::transform と std::accumulate、それぞれの並列バージョンです。同時実行ランタイム バージョンは、STL のバージョンのと同様ですが、それらが並列実行されるため、命令を判断する方法ではありません。並列処理のパフォーマンスとスケーラビリティを向上させるのに十分な大きさのセットを使用するときのアルゴリズムを使用します。

重要
parallel_transform と parallel_reduce のアルゴリズムはこれらの反復子が安定したメモリ アドレスが生成されるため、双方向のランダム アクセス、および前方反復子のみサポートされます。また、これらの反復子はconst の非左辺値を作り出さなければ必要があります。

parallel_transform のアルゴリズム

多くのデータの並列化の操作を実行するには parallel transform のアルゴリズムを使用できます。たとえば、次のように操作できます。

• イメージの輝度を調整し、操作を処理するそのほかのイメージを実行します。

• 合計するか、ドット積を 2 二つのベクターの間で受け取り、ベクター内の他の数値の計算を実行します。

• 各イテレーションを表示する 1 ピクセルを示す 3-D 射線のトレースを実行します。

次の例では parallel_transform のアルゴリズムの呼び出しに使用される基本的な構造を示します。この例は、2 種類の方法で std::vector のオブジェクトの各要素を拒否します。最初の方法では、ラムダ式を使用します。std::unary_functionから派生する 2 番目の方法は std::negateを使用します。

// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a large vector that contains random integer data.
    vector<int> values(1250000);
    generate(begin(values), end(values), mt19937(42));

    // Create a vector to hold the results.
    // Depending on your requirements, you can also transform the 
    // vector in-place.
    vector<int> results(values.size());

    // Negate each element in parallel.
    parallel_transform(begin(values), end(values), begin(results), [](int n) {
        return -n;
    });

    // Alternatively, use the negate class to perform the operation.
    parallel_transform(begin(values), end(values), begin(values), negate<int>());
}

注意
この例では parallel_transformの基本的な使用例を次に示します。処理関数は、大量の作業を実行しないため、この例のパフォーマンスに増えている場合、処理は行われません。

parallel_transform のアルゴリズムに 2 二つのオーバーロードがあります。最初のオーバーロードは 1 個の入力範囲と単項演算子関数を受け取ります。単項演算子関数は 1 個の引数、関数オブジェクト、または unary_functionから派生する型を受け取るラムダ式を指定できます。2 番目のオーバーロードは 2 個の入力範囲とバイナリの関数を受け取ります。バイナリ関数は 2 個の引数、関数オブジェクト、または std::binary_functionから派生する型を受け取るラムダ式を指定できます。次の例は、こうした違いを示しています。

//
// Demonstrate use of parallel_transform together with a unary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), 
    begin(results), [](int n) { 
        return -n;
    });

// Alternatively, use the negate class:
parallel_transform(begin(values), end(values), 
    begin(results), negate<int>());

//
// Demonstrate use of parallel_transform together with a binary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), [](int n, int m) {
        return n * m;
    });

// Alternatively, use the multiplies class:
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), multiplies<int>());

重要
、parallel_transform の出力に指定する反復子は完全に入力反復子と重複するか、まったく重複する必要があります。このアルゴリズムの動作は、入力および出力反復子が部分的に重複する未指定です。

parallel_reduce のアルゴリズム

parallel_reduce のアルゴリズムであってもプロパティを満たす一連の操作がある場合に便利です。(このアルゴリズムは、可換性のプロパティはありません)。、parallel_reduceで実行できる操作を次に示します。:

• 行列を作成するために、行列のシーケンスをインクリメントします。

• ベクターを作成するために、行列のシーケンスによってベクターをインクリメントします。

• 文字列のシーケンスの長さを計算します。

• 1 個の要素に要素の一覧が、文字列、まとめてします。

次の基本的な例では、1 文字列に文字列のシーケンスを parallel_reduce にまとめるためのアルゴリズムを使用する方法を示します。parallel_transformの例と同様に、パフォーマンス上の違いはこの基本的な例で処理は行われません。

// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string> 
#include <vector>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a vector of strings.
    vector<wstring> words;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(L"elit.");

    // Reduce the vector to one string in parallel.
    wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

多くの場合、concurrency::combinable のクラスとともに parallel_for_each アルゴリズムの使用の表現として parallel_reduce と考えることができます。

例: マップ並列計算を実行

マップの 操作では、シーケンスの各値に関数を適用します。リダクション演算は、1 の値は、シーケンスの要素をパッケージ化します。マップを実行し、操作を軽減するためのテンプレート ライブラリの (STL) 標準 std::transformstd::accumulate のクラスを使用できます。ただし、多くの問題のために、マップ操作を並列実行するために、parallel_transform アルゴリズムを使用して、parallel_reduce のアルゴリズムは減少の操作を並列実行します。

次の例では、素数の合計を逐次的および並列計算するためにかかる時間を比較します。0 にマップ フェーズの変換の非主な値とデクリメントのフェーズでは、値の合計を入力します。

// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

// Determines whether the input value is prime.
bool is_prime(int n)
{
   if (n < 2)
      return false;
   for (int i = 2; i < n; ++i)
   {
      if ((n % i) == 0)
         return false;
   }
   return true;
}

int wmain()
{   
   // Create an array object that contains 200000 integers.
   array<int, 200000> a;

   // Initialize the array such that a[i] == i.
   iota(begin(a), end(a), 0);

   int prime_sum;
   __int64 elapsed;

   // Compute the sum of the numbers in the array that are prime.
   elapsed = time_call([&] {
       transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = accumulate(begin(a), end(a), 0);
   });   
   wcout << prime_sum << endl;   
   wcout << L"serial time: " << elapsed << L" ms" << endl << endl;

   // Now perform the same task in parallel.
   elapsed = time_call([&] {
      parallel_transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = parallel_reduce(begin(a), end(a), 0);
   });
   wcout << prime_sum << endl;
   wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
   1709600813
   serial time: 7406 ms

   1709600813
   parallel time: 1969 ms
*/

マップを実行し、操作を並列に減らす別の例については、方法: マップ操作と縮小操作を並列実行するを参照してください。

[Top]

作業のパーティション分割

データ ソースの操作を並列化するには、必要な手順は、複数のスレッドから同時にアクセスできる複数のセクションにソースをパーティション分割する こと です。パーティショナーは並列アルゴリズムがスレッド間の範囲をどのように分割するかを指定します。このドキュメントで説明するように、PPL では、作業負荷のバランスが崩れたときに最初の作業負荷を作成し、これらのパーティションを分散させるために盗むワーク スティーリング アルゴリズムと範囲を使用して、既定のパーティション分割の機構を使用します。たとえば、1 種類のループ反復が反復範囲を完了すると、ランタイムは他のスレッドからそのスレッドに再分配します。ただし、ある場合に、問題に適したパーティション分割機構を指定する必要があります。

parallel_for、parallel_for_eachと parallel_transform のアルゴリズムは追加のパラメーターを受け取るオーバーロードされたバージョン、_Partitionerを提供します。このパラメーターは、作業をパーティション分割の種類を定義します。PPL で定義されているパーティショナーを次に示します。:

• concurrency::affinity_partitioner
  範囲 (通常はループの動作に使用できる) のワーカー スレッドの数への分割の作業数。このパーティショナーの型は static_partitionerに似ていますが、キャッシュのアフィニティが向上します。ここでワーカー スレッドに範囲をマップします。このパーティショナーの型はループが同じデータセットに複数回 (ループ内のループなど)、およびキャッシュのデータの最適に実行するとパフォーマンスが向上します。このパーティショナーはキャンセルに完全に含められません。これは、協調ブロック セマンティクスを使用せず、前方依存関係が並列ループでは使用できません。

• concurrency::auto_partitioner
  は、範囲 (通常はループの動作に使用できる) ワーカー スレッドの数の元の値に動作します。ランタイムは _Partitioner のパラメーターを使用するオーバーロードされた並列アルゴリズムを呼び出さない場合、この型が既定で使用されます。各スコープはサブ範囲に分割してそれにより実行するように負荷を分散できます。作業スコープが完了すると、ランタイムは他のスレッドからそのスレッドに処理のサブ範囲を再配分します。自分の作業負荷が他のカテゴリの 1 個下らないか、キャンセルまたは協調ブロックに対して完全にサポートが必要な場合はこのパーティショナーを使用します。

• concurrency::simple_partitioner
  分割がスコープ内に各スコープにイテレーションの少なくとも一部のチャンクのサイズで指定された数を持つようにを設定します。このパーティショナーの型は負荷分散に参加します; ただし、ランタイムはサブ範囲に範囲を分割します。各ワーカー スレッドの場合、ランタイムは、取り消し状態をチェックし、完全な _Chunk_size のイテレーション後で負荷分散を実行します。

• concurrency::static_partitioner
  範囲 (通常はループの動作に使用できる) のワーカー スレッドの数への分割の作業数。このパーティショナーの型は、ワーク スティーリングを使用しないパフォーマンスが向上し、オーバーヘッドがためです。並列ループの各反復でアンカーと同じ処理を実行し、取り消し処理のサポートを必要とせず、協調的にブロックが転送されたときにこのパーティショナーの型を使用します。

注意
parallel_for_each と parallel_transform のアルゴリズムは静的なに対してランダム アクセス反復子 (std::vectorなどの単純な)、およびアフィニティのパーティショナーだけをサポートするコンテナー。双方向と順方向の反復子を使用するコンテナーの使用は、コンパイル時エラーが生成されます。既定のパーティショナー auto_partitionerのサポート、これらの反復子の種類の 3。

通常、これらのパーティショナーは affinity_partitionerを除き、同じように使用されます。ほとんどのパーティショナーの型に状態を保持せずに、実行時には変更されません。このため、次の例に示すように、呼び出しサイトでこれらのパーティショナーのオブジェクトを作成できます。

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>

using namespace concurrency;

void DoWork(int n)
{
    // TODO: Perform a fixed amount of work...
}

int wmain()
{
    // Use a static partitioner to perform a fixed amount of parallel work.
    parallel_for(0, 100000, [](int n) {
        DoWork(n);
    }, static_partitioner());
}

ただし、アルゴリズムで再利用するには、その後のループの状態を格納できるように、非constには左辺値 affinity_partitioner のオブジェクトの参照を渡す必要があります。次の例では、データ セットの複数回の同じ操作を並列に実行する基本的なアプリケーションを示しています。affinity_partitioner の使用は、配列がキャッシュに格納する可能性があるためパフォーマンスが向上します。

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;

int wmain()
{    
    // Create an arry and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    //
    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {        
        parallel_for_each(begin(data), end(data), [](unsigned char& c) {
            c++;
        }, ap);
    }
}

注意
static_partitioner か affinity_partitionerを使用する協調的にブロック セマンティクスに依存する既存のコードを変更する場合は注意してください。これらのパーティショナーの型は負荷分散を使用し、&、およびことがありますが、アプリケーションの動作を変更する盗みます。

判断する最適な方法は、特定のシナリオで使用するパーティショナーを試し、典型的な負荷およびコンピューター構成では、操作が完了するまでどの程度時間を計測する時間計測することです。たとえば、静的パーティション分割は、少数のコアしか持たないマルチコア コンピューターでは速度が飛躍的に向上することがありますが、比較的多くのコアを持つコンピューターでは速度が低下することがあります。

[Top]

並列並べ替え

PPL では、3 種類の並べ替えアルゴリズムを指定します: concurrency::parallel_sort、concurrency::parallel_buffered_sortと concurrency::parallel_radixsort。これらの並べ替えアルゴリズムは、並列並べ替えの利点を活用できるデータ セットがある場合に便利です。特に、並列並べ替えでは大きなデータセットがある、またはユーザーのデータを並べ替えるために計算の使用時に操作を比較する場合に便利です。これらのアルゴリズムの配置内の各要素。

parallel_sort と parallel_buffered_sort のアルゴリズムは比較型の両方のアルゴリズムです。つまり、値によって要素を比較します。parallel_sort のアルゴリズムに別のメモリ要件がなく、汎用の並べ替えに適しています。parallel_buffered_sort のアルゴリズムは parallel_sortより適切に実行できますが、O(N) の領域が必要です。

parallel_radixsort のは、ハッシュ アルゴリズムから始まります。つまり、要素の並べ替えに整数のキーを使用します。キーを使用して、このアルゴリズムは、比較を使用する代わりに直接コピー先の要素を計算できます。parallel_buffered_sortのように、このアルゴリズムは O(N) の領域が必要です。

次の表は、3 種類の並列並べ替えアルゴリズムの重要なプロパティの概要を示します。

アルゴリズム	説明	並べ替えの機構	並べ替えの安定性	メモリ要件	時間の複雑さ	反復子のアクセス
parallel_sort	汎用的な比較型の並べ替え。	比較型 (昇順)	不安定	なし	O((N/P)log(N/P) + 2N((P-1)/P))	ランダム
parallel_buffered_sort	O を必要とするより高速な汎用的な比較型の並べ替え (N) 空間。	比較型 (昇順)	不安定	O(N) の領域が必要です	O((N/P)log(N))	ランダム
parallel_radixsort	O を要求する整数キーに基づく並べ替え (N) 空間。	ハッシュ ベース	安定	O(N) の領域が必要です	O(N/P)	ランダム

次の図は、3 種類の並列並べ替えアルゴリズムの重要なプロパティがグラフィカルに示します。

これらの並列並べ替えアルゴリズムでは、キャンセル処理と例外処理の規則に従います。キャンセル処理の詳細と同時実行ランタイムの例外処理では、並列アルゴリズムの取り消し と 同時実行ランタイムでの例外処理を参照してください。

ヒント
これらの並列並べ替えアルゴリズムのサポートの移動セマンティクス。より効率的に発生することをスワップ操作が可能にするように移動の代入演算子を定義できます。移動セマンティクスおよび移動の代入演算子に関する詳細については、右辺値参照宣言子: &&と 方法: 移動コンストラクターを作成しますを参照してください。移動の代入演算子または swap 関数を提供する、並べ替えアルゴリズムはコピー コンストラクターを使用します。

次の基本的な例に int の値の vector の並べ替えに parallel_sort を使用する方法を示します。既定では、parallel_sort は値の比較に std::less を使用します。

// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create and sort a large vector of random values.
    vector<int> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values));

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
} 
/* Output:
   V(0)        = -2147483129
   V(12500000) = -427327
   V(24999999) = 2147483311
*/

この例では、カスタムを提供する方法の比較関数を示します。これは、昇順の std::complex<double> の値を並べ替えるために std::complex::real のメソッドを使用します。

// For this example, ensure that you add the following #include directive:
// #include <complex>

// Create and sort a large vector of random values.
vector<complex<double>> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values),
    [](const complex<double>& left, const complex<double>& right) {
        return left.real() < right.real();
    });

// Print a few values.
wcout << "V(0)        = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
/* Output:
   V(0)        = (383,0)
   V(12500000) = (2.1479e+009,0)
   V(24999999) = (4.29497e+009,0)
*/

この例で parallel_radixsort のアルゴリズムにハッシュ関数を提供する方法を示します。この例では、3-D ポイントを分類しています。点が参照ポイントからの距離に基づいて並べ替えられます。

// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Defines a 3-D point.
struct Point
{
    int X;
    int Y;
    int Z;
};

// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
    int dx = p1.X - p2.X;
    int dy = p1.Y - p2.Y;
    int dz = p1.Z - p2.Z;
    return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}

int wmain()
{
    // The central point of reference.
    const Point center = { 3, 2, 7 };

    // Create a few random Point values.
    vector<Point> values(7);
    mt19937 random(42);
    generate(begin(values), end(values), [&random] {
        Point p = { random()%10, random()%10, random()%10 };
        return p;
    });

    // Print the values before sorting them.
    wcout << "Before sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;

    // Sort the values based on their distances from the reference point.
    parallel_radixsort(begin(values), end(values), 
        [center](const Point& p) -> size_t {
            return euclidean_distance(p, center);
        });

    // Print the values after sorting them.
    wcout << "After sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;
} 
/* Output:
    Before sorting:
    (2,7,6) D = 5
    (4,6,5) D = 4
    (0,4,0) D = 7
    (3,8,4) D = 6
    (0,4,1) D = 7
    (2,5,5) D = 3
    (7,6,9) D = 6

    After sorting:
    (2,5,5) D = 3
    (4,6,5) D = 4
    (2,7,6) D = 5
    (3,8,4) D = 6
    (7,6,9) D = 6
    (0,4,0) D = 7
    (0,4,1) D = 7
*/

図のために、この例は比較的小さいデータセットを使用します。大きなデータ セットのパフォーマンスの向上を試すにベクター内の最初のサイズを増やすことができます。

この例では、ハッシュ関数としてラムダ式を使用します。また std::hash のクラスの組み込み実装の 1 つを使用するか、独自の特殊化を定義できます。また、この例に示すように、カスタム ハッシュ関数オブジェクトを使用できます:

// Functor class for computing the distance between points.
class hash_distance
{
public:
    hash_distance(const Point& reference)
        : m_reference(reference)
    {
    }

    size_t operator()(const Point& pt) const {
        return euclidean_distance(pt, m_reference);
    }

private:
    Point m_reference;
};

// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));

ハッシュ関数は整数型を返す必要があります (std::is_integral::value は trueである必要があります)。この整数型は size_tを型に変換できる必要があります。

並べ替えアルゴリズムの選択

多くの場合、parallel_sort は、速度とメモリの最適なパフォーマンスのバランスを提供します。ただし、使用できるプロセッサのデータ セット、数値、またはの複雑さのサイズを大きくする関数 parallel_buffered_sort、または parallel_radixsort に実行できます。比較します。並べ替えアルゴリズム、特定のシナリオで使用すると、試し、典型的なコンピューター構成では、通常のデータを並べ替えるためにかかる時間を測定するかを判断する最適な方法。並べ替え方法を選択するときは、次のガイドラインを考慮してください。

• データ セットのサイズ。このドキュメントでは、小さい データセットは 1,000 以下の要素が含まれますが、中程度の データセットは 10,000 と 100,000 の要素の間であり、大きなデータセットは 100,000 以上の要素が含まれます。

• 独自の関数やハッシュ関数を比較する作業量はです。

• コンピューティング リソースが使用できるメモリ量。

• データ セット特性。たとえば、1 台のアルゴリズムは既に並べ替えられたが、ほぼ完全に、パンであるデータに対して可能性があるデータに対して同様に機能する。

• チャンクのサイズ。_Chunk_size の省略可能な引数は、作業の小さな単位に全体的な並べ替えを分割するようにアルゴリズムを並列実行から並べ替えの実装に切り替えるかを指定します。たとえば、512 を指定した場合、アルゴリズムは、実装に作業の単位が 512 を含む以下の要素と切り替えます。連続実装は、データを並列処理するために必要なオーバーヘッドを回避するため、全体のパフォーマンスが向上します。

リソースを計算する複数の使用できる場合は、その関数またはハッシュ関数を比較するのは比較的高いの処理を実行する場合でも小さいデータセットを並列並べ替えは値がない場合があります。小さいデータセットの並べ替えに std::sort 関数を使用できます。より大きなチャンクのサイズを指定した場合parallel_sort と parallel_buffered_sort は sort を呼び出してデータセット; ただし、parallel_buffered_sort はロックの競合やメモリ割り当てによって余分な時間がかかる場合がある O(N) の領域を割り当てる必要があります)。

メモリを節約する必要がある場合、または、メモリ アロケーターがロックの競合に応じて場合は、中のデータセットの並べ替えに parallel_sort を使用します。parallel_sort は追加の空間は必要ではありません; 他のアルゴリズムは O(N) の領域が必要です。

アプリケーションが追加 O(N) の空き容量を満たす場合、中程度のデータセットの並べ替えに parallel_buffered_sort を使用します。parallel_buffered_sort は、関数またはハッシュ関数を比較する複数のコンピューティング リソースまたは低いのが存在する場合に特に便利です。

アプリケーションが追加 O(N) の空き容量を満たす場合に大きなデータセットの並べ替えに parallel_radixsort を使用します。parallel_radixsort は同等の操作で高い比較するか、または操作の両方が高い場合に特に便利です。

注意
適切なハッシュ関数を実行すると、データセットの範囲を理解するうえでのデータセットの各要素が対応する符号なしの値に変換する必要があります。ハッシュ演算で符号なしの値で動作するため、符号なしのハッシュ値が生成する場合は、別の並べ替え方法を検討してください。

次の例ではランダム データの大きな同じセットに対する sort、parallel_sort、parallel_buffered_sortと parallel_radixsort のパフォーマンスを比較します。

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.h>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

const size_t DATASET_SIZE = 10000000;

// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
    vector<size_t> data(DATASET_SIZE);
    generate(begin(data), end(data), mt19937(42));
    return data;
}

int wmain()
{
    // Use std::sort to sort the data.
    auto data = GetData();
    wcout << L"Testing std::sort...";
    auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_sort...";
    elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_buffered_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_buffered_sort...";
    elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_radixsort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_radixsort...";
    elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):
    Testing std::sort... took 2906 ms.
    Testing concurrency::parallel_sort... took 2234 ms.
    Testing concurrency::parallel_buffered_sort... took 1782 ms.
    Testing concurrency::parallel_radixsort... took 907 ms.
*/

並べ替えの実行中に O(N) の領域を割り当てることで、許容できると想定するこの例では、parallel_radixsort は、このコンピューターの構成にこのデータセットのベストを実行します。

[Top]

関連トピック

Title	説明
方法: parallel_for ループを記述する	parallel_for アルゴリズムを使用して行列の乗算を行う方法について説明します。
方法: parallel_for_each ループを記述する	parallel_for_each アルゴリズムを使用して、std::array オブジェクトの素数の数を並列に計算する方法について説明します。
方法: 並列呼び出しを使用して並列並べ替えルーチンを記述する	parallel_invoke アルゴリズムを使用して、バイトニック ソート アルゴリズムのパフォーマンスを向上させる方法について説明します。
方法: 並列呼び出しを使用して並列操作を実行する	parallel_invoke アルゴリズムを使用して、共有データ ソースに対して複数の操作を実行するプログラムのパフォーマンスを向上させる方法について説明します。
方法: マップ操作と縮小操作を並列実行する	parallel_transform と parallel_reduce アルゴリズムをマップを実行してファイルの単語の生成をカウントする操作を軽減する方法を示します。
並列パターン ライブラリ (PPL)	同時実行アプリケーションの開発を支援する、スケーラビリティが高く使いやすいプログラミング モデルである PPL について説明します。
PPL における取り消し処理	PPL でのキャンセル処理の役割、並列処理を取り消す方法、およびタスク グループのキャンセルを判定する方法について説明します。
同時実行ランタイムでの例外処理	同時実行ランタイムでの例外処理の役割について説明します。

Reference

parallel_for 関数

parallel_for_each 関数

parallel_invoke 関数

affinity_partitioner クラス

auto_partitioner クラス

simple_partitioner クラス

static_partitioner クラス

parallel_sort 関数

parallel_buffered_sort 関数

parallel_radixsort 関数