HPC/並列プログラミングポータルでは、HPC(High Performance Computing)プログラミングや並列プログラミングに関する情報を集積・発信しています。

新着トピックス

複数スレッド間での変数の安全な共有を提供する「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_opaddint 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_maxCILK_C_REDUCER_MAX配列配列の最大値の取得(cilk::max_of())
reducer_max_indexCILK_C_REDUCER_MAX_INDEX配列配列の最大値のインデックス取得(cilk::max_of())
reducer_minCILK_C_REDUCER_MIN配列配列の最小値の取得(cilk::min_of())
reducer_min_indexCILK_C_REDUCER_MIN_INDEX配列配列の最小値のインデックス取得(cilk::min_of())
reducer_opaddCILK_C_REDUCER_OPADD数値加算(+=、=、-=、++、--)
reducer_opandCILK_C_REDUCER_OPAND数値AND演算(、=、=)
reducer_oporCILK_C_REDUCER_OPOR数値OR演算(|、|=、=)
reducer_opxorCILK_C_REDUCER_OPXOR数値XOR演算^、^=、=)
reducer_ostream-出力ストリーム出力ストリームへの書き込み()
reducer_basic_string、reducer_string、reducer_wstring-文字列(string)文字列末尾への追加(+=、append())

Cilk Plusを使用したコードの非並列実行(Serialization)

 Cilk Plusを使用したコードは、コンパイル時にコンパイルオプションとして「/Qcilk-serialize」、もしくは「/FI cilk/cilk_stub.h」を指定することで、cilk_spawnやcilk_forによる並列処理を無効化し、非並列のプログラムとして実行できる。プログラムが正しく動作せず、並列化による問題が疑われる場合、このオプションを使用してコンパイルを行って実行結果を確認してみると良いだろう。