並列アルゴリズム

[アーティクル]
08/09/2011

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

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

セクション

ここでは、次の並列アルゴリズムについて詳しく説明します。

parallel_for アルゴリズム
parallel_for_each アルゴリズム
parallel_invoke アルゴリズム

parallel_for アルゴリズム

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

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

parallel_for アルゴリズムには、2 つのオーバーロードバージョンがあります。 1 つ目のバージョンは、開始値、終了値、および処理関数 (ラムダ式、関数オブジェクト、または関数ポインター) を受け取ります。 2 つ目のバージョンは、開始値、終了値、およびステップ値、および処理関数を受け取ります。この関数の 1 つ目のバージョンは、ステップ値として 1 を使用します。

複数の 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();
   });
}

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

1 2 4 3 5

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(values.begin(), values.end(), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

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

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

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