計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」 2007年5月8日 計算数理グループ　張研究室 山本有作 日立製作所の山本有作です。 「～」について発表いたします。

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

ハイパフォーマンスコンピューティング（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%以上を達成している。

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

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

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

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

並列計算機の種類と特徴 共有メモリ型並列計算機 分散メモリ型並列計算機 SMPクラスタ 情報連携基盤センターの並列計算機 はじめに，研究の背景として，有限要素法とスパースソルバの必要性についてご説明します。

スーパーコンピュータの性能動向 性能 年 2010 2000 1990 1980 1970 1960 1PFLOPS スカラー機 ASCI-5 性能 ベクトル機 ASCI-4 地球ｼﾐｭﾚｰﾀ ベクトル並列機 SR8000 並列機 VPP500 T3E-900 1TFLOPS CM-5 SR2201 nCUBE2 S3800 X-MP 1GFLOPS CRAY-1 S-810 スカラー／ベクトル機 → 並列機 CDC6600 (10 times faster / 20 years) 4 1MFLOPS IBM360/95 年 2010 2000 1990 1980 1970 1960

並列計算機の登場 並列計算機の普及の背景 並列計算機の特長 並列計算機の問題点 プロセッサの動作周波数向上の飽和 専用スーパーコンピュータの設計コストの増加 並列計算機の特長 プロセッサ数を増やすことでピーク性能を無制限に向上可能 分散メモリ型並列機では，プロセッサ数に比例した大きなメモリ空間が利用可能 汎用のプロセッサを使うことで設計コストを大幅に削減可能 並列計算機の問題点 多数のプロセッサを効率良く働かせるには，良い並列化アルゴリズムが必要

並列処理による高速化 複数のプロセッサで処理を分担することにより，プログラムの実行時間を短縮 プログラムの中で並列化対象部分の占める割合が大きいほど，高速化の効果が大きい １プロセッサ 並列計算機

さまざまな並列計算機 共有メモリ型並列計算機（SMP） SMPクラスタ 分散メモリ型並列計算機 地球シミュレータ Itaniumサーバ Power Mac G5 分散メモリ型並列計算機 日立 SR11000 並列計算機の主流は，両者を融合させた形のSMPクラスタへ。 日立 SR2201 PCクラスタ Power Mac G5 クラスタ

チップレベルでの並列処理 最近では，ゲーム機の専用プロセッサが非常に高性能化 Xbox360用プロセッサ： 汎用PCの６倍の性能 PlayStation3用プロセッサ（Cell）：　汎用PCの20倍の性能 これらを数値計算に活用できれば，非常に低コストで 超高速の計算が可能 Cell ﾌﾟﾛｾｯｻ写真 Cell ﾌﾟﾛｾｯｻﾌﾞﾛｯｸ図 （9個のCPUを内蔵） PlayStation3

共有メモリ型並列計算機 構成 特徴 プログラミング言語 複数のプロセッサ（PU）がバスを 通してメモリを共有 　　通してメモリを共有 PUはそれぞれキャッシュを持つ。 特徴 メモリ空間が単一のためプログラミングが容易 PUの数が多すぎると，アクセス競合により性能が低下 　 →　４～８台程度の並列が多い。 プログラミング言語 OpenMP （FORTRAN/C/C++ ＋ 指示文）を使用 キャッシュ PU0 PU1 PU2 PU3 バス メモリ

分散メモリ型並列計算機 構成 特徴 プログラミング言語 各々がメモリを持つ複数のPUを ネットワークで接続 PUはそれぞれキャッシュを持つ。 　　ネットワークで接続 PUはそれぞれキャッシュを持つ。 特徴 数千～数万PU規模の並列が可能 PU間へのデータ分散を意識したプログラミングが必要 プログラミング言語 FORTRAN/C/C++ ＋ MPI を使用 キャッシュ PU0 PU1 PU2 PU3 メモリ ネットワーク

SMPクラスタ 構成 特徴 プログラミング 複数の共有メモリ型並列計算機 （SMP）をネットワークで接続 各ノードの性能を高くできるため，比較的少ないノード数で高性能を達成できる。 プログラミングは，ノード内部の計算では共有メモリ型並列機として，ノードをまたがる計算では分散メモリ型並列機として行う。 プログラミング MPI と OpenMP とを組み合わせて使用 PU0 PU1 PU2 PU3 メモリ PU0 PU1 PU2 PU3 メモリ PU0 PU1 PU2 PU3 メモリ ネットワーク

情報連携基盤センターの並列計算機 富士通 PrimePower HPC2500 （SMPクラスタ） 講義での利用 8GFLOPS／プロセッサ 64プロセッサ／ノード 全24ノード 全体で12TBの主記憶 講義での利用 ID: w49021a ～ w49040a Password: mpi2006 PU0 PU1 PU2 PU3 メモリ ネットワーク

並列アルゴリズムの例 (1) 数値積分によるπの計算 計算の並列化 π =∫0 1 4/(1+x2) dxの積分区間をn等分し，中点則により計算。 計算の並列化 n個の長方形を４個のプロセッサに割り当て，担当する長方形の面積の計算と部分和の計算を各プロセッサが行う。 各プロセッサからの寄与を合計する処理はプロセッサ０が行う。 4/(1+x2) x 1 プロセッサ0 プロセッサ1 プロセッサ2 プロセッサ3

並列アルゴリズムの例 (2) ２次元領域の温度変化の計算 計算の並列化 プロセッサ0 プロセッサ1 各格子点での温度変化を，隣接する４個の格子点との温度差から計算。 計算の並列化 格子を４個の領域に分割し，各領域に属する格子点での温度変化をその領域の担当プロセッサが計算。 プロセッサ2 プロセッサ3

分散メモリ型並列計算機での並列化 分散メモリ プロセッサ間通信 プロセッサ0 プロセッサ1 通信 各プロセッサは固有のメモリ空間を持ち，自分の担当する部分データを格納する。 共有メモリ方式に比べハードが作りやすく，超並列機に向く。 プロセッサ間通信 他プロセッサの持つデータを参照するには，通信が必要。 通信 プロセッサ2 プロセッサ3

分散メモリ型並列計算機での並列化（続き） プロセッサ0 プロセッサ1 プログラム例 通信 PROGRAM HEAT REAL*8 A(4,4) ◆ 初期設定 DO ITER=1, 100 DO I=1, 4 DO J=1, 4 ◆ 必要なら隣接プロセッサ 　　　　　　　　よりAの値を受け取る ◆ A(I,J)の値を更新 END DO ◆ 結果の出力 STOP END プロセッサ2 プロセッサ3

並列化効率の向上 並列実行時間＝演算時間＋通信時間＋待ち時間 並列化効率＝ １プロセッサでの実行時間 pプロセッサでの実行時間 × p プロセッサ０ プロセッサ１ プロセッサ２ プロセッサ３ 時間 ：　演算時間 ：　通信時間 ：　待ち時間