インテル Parallel Composerの新機能――並列プログラムを容易に実装できる「インテル Cilk Plus」入門 4ページ

複数スレッド間での変数の安全な共有を提供する「reducer」

　並列プログラミングにおいて、注意しなければならないのが変数の共有方法や排他制御だ。複数スレッドで共有する変数に対しては適切な排他制御が必要であり、それを行わないとバグやパフォーマンス低下を引き起こす原因となる。Clik Plusでは変数に対して汎用的な排他制御の仕組みを提供する「reducer」という機能が備えられている。一般的な変数の代わりにreducerを用いて宣言した変数/オブジェクトを利用することで、並列実行時も整合性が保証される。

　reducerの特徴は次のとおりだ。

• アクセス時に競合が発生しない、安全な共有変数を提供する
• ロックを使用しないため、ロックの競合が発生しない
• 適切に使う限り、並列版と非並列版で同様の挙動を示す
• 最小のオーバーヘッドで効率的に動作する

　reducerはmutexやセマフォのようなロック機構は使用しない。そのためデッドロックが発生せず、またパフォーマンスも高い。ただし、reducer変数/オブジェクトに対して行える処理は限られており、使用するreducerの種類によって保証される操作は限られる。たとえば後述する「CILK_C_REDUCER_OPADD()」や「cilk::reducer_opadd<>」で作成したreducerに対しては加算や減算のみが実行可能となる。

　C++では排他制御機構が実装されたテンプレートクラスという形でreducerが実装されており、このクラスのオブジェクトを一般的な変数の代わりとして利用する。たとえばC++で複数スレッドから変数に対し安全に加減算を行いたい場合、「cilk::reducer_opadd<>」というテンプレートクラスを使用する（リスト6）。テンプレートクラスでは安全に利用できる処理がオペレータ関数として定義されており、その範囲で一般的な変数と同様にアクセスできる。また、reducerオブジェクトの値を取得するには「get_value()」メソッドを用いる。

リスト6 C++でのreducer使用例

#include <cilk/cilk.h>
#include <cilk/reducer_opadd.h>　　← reducer_opaddが定義されたヘッダーファイルをinclude

cilk::reducer_opadd<int> sum;　　← int型の加算reducerを定義

void addsum() {
     sum += 1;
}

int main() {
  sum += 1;
  cilk_spawn addsum();　　← addsum()関数を並列実行
  sum += 1;
  cilk_sync;　　← addsum()関数の終了を待機
  return sum.get_value();　　← 「3」を返す
}

　Cでreducerを利用する場合、reducerの内部処理を実装した関数をラッピングしたマクロ経由でreducer変数を宣言する。たとえば安全に加減算を行うreducerを利用する場合、「CILK_C_REDUCER_OPADD()」マクロを使ってreducer変数を宣言し、変数へのアクセスには「REDUCER_VIEW()」マクロを使用する（リスト7）。

リスト7 Cでのreducer使用例

#include <cilk/cilk.h>
#include <cilk/reducer_opadd.h>　　← reducer_opaddが定義されたヘッダーファイルをinclude

CILK_C_REDUCER_OPADD(sum, int, 0);　　← int型の加算reducerを定義

void addsum() {
  REDUCER_VIEW(sum) += 1;
}

int main() {
  REDUCER_VIEW(sum) += 1;
  cilk_spawn addsum();　　← addsum()関数を並列実行
  REDUCER_VIEW(sum) += 1;
  cilk_sync;　　← addsum()関数の終了を待機
  return REDUCER_VIEW(sum);　　← 「3」を返す
}

reducerの動作原理

　reducerではスレッドごとに値を保持する変数を用意することで、複数スレッドからの安全なアクセスを実現している。書き込みアクセスを行う場合はスレッドごとの変数に値を保持し、読み出しアクセスを行う際にはその時点で各スレッドの変数で保持されている値を集計し値を返す、という処理を行っている。これにより並列で実行した場合でも非並列で実行した場合と同じ値を返すことが保証され、また同一の変数に書き込みアクセスが同時に発生することを避けることができる。

　ただし、浮動小数点演算の処理に関しては、処理によっては丸め誤差などのため結果に違いが出ることがある。厳密な計算を要するものなど、プログラムによっては許容できない誤差が出ることがあるため注意してほしい。また、reducerを使用することによるパフォーマンス低下は一般的には少ないものの、たとえば大量のreducerオブジェクトを使用する場合、最悪の場合同時に実行されているスレッド分だけの変数が割り当てられるため、大きなオーバーヘッドが生じる可能性がある。

　そのほか、読み出しアクセスを行う際には各スレッドごとの変数から集計を行う必要があるため、同時に多くのスレッドが動作している状況で頻繁に読み出しアクセスを行うとパフォーマンス低下の恐れがある。

あらかじめ用意されているreducer

　Cilk Plusではあらかじめ表3のようなreducerが用意されている。また、既存のマクロやテンプレートをベースに独自のreducerを実装することも可能だ。

表3 あらかじめ用意されているreducer

テンプレートクラス（C++）	マクロ（C）	オブジェクトの型	オブジェクトに対し行える操作
reducer_list_append	–	リスト	リスト末尾への追加（push_back()）
reducer_list_prepend	–	リスト	リスト先頭への追加（push_front()）
reducer_max	CILK_C_REDUCER_MAX	配列	配列の最大値の取得（cilk::max_of()）
reducer_max_index	CILK_C_REDUCER_MAX_INDEX	配列	配列の最大値のインデックス取得（cilk::max_of()）
reducer_min	CILK_C_REDUCER_MIN	配列	配列の最小値の取得（cilk::min_of()）
reducer_min_index	CILK_C_REDUCER_MIN_INDEX	配列	配列の最小値のインデックス取得（cilk::min_of()）
reducer_opadd	CILK_C_REDUCER_OPADD	数値	加算（+=、=、-=、++、–）
reducer_opand	CILK_C_REDUCER_OPAND	数値	AND演算（&、&=、=）
reducer_opor	CILK_C_REDUCER_OPOR	数値	OR演算（|、|=、=）
reducer_opxor	CILK_C_REDUCER_OPXOR	数値	XOR演算^、^=、=）
reducer_ostream	–	出力ストリーム	出力ストリームへの書き込み（<<）
reducer_basic_string、reducer_string、reducer_wstring	–	文字列（string）	文字列末尾への追加（+=、append()）