並列計算とスパコン
スパコンプログラミング
目 標 高性能計算を学ぶためには、計算機アーキテクチャに始まり、コンパイラやOSといったシステム ソフトウエア、さらに扱っているアプリケーションのアルゴリズムに至る広範な階層の知識が必 要となる。講義でこれらすべてを扱うことはできない。そこで、厳選された実用的な課題について、 講義と演習を行う。本講義は、従来講義のように広い知識の獲得を目指すものではない。実際に高性能プログラムを基盤センタのスーパーコンピュータ上で開発できるという、実用的でかつ、研究者として生き残るために必須な技能の習得を目指すものである。この技能の習得により、受講者の研究を格段に進展させることを目標とする。本講義は通年（夏学期、冬学期）予定されており、夏学期、冬学期ともに同様の講義を行います。 本講義に登録の学生は、国内最高性能を持つ共用のスーパーコンピュータOakforest-PACS、GPUスパコンReedbushが無償で利用できるという特典があります。なお、アカウントの発行のため、履修登録とは別途、事前登録を必要とします。(備考参照)
ガイダンスを2020年9月29日（火）10時25分から予定していますので、 必ず出席をお願いします。
概 要
高性能計算を行うために必須な並列計算プログラミング技法の講義と実習を行う。
並列プログラミングで多く用いられている、MPI（Message Passing Interface）
の入門的な利用技術を 習得する。処理対象は数値計算の基本演算とする。
また、情報基盤センタのスーパコンピュータOakforest-PACS, Reedbush-Hを用いて高性能計算を行う上で
必要となる技法（テクニック、ノウハウ等）についても習得を目指す。
本講義のキーワード
（１）並列計算機入門
i) 並列計算機の種類：分散メモリ型並列計算機とは
ii) 並列プログラミングモデル：SPMDモデルとは
（２）C言語およびFortran言語を用いた並列プログラム作成の基礎
i) 情報基盤センタのスーパーコンピュータの紹介
ii) 通信インタフェースMPI （Message Passing Interface）の概要
（３）高性能プログラミング技法の基礎
i) 配列連続アクセス
ii) ループアンローリング
iii) キャッシュブロック化
iv) 通信隠蔽技法：パイプライン化、通信と計算との重複、など
v) レジスタおよびキャッシュブロックのチューニング など
（４）基礎的な数値計算処理の並列プログラミング
i) 行列演算基本操作
- 行列-ベクトル積
- 行列-行列積
- 行列の転置処理 など
ii) 基礎的な数値計算アルゴリズム
- 密行列の解法：連立一次方程式の解法（密行列LU分解）、
固有値解法（べき乗法） など
（５）発展的話題
i) GPUコンピューティング
演習環境
本演習には、JCAHPCが所有するスーパーコンピュータ Oakforest-PACSシステム、および本学情報基盤センターが所有するReedbush-Hシステムを利用する。 受講者は無料でスーパコンピュータの利用ができる。情報基盤センターの演習室からの利用を行う。
ガイダンス
高性能計算の研究者として生き残るための最低限の技術を習得
1 情報基板センターのスパコンの利用法
2 並列化手法とMPIの使い方
3 高性能計算手法
スパコンはPCの1000倍高速で、1000倍大容量なメモリを持つ計算機
スパコンは多数のCPUを接続することで高性能化
TFLOPS 1秒間に1兆回の浮動小数点演算能力
評価指標
理論ピーク性能
実行性能
アクセラレータというものがあり、現在ではGPUをよく使う
並列プログラミングとは
できるかどうかは対象処理の内容で大きく難しさが異なる
アルゴリズム上、絶対に並列化できない部分の存在
通信のためのオーバヘッドの存在
MPIとはMessage Passing Interface
メッセージ通信用のライブラリ規格
大規模計算が可能
第1講 並列数値処理の基本演算
並列プログラミングは逐次実行のプログラムを何台かの計算機を使って時間を短縮すること
素人考えでは自明だが、実際はできるかどうかは対象処理の内容で大きく難しさが異なる
並列：ある時間に実行されるものは多数
並行：ある論理的に並列（ある時間に実行されるものは１つ）
並列計算木の分類
単一命令・単一データ流(SISD)
単一命令・複数データ流(SIMD)
複数命令・単一データ流(MISD)
複数命令・複数データ流(MIMD)
SIMDとMIMDは生き残っている言葉
MISDはパイプラインとも言えそう
並列計算機のメモリ型による分類
共有メモリ型
分散共有メモリ型
分散メモリ型
プログラムをかくにあたって、プログラムからどう見えているのか
みんながアクセスできるのか、できないのかが重要
共有メモリでは8とか16ぐらいが限界
分散メモリでは互いのメモリはアクセスできないので、通信によってデータのやり取りをプログラムする必要がでてくる
プログラミング手法からみた分類
・マルチスレッド
Pthreads,
・データ並列
OpenMP, Fortran
・タスク並列
Cilk, TBB, Stack Threads
・メッセージ通信
MPI
並列計算きの分類とMPIとの関係
・MPIは分散メモリ型計算機に欠かせない通信ライブラリ
・MPIは共有メモリ型計算機でも動く
共有メモリ上でのプロセス間通信ができる
・MPIを用いたプログラミングモデルは基本的にSIMD的
MPIはプログラムが１つしかないが、データは複数あるので
並列プログラミングのモデル
実際の並列プログラムはMIMDだが、アルゴリズムを考える上ではSIMD的に考える
・SPMD
１つの共通プログラムが並列処理開始時に全プロセッサ上で起動する
・Master/Worker
１つのプロセスが、複数のプロセスを管理する
並列処理の実行形態
・データ並列
データを分割することで並列化する
データの操作は同一となる
これはSIMDの考え方と同じ
・タスク並列
タスクを分割することで並列化する
これの方が難しい
データの操作（演算）が異なるかもしれない
並列プログラム中の実行主体
マルチプロセス
マルチスレッド
アダマールの法則
並列化の効率を上げることがめっちゃ大事だとわかる
Weak ScalingとStrong Scaling
並列処理においてシステム規模を大きくする方法
Weak Scaling：装置あたりの問題サイズを変えず並列度を上げる
Strong Scaling：全体の問題サイズを変えずに並列度を上げる
つまり、Strong Scalingが重要
Byte/Flop
メモリシステムがデータ演算コアに供給する能力、供給できた割合
ピークの5%ぐらいしか使えないのでこれを上げるためにキャッシュという機能がある
基本演算
逐次処理ではデータ構造が重要
並列処理においてはデータ分散方法が重要になる
・各PEの演算負荷を均等にする
・各PEの利用メモリ量を均等にする
・演算に伴う通信時間を短縮する
行列とベクトルの積
C言語とFortranの違い
MPI
並列プログラミングのための標準メッセージ通信インターフェース
共有しているメモリがないというモデルの上で明示的に通信を書くためのライブラリ
メッセージパッシング用のライブラリ企画の１つ
分散メモリ型計算機で並列実行に向き
スケーラビリティ、性能が高い
現在はMPI-3.1
昔のコードも動く
MPI-4.0を策定中
ハイブリッドプログラミングへの対応や対故障性への対応を検討中
実装としては、MPICHとOpenMPIが２強
MPIによる通信
郵便物の郵送に同じ
自分認識IDおよび相手の認識ID
データ格納先のアドレス
データ型
データ量
タグ番号（同じ相手先と複数のやり取りをするときに間違わないように）
MPI関数
システム関数
1対1通信関数
1対全通信関数
集団通信関数
コミュニケータ
プロセスのグループを定義したもの
略語とMPI用語
MPIはプロセス間の通信を行う
プロセスはHTを使わなければプロセッサに１対１で割り当てられる
ランクとは、各MPIプロセスの識別番号のこと、重要
MPI関数
MPIは基本的に関数の集合
PythonとかJavaでも使えるが言語仕様的にはCとFortran
C言語インタフェースとFortranインターフェースでは大文字小文字の区別がある
MPI_Bcastの概念（集団通信）
みんなが同じように関数を呼ばないといけない
リダクション演算
MPIプログラム実例
実行ファイルは１つ
MPIではラッパープログラムというものを使って動かす
mpirunとmpiexecがあって、使い分けることがある
MPIプロセスの割り当て
MPI関数は大きく分けると２つ
send receive１対１で明示的にやるもの
コミュニケーター全体で通信するもの
第2講 ログイン処理、テストプログラム実行
ログイン作業
ssh
暗号化や認証の技術により、遠隔のシステムとの間で安全な通信をするためのプロトコル、コマンド群
公開鍵暗号方式でユーザ・ホストの認証、共通鍵暗号方式で通信路を暗号化
ssh, scp, sftp
スパコン利用の仕方
サンプルプログラムの実行
並列番Helloをコンパイルする
バッチ処理とは
スパコン環境では通常はインタラクティブ実行はできない
ジョブはバッチ処理で実行する
/homeと/workがあるが、/workのみがノードに見える
rm
ls
cd
cat
make(Makefileがあるとき)
make clean
less(catで画面がいっぱいになるとき)
ジョブ実行形態
インタラクティブ実行
PCでの実行のようにコマンドを入力して実行する方法
デバッグ用
バッチジョブ実行
バッチジョブシステムに処理を依頼して実行する方法
スパコンは基本バッチジョブ実行
２つのメモリモードがあるが、Flatモードだけが使える
mpiを使う時のコンパイラはmpiicc
-xMIC-AVX512の最適化をつけると良い
富士通のバッチシステムで管理されている
ジョブを投げる
実行中などの状況を観察できる
68コアあるので、68プロセスあげられる
それを16こ使える
ls -lで大きさもわかる
エラーが出てなければ.eは大きさ0
総和演算
演習課題
レポート課題
第3講 高性能プログラミング技法の基礎1(階層メモリ、ループアンローリング)
今回は１コアでの高速化に焦点を当てる
メモリが重要
次回はノード内複数コアでの並列化
メインメモリからレジスタへの転送コストはレジスタ上のデータアクセスコストの１００倍なのでキャッシュを考える
ソフトウェアにキャッシュはみえていないので、ハードウェアに処理を任せる
/homeと/workがあるが、/workのみがノードに見える
rm
ls
cd
cat
make(Makefileがあるとき)
make clean
less(catで画面がいっぱいになるとき)
ジョブ実行形態
インタラクティブ実行
PCでの実行のようにコマンドを入力して実行する方法
デバッグ用
バッチジョブ実行
バッチジョブシステムに処理を依頼して実行する方法
スパコンは基本バッチジョブ実行
２つのメモリモードがあるが、Flatモードだけが使える
mpiを使う時のコンパイラはmpiicc
-xMIC-AVX512の最適化をつけると良い
富士通のバッチシステムで管理されている
ジョブを投げる
実行中などの状況を観察できる
68コアあるので、68プロセスあげられる
それを16こ使える
ls -lで大きさもわかる
エラーが出てなければ.eは大きさ0
今回は1コアでの高速化について
次回はノード内複数コアでの並列化
階層キャッシュメモリ
レジスタ：1ns
キャッシュ：10ns
メインメモリ：100ns
ハードディスク：10ms
演算パイプライン
どんどん次の作業に行くみたいな感じ
コンピュータアーキテクチャでやった
・ハードウェアパイプライニング
演算処理におけるパイプラインしょり
メモリからデータ転送におけるパイプライン処理
・ソフトウェアパイプライニング
コンパイラが行うパイプライン処理
人手によるコード改編によるパイプライン処理
演算器をフル稼働させるために必要な概念
以下のような問題がある
計算機アーキテクチャの構成による遅延
配列データを参照するためのメモリアドレスの計算処理
コンパイラが正しくパイプライン化される命令を生成するか
実際のプロセッサでは加減算、乗算ごとに独立したパイプラインがある
1クロックあたり最大32回の演算ができる
1コアあたり1.4GHzのクロックなので、理論最大演算は44.8GFLOPS/コア
１ノードでは3.04TFLOPS/ノード
ループアンローリング
コンパイラがやりそうでなかなかやらない
ループを展開することをアンローリングという
コンパイラがレジスタへのデータの割り当てとパイプライニングをやりやすくするためにコードを書き換えるチューニング技法
例えば、nが2の倍数のときは２つずつ進めれば計算量は半分になる
Aikなどの共通部分があるときはそれをtmpという変数に入れてレジスタに置いておけば早くなる 配列連続アクセス
飛び飛びのアクセスには弱い
CとFortranでは配列の格納形式が違う
キャッシュの利用を考える上でプログラミング言語の格納方式を気にするのは普通
キャッシュとキャッシュライン
キャッシュはいくつかセットで管理され、それをキャッシュラインという
メインメモリ上とキャッシュ上のデータマッピング方式
単位ごとに直接的に決めるのがダイレクトマッピング方式、ハッシュ関数で写像するのがセットアソシアティブ方式である
近年はライトバック方式が多い
キャッシュライン衝突が起こるとキャッシュがないのと同じ
演算器にデータが高速に届かず、演算パイプラインが中断して演算器の利用効率が悪くなる
キャッシュラインへのメモリバンク割付は2ベキの感覚で行っていることが多いので、２ベキサイズでの配列確保は避けるべき
パディングというテクニックはわざとずらすということ
メモリインターリービング
物理的なデータ格納方向に連続アクセスするループ構成にする
キャッシュライン衝突への対応
・パディング法：配列に２ベキでない余分な領域を確保して確保配列の一部の領域を使う
・データ圧縮法：
・予測計算法
.eはエラーのファイル
.oは出力ファイル
やばくなったら unset LCなんとかとunset Lang
ループの３、４、５・・・段展開でもOK
少なくとも512の約数
pragma unroll 数字で簡単にアンロールできる
12:10過ぎたらlecture8はサブミットできない
演習課題
レポート課題
第4講 高性能プログラミング技法の基礎2(キャッシュブロック化)
ブロック化
小さい範囲のデータ再利用
キャッシュには大きさがあるので、高速化のためには以下が必要
・キャッシュサイズ限界までデータを詰め込む
・詰め込んだキャッシュ上のデータを何度もアクセスして再利用する
ブロック化によるキャッシュミス削減例
どのキャッシュラインにのるかは配列アクセスパターンと置き換え依存アルゴリズム依存で決まる
ブロック化すると、キャッシュミスが半分以下になることも
配列とキャッシュライン構成の関係
6重ループにする
その他の高速化技術
共通部分式の削除
temp = a + b;などとおく
配列のアクセスのときも
コードの移動
割り算は演算時間がかかるので、掛け算かして書くのが良い
ループ中のif文
なるべくループ中にif文を書かない
ソフトウェア・パイプライニングの強化
定義と参照の距離が近いとソフトウェア的には何も出来ない
定義と参照の距離が遠いとソフトウェアパイプライニングが適用できる機会が増加
OpenMP超入門
指示文による簡単並列化
OpenMPは共有メモリ計算機のためのプログラム言語
OpenMPとは共有メモリ型並列計算機ようにプログラムを並列化する
・指示文
・ライブラリ
・環境変数
を規格化したもの
ユーザが、並列プログラムの実行をさせるための指示を与えるためのものであり、コンパイラによる自動並列化ではない
MPIなどに比べてデータ分散の処理の手間がない分、実装が簡単
OpenMPとマルチコア計算機
スレッド並列化を行うプログラミングモデル
８スレッドを超えるスレッド実行で高い並列化効率を確保するにはプログラミングの工夫が必要
ノード間の並列化はOpenMPではできない
ノード間の並列化にはMPIを用いる
自動並列化コンパイラもスレッド並列化のみ
スレッド数はOMP_NUM_THREADSで指定する
代表的な指示文
まずは#pragma omp parallel
work sharing構文
parallel指示文のように複数のスレッドで実行する場合においてOpenMPで並列を記載する処理の部分を並列領域と呼ぶ
1 並列領域内で記載するもの(for構文、section構文など)
2 parallel指示文と組み合わせるもの(paralle for構文など)
For構文
指示文を書くループが並列化しても正しい結果になることをユーザが保証する
Sections構文
オーソドックス
Critical補助指示文
ある瞬間には１つのスレッドしか実行しないことを保証
Criticalセクションのことかな
Private補助指示文
共有領域に置くよりはプライベート領域においた方が早い
こういうものは共有せずにプライベートにする
例えば、二重ループでprivate(j)がないと各スレッドが別々にjを計算してしまう
リダクション補助指示文
内積値など、スレッド並列の結果を足し込み、１つの結果を得たい場合に利用する
reduction補助指示文がないと、ddotは共有変数になるため、並列実行で逐次の結果と合わなくなる
最後に総和をとるという高速化もある
よく使うOpenMPの関数
omp_get_num_threads：最大スレッド数取得関数
omp_get_wtime()：時間測定
その他の構文
Single構文
Single補助指示文で指定されたブロックをどれか１つのスレッドに割り当てる
どのスレッドに割り当てるかは予測できない
Master構文
マスタースレッドにブロックの内容を割り当てる
通常はSingleを使う
Flush構文
物理メモリとの一貫性をとる
Threadprivate構文
スレッドごとに
スケジューリング
最適な割り当て感覚は計算機と対象となる処理に依存する
以上の割り当てを行う補助し自分が用意されている
各スレッドで担当したループに対する計算負荷が等しくないとだめ
負荷分散を改善するには、短く切ってサイクリックに割り当てる
また、動的に終わった順に割り当てるなどができれば良い
ループスケジューリングの補助指示文
ループ長をチャンクサイズで分割し、
ループスケジューリングにおけるプログラミング上の注意
事前に負荷分散が均衡となるループ範囲を調べた上でstaticスケジューリングを使うと最も効率が良い可能性がある
OpenMPのプログラミング上の注意
OpenMPの並列化はparalell構文を用いた単純なforループ並列化が主になることが多い
parallel構文による並列化はprivate補助指示文の正しい使い方を理解しないとバグが生じる
OpenMPでは対象となる直近のループ変数以外はprivate変数で指定しない限り全て共有変数になる
Parallel doを連続して使うよりも
Parallelを大きくとって中にdoを入れるのもあり
parallel構文の入れ子に関する注意
Critical補助指示文による速度低下
OpenMPを用いた並列化の欠点
サンプルプログラム実行
演習課題
レポート課題
第5講 行列-ベクトル積の並列化
演習のようなもの
データ分散方式と順番を組み合わせる
MPIでは、データをどのように分散するかを自分で考える必要がある
第6講 冪乗法の並列化
冪乗法は簡単な簡単な数値アルゴリズム
冪乗法では標準固有値問題の最大固有値とそれに付随する固有ベクトルを計算できる
冪乗法のアルゴリズム
サンプルプログラムの実行
行列積と内積の計算を並列化すれば早くなりそう
並列化の対象のループは１つにし、ループ制御変数を工夫する
第7講 行列-行列積の並列化1
行列-行列積とは実装により性能向上が見込める基本演算
行列積はコンパイラや計算機のベンチマークに使われることが多い
実装方法の違いで性能に大きな差が出る
手ごろな問題である
科学技術計算の特徴がよくでている
行列のせき
各小行列をキャッシュに収まるサイズにする
Cannonのアルゴリズム
Foxのアルゴリズム
SUMMA, PUMMA
Strassenのアルゴリズム
サンプルプログラムの実行
第8講 行列-行列積の並列化2
サンプルプログラムの実行
第9講 LU分解1
ガウス・ジョルダン法
ガウス消去法
内積形式のガウス法のまとめ
枢軸選択
LU分解法
並列化の検討
LUアルゴリズムの逐次アルゴリズムの説明
LU分解法の並列化実習
第10講 LU分解2、非同期通信
来週はGPUのアカウント発行する
１対１通信に関するMPI用語
ブロッキング、ノンブロッキング
ローカル、ノンローカル
通信モード
非同期通信
永続的通信
サンプルプログラムの実行
レポート課題
第11講 RB-Hお試し
GPUプログラミングの紹介
GPUプログラミングは何が難しい？
押さえておくべきGPUの特徴
CPUと独立のGPUメモリ
性能を出すためにはスレッド数 >> コア数
階層的スレッド管理と同期
Warp単位の実行
やってはいけないWarp内分岐
コアレスドアクセス
GPUとCPUのメモリは別
計算する時は、データを送る必要がある
最近のやつはやってくれてるが
計算はCPUから始まる
Warp単位の実行が普通
連続した32スレッドをWarpという
このWarpは足並みを揃えて動く
Warp内での分岐はだめ
コアレスドアクセス
同じWarp内のスレッドが近いアドレスに同時にアクセスするのがメモリの性質上効率的
128バイト単位でアクセス
GPU向けプログラミング環境
CUDA:GPU向け開発環境
OpenACC:指示文を用いて並列化を行うプログラミング環境
コンパイラはPGIが一択
OpenACCとOpenMPの比較
Reedbush-Hの利用開始
OpenACCの指示文
OpenACCへのアプリケーション移植方法
サンプルプログラムの実行
第12講 GPUプログラミング、研究紹介
・Pythonを使った数値計算
・機械学習、深層学習
Reedbushを用いた成果例
ChainerMN
コンテスト
うおおおお
「Numpyがなぜ速いのか」
計算工学ナビ
0回 スパコンって本当にすごいの
シミュレーションによく使われる
1回 スパコンを作ろう
スパコンの主流はクラスタ
長崎大学が制作したDEGIMAは自作パソコンで作られたクラスタマシンでTOP500にのった
ラズパイを16台クラスタリングすれば20年前のスパコンDeep Blueとほぼ互角の性能が出せる
2回 スパコンで遊ぼう
PHASE/0を動かして実感する
比例して性能が上がるわけではない
アダマールの法則がある
3回 並列プログラミング
4回 BareMetal並列計算
「GAE/Goでもgoroutine」
「並列化プログラミング入門」
「Pythonでマルチコア並列処理」
「Pythonの非同期プログラミングを完全理解」
並列数値計算論
並列数値計算論
並列処理を中心とした高性能な計算環境における数値計算のアルゴリズムと手法について講究する。
・並列計算の手法と性能
・高性能数値アルゴリズム
Lectures numerical algorithms and methods for parallel and high performance computing systems.
・Parallel processing methods and performance
・High performance numerical algorithms
1. Architecture and performance
2. Dependency
3. Locality
4. Scheduling
5. MPI
6. Collective communication
7. Distributed data structure
8. Supercomputer How To
9. OpenMP
10. Cache performance
11. Dynamic parallelism
12. GPU and CUDA
13. SIMD performance
東大情報基盤センターの目指す『計算・データ・学習』の融合による革新的スーパーコンピューティング