上級者向けトピック: 新しいレデューサーの記述方法

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

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

事前定義されているレデューサーで要件を満たすことができない場合は、カスタム・レデューサーを記述することができます。

新しいレデューサーを作成する際には、事前定義されているレデューサーを参考にすることができます。ただし、一部複雑なものもあります。各レデューサーのコードは、インストール・ディレクトリーの include/cilk サブディレクトリーにある reducer_*.h ヘッダーファイルにあります。

次のセクションで、その他の例も紹介します。

レデューサーの基本定義は include/cilk/reducer.h にあります。

モノイド

数学的に、モノイドは値のセット T、値のセットに対する結合操作 OP、およびそれらの操作のための単位元 I からなります。つまり、以下の条件を満たす場合、(T, OP, I) はモノイドと言えます。

OP が結合則を満たしている: T に含まれるそれぞれの x、y、および z ごとに x OP (y OP z) = (x OP y) OP z を満たす場合。
I が OP の単位元である: T に含まれる各 x が x OP I = I op x = x を満たす場合。

以下にモノイドの例を示します。

T = すべての整数; OP = 加算; I = 0。
T = すべての 32 ビット符号なし整数; OP = モジュロ 2³² の加算; I = 0。
T = すべての文字列; OP = 連結; I = 空の文字列。

レデューサーは常にモノイドを核に構築されます。値のセットと演算子を使用して最終値を計算します。単位元により各部分計算で使用するアキュムレーター変数を初期化し、結合則を満たす演算子により、並列に実行される部分計算の結果を再結合します。

レデューサーのコンポーネント

レデューサーは、論理的にこれらのコンポーネントに分けることができます。

"値の型" は、レデューサーにより計算される値の型です。
"ビュー" クラスは、レデューサー内のアキュムレーター変数を表します。多くの場合、ビュークラスは値の型の値になります。例えば、int 値のセットの合計を計算する reducer<op_add> のビュークラスには、int 値が含まれます。ただし、ビュークラスには最終値とは関連のない計算の追加情報が含まれていることがあります。例えば、文字列のセットを連結する reducer<op_string> のビュークラスには、まだ連結されていない部分文字列のリストが含まれているかもしれません。

レデューサーにはビュークラスの 1 つのインスタンスが直接含まれています ("左端ビュー")。ほかのビュー・インスタンスは並列実行するストランドの開始と終了に伴って作成/破棄されます。
"モノイド" クラスは、レデューサーの核となる数学的モノイドを表します。値の型を定義し、レデューサーでビューの作成とマージに使用される identity() 関数と reduce() 関数、およびビューのメモリー割り当て処理を行ういくつかの関数を提供します。後述の説明を参照してください。
"レデューサー" クラスは cilk::reducer クラス・テンプレートであり、モノイド (cilk::reducer<Monoid>) によりインスタンス化されます。レデューサー・オブジェクトにはモノイド・オブジェクトと左端ビューが含まれており、ランタイムシステムとの相互作用を管理し、実行中に現在のストランドのビュー・インスタンスへのアクセスを提供します。

モノイドクラス

モノイドクラスは、レデューサー・クラスでビュー・インスタンスの作成、初期化、マージ、破棄を行うのに必要な情報を提供します。レデューサーの値の型である value_type、レデューサーのビュークラスである view_type、および次の関数 (static または const のいずれか) を定義する必要があります。

モノイド関数	説明
`reduce(value_type left, value_type right)`	`left = left OP right` を評価します。`right` は不定の有効な値になります。
`identity(value_type *p)`	`p` のポイント先の初期化されていないメモリー位置に単位元を配置します。
`destroy(value_type *p)`	`p` のポイント先のオブジェクトに対して `value_type` デストラクターを呼び出します。
`allocate(size)`	生メモリーの `size` バイトへのポインターを返します。
`deallocate(p)`	`p` にある生メモリーを解放します。

これらが定義されたクラスはいずれもモノイドクラスとして使用できますが、実際には、モノイドクラスは常にビューを View に、値の型を Value に定義し、new 演算子を使用して allocate()、destroy()、deallocate() クラスを定義する cilk::monoid_base<Value, View=Value> サブクラスとして定義されます。monoid_base の派生クラスは、identity() 関数と reduce() 関数を宣言し、実装するだけで済みます。

reduce() 関数は、right ビューに保持される値を制限していませんが、reduce() の後で破棄できるように有効な値でなければなりません。

結合則を満たさなければならない理由

レデューサーが決定論的にシリアル・セマンティクスを再現するには、reduce 関数とビューで許可される操作において、結合則を満たす操作を実装する必要があります。(可換でなくてもかまいません。)

リダクションのシリアル実行は、式 (a₀ OP a₁ OP a₂ OP … OP a_N) を計算します。リダクションを並列実行すると、この式は部分式のセットに分割され、結合されます。例えば、((a₀ OP a₁ OP a₂) OP ((a₃ OP a₄) OP (a₅))) OP (a₆ OP a₇ OP … OP a₁₀) OP … のようになります。部分式への分割方法と部分式の結合順序はプログラムの実行ごとに異なり、予測できません。しかし、OP が結合則を満たしていれば、部分式への分割方法と部分式の結合順序に関係なく結果は同じになるため、これは問題ではありません。

レデューサーの記述方法 - シングルリンク・リスト

次のサンプルコードは、ループにより単純なシングルリンク・リストを作成します。このサンプルコードでは、cilk_for を使用してループを並列化していますが、リストノードの更新でデータ競合が発生するため並列に実行できません。値を並列に作成するには、レデューサーを使用します。

#include <cilk/cilk.h>
#include <iostream>

//  シングルリンク・リスト
//
struct IntListNode {
    int data;
    IntListNode* link;
};

// 値を計算します。(実際のプログラムでは 
// ここでさまざまな操作を行うことができます。)
//
int compute(int i)
{
    return i;
}

// リストを作成します。
//
IntListNode* make_list(int n)
{
    IntListNode* list = 0;
    for (int i = 0; i < n; ++i) {
        IntListNode* node = new IntListNode;
        node->data = compute(i);
        node->link = list;
        list = node;
    }
    return list;
}

// リストを使用します。(実際のプログラムでは 
// ここでさまざまな操作を行うことができます。)
//
void print_list(IntListNode* list)
{
    for (IntListNode* node = list; node; node = node->link)
        std::cout << node->data << "\n";
}

int main()
{
    IntListNode* list = make_list(20);
    print_list(list);
   // ここにリストの割り当て解除コードを配置します。
}

レデューサーを作成する最初のステップは、モノイドを指定することです。ここでは、データ型として整数型のシングルリンク・リストを IntListNode オブジェクトとして定義しています。この処理の並列化では複数のサブリストの作成と結合を伴うため、結合操作はリスト連結でなければなりません。リスト連結の単位元は空のリストです。リストの先頭にオブジェクトを追加することは、リストの前にオブジェクトを含む新しいリストを追加することと同じです ( list = {x} || list )。そのため、レデュース操作は "left = right || left " でなければなりません。

どのようにリストを表現したら良いでしょうか? ビューの型は値の型と異なりますか? シングルリンク・リストは、先頭ノードへのポインター (あるいは、空のリストの場合は null ポインター) として表現され、make_list 関数はこのポインターを返し、print_list 関数にこのポインターが渡されます。しかし、先頭ノードへのポインターだけでは 2 つのリストを効率良く連結することはできないため、ビューは先頭へのポインターと末尾へのポインターの両方を必要とします。

モノイドの構造は次のようになります。値の型はリストの先頭ノードへのポインター (あるいは、空のリストの場合は null ポインター) です。ビューは (先頭と末尾の) ポインターのペアで、リストに新しい値を追加する操作を提供します。モノイドの identity 関数は空のリストに初期化し、reduce() 関数は 2 つのビューのリストを連結します。

以下は、新しいレデューサーを使用する並列コードです。

#include <cilk/cilk.h>
#include <cilk/reducer.h>
#include <iostream>

//  シングルリンク・リスト
//
struct IntListNode {
    int data;
    IntListNode* link;
};


class IntListMonoid;            // 事前宣言

//  ビュークラス
//
class IntListView {
    friend class IntListMonoid; // 単位元とレデュース関数用
    IntListNode* head;
    IntListNode* tail;
public:
    void add_value(int x) { 
        IntListNode* node = new IntListNode;
        node->data = x;
        node->link = head;
        head = node;
        if (!tail) tail = node;
    }
    IntListNode* get_value() const { return head; }
};

// モノイドクラス
//
struct IntListMonoid : public cilk::monoid_base<IntListNode*, IntListView> {

    // *view を空のリストに設定します。
    //
    static void identity(IntListView* view) {
        view->head = view->tail = 0;
    }
    
    // 右側のリストを左側のリストの前に移動します。
    // 右側のリストは空のままにします。
    //
    static void reduce(IntListView* left, IntListView* right) {
        if (right->head) {
            right->tail->link = left->head;
            left->head = right->head;
            right->head = right->tail = 0;
        }
    }
};


// 値を計算します。(実際のプログラムでは 
// ここでさまざまな操作を行うことができます。)
//
int compute(int i)
{
    return i;
}

// リストを作成します。
//
IntListNode* make_list(int n)
{
    cilk::reducer<IntListMonoid> list;
    cilk_for (int i = 0; i < n; ++i) {
        list->add_value(i);     // "list->" はビューにアクセスします。
    }
    return list.get_value();   // get_value() はリダクション関数です。
}

// リストを使用します。(実際のプログラムでは 
// ここでさまざまな操作を行うことができます。)
//
void print_list(IntListNode* list)
{
    for (IntListNode* node = list; node; node = node->link)
        std::cout << node->data << "\n";
}

int main()
{
    IntListNode* list = make_list(20);
    print_list(list);
   // ここにリストの割り当て解除コードを配置します。
}

このような単純なビューを持つレデューサーの場合、コードをさらに単純化できます。ビュークラスで次のことを行います。

value_type を定義します。
デフォルトのビュー・コンストラクターにより、ビューを単位元に初期化します。
このビューと別のビューの値を結合する reduce() 関数を定義します。

そして、monoid_base の代わりに monoid_with_view クラスを使用します。モノイドクラスを特殊化する必要はありません。

// ビュークラス
//
class IntListView {
    IntListNode* head;
    IntListNode* tail;

public:
    typedef IntListNode* value_type;
    IntListView() : head(0), tail(0) {}
    void reduce(IntListView* right) { 
        if (right->head) {
            right->tail->link = this->head;
            this->head = right->head;
            right->head = right->tail = 0;
        }
    }
    void add_value(int x) { 
        IntListNode* node = new IntListNode;
        node->data = x;
        node->link = head;
        head = node;
        if (!tail) tail = node;
    }
    IntListNode* get_value() const { return head; }
};

// モノイドクラス
//
typedef cilk::monoid_with_view<IntListView> IntListMonoid;