応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング 応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング 2006年4月13日 計算理工学専攻　張研究室 山本有作 日立製作所の山本有作です。 「～」について発表いたします。

計算科学・工学における大規模シミュレーション 流体計算 電子状態計算 構造解析 電子状態計算 数万～数億の自由度を持つ超多自由度の系 解析のために多大な計算機パワーが必要

最新の計算機を効率的に使うには アーキテクチャの理解と最適化手法の習得 線形計算の高速化 最新の計算機がどんな原理で高速化を実現しているかを理解し，その高速性を引き出すための手法を学ぶことが必要 線形計算の高速化 科学技術計算では，計算の大部分が線形計算に帰着されることが多い。 その高速化は重要な課題 ファイナンス理論では，確率論をはじめとする数学が大きな役割を果たす。 更に，実際の問題に適用するには，数値計算が必須。 そのため，数学出身者が多い。 金融工学とも呼ばれる。

授業の目標 最新の計算機で大規模な計算を高速に行うための技法について学ぶ。 線形計算のための高速アルゴリズムについて学ぶ。 生協の書籍部の数学の棚に行くと，金融工学と呼ばれる本がたくさん並んでいる。 ブラック＝ショールズという名前のついた本もたくさん見つかるはず。

授業の構成 高性能計算のための計算機アーキテクチャ RISCプロセッサにおける高性能計算の手法 並列計算機における高性能計算の手法 連立一次方程式の高性能解法（密行列の場合） 連立一次方程式の高性能解法（疎行列の場合） 固有値計算の高性能化手法 高速フーリエ変換の高性能化手法 前のスライドで述べたようなことを念頭におきながら，次のような解法を勉強する。

テーマ間の関連 高性能計算のための計算機アーキテクチャ RISCプロセッサにおける高性能計算の手法 並列計算機における 高性能計算の手法 連立一次方程式 （密行列） 連立一次方程式 （疎行列） 固有値計算 高速フーリエ 変換 ・関連図を示す。 ・実は必ずしも矢印の根元から先の方へ，授業が進むわけではない。親しみやすいトピックから先に話をしたり，あるいは，偏微分方程式のように，物理的な重要性がわかりやすい問題から先に話をして，それに必要な計算法として，連立一次方程式の話をすることもある。 ・ただし，各回の授業を聞くに当たっては，この図を思い出して，その回で勉強したことがどんなふうに使われるのかを頭に置いて欲しい。 グループ発表

授業の進め方(1) レポート グループ発表 ３回出題予定 そのうち２回を選んで提出 提出は授業後２週間以内に３号館南305号室まで 最後の２回の授業を使って行う。 ２～３人のグループで１つの発表を行う。 論文を読んでまとめるか，あるいは講義で勉強したことをもとに自分たちで数値実験を行った結果を発表。

授業の進め方(2) 授業ノート 各回の授業内容を担当者（２名）が記録して提出 TeX，テキスト形式，あるいは Word で 提出は授業後１週間以内に 山本のホームページに掲載予定 http://www.na.cse.nagoya-u.ac.jp/~yamamoto 　　 /lectures.html ノート担当はレポート提出１回分とみなす この授業では，新しい試みとして，学生さんによる授業ノート作りをお願いしたい。 ノート担当は，ぜひ積極的に。 こちらで必要な補足などを行ってから，HPに載せる。

授業の進め方(3) 質問シート 2～3回の授業に１回程度，質問シートを提出してもらう。 授業最後の５分間を使い，授業内容でわからなかった点，疑問に思った点を紙に書いて提出 質問が多かった点について，次回の授業の最初に補足説明を行う。 その回の授業内容をどれだけ理解してもらったか，フィードバックが欲しい。

授業の進め方(4) スーパーコンピューティング実習との連携 この授業を受ける人は，同時に「計算科学フロンティア特別講義：並列計算特論」も受けることを勧めます。 これにより，名大のスーパーコンピュータが授業用に利用可能 その回の授業内容をどれだけ理解してもらったか，フィードバックが欲しい。

授業の進め方(5) 連絡先 ３号館南305号室 山本まで あるいはメールで ３号館南305号室　山本まで あるいはメールで 　　yamamoto@na.cse.nagoya-u.ac.jp　まで

参考書 J. Demmel: Applied Numerical Linear Algebra, SIAM, 1997. G. H. Golub & C. F. van Loan: Matrix Computations, 3rd Edition, Johns Hopkins Univ. Press, 1996. K. A. Gallivan et al.: Parallel Algorithms for Matrix Computations, SIAM, 1994. 今野先生の本は，本講義で扱うテーマの概要を知るには大変お勧め。 講義はOption Pricing の本に沿う。ただし，確率論の基礎についてもう少し簡単なところから述べる。

ハイパフォーマンスコンピューティング（HPC）技術とは 大規模な計算を高速かつ高精度に行うための技術 HPC技術の内容 高速・高精度な計算アルゴリズム 単体プロセッサ向けの性能最適化技術 並列化技術 ネットワーク・GRID技術

PC向けプロセッサの クロック周波数の向上 周波数は10年間で約50倍も向上 たとえば AMD Opteronプロセッサ（1.6GHz）の場合，１秒間に最高で32億回の浮動小数点演算を実行可能 　　（3200MFLOPSのピーク性能）

それでは，一般的な科学技術計算のプログラムでは，ピーク性能の何％程度を発揮できているか？ 例：　連立一次方程式を解くためのガウスの消去法 do k=1, n do i=k+1, n a(i,k)=a(i,k)/a(k,k) end do do j=k+1, n a(i,j)=a(i,j)–a(i,k)*a(k,j) n=1000のとき，Opteronでの性能はピークの何％？ 10% 30% 50% 80%

Opteronでの性能測定結果 n=1000 での性能は225MFLOPS（ピークの7%） n が大きくなるにつれ，性能は低下 Performance (MFLOPS) n

ピークよりはるか下の性能しか得られない原因は？ 最大の要因は，データ転送速度のネック 計算を行うには，主メモリに格納されているデータをプロセッサ内の演算器に転送する必要あり。 演算器は十分速いが，データを供給する速度が追い付かない。 それでは，データ転送速度のネックを解消するにはどうすればよいか？ 　　まず，プロセッサのアーキテクチャを知る必要がある。

典型的なマイクロプロセッサのメモリ階層 演算器に近い記憶装置ほど高速だが，容量は小さい。 演算器と主メモリの速度差は，年々大きくなっている。 データ転送速度 非常に大 レジスタ 演算器 8～128 ワード データ転送速度大 キャッシュ 数100Kバイト ～ 数Mバイト データ転送速度小 ラインサイズ 主メモリ 数100Mバイト ～ 数Gバイト 演算器に近い記憶装置ほど高速だが，容量は小さい。 演算器と主メモリの速度差は，年々大きくなっている。

性能最適化の原理 データがレジスタ中にあれば，演算器は最高速度で計算が可能 　 いったんデータをレジスタに持ってきたら，そのデータに対して必要な計算を集中して行うよう，計算の順序を変更する。 　 （データ参照の局所性を高める。） キャッシュと主メモリについても，同じ方針で最適化を行う。

性能最適化の具体例 もっとも単純なアルゴリズムである行列乗算 C=AB に対して最適化を行う。 最適化前のプログラム do i=1, n do j=1, n sum=0.0d0 do k=1, n sum=sum+a(i,k)*b(k,j) end do c(i,j)=sum 性能 = 77.7MFLOPS （Opteron 1.6GHz，n=500） ピーク性能の2.4%

レジスタの再利用性を高める最適化（レジスタブロッキング） iのループを２倍展開 →　 162.8MFLOPS i, jの各ループを２倍展開 → 240.8MFLOPS iを４倍，jを２倍展開 → 324.7MFLOPS i, jの各ループを４倍展開 → 495.5MFLOPS

キャッシュの再利用性を高める最適化（キャッシュブロッキング） 行列を部分行列（１個がL×L）に分割 部分行列単位で乗算を行う。 Lは部分行列３個がキャッシュに格納できるサイズに取る。 演算量は同じだが，主メモリへのアクセス回数が約1/Lに減少する。 do I=1, n/L do J=1, n/L CIJ=0 do K=1, n/L CIJ=CIJ + AIKBKJ end do

キャッシュブロッキングの効果 Block size

これまでに説明した最適化手法の限界 レジスタブロッキングとキャッシュブロッキングの併用により，行列乗算の性能は800MFLOSまで向上できた。 しかし，ピーク性能に対しては，まだ25%に過ぎない。 その理由 実際のプロセッサでは，キャッシュが２階層になっている。 データ転送速度だけでなく，アクセス遅延時間も考慮した最適化が必要，など。 性能を最大限に引き出すには，これらの点も考慮した最適化が必要

BLAS （Basic Linear Algebra Subprograms） 行列乗算 行列とベクトルの積 ベクトルの和，内積，など。 ATLAS（Automatically Tuned Linear Algebra Subprograms） 自分で自分を最適化するBLAS インストール時に，ループ展開のサイズやキャッシュブロッキングのサイズなどの最適値を自分で探し，設定。

ATLASの性能 n=1000のとき，ピーク性能の95%以上を達成している。