レデューサーの使用

インテル® C++ コンパイラー 18.0 デベロッパー・ガイドおよびリファレンス

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

ここでは、文字列やリストなど、各種レデューサーの使用方法について説明します。

文字列レデューサー

reducer<op_string> は、8 ビットの文字型の文字列を作成します。例では、更新操作に += (文字列結合) を使用しています。(16 ビットまたは 32 ビットの文字型の文字列では、reducer<op_basic_string> または reducer<op_wstring> を使用します。)

この例は、シリアル・セマンティクスを保持するために、レデューサーがランタイムシステムでどのように動作するかを示します。このレデューサーは、シリアルの for ループで 'A' から 'Z' までの文字を結合し、次の結果を出力します。

The result string is: ABCDEFGHIJKLMNOPQRSTUVWXYZ

cilk_for ループは、分割統治アルゴリズムを使用して作業を 2 つに分割し、分割したものをさらに 2 つに分割し、適切なチャンクサイズになるまで繰り返し分割します。そのため、1 番目のワーカーが "ABCDEF"、2 番目のワーカーが "GHIJKLM"、3 番目のワーカーが "NOPQRS"、4 番目のワーカーが "TUVWXYZ" を作成するというようになります。ランタイムシステムは、レデューサーの reduce メソッドを呼び出して、最終結果がアルファベットを順番に含む文字列になるようにします。

文字列結合は、(可換ではありませんが) 結合則を満たしているため、操作の順序は重要ではありません。例えば、次の 2 つの式は同じです。

"ABCDEF" concat ("GHIJKLM" concat ("NOPQRS" concat "TUVWXYZ"))
("ABCDEF" concat "GHIJKLM") concat ("NOPQRS" concat "TUVWXYZ")

この結果は、cilk_for がどのように作業チャンクを作成しても、常に同じになります。

get_value() を呼び出すと、reduce 処理を実行して各部分文字列を 1 つの文字列に結合し、その結果を返します。文字列の取得に使用する get_value() は、どのタイミングで呼び出すかが重要です。値の取得はどのタイミングでもできますが、いつでもいいわけではありません。適切なタイミングで取得しないと、意味のない中間値を取得してしまうことがあります。例えば、この例では、"GHIJKLM" と "NOPQRS" を結合した "GHIJKLMNOPQRS" になってしまうかもしれません。

インテル® Cilk™ Plus のレデューサーは、シリアル・セマンティクスを提供します。このシリアル・セマンティクスは、ランタイムシステムがすべての reduce 操作を完了した後の、cilk_for ループなどの並列計算の最後でのみ保証されています。get_value() を cilk_for ループ内で呼び出すべきではありません。ほかの反復からの結果が呼び出す反復の結果と結合されるため、予測不可能な意味のない値になります。

先の例における整数値の加算とは異なり、この例では reduce 操作は可換的ではありません。次のセクションのコード例のように、レデューサー・ライブラリーの reducer_list_append を使用して、リストの最後 (または先頭) に要素を追加するコードを記述することもできます。

#include <cilk/cilk.h>
#include <cilk/reducer_string.h>
#include <iostream>
int main()
{
   //...
   cilk::reducer<cilk::op_string> result;
   cilk_for (std::size_t i = 'A'; i < 'Z'+1; ++i){
     *result += (char)i;
   }
   std::cout << "The result string is: "
             << result.get_value() <<std::endl;
   return 0;
}

この例やその他の例では、ループの各反復でレデューサーを 1 回だけ更新していますが、複数回更新することも可能です。次に例を示します。

cilk_for (std::size_t i = 'A'; i < 'Z'+1; ++i){
   *result += (char)i;
   *result += tolower((char)i);
}

このような処理を行うこともできます。次の文字列が出力されます。

AaBb...Zz

リスト・レデューサー (ユーザー定義型)

reducer<op_list_append> は、更新操作に STL の append メソッドを使用してリストを作成します。単位元は空のリストです。次の例は、前述の文字列の例に似ています。reducer<op_list_append> の宣言にはデータ型が必要です。

#include <cilk/cilk.h>
#include <cilk/reducer_list.h>
#include <iostream>
int main()
{
  //...
  cilk::reducer<op_list_append<char> > result;
  cilk_for (std::size_t i = 'A'; i < 'Z'+1; ++i){
     result->push_back ((char)i);
  }

  std::cout << "String = ";
  std::list<char> r;
  r = result.get_value() ;
  for (std::list<char>::iterator i = r.begin();
                                 i != r.end(); ++i){
     std::cout << *i;
  }
  std::cout << std::endl;
}

再帰関数のレデューサー

レデューサーは、cilk_for ループ内の更新操作だけに制限されているわけではありません。再帰的にスポーンされる関数など、任意の制御フローで使用することができます。次の例は、レデューサーを使用して、ツリーの要素のインオーダー・リストを作成します。最終リストの要素の順序は、コア数や計算のスケジュール方法に関係なく、常にシリアル実行と同じになります。

#include <cilk/reducer_list.h>
Node *target;
cilk::reducer<op_list_append<int> > output_list;
...
// インオーダーで走査してツリーを出力
void walk (Node *x)
{
   if (NULL == x)
     return;
   cilk_spawn walk (x->left);
   output_list->push_back (x->value);
   walk (x->right);
 }

レデューサーの使用 - その他の例