並列アルゴリズム

並列パターン ライブラリ (PPL) には、データのコレクションに対して作業を同時に実行するアルゴリズムがあります。 これらのアルゴリズムは、C++ 標準ライブラリによって提供されるアルゴリズムに似ています。

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

セクション

• parallel_for アルゴリズム

• parallel_for_each アルゴリズム

• parallel_invoke アルゴリズム

• parallel_transformアルゴリズムとparallel_reduce アルゴリズム

  • parallel_transform アルゴリズム

  • parallel_reduce アルゴリズム

  • 例: マップと Reduce を並列で実行する

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

• 並列並べ替え

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

parallel_for アルゴリズム

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

この parallel_for アルゴリズムは、並列実行に最適な方法でタスクをパーティション分割します。 これは、ワークロードが不均衡な場合、ワーク スティーリング アルゴリズムおよび範囲スティーリングを使用してこれらのパーティションを均等化します。 1 つのループ イテレーションが協調的にブロックされる場合、ランタイムは、現在のスレッドに割り当てられているイテレーションの範囲を他のスレッドまたはプロセッサに再配布します。 同様に、スレッドがさまざまなイテレーションを完了すると、ランタイムは他のスレッドからそのスレッドに作業を再配布します。 parallel_for アルゴリズムは、入れ子にされた並列処理もサポートします。 ある並列ループに別の並列ループが含まれている場合、ランタイムは、並列実行のために効率的な方法でループ体間の処理リソースを調整します。

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

多数の for ループを変換して parallel_for を使用できます。 ただし、parallel_for アルゴリズムは次の点で for ステートメントとは異なります。

• parallel_for アルゴリズムの parallel_for は、事前に決定された順序でタスクを実行しません。

• parallel_for アルゴリズムは、任意の終了条件をサポートしていません。 イテレーション変数の現在の値が last より 1 小さい場合、parallel_for アルゴリズムは停止します。

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

• ループの繰り返しは前方に進む必要があります。 _Step パラメーターが 1 未満の場合、parallel_for アルゴリズムは、std::invalid_argument 型の例外をスローします。

• parallel_for アルゴリズムの例外処理メカニズムは、for ループの例外処理メカニズムとは異なります。 並列ループ本体で複数の例外が同時に発生した場合、ランタイムは、parallel_for を呼び出したスレッドに例外の 1 つのみを伝達します。 さらに、1 回のループ反復で例外がスローされた場合、ランタイムはループ全体をすぐには停止しません。 代わりに、ループは取り消し状態になり、ランタイムはまだ開始されていないタスクをすべて破棄します。 例外処理と並列アルゴリズムの詳細については、「例外処理」をご覧ください。

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

Note

負荷分散と取り消しなどの機能のサポートによって発生するスケジューリング コストは、特にループ本体が比較的小さい場合に、ループ本体を並列で実行する利点を克服できない可能性があります。 並列ループでパーティショナーを使用することで、このオーバーヘッドを最小限に抑えることができます。 詳細については、このドキュメントで後述する「パーティション分割作業」をご覧ください。

例

次の例は、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();
   });
}

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

1 2 4 3 5

parallel_for アルゴリズムは各項目に対して並列に動作するため、値がコンソールに出力される順序は異なります。

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

[トップ]

parallel_for_each アルゴリズム

concurrency::parallel_for_each アルゴリズムは、反復コンテナーに対して C++ 標準ライブラリに用意されているタスクなどのタスクを並列実行します。 このアルゴリズムでは、parallel_for アルゴリズムで使用されるのと同じ分割ロジックが使用されます。

parallel_for_each アルゴリズムは C++ 標準ライブラリの 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), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

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

4 5 1 2 3

parallel_for_each アルゴリズムは各項目に対して並列に動作するため、値がコンソールに出力される順序は異なります。

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

[トップ]

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;
}

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

108 11.2 HelloHello

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

[トップ]

parallel_transformアルゴリズムとparallel_reduce アルゴリズム

concurrency::parallel_transform アルゴリズムおよび concurrency::parallel_reduce アルゴリズムは、それぞれ、C++ 標準ライブラリ アルゴリズム std::transform と std::accumulate の並列バージョンです。 この同時実行ランタイム バージョンは、C++ 標準ライブラリのバージョンと同様に動作しますが、操作が並列で実行されるため、操作順序は決まっていません。 これらのアルゴリズムを使用するのは、並列処理によるパフォーマンスとスケーラビリティの利点を得るのに十分に大きいセットを使用する場合です。

重要

parallel_transform アルゴリズムおよび parallel_reduce アルゴリズムは、ランダム アクセス反復子、双方向反復子、および前方反復子のみをサポートします。その理由は、これらの反復子は安定したメモリ アドレスを生成するからです。 また、これらの反復子は const 以外の l 値を生成する必要があります。

parallel_transform アルゴリズム

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

• 画像の明るさを調整し、その他の画像処理操作を実行します。

• 2 つのベクトル間のドット積を合計または取得し、ベクターに対して他の数値計算を実行します。

• 3D レイ トレースを実行します。ここでは、各イテレーションは、レンダリングする必要がある 1 つのピクセルを表します。

次の例は、parallel_transform アルゴリズムを呼び出すために使用される基本構造を示しています。 この例では、2 つの方法で std::vector オブジェクトの各要素を否定します。 最初の方法では、ラムダ式を使用します。 2 番目の方法では、std::unary_function から派生する 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 つの要素に結合します。

次の基本的な例は、parallel_reduce アルゴリズムを使用して文字列のシーケンスを 1 つの文字列に結合する方法を示しています。 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{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      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.
*/

多くの場合、parallel_reduce は、concurrency::combinable クラスと共に parallel_for_each アルゴリズムを使用するための短縮形と考えることができます。

例: マップと Reduce を並列で実行する

マップ 演算は、シーケンスの各値に関数を適用します。 リデュース 演算は、シーケンスの要素を 1 つの値に結合します。 C++ 標準ライブラリの std::transform 関数と std::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
*/

マップ操作と縮小操作を並列で実行する例については、「方法: マップ操作と縮小操作を並列実行する方法: マップ操作と縮小操作を並列実行する」をご覧ください。

[トップ]

パーティション分割作業

データ ソース上で操作を並列化する場合の必須の手順は、ソースを複数のスレッドによって同時にアクセスできる複数のセクションにパーティション分割することです。 パーティショナーは、並列アルゴリズムでスレッド間の範囲をパーティション分割する方法を指定します。 このドキュメントで既に説明したように、PPL は初期ワークロードを作成する既定のパーティション分割メカニズムを使用し、ワークロードが不均衡な場合にワーク スティーリング アルゴリズムと範囲スティーリングを使用してこれらのパーティションを均等化します。 たとえば、1 回のループ反復がさまざまなイテレーションを完了すると、ランタイムは他のスレッドからそのスレッドに作業を再配布します。 ただし、シナリオによっては、問題に適した別のパーティション分割メカニズムを指定することが必要になる場合があります。

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

concurrency::affinity_partitioner
作業を一定の範囲に分割します (通常は、ループで動作できるワーカー スレッドの数)。 このパーティショナーの種類は static_partitioner に似ていますが、範囲をワーカー スレッドにマップする方法によってキャッシュ関係が向上します。 このパーティショナーの種類により、ループが同じデータセットに対して複数回実行され (ループ内のループなど)、データがキャッシュに収まる場合にパフォーマンスを向上させることができます。 このパーティショナーはキャンセルに完全には参加しません。 また、協調ブロッキング セマンティクスを使用しないため、前方依存関係を持つ並列ループでは使用できません。

concurrency::auto_partitioner
作業を初期の範囲に分割します (通常は、ループで動作できるワーカー スレッドの数)。 _Partitioner パラメーターを取るオーバーロードされた並列アルゴリズムを呼び出さない場合、ランタイムは既定でこの型を使用します。 各範囲をサブ範囲に分割できます。そうすることにより、負荷分散を行うことができます。 一連の作業が完了すると、ランタイムは他のスレッドからそのスレッドに作業のサブ範囲を再配布します。 このパーティショナーは、ワークロードが他のカテゴリのいずれにも該当しない場合、または取り消しや協調ブロッキングの完全なサポートが必要な場合に使用します。

concurrency::simple_partitioner
指定されたチャンク サイズによって指定されたイテレーションの数以上が各範囲に含まれるように、作業を複数の範囲に分割します。 このパーティショナーの種類は負荷分散に関与しますが、ランタイムは範囲をサブ範囲に分割しません。 ランタイムは、各ワーカーに対して取り消しをチェックし、_Chunk_size イテレーションの完了後に負荷分散を実行します。

concurrency::static_partitioner
作業を一定の範囲に分割します (通常は、ループで動作できるワーカー スレッドの数)。 このパーティショナーの種類は、ワークスティーリングを使用しないため、オーバーヘッドが少なくなるため、パフォーマンスを向上させることができます。 このパーティショナーの種類は、並列ループの各反復処理が固定された均一な量の作業を実行し、取り消しまたは前方協調ブロッキングのサポートを必要としない場合に使用します。

警告

parallel_for_each および parallel_transformアルゴリズムでは、static、simple、および affinity パーティショナーのランダム アクセス反復子 (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());
}

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

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

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create an array 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 を使用するために、協調ブロッキング セマンティクスに依存する既存のコードを変更する場合は注意が必要です。 これらのパーティショナーの種類は負荷分散や範囲スティーリングを使用しないため、アプリケーションの動作を変更できます。

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

[トップ]

並列並べ替え

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	汎用の比較ベースの並べ替え。	比較ベース (昇順)	Unstable	なし	O((N/P)log(N/P) + 2N((P-1)/P))	ランダム
parallel_buffered_sort	O(N) 領域を必要とする汎用比較ベースの並べ替えの高速化。	比較ベース (昇順)	Unstable	追加の O(N) 領域が必要	O((N/P)log(N))	ランダム
parallel_radixsort	O(N) 領域を必要とする整数キーベースの並べ替え。	ハッシュベース	Stable	追加の O(N) 領域が必要	O(N/P)	ランダム

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

これらの並列並べ替えアルゴリズムは、取り消しと例外処理の規則に従います。 同時実行ランタイムの取り消し処理および例外処理の詳細については、「並列アルゴリズムの取り消し」および「例外処理」をご覧ください。

ヒント

これらの並列並べ替えアルゴリズムでは、移動セマンティクスがサポートされます。 移動代入演算子を定義して、スワップ操作を効率的に実行できます。 移動セマンティクスと移動代入演算子の詳細については、「 Rvalue Reference Declarator: &」および「Move コンストラクターと移動代入演算子 (C++)」 を参照してください。 移動代入演算子またはスワップ関数を指定しない場合、並べ替えアルゴリズムではコピー コンストラクターが使用されます。

次の基本的な例では、parallel_sort を使用して int 値の vector を並べ替える方法を示しています。 既定では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::real メソッドを使用して std::complex<double> 値を昇順に並べ替えます。

// 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 超です。

• 比較関数またはハッシュ関数が実行する作業の量。

• 使用可能なコンピューティング リソースの量。

• データ セットの特性。 たとえば、あるアルゴリズムが既にほぼ並べ替え済みのデータに対して良いパフォーマンスを示すが、まったく並べ替えされていないデータに対しては同様の結果にならない場合があります。

• チャンク サイズ。 省略可能な _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 のパフォーマンスが最高です。

[トップ]

関連項目

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

リファレンス

parallel_for関数

parallel_for_each関数

parallel_invoke関数

affinity_partitioner クラス

auto_partitioner クラス

simple_partitioner クラス

static_partitioner クラス

parallel_sort関数

parallel_buffered_sort関数

parallel_radixsort関数