Intel Cilk Plusの畳み込み

何らかの理由で、配列の要素の合計を見つける必要があるとします。 配列を2つの部分に分割し、各部分を個別に合計して、結果を追加できます。 この場合、これらの部分を並行して要約できます。 しかし、配列の一部を合計することはまさに元のタスクであり、各部分を再び2つの部分に分割し、各部分を個別に合計し、結果を加算することなどができます。この計算戦略は「 分割統治 」 と呼ばれます。

この方法で、配列の他の多くの関数を計算できます。以下の記事の最初の部分でこのアイデアの数学的説明を行い、2番目でIntel Cilk Plusを使用してプログラムでこのアイデアを使用する方法を説明します。

したがって、夏の最後の数日間に数式やC ++コードを調べたい場合は、habrakatへようこそ。

モノイドと準同型

多くの例と非常に詳細な説明を含むモノイドの定義は、habrastatのモノイドとそのアプリケーション（ツリーのモノイド計算）にあります 。そのため、定義といくつかの例に限定します。

モノイドはトリプル（ M 、⋅、 e ）です。ここで、 Mは空でない集合、⋅は集合Mに対するバイナリ連想操作、 eは集合Mの操作⋅に関する中立要素です。

演算theは結合的であるため、つまりMからのx 、 y 、およびz について 、x⋅（y⋅z）=（x⋅y）⋅zであり、式x 1⋅x 2⋅... ⋅x _nは括弧の配置に依存しないため、括弧はまったく省略できます。 この単純だが重要な事実の証明（およびそれに続くすべての単純だが重要な事実）は、高等代数に関する教科書で見つけるか、自分で考え出すことができます。

モノイドの例はたくさんあります。たとえば、6年生の場合、加算（ Z 、+、0）による整数のセットがモノイドであることは誰もが知っています。 モノイドの別の例は、リストモノイドです。 つまり、Xを任意のセットとし、空のシーケンス[]を含むセットXの要素のすべての有限シーケンスのセットをX ^∗で示し、++でリストの連結の操作を示します。 次に、検証することは難しくないため、トリプル（ X ^∗ 、++、[]）はモノイドです。

次に、準同型の概念が必要です。 （ M 、⋅M、 e _M ）と（ N 、⋅N、 e _N ）を任意の2つのモノイドとする。 関数h ： M → Nは、 Mからの任意のxとyに対してh （x⋅M y ）= h （ x ）⋅N h （ y ）であり、h（ e _M ）= e _Nである場合、 準同型と呼ばれます_。

大まかに言って、関数は二項演算の符号を介してドラッグできる場合、準同型であることに注意してください。 アイデンティティマッピングが準同型であることは明らかですが、数学の学校や大学のコースから、誰もが準同型のより興味深い例をいくつか知っています。 たとえば、 積の対数は、対数の合計 ln（ xy ）= ln x + ln yに等しく、この用語では、マップlnは（ R ₊ 、⋅、1）を実数のモノイドに乗算することにより、正の実数のモノイドからの準同型であることを意味します加算（ R 、+、0）。 さらに、 行列の積の行列式は、これらの行列の行列式の積 det（ AB ）= det A⋅det Bに等しく 、すなわち、マッピングdetは、正方行列のモノイドからの乗算（Mat _n （ R ）、⋅、 I ）への準同型です乗算数（ R 、⋅、1）。 アイデアが明確であることを願っています。 次に、準同型をリストします。

リストモノイド（ X ^∗ 、++、[]）から任意のモノイド（ M 、⋅、 e ）への準同型hは、 リスト準同型と呼ばれます。 リスト準同型には、次の有用なプロパティがあります。 [ x ₁ 、 x ₂ 、...、 x _n ]を任意のリストとし、 h （[ x ₁ 、 x ₂ 、...、 x _n ]）= h （[ x ₁ ] ++ [ x ₂ ] ++ ... + + [ x _n ]）= h （[ x ₁ ]）⋅h（[ x ₂ ]）⋅...⋅h（[ x _n ]）。 したがって、リスト準同型は、シングルトンリストの値によって一意に決定されます。 したがって、 f ： X → Mをf （ x ）= h （[ x ]）のような関数とすると、一意に定義されたリスト準同型hをhom（⋅、 f 、 e ）の形式で書き留めます。

次に、いくつかの例を示します。

1. 数のリストの要素の合計、数のリストの要素の積、数のリストの最小および最大要素の検索は、リスト準同型と見なすことができますhom（+、id、0）、hom（⋅、id、1）、hom（max、id、-∞）およびそれぞれhom（min、id、+∞）。 同様のリスト準同型では、2番目のパラメーターはidの恒等写像であり、reduce（⋅、e）と簡単に記述します。
2. リストの長さを計算する長さ関数は、リスト準同型ホモ（+、one、0）です。ここで、one（ x ）= 1です。
3. リストの各要素に関数fを適用する関数も、リスト準同型、すなわちhom（++、 g 、[]）であり、 g （ x ）= [ f （ x ）]です。 このような関数は、簡単にmap（ f ）として記述されます。
4. ソート関数は、リスト準同型として表現することもできます。 つまり、mergeを2つの順序付きリストをマージする関数とします。list（ x ）= [ x ]は、要素をシングルトンリストに変換する関数です。 準同型hom（merge、list、[]）が望ましいリスト準同型になります。

準同型はリスト相同性と呼ばれますが、リストは配列、文字列、またはその場で生成されるシーケンスを意味する場合があることに注意してください。 次に、準同型定理として知られる3つの有用なステートメントを示します。

最初の準同型定理。 リスト準同型は、コンポジション hom（⋅、 f 、 e ）= reduce（⋅、e）∘map（ f ） として表すことができます 。

MapReduceのアイデアは、この単純な観察に基づいています。 MapReduceの簡単な紹介は、 MapReduce habrastas またはメモリとプロセッサの能力を超える計算（zaumiなしで試してみます）およびMapReduce：より高度な例、zaumiなしで試してみます。

[ x ₁ 、 x ₂ 、...、 x _n ]を任意のリスト、関数foldl（⋅L、 e _L ）（[ x ₁ 、 x ₂ 、...、 x _n ]）=（...（（e _L ⋅L x ₁ ）⋅L x ₂ ）⋅L ...⋅L x _n ）、右折りは関数foldr（⋅R、 e _R ）（[ x ₁ 、 x ₂ 、...、 x _n ]）=（ x ₁ ⋅R（ x 2⋅R ...⋅R（ x n⋅R e _R ）...））。 2番目の準同型定理は次のことを述べています。

2番目の準同型定理 。 リスト準同型は、左右の畳み込み、つまり、 hom（⋅、 f 、 e ）= foldl（⋅L、 e ）= foldr（⋅R、 e ）として表されます 。 ここで 、x⋅L y = x⋅ f （ y ）、x⋅R y = f （ x ）⋅y。

この定理は、リスト準同型を計算​​するための2つの連続した方法-左の形式と右の畳み込みの形式を示します。 これらの畳み込みを計算する関数は、特定のプログラミング言語で呼び出されます。Fold（高階関数）ウィキペディアの記事で見つけることができます。 畳み込みの詳細については、関数型言語の Evgeny Kirpichev Elementsの記事を参照してください。

私たちにとって、リスト準同型h = hom（⋅、 f 、e）の並列計算の方法はより興味深いです。 リスト準同型h （ x ++ y ）= h （ x ）⋅h（ y ）の定義により、言い換えると、独立して、したがって並列にh （ x ）とh （ y ）を計算できることを思い出してください。その後、すでにh （ x ++ y ）の最終値を計算します。 しかし、リストxとyをそれぞれ2つの部分に分割し、準同型の定義を使用して、それらのhの値を個別に計算し、結果を収集するなどもできます。これは、 分割統治戦略に過ぎません。

演算theが一定時間Cで計算され、リストxがn個の要素で構成されているとします。 左畳み込みを計算するには、操作を正確にn回計算する必要があります。つまり、 Cn時間かかります。 プロセッサがp個ある場合、リストxをp個の等しい部分x _iに分割し、各x _iの左畳み込みを使用して時間Cn / pの h _を計算し、次に時間C log ₂ pの最終結果を計算します。 したがって、合計時間はC （ n / p + log ₂ p ）です。

最後に、関数がリスト準同型である場合を言う3番目の準同型定理を述べま​​す。

3番目の準同型定理。 リストモノイドから特定のモノイドへの関数が左 foldl（⋅L、 e ） および右畳み込み foldr（⋅R、 e ） として表現される 場合、それはリスト準同型です。

これらの3つの定理の証拠はJeremy Gibbonsの記事The Third Homomorphism Theoremにあり、Intel Cilk Plusに進みます。

Intel Cilk Plusの畳み込み

Intel Cilk Plusは、マルチスレッドプログラムを作成するためのC ++言語の拡張機能であり、特に次のものが含まれます。

1. キーワードcilk_spawnおよびcilk_sync （最初の関数は関数を並列に実行できることを示し、2番目の関数は同期に使用されます）、
2. ループを並列化するcilk_forキーワード、
3. スレッドセーフなデータ共有のためのハイパーオブジェクト
4. 配列と配列の操作のための特別な構文、たとえば配列の要素ごとの追加はc[:] = a[:] + b[:]の形式で記述できます。

ここでは2番目と3番目のポイントのみが影響を受けます。 Intel Cilk Plusに関するドキュメントおよびその他の資料は、 http：//software.intel.com/en-us/articles/intel-cilk-plus/にあります。

したがって、整数の配列の要素の合計を計算する必要があるとします。 可能な順次実装を以下に示します。

 int sum = 0; for (int i = 0; i < n; ++i) { sum += a[i]; } std::cout << sum << std::endl; 

これは左畳み込みの実装に過ぎないことに注意してください。 ただし、配列の要素の合計はリスト準同型であるため、上記で説明したように、並列実装も可能です。 Intel Cilk Plusを使用すると、このような実装を簡単に行うことができます。次を実行するだけで十分です。

1. ヘッダーファイルcilk/reducer_opadd.hおよびcilk/cilk.h 。
2. タイプsumをreducer_opadd<int> 、
3. をcilk_forに変更for 、
4. get_value()を使用して結果を取得します。

 #include <cilk/cilk.h> #include <cilk/reducer_opadd.h> ... cilk::reducer_opadd<int> sum; cilk_for (int i = 0; i < n; ++i) { sum += a[i]; } std::cout << sum.get_value() << std::endl; 

この場合、およそ次のことが起こります。 コンパイラーはcilk_forサイクルの本体を、分割統治戦略を実装する関数に変換します;これは、次のように疑似コードで記述されます。

 void run_loop(first, last) { if ((last - first) < grainsize) { for (int i = first; i < last; ++i) { LOOP_BODY; } } else { int mid = (last - first) / 2; cilk_spawn run_loop(first, mid); run_loop(mid, last); } } 

また、sum変数はレデューサーであるため、スレッドを2つに分割してそれらの並列実行を行う場合、子は古い表現を使用し、継続は新しい表現を取得し、同期時にゼロに初期化され、両方の表現が追加されます。

reducer_opadd加えてreducer_opaddインテルCilk Plusは幅広いreducer_list_append ： reducer_list_append 、 reducer_list_prepend 、 reducer_min 、 reducer_max 、 reducer_min_index 、 reducer_max_index 、 reducer_opor 、 reducer_opand 、 reducer_opxor 、 reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream reducer_basic_string reducer_string reducer_wstring reducer_ostream どれも機能しない場合は、独自のレデューサーを作成できます。

レデューサーを作成するには、 Monoidを実装するMonoidクラスを作成する必要があります。 このクラスには、次の関数が含まれている必要があります。

• reduce(T *left, T *right) *left = *left OP *right計算し*left = *left OP *right 。
• identity(T *p)は、 p指すメモリ領域に中立要素を作成します。
• destroy(T *p)は、 p指すオブジェクトのデストラクターを呼び出します。
• allocate(size)は、サイズsizeバイトのメモリ領域へのポインタを返します。
• deallocate(p)は、 deallocate(p)指すメモリを解放します。

ほとんどの場合、これらのすべてのメソッドを実装する必要はありません; cilk::monoid_base<T>クラスから継承し、 reduce()および場合によってはidentity()を実装reduce()だけで十分です。

さらに、リデューサーを実装するクラスには、 cilk::reducer<Monoid> imp_と、このハイパーオブジェクトにアクセスし、非表示メンバーとして変更するためのメソッドが含まれている必要があります。

数値の配列の要素の積を見つけるためのレデューサーを作成します。

 #include <cilk/reducer.h> #include <cilk/cilk.h> #include <iostream> class reducer_prod { public: struct Monoid: cilk::monoid_base<double> { void reduce(double *left, double *right) const { *left *= *right; } void identity(double* p) const { new ((void*) p) double(1.0); } }; reducer_prod(): imp_(1.0) { } reducer_prod &operator*=(const double &v) { imp_.view() *= v; return *this; } double get_value() const { return imp_.view(); } private: cilk::reducer<Monoid> imp_; }; 

 reducer_prod prod; cilk_for (int i = 0; i < n; ++i) { prod *= a[i]; } std::cout << prod.get_value() << std::endl;