分散メモリ型スパースソルバの開発と評価

計算理工学基礎
「ハイパフォーマンスコンピューティングの基
礎」
2005年4月19日
計算数理グループ
山本有作
ハイパフォーマンスコンピューティング（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
do i=k+1, n
a(i,j)=a(i,j)–a(i,k)*a(k,j)
end do
end do
end do
• n=1000のとき，Opteronでの性能はピークの何％？
10%
30%
50%
80%
Opteronでの性能測定結果
• n=1000 での性能は225MFLOPS（ピークの7%）
• n が大きくなるにつれ，性能は低下
Performance (MFLOPS)
3500
3000
Gaussian elimination
peak performance
2500
2000
1500
1000
500
0
100
200
300
400
500
600
700
800
900
1000
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
end do
end do
• 性能 = 77.7MFLOPS （Opteron 1.6GHz，n=500）
• ピーク性能の2.4%
レジスタの再利用性を高める最適化（レジスタブロッキング）
•
•
•
•
→
→
→
→
iのループを２倍展開
i, jの各ループを２倍展開
iを４倍，jを２倍展開
i, jの各ループを４倍展開
162.8MFLOPS
240.8MFLOPS
324.7MFLOPS
495.5MFLOPS
500
450
performance
400
350
300
250
200
150
100
50
0
1×1
2×1
2×2
4×2
4×4
キャッシュの再利用性を高める最適化（キャッシュブロッキング）
• 行列を部分行列（１個がL×L）に分割
• 部分行列単位で乗算を行う。
• Lは部分行列３個がキャッシュに格納できるサイズに取る。
do I=1, n/L
do J=1, n/L
CIJ=0
do K=1, n/L
CIJ=CIJ + AIKBKJ
end do
end do
end do
• 演算量は同じだが，主メモリへのアクセス回数が約1/Lに減少する。
キャッシュブロッキングの効果
800
performance
700
600
500
400
300
200
100
0
1
8
20
40
100
200
500
Block size
これまでに説明した最適化手法の限界
• レジスタブロッキングとキャッシュブロッキングの併用により，行列乗
算の性能は800MFLOSまで向上できた。
• しかし，ピーク性能に対しては，まだ25%に過ぎない。
• その理由
– 実際のプロセッサでは，キャッシュが２階層になっている。
– データ転送速度だけでなく，アクセス遅延時間も考慮した最適化が必要，
など。
• 性能を最大限に引き出すには，これらの点も考慮した最適化が必要
BLAS （Basic Linear Algebra Subprograms）
• 行列乗算をはじめとする基本的な行列演算については，BLASと呼
ばれる最適化済みのライブラリが各プロセッサに対して提供されて
いる。
• BLASの機能
– 行列乗算
– 行列とベクトルの積
– ベクトルの和，内積，など。
• ATLAS（Automatically Tuned Linear Algebra Subprograms）
– 自分で自分を最適化するBLAS
– インストール時に，ループ展開のサイズやキャッシュブロッキングのサイ
ズなどの最適値を自分で探し，設定。
ATLASの性能
• n=1000のとき，ピーク性能の95%以上を達成している。
3500
3000
2500
hand-coded
ATLAS
peak performance
2000
1500
1000
500
0
100
200
300
400
500
600
700
800
900
1000
その他の行列乗算の高速化手法
• Strassenのアルゴリズム
– A，B，Cをそれぞれ２×２に分割して乗算を行う。
– 乗算の回数を7/8に削減可能
– Strassenのアルゴリズムで現れる小行列の乗算に再帰的に
Strassenのアルゴリズムを使うことにより，計算量を更に削減可能
Strassenのアルゴリズム
C11 C12  A11 A12  B11 B12




C 21 C 22  A21 A22 B21 B22
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%以上の性能を達成
3500
3000
2500
2000
Gaussian elimination
1500
peak performance
1000
blocked Gaussian +
ATLAS
500
0
100
200
300
400
500
600
700
800
900
1000

Download Report