並列アルゴリズム

並列パターン ライブラリ (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 アルゴリズムは、並列実行に最適となるようにタスクを分割します。 これは負荷が崩れたときにこれらの分割を分散させるために持ち出すワーク スティーリング アルゴリズムと Circle を使用します。 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 ループを記述する」を参照してください。

[トップ]

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), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

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

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

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

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

[トップ]

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 ピクセルを示す 3D 射線のトレースを実行します。

次の例では 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の基本的な使用例を次に示します。処理関数は、大量の作業を実行しないため、この例のパフォーマンスに大きな increase は要求されません。

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 の出力に指定する反復子は完全に入力反復子を複製する場合もあれば、まったく重なる必要があります。このアルゴリズムの動作は、入力と出力反復子が部分的に重複した unspecified です。

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
*/

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

[トップ]

パーティション分割作業

データ ソース上で操作を並列化するには、必要な手順は、複数のスレッドから同時にアクセスできる複数のセクションにを パーティションに分割すること です。 パーティショナーは並列アルゴリズムがスレッド間の範囲をどのようにパーティションに分割するかどうかを指定します。 このドキュメントで説明するように、PPL は負荷が崩れたときに最初のロードを作成し、これらのパーティションを分散させるために持ち出すワーク スティーリング アルゴリズムと Circle を使用する機能をパーティションに分割する既定を使用します。 たとえば、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として lvalue 参照 affinity_partitioner オブジェクトを渡す必要があります。 次の例では、データセット内の同じ操作を並列に実行する基本的なアプリケーションを示しています。 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 アルゴリズムはハッシュ ベースです。 つまり、要素を並べ替えるために整数 (Integer) のキーを使用します。 キーを使用して、このアルゴリズムは比較を使用せずに直接要素の目的を計算できます。 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 種類の並列並べ替えアルゴリズムの重要なプロパティがグラフィカルに表示されます。

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

ヒント

これらの並列並べ替えアルゴリズム サポート移動セマンティクス。交換操作はより効率的に実行できるようにムーブ代入演算子を定義できます。移動セマンティクスとムーブ代入演算子に関する詳細については、「右辺値参照宣言子: &&と 方法: 移動コンストラクターを記述する」を参照してください。ムーブ代入演算子または交換関数を提供する、並べ替えアルゴリズムはコピー コンストラクターを使用します。

次の基本的な例に 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 はこのコンピューターの構成にこのデータセットの作業を実行します。

[トップ]

関連トピック

タイトル	説明
方法: parallel_for ループを記述する	parallel_for アルゴリズムを使用して行列の乗算を行う方法について説明します。
方法: parallel_for_each ループを記述する	parallel_for_each アルゴリズムを使用して、std::array オブジェクトの素数の数を並列に計算する方法について説明します。
方法: 並列呼び出しを使用して並列並べ替えルーチンを記述する	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 関数