計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」

Presentation on theme: "計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」"— Presentation transcript:

1 計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
2004年7月6日 杉原研究室 山本有作 日立製作所の山本有作です。 「～」について発表いたします。

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

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

4 それでは，一般的な科学技術計算のプログラムでは，ピーク性能の何％程度を発揮できているか？
例：　連立一次方程式を解くためのガウスの消去法 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%

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

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

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

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

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

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

11 キャッシュの再利用性を高める最適化（キャッシュブロッキング）
行列を部分行列（１個が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

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

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

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

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

16 その他の行列乗算の高速化手法 Strassenのアルゴリズム A，B，Cをそれぞれ２×２に分割して乗算を行う。 乗算の回数を7/8に削減可能
Strassenのアルゴリズムで現れる小行列の乗算に再帰的にStrassenのアルゴリズムを使うことにより，計算量を更に削減可能

17 Strassenのアルゴリズム P1 = (A11+A22) (B11+B22) P2 = (A21+A22) B11
P3 = A11 (B12 – B22) P4 = A22 (B21 – B11) P5 = (A11+A12) B22 P6 = (A21 – A11) (B11+B12) P7 = (A12 – A22) (B21+B22) C11 = P1 + P4 – P5 + P7 C12 = P3 + P5 C21 = P2 + P4 C22 = P1 + P3 – P2 + P6

18 ガウスの消去法を行列乗算を用いて書き直してみる。
行列乗算の応用 行列乗算は，高度な最適化が可能であり，性能も高い。 他のアルゴリズムも行列乗算を用いて計算を行うように書き直すことができれば，BLAS や ATLAS を用いて高速化が可能 ガウスの消去法を行列乗算を用いて書き直してみる。

19 行列乗算を用いたガウスの消去法の性能 n=1000のとき，ピークの65%以上の性能を達成