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

(1)

生物情報実験法

(7/23)

笠原_雅弘 ([email protected])

(2)

Deadline



The deadline is Aug 5 23:59

◦ Your e-mail must have reached my e-mail box at the deadline time. It may take a couple of hours to send an e-mail.

◦ 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)

スレッドとは



アプリケーションにおいて、複数の

実行コンテキストを作るための仕組み

◦ 大雑把に言うと、プログラムが実行される「流れ」を複数にする仕組み。プログラム起動プログラム終了スレッド１動作スレッド２動作スレッド３動作生成合流合流生成時間軸

(5)

スレッド生成

(Windows)

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

(6)

(7)

クラスインスタンスを

スレッドに渡す

スレッドには引数は１つしか渡せない。予めデータは s に格納 static 関数のみCreateThread の引数に渡すことができる。

(8)

マルチスレッドで配列をクリア

大きな配列

・・・・スレッド₀ が担当して配列をクリアスレッド₁ が担当して配列をクリアスレッド_n-1 が担当して配列をクリア 

複数の

CPUを用いてスピードアップ。

(9)

配列クリアの実装（

1/2）

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

(10)

配列クリアの実装（

2/2）

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

(11)

大きな配列要素の和を計算する

大きな配列

・・・・スレッド 0 が 担当して部分和計算スレッド 1 が 担当して部分和計算スレッド n-1 が 担当して部分和計算 

スレッドごとに担当領域の部分和を

計算し、最後に部分和の和を計算。

部分和部分和・・部分和・・最後に全体の和を計算

(12)

自分で並列プログラムを

書く際の指針

 なるべく同期はしないほうが良い。 ◦ mutex のロックは速くない。  例えば_{lock 命令は実行がかなり遅い。}  配列の総和を計算する場合の例 ◦ 自スレッド担当分の和をローカルに計算、全体の和は最後に計算すると良い。  local_sum の計算はスレッド毎に独立していて干渉しない ←必要に応じてここで mutex や CriticalSection を用いる。

(13)

CPU cache とマルチスレッド

 メモリへの書き込みが起こると、書き込みを行っていないＣＰＵはそのアドレスのキャッシュを破棄する必要がある ◦ ＣＰＵ１が変数 a を読み込み・キャッシュ ◦ ＣＰＵ２が変数 a を読み込み・キャッシュ ◦ ＣＰＵ１が変数_{a に書き込み}  ＣＰＵ２は変数_{a のキャッシュを捨てる} ＣＰＵ１ＣＰＵ２変数 a は書き込んだから値が変わってるよ！分かった！手持ちの変数 a の値は捨てとく！

(14)

キャッシュラインと

False Sharing

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

(15)

スレッドプログラミングの

問題点



記述が面倒

◦ プログラムが長くなる。 ◦ 既存のプログラムの並列化にもかなりの時間を要するのでやる気が削がれる。 

デバッグが面倒

◦ バグが並列化と絡んでいるのか、そうでないのか切り分けが難しい。 

保守が面倒

◦ アルゴリズムを変えにくくなる。 ◦ 変化に弱くなる。

(16)

OpenMPとは何か



スレッド並列のプログラムを

簡潔・簡便に書くための言語拡張。

◦ 複数の_{HPC(High Performance Computing)ベン} ダーから成る委員会で策定した各社共通仕様 ◦ http://openmp.org/wp/を参考にしてください ◦ 言語は Fortran/C++が対象であり、複数のコンパイラに実装されている。 

注意

◦ OpenMPI とは名前が非常に良く似ていますが全く異なるものです。

(17)

OpenMP を使うと嬉しいこと



記述が（スレッドより）ずっと簡単

◦ プログラムが短く書ける。 ◦ 既存のプログラムを並列化するのも簡単。 

デバッグが（スレッドより）簡単

◦ コンパイルオプション一つで並列版を非並列版に変更してデバッグできる。（※適切にプログラムされていれば。） 

保守が（スレッドより）容易

◦ 読みやすくアルゴリズムを変更しやすい。

(18)

OpenMP対応C++コンパイラ

 Visual C++ 2005 以降

◦ 注意：Microsoft Visual Studio 20xx

Express Edition では使えない！ ◦ Professional Edition 以降をインストールする。  Intel C++ 11.0 以降  GCC 4.3.1 以降 ◦ 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 指示直後のブロックが

マルチスレッドで実行される。

このブロックを並列リージョンと呼ぶ。



何スレッドになるかは環境依存。

◦ 4コアのマシンだと通常は4スレッド。 

スレッド数の手動設定もできる。

スレッド数だけ “Hello” が表示されるはず。

(23)

スレッド数の指定方法



何もしない

◦ スレッド数=CPUコア数になる。（規格としては実装依存。） 

環境変数

◦ 環境変数OMP_NUM_THREADS にセットした値だけスレッドを起動する。 

OpenMP の関数を呼ぶ

◦ omp_set_num_threads(n) を呼ぶと n スレッド起動する。 

parallel ディレクティブにスレッド数を指

定する。（以下の例で

10スレッド。）

(24)

ループの高速化

i=0～ ARRAY_SIZE/4 fork join ４コアのCPUで実行した場合のイメージ 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

// OpenMP の指示構文（直後の for を並列化する指示）

本当はもう少し賢く分割できる。

(25)

単純なプログラム例

// OpenMPを用いるプログラムは omp.h を include する

// OpenMP の指示構文（並列化の指示） // OpenMP の指示構文（for文の並列化）

// OpenMP の指示構文（for文の並列化） // 時間が掛かるように無駄に２０回ループ。（並列化の威力が分かりやすくなる。）

(26)

注意点

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

(27)

実行例



２スライド前のプログラムを

Windows

(Visual Studio) 上で実行した例

◦ タスクマネージャを見ると４コアを

(28)

設定

(Windows)

(29)

設定

(Linux)



gcc/icc(g++/icpc)の場合には

(30)

並列リージョン内の変数



並列リージョンで宣言した変数は

基本的にスレッドに固有のものになる。

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())}

◦ ループのイテレーション間に依存関係がある場合もダメ

(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)

(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

大きな配列

・・・・スレッド 0 が 担当して reduction スレッド 1 が 担当して reduction スレッド n-1 が 担当して reduction 

スレッドごとに担当領域を

reductionし、

最後に全体の

reduction を計算。

r₀ r₁ ・・ r_n-1 ・・最後に f(…, f(f(r₀, r₁), r₂), …), r_n-1) を計算。

(41)

sections ディレクティブ



#pragma omp sections ブロックの中に

#pragma omp section ブロックを入れる

と平行して実行してよいタスクを表す。

#pragma omp section #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 }

(42)

同期を伴うディレクティブ



並列リージョン内において、

#pragma omp master の直後に記述された

ブロックはマスタースレッド

（スレッド番号０）でのみ実行される。



並列リージョン内において、

#pragma omp single の直後に記述された

ブロックは（最初に到達した）１つの

スレッドでのみ実行される。



並列リージョン内において、

#pragma omp critical の直後に記述された

ブロックは直列化されて実行される。

◦ critical ブロックの内部に入れるスレッドは同時に最大１つまでに制限される。

(43)

蛇足



OpenMPが有効になるオプションを

付けてコンパイルされた場合には

_OPENMP マクロが有効になっている

◦ シングルスレッド・マルチスレッドでどうしても異なるコードを書きたいときには #ifdef _OPENMP などとしてコードを分けることができる。

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