生物情報実験法 (オンライン, 4/20)

Transcription

1 生物情報実験法 (7/23) 笠原雅弘

2 Table of Contents スレッドの使い方 OpenMP プログラミング

3 Deadline The deadline is Aug 5 23:59 Your must have reached my box at the deadline time. It may take a couple of hours to send an . Even if you are not able to hand in assignments in time, we accept late submissions (although with some penalty in grades) so you should try. You should try optional assignments if you have time.

4 スレッドとは アプリケーションにおいて 複数の実行コンテキストを作るための仕組み 大雑把に言うと プログラムが実行される 流れ を複数にする仕組み プログラム起動 時間軸 スレッド 1 動作 生成 合流 スレッド 2 動作 合流 生成 スレッド 3 動作 プログラム終了

5 スレッド生成 (Windows) スレッドを作成する 本来であれば要エラー対策 2 つのスレッドの合流を待つ. と * の表示順は実行するごとに異なる可能性がある

6 スレッド生成 (Linux)

7 クラスインスタンスを スレッドに渡す static 関数のみ CreateThread の引数に渡すことができる 予めデータは s に格納 スレッドには引数は 1 つしか渡せない

8 マルチスレッドで配列をクリア 複数の CPU を用いてスピードアップ 大きな配列 スレッド 0 が担当して配列をクリア スレッド 1 が担当して配列をクリア スレッド n-1 が担当して配列をクリア

9 配列クリアの実装 (1/2) 使用するスレッド数 ( CPU コア数 ) 何番目のスレッドか (0 NUM_THREADS 1) を記憶クリアしたい配列の先頭アドレスクリアしたい配列のサイズ (int が 3 要素なら 3 が入る ) スレッドの番号と配列の先頭アドレス 配列のサイズを記憶 自スレッドが担当する範囲を計算する [startp, endp) 実際に配列をクリアする

10 配列クリアの実装 (2/2) 今回用いる配列のサイズ NUM_THREADS 個のスレッドを生成 全てのスレッドと合流するまで待つ 0 クリアされていない要素が見つかったらエラーを表示する

11 大きな配列要素の和を計算する スレッドごとに担当領域の部分和を計算し 最後に部分和の和を計算 大きな配列 スレッド 0 が担当して部分和計算 スレッド 1 が担当して部分和計算 スレッド n-1 が担当して部分和計算 部分和 部分和 部分和 最後に全体の和を計算

12 必要に応じてここで mutex や CriticalSection を用いる 自分で並列プログラムを 書く際の指針 なるべく同期はしないほうが良い mutex のロックは速くない 例えば lock 命令は実行がかなり遅い 配列の総和を計算する場合の例 自スレッド担当分の和をローカルに計算 全体の和は最後に計算すると良い local_sum の計算はスレッド毎に独立していて干渉しない

13 CPU cache とマルチスレッド メモリへの書き込みが起こると 書き込みを行っていない CPU はそのアドレスのキャッシュを破棄する必要がある CPU1 が変数 a を読み込み キャッシュ CPU2 が変数 a を読み込み キャッシュ CPU1 が変数 a に書き込み CPU2 は変数 a のキャッシュを捨てる CPU1 CPU2 分かった! 手持ちの変数 a の値は捨てとく! 変数 a は書き込んだから値が変わってるよ!

14 キャッシュラインと False Sharing 同じキャッシュラインに含まれる変数 a と b に対して複数の CPU から書き込みを行うとお互いにの CPU キャッシュを無効化してしまい 実効効率が悪化 変数 a と b を格納しているアドレスを 64 で割った商が同じ場合には同一キャッシュラインの上に載っている 本当は複数の CPU コアから共有していない変数を 共有 してしまってキャッシュが実質的に効かなくなる現象を False Sharing と言う CPU1 CPU2 変数 b も同じラインに乗っているから値を捨てないと 変数 a は書き込んだから値が変わってるよ!

15 スレッドプログラミングの 問題点 記述が面倒 プログラムが長くなる 既存のプログラムの並列化にもかなりの時間を要するのでやる気が削がれる デバッグが面倒 バグが並列化と絡んでいるのか そうでないのか切り分けが難しい 保守が面倒 アルゴリズムを変えにくくなる 変化に弱くなる

16 OpenMP とは何か スレッド並列のプログラムを簡潔 簡便に書くための言語拡張 複数の HPC(High Performance Computing) ベンダーから成る委員会で策定した各社共通仕様 を参考にしてください 言語は Fortran/C++ が対象であり 複数のコンパイラに実装されている 注意 OpenMPI とは名前が非常に良く似ていますが全く異なるものです

17 OpenMP を使うと嬉しいこと 記述が ( スレッドより ) ずっと簡単 プログラムが短く書ける 既存のプログラムを並列化するのも簡単 デバッグが ( スレッドより ) 簡単 コンパイルオプション一つで並列版を非並列版に変更してデバッグできる ( 適切にプログラムされていれば ) 保守が ( スレッドより ) 容易 読みやすくアルゴリズムを変更しやすい

18 OpenMP 対応 C++ コンパイラ Visual C 以降 注意 :Microsoft Visual Studio 20xx Express Edition では使えない! Professional Edition 以降をインストールする Intel C 以降 GCC 以降 Cygwin 環境を用いている人は gcc-4 パッケージを用いても ( 少なくとも手元で試した限りでは ) 動かない 未確認だがかなり昔からサポートしているはずのコンパイラ Sun Studio IBM XL C++ 日立と富士通の C++ コンパイラは知りません

19 OpenMP の思想 シングルスレッド用に書いたプログラムに ディレクティブ を加えてマルチスレッド化する OpenMP 用のプログラムを非 OpenMP 対応コンパイラでコンパイルするとシングルスレッド用のプログラムとして動作する シングルスレッドのプログラムを書いてロジックが正常動作することを確かめてから並列化を行うことができる 最近ゲノム情報処理界隈では使って当たり前のテクニックになってきた 今後は OpenACC の様な GPGPU ハイブリッド並列化が流行っていくのだろう

20 Fork-Join モデル シングルスレッド マルチスレッド (OpenMP) fork join fork join

21 OpenMP のディレクティブ プログラムの頭の方で #include <omp.h> を加える OpenMP を有効にするコンパイルオプションが指定されていないときには OpenMP の関数を全てダミーに置き換える (=OpenMP 無効でもコンパイル可 ) #pragma omp で始まる行が OpenMP のディレクティブ

22 まずは基本の並列化 parallel 指示直後のブロックがマルチスレッドで実行される このブロックを並列リージョンと呼ぶ スレッド数だけ Hello が表示されるはず 何スレッドになるかは環境依存 4 コアのマシンだと通常は 4 スレッド スレッド数の手動設定もできる

23 スレッド数の指定方法 何もしない スレッド数 =CPU コア数になる ( 規格としては実装依存 ) 環境変数 環境変数 OMP_NUM_THREADS にセットした値だけスレッドを起動する OpenMP の関数を呼ぶ omp_set_num_threads(n) を呼ぶと n スレッド起動する parallel ディレクティブにスレッド数を指定する ( 以下の例で 10 スレッド )

24 ループの高速化 // OpenMP の指示構文 ( 直後の for を並列化する指示 ) 4 コアの CPU で実行した場合のイメージ fork 本当はもう少し賢く分割できる i=0~ ARRAY_SIZE/4 i=array_size/4~ ARRAY_SIZE*2/4 i=array_size*2/4~ ARRAY_SIZE*3/4 i=array_size*2/4~ ARRAY_SIZE*4/4 join

25 単純なプログラム例 // OpenMP を用いるプログラムは omp.h を include する // 時間が掛かるように無駄に20 回ループ ( 並列化の威力が分かりやすくなる ) // OpenMP の指示構文 ( 並列化の指示 ) // OpenMP の指示構文 (for 文の並列化 ) // OpenMP の指示構文 (for 文の並列化 )

26 注意点 注意深く書かれた OpenMP のプログラムはシングルスレッドのプログラムとしても有効 正しく並列化されているか確認しないと実はシングルスレッドで動いている可能性がある C/C++ 言語の仕様では #pragma 構文で知らない単語が出てきた場合には単に無視すれば良いことになっている (=OpenMP サポートが無い場合には #pragma omp の行は無いのと同じ ) コンパイラオプションを忘れずに付加する gcc なら fopenmp VC++ なら /openmp 注意 : 付けなくてもコンパイル 実行できてしまう! ( ただし並列化されない )

27 実行例 2 スライド前のプログラムを Windows (Visual Studio) 上で実行した例 タスクマネージャを見ると 4 コアを用いて計算が行われていることが分かる

28 設定 (Windows) Visual Studio の場合

29 設定 (Linux) gcc/icc(g++/icpc) の場合には -fopenmp を付加する

30 並列リージョン内の変数 並列リージョンで宣言した変数は基本的にスレッドに固有のものになる スレッド 0 スレッド 1 スレッド 2 スレッド 3 int a int b int b int b int b

31 スレッド毎に動作を分けたいと きにどうするか? n スレッドで動作しているとき 自分のスレッド番号 (0~n-1) は omp_get_thread_num() で得られる 巨大配列 a を n 分割して 各パートについて和を求める例

32 for ディレクティブ 並列リージョン中に #pragma omp for と書くと 直後の for 文が複数のスレッド用に分割されて実行される 分割方法が見た目で ( コンパイラに ) 分からない難しい for 文はダメ for(int i = 0; i < n; i++) // n がループ内で不変 for(s = a.get(); a.eof(); s = a.get()) ループのイテレーション間に依存関係がある場合もダメ for(i = 1; i < n; i++) a[i] += a[i-1];

33 for の例 この行に注目! ループの範囲は [0, VERY_BIG_SIZE) となっているが OpenMP が勝手にスレッド数分の範囲に分割してくれる

34 大きな配列要素の和を計算する ( 再 ) スレッドごとに担当領域の部分和を計算し 最後に部分和の和を計算 大きな配列 スレッド 0 が担当して部分和計算 スレッド 1 が担当して部分和計算 スレッド n-1 が担当して部分和計算 部分和 部分和 部分和 最後に全体の和を計算

35 配列の和を計算する例

36 for directive のループ分割 ループタスクの分割方法 #pragma omp for schedule(static, 1000) 1000 個ずつに分割し ラウンドロビン方式でスレッドに割り付ける #pragma omp for schedule(dynamic, 1000) 1000 個ずつに分割し 暇なスレッドが分割されたチャンクを処理していく #pragma omp for schedule(guided, 1000) 未処理の配列個数 / スレッド数で分割し 暇なスレッドがチャンクを処理していく #pragma omp for schedule(runtime) 環境変数 OMP_SCHEDULE を見て分割方法を選ぶ

37 for ブロック後の同期 #pragma omp for の対象となる for 文が終わるとスレッド間で同期する 異なるスレッドから同一変数の値を参照したときに異なって見えることは ( 同期後は ) なくなる 同期する時間が惜しい場合は #pragma omp for nowait として for directive に nowait を追加することで同期を省くこともできる

38 reduction 操作 reduction とはある種の構造を持った演算の総称 r = f(, f(f(x1, x2), x3), x4), ), xn) の形 合計を求める r = x1 + x2 + x3 + + xn r = add(, add(add(x1, x2), x3), x4), ), xn) 最大値を求める r = max(,max(max(x1, x2), x3), x4), ), xn) 最小値を求める r = min(,min(min(x1, x2), x3), x4), ), xn) 積を取る r = x1 * x2 * x3 * * xn r = mul(, mul(mul(x1, x2), x3), x4), ), xn)

39 reduction + for を簡潔に記述 #pragma omp for の対象となる for 文が reduction を行う場合には reduction を行う変数名と演算子を指定すると競合問題を自動で解決してくれる e.g.) #pragma omp for reduction(+:sum) 自スレッドに割り当てられた要素のみを先に reduction し 最後に全体変数に reduction する 当然ながら 結合律が成り立たない演算子ではこのような演算は無理である

40 大きな配列要素の reduction スレッドごとに担当領域を reduction し 最後に全体の reduction を計算 大きな配列 スレッド 0 が担当して reduction スレッド 1 が担当して reduction スレッド n-1 が担当して reduction r 0 r 1 r n-1 最後に f(, f(f(r 0, r 1 ), r 2 ), ), r n-1 ) を計算

41 sections ディレクティブ #pragma omp sections ブロックの中に #pragma omp section ブロックを入れると平行して実行してよいタスクを表す #pragma omp sections { #pragma omp section { // DO JOB A } #pragma omp section { // DO JOB B } #pragma omp section { // DO JOB C } } #pragma omp sections #pragma omp section #pragma omp section #pragma omp section

42 同期を伴うディレクティブ 並列リージョン内において #pragma omp master の直後に記述されたブロックはマスタースレッド ( スレッド番号 0) でのみ実行される 並列リージョン内において #pragma omp single の直後に記述されたブロックは ( 最初に到達した )1 つのスレッドでのみ実行される 並列リージョン内において #pragma omp critical の直後に記述されたブロックは直列化されて実行される critical ブロックの内部に入れるスレッドは同時に最大 1 つまでに制限される

43 蛇足 OpenMP が有効になるオプションを付けてコンパイルされた場合には _OPENMP マクロが有効になっている シングルスレッド マルチスレッドでどうしても異なるコードを書きたいときには #ifdef _OPENMP などとしてコードを分けることができる

44 Assignment 1 Write a program that allocates a large array of floating point numbers (double). Fill it with square roots of uniformly random numbers ranging from 0.0 to 1.0, using multiple CPU cores. See how your program scaled with the number of CPU cores. In other words, test your program with 1 to max # of CPU cores, and see the computation time.

45 Assignment 2 Write a program that allocates a large array of integers. Fill it with 0, 1, 2,, size -1, using multiple CPU cores. See how your program scaled with the number of CPU cores. In other words, test your program with 1 to max # of CPU cores, and see the computation time. Maybe your program did not scale well as in the program for Assignment 1. Answer the reason why your program did not scale well with the number of cores.