レデューサーの動作

インテル® Cilk™ Plus は古い機能 (非推奨) です。代わりに、OpenMP* またはインテル® TBB を使用してください。詳細は、「インテル® Cilk™ Plus の代わりに OpenMP* またはインテル® TBB を使用するためのアプリケーションの移行」を参照してください。

レデューサーのメカニズムとセマンティクスの説明は、プログラミングの上級者がレデューサーの使用規則を理解する上で役立ち、カスタム・レデューサーを記述するのに必要な情報が得られます。

レデューサーは、"リダクション" アルゴリズムの並列実行をサポートするように設計されています。

1. アキュムレーター変数 x と初期値 a₀ があります。

2. リダクション操作 OP があります。

3. OP は結合側を満たす操作です。つまり、x OP y = y OP x になります。

4. OP には単位元I があります。つまり、x OP I = I OP x = x になります。

5. コードは x = x OP a_i 形式で変数を繰り返し更新します。N 回目の更新の後、x には a₀ OP a₁ OP a₂ OP … OP a_N が格納されます。

このパターンに該当する一般的な操作には、加算、乗算、ビット単位の AND (論理積)、ビット単位の OR (論理和)、セットの和集合、リストの連結、文字列の連結があります。(数学的に、型の組み合わせ、型に対する結合操作、および操作の単位元はモノイドと呼ばれます。)

レデューサー・オブジェクトは、並列実行するストランドがスポーンされ、同期されるのに伴い、"ビュー" と呼ばれるアキュムレーター変数のコピーをストランドごとに作成し自動で管理します。並列に実行する各ストランドは個別のビューを保持するため、異なるストランドがアキュムレーター変数を変更してもデータ競合は発生しません。

1. 初期状態では、レデューサーには "左端" ビューと呼ばれる 1 つのビューがあります。

2. レデューサーは、左端ビューから、並列に実行するストランドごとにビューの新しいインスタンスを作成します。新しいビュー・インスタンスは、レデューサーの identity() 関数によってリダクション操作の単位元に初期化されます。

3. 各ストランドがレデューサーのビューにアクセスする場合は常に、レデューサーによって作成された個別のビュー・インスタンスにアクセスします。

4. スポーンされたストランドが実行を完了し、親にマージされると、レデューサーの reduce() 関数はリダクション操作によって 2 つのストランドの値を結合し、その結果を継続するストランドのビュー・インスタンスに保持します。そして、レデューサーは完了したストランドのビューを破棄します。

5. スポーンされたストランドがすべて完了すると、最終値が左端ビューに保持されます。

この処理により、各ストランドはそれぞれのビューで全体のシーケンスのサブシーケンスを処理し (I OP a_i OP a_i+1 OP … OP a_i+m = a_i OP a_i+1 OP … OP a_i+m)、処理が完了すると左端ビューに最終的な値が格納されます (a₀ OP a₁ OP a₂ OP … OP a_N)。サブシーケンスの値の順序はシリアル処理と同じになりますが、リダクション操作は結合側を満たしているため、どの順序で結合するかは重要ではありません。

遅延ビュー作成

ストランドのプライベート・ビュー・インスタンスは、データ競合を排除するために作成されます。ストランドがビューにアクセスし、ほかのストランドと並列に実行する場合のみ、そのストランド専用のビュー・インスタンスが必要になります。ビューの作成、管理、マージのオーバーヘッドはわずかですが、ゼロではありません。そのため、スケジューラーは不要にビューを作成しないようにします。次のような規則があります。

1. ストランドがスチールされない限り、レデューサーはそのストランド用の新しいビュー・インスタンスを作成しません。スチールされない場合、ストランドは子と同じビューを安全に使用できます。

2. スチールされたストランドが初めてビューにアクセスするまで、レデューサーはそのストランド用の新しいビュー・インスタンスを作成しません。ストランドがビューにアクセスしない場合、新しいインスタンスは作成されません。

reducer<op_list_append<>> の使用例

この例は、reducer<op_list_append<>> を使用して文字列のリストを並列に集計する簡単なプログラムです。リストの連結に使用される単位元は空のリストで、リダクション関数は左のリストと右のリストを連結します。

 1 #include <cilk/cilk.h>
 2 #include <cilk/reducer_list.h>
 3
 4 cilk::reducer< cilk::op_list_append<std::string> > lr();
 5
 6 void depart()
 7 {
 8   lr->push_back("leave");
 9 }
10
11 int main()
12 {
13   lr->push_back("Don’t ");
14   cilk_spawn depart();
15   lr->push_back(" the path!");
16   cilk_sync;
17   std::list<std::string> result = list.get_value();
18 }

最初に、シングル・プロセッサーで実行するシリアルケースについて考えてみます。

1. レデューサーの作成時に左端ビューは空のリストに初期化されます。

2. 行 13 で文字列 "Don't " がリストに連結されます。

3. スポーンにより 1 つ目のワーカーは depart() ストランドを実行し、行 8 で "leave" をリストに連結します。

4. ワーカーは、1 つだけなのでスチールは発生せず、継続するストランド用に新しいビューは作成されません。行 15 で " the path!" がリストに連結されます。

5. ビューが 1 つしかないため、同期処理は行われず、左端ビューの最終値は {"Don't ", "leave", " the path!"} になります。

次に、プログラムを 2 つのワーカーで実行した場合について考えてみます。

1. レデューサーの作成時に左端ビューは空のリストに初期化されます。

2. 行 13 で文字列 "Don't " がリストに連結されます。

3. スポーンにより 1 つ目のワーカーは depart() ストランドを実行し、行 8 で "leave" をリストに連結します。

4. 一方、2 つ目のワーカーは継続ストランドをスチールします。2 つ目のワーカーが行 15 でビューにアクセスすると、レデューサーは新しいビューを作成し、空のリストに初期化します。

5. そして、行 15 で "the path!" が継続ストランドのプライベート・ビューのリストに連結されます。

6. 同期ポイントで、右側のビューの値 {"the path!"} が左側のビューの値 {"Don't", "leave"} に連結され、左端ビューの値が {"Don't ", "leave", " the path!"} になり、右側のビューが削除されます。