OpenMP 入門

OpenMP は共有メモリ並列プログラミングの標準 API である。ここでは C/C++ 版を紹介する。Fortran 版もある。本ページは OpenMP 3.1 向けである．

OpenMP は自動並列化ではない。依存性の分析と解決はプログラマに任されている。使い方を間違えば、当然正しくない結果を出す。

#include <omp.h>
OpenMP を使うときにはインクルードする。

_OPENMP
OpenMP コンパイラが define するマクロ。OpenMP のバージョンを示す．

#pragma omp parallel 節
次の行から始まるブロックを並列に（重複して）実行する。
スレッドの数は num_threads 節か、omp_set_num_threads 関数か、環境変数 OMP_NUM_THREADS で指定する。
Parallel 指示行の時点で既に定義されている変数と、ブロック内でもstatic 宣言されている変数はスレッド間で共有される。ブロック内のauto変数はスレッド私有の変数となる。これを変えたければ、shared(変数リスト)あるいはprivate(変数リスト)のように節として指示する。
これを使うと SPMD なプログラムが書ける．もっともそれが OpenMP として推奨される書き方かどうかは微妙なところである．

#pragma omp for 節
次のブロックをループ並列化する。並列化の仕方として5通りが指定できる。

schedule(static, チャンクサイズ)：反復をチャンクサイズごとにラウンドロビン（ブロックサイクリック割付）で割り付ける。デフォルトのチャンクサイズは反復数をスレッド数で割った値。
schedule(dynamic, チャンクサイズ)：反復をチャンクサイズごとに分けて、遊んでいるスレッドに動的に割り付ける。デフォルトのチャンクサイズは1。
schedule(guided, チャンクサイズ)： dynamic と同様だが、チャンクサイズが徐々に小さくなって指定された値に至る。
schedule(runtime)：実行時に環境変数で指定する。

reduction(演算子:変数リスト) 節を指定すると、指定された変数と演算子に関するリダクションが行われる。
#pragma omp paralle for のように組み合わせることができる．

#pragma omp single 節：1スレッドで実行する
#pragma omp master：0 番スレッドで実行する
#pragma omp critical (名前)：クリティカルセクション（名前はなくても良い）
#pragma omp atomic [read|write|update|capture]：後続の文を不可分的に実行する．後続に書ける文は限られている（x++ とか）．節を書かないと update となる．
#pragma omp barrier：バリア同期

#pragma omp flush (変数リスト)
メモリの一貫性を取る。スレッド間でのメモリアクセスの一貫性は通常は確保されていない。変数 x を介してスレッド 0 からスレッド 1 にデータを送るには，

スレッド 0 が x にデータを書き込む．
スレッド 0 が x を flush する．
スレッド 1 が x を flush する．
スレッド 1 が x からデータを読み込む．

がこの順序で行われることを保証したプログラムにしなければならない．しかしこれは大変難しい．flush は使わないことを推奨する．
但し、barrier, criticalとparallel の出口と入口、for と singleの出口では暗黙のflushが行われる（但しnowait 節を入れるとflushされない）。
逆に、forとsingleの入口およびmasterの入口と出口では暗黙のflushは行われない。

int omp_get_num_threads(void);
スレッドの数を返す
int omp_get_thread_num(void);
スレッド番号を返す

void omp_init_lock(omp_lock_t *lock);
ロックを初期化する
void omp_destroy_lock(omp_lock_t *lock);
ロックを終了する
void omp_set_lock(omp_lock_t *lock);
ロックが得られるまで待つ
void omp_unset_lock(omp_lock_t *lock);
ロックを解放する
int omp_test_lock(omp_lock_t *lock);
ロックが得られなければ 0 を返す以外は omp_set_lock に同じ
ネストできるロックのためのデータ構造と関数も準備されている。

このほか，3.0 から task という構文が追加されている．

使用上の注意

OpenMP は比較的シンプルな並列化を想定しているようである。 Fuzzy barrier や一対一の同期は提供されていない。また、配列に対するリダクションも C 言語版には含まれていないようである（fortran にはあるという話）。

OpenMP のプログラムは、指示行を無視してやれば逐次処理のコンパイラで動くのが特徴である。これは結構デバッグの役に立つので、関数などを使って明示的な処理をする場合にも _OPENMP マクロなどをうまく使って、逐次実行ができるように工夫するべきである。

parallel 指示行とその他の指示行とが、異なる関数に含まれていても良い。parallel 指示行の静的なスコープに入っていない指示行を orphan directive と呼び、これらは parallel 指示の範囲外であれば無視される。

私有変数

一般的に変数のそれぞれが私有なのか共有なのかには十分な注意が必要である。私有のつもりで共有変数を使うと、とんでもない結果が簡単に出てしまう。これは OpenMP で陥りやすいバグである．

3.0 から「私有変数」と「スレッド私有変数」というビミョ～なものが導入された．しかもそれ以前と互換性がない．私有変数を使わないことはできないので，スレッド私有変数を活用しないことをお勧めする．

parallel ブロックを一つの関数にしてしまうと間違いがすくないようである。

私有変数のデータを他のスレッドに送るには、「通信」のための共有変数を準備しておく必要がある。これは結構面倒くさい。

同期

共有メモリを介してデータをやり取りする場合には、生産者のデータが確実にメモリに書き込まれたことを確認するまで消費者は読出しを待つ必要がある。この待ち合わせが同期である。

データ並列のような並列処理の場合には、バリア同期で事が足りることが多い。すなわち、

それぞれのスレッドが「送信」データをメモリに書きこむ
バリア同期を取る
それぞれのスレッドが「受信」データをメモリから読み出す
バリア同期を取る

のように行うのである。最後のバリア同期は、消費者が読み出し中のメモリ領域に生産者が次のデータを書きこむことを防ぐために必要である。

タスクプールのような動的なスケジューリングを行う場合には、critical を用いる。さらに手の込んだことがしたい場合には、lock を用いることになる。lock には暗黙の flush が付いていないことに注意。

flush

共有メモリを介してデータをやり取りする場合には、flush は不可欠である。共有変数に volatile を指定すればよさそうに思われるが、実際にはそれでは不充分である。その最大の理由は、

命令スケジューリングや out-of-order 実行
ライトバッファやポストロード
キャッシュ一貫性はあるがレジスタ一貫性はない

のような理由で、プログラムが書いた通りの順序で必ずしも実行されないということである。

そこで提案された解決策が weak consistency model と呼ばれるものである。すなわち、特別な同期命令 (i.e. flush) の前後で実行の順序とメモリアクセスの完了を保証するのである。

デバッグに関して言うと、共有メモリの方が難しいように思われる。分散メモリの場合には，明示的に receive をしなければ他人のデータは自分の計算の邪魔をしない．しかし共有メモリでは相手が予期できない勝手なタイミングで共有メモリ部分にデータを書き込んでくる．タイミングは毎回異なるので，エラーが生じる場所も毎回異なる．だれがどこで書き込んだどのデータが悪いのかを特定するのは非常に難しい．　

最大の救いは、OpenMP のプログラムはうまく書いておけば、そのまま逐次モデルでのコンパイルと実行ができるということである。また、明示的なデータ分散は必ずしも必要ないので、漸進的な並列化が容易であるということである。しかし、以下に示すように、高性能化はかなり難しい。

性能の低下要因とその解決

データローカリティ：キャッシュマシンであれば、データのローカリティが性能に大きな影響を及ぼす。残念ながら、共有メモリのプログラミングは局所性が悪くなる傾向にあるようである。CPU 毎のデータ局所性を改善するには、データの配置を工夫したり、一部を私有化したりする必要がある。これは実質的に「データ分散」を要求することになる。

メモリアクセス衝突：バス結合の SMP では、複数の CPU が同時にメモリをアクセスするとバスの取り合いが生じる。このためメモリアクセスが性能を決めているようなプログラムでは CPU 数を増やした分だけバス性能が実効的に下がり、CPU あたりの性能が下がる。スイッチ結合の SMP の場合にはスループットは確保されるが、同じメモリブロックにアクセスがあれば衝突により遅延が増大する。この問題を解決するには、キャッシュデータの有効利用と、遅延隠蔽のための工夫が必要である。

「通信」遅延：スレッド間でデータをやり取りする場合には「通信」が必要となるのは当然である。これは共有メモリを介して行われるが、キャッシュよりも遅いメモリを通すために、それなりの時間がかかる。共有メモリハードウェアであっても、できるだけ「通信」量は減らすような工夫をしたほうが良い。

False sharing：キャッシュの一貫性は、通常ライン単位で行われている。実際にデータをやり取りするつもりでなくても、偶然同じラインに乗ってしまったデータを異なる CPU がアクセスすれば、キャッシュの一貫性操作が行われ、性能が下がることになる。これが false sharing である。私有データのメモリ上の配置に工夫をする必要がある。

同期などのオーバーヘッド：同期や flush、スレッドの生成などは、並列化しなければ必要ない部分であるから、純粋な並列化オーバーヘッドである。できるだけこれらは減らしたいところであるが、無理をするとバグを発生するもとになる。安全のために多めに同期をいれてしまうことが多い。

負荷の不均衡：負荷の不均衡は、メモリモデルによらずに並列性能に影響を及ぼす。共有メモリの場合、false sharing やメモリアクセス衝突のような、定量的に予測しにくい要因でスレッド毎の実行時間に違いが出てくる。このため、計算量だけ考えても完全な負荷の均衡化が実現できないという問題が発生する。

読み出し型の情報交換：分散メモリでは，データを生成したプロセッサが，それを必要としているプロセッサに送ってやる書き込み型の情報交換となっている．従って，データの転送は１回で済む．共有メモリでは，データを使用するプロセッサがそれを持っているプロセッサにデータを要求する．従って，データの要求とデータの転送の２回の通信が必要となる．また，キャッシュライン単位の転送となるため，必要以上のデータが送られることも多い．

性能評価の難しさ：分散メモリでは，性能の劣化の原因となるのは負荷の不均衡とメッセージ通信のオーバヘッドである．これらのものは（かなり複雑な場合もあるが）それなりの精度で予測できる．それ以外に通信遅延の隠蔽やキャッシュヒットの向上などで思わぬ性能向上が得られる場合が多い．共有メモリでは，性能劣化の原因は負荷の不均衡と同期のオーバーヘッドのほか，キャッシュミスヒットの増大や false sharing がある．同期のオーバーヘッドは小さいが，キャッシュミスが性能におよぼす影響は評価が難しく，予想外に性能が伸び悩むことになる．