自動チューニング機能付き

計算理工学基礎
「ハイパフォーマンスコンピューティングの基礎」
2005年4月26日
計算数理グループ
山本有作
前回と今回の講義のホームページ
アドレス



http://www.na.cse.nagoya-u.ac.jp/~yamamoto/lectures.html
上記のページで「2005年度前期計算理工学基礎」をクリック
ページは今週末までに作成予定
内容


講義で使ったパワーポイントのファイル
レポート課題と提出方法
ハイパフォーマンスコンピューティング（HPC）技術とは
大規模な計算を高速かつ高精度に行うための技術
HPC技術の内容




高速・高精度な計算アルゴリズム
単体プロセッサ向けの性能最適化技術
並列化技術
ネットワーク・GRID技術
今回の講義の目的
連立一次方程式の解法を例に取り，並列アルゴリズムの
基礎について学ぶ。
もくじ
並列計算機の基礎
簡単な並列アルゴリズムの例
ポアソン方程式の数値解法
ポアソン方程式のための並列アルゴリズム
性能評価
並列計算機の基礎 (1)
スーパーコンピュータの性能動向
1PFLOPS
性能
1TFLOPS
1GFLOPS
スカラー機
ベクトル機
ベクトル並列機
並列機
ASCI-5
ASCI-4
地球ｼﾐｭﾚｰﾀ
SR8000
VPP500
T3E-900
CM-5
SR2201
nCUBE2
S3800
X-MP
S-810
CRAY-1
スカラー／ベクトル機 → 並列機
1MFLOPS
1960
CDC6600
4
(10 times faster / 20 years)
IBM360/95
1970
1980
1990
2000
2010
年
並列計算機の基礎 (2)
並列計算機の普及の背景


プロセッサの動作周波数向上の飽和
専用スーパーコンピュータの設計コストの増加
並列計算機の特長



プロセッサ数を増やすことでピーク性能を無制限に向上可能
分散メモリ型並列機では，プロセッサ数に比例した大きなメモリ
空間が利用可能
汎用のプロセッサを使うことで設計コストを大幅に削減可能
並列計算機の問題点

多数のプロセッサを効率良く働かせるには，良い並列化アルゴリ
ズムが必要
並列計算機の例
共有メモリ型並列計算機（SMP）
SMPクラスタ
地球シミュレータ
Itaniumサーバ
Power Mac G5
分散メモリ型並列計算機
日立 SR11000
日立 SR2201
PCクラスタ
Power Mac G5 クラスタ
並列処理による高速化
複数のプロセッサで処理を分担することにより，プログラムの実行時
間を短縮
前処理，後処理などは１プロセッサで行わなければならない場合が
多い
１プロセッサ
並列計算機
簡単な並列アルゴリズムの例 (1)
数値積分によるπの計算

π =∫0 1 4/(1+x2) dxの積分
区間をn等分し，中点則により
計算
4/(1+x2)
計算の並列化


n個の長方形を４個のプロセッ
サに割り当て，担当する長方
形の面積の計算と部分和の
計算を各プロセッサが行う
各プロセッサからの寄与を合
計する処理はプロセッサ０が
行う
0
プ
ロ
セ
ッ
サ
0
1
プププ
ロロロ
セセセ
ッッッ
サササ
1 2 3
x
簡単な並列アルゴリズムの例 (2-1)
２次元領域の温度変化の計算

各格子点での次のステップの
温度を，隣接する４個の格子
点の温度の平均として計算
プロセッサ0
プロセッサ1
プロセッサ2
プロセッサ3
計算の並列化（分散メモリ型）


格子を４個の領域に分割
各領域に属する格子点の温
度をその領域の担当プロセッ
サが計算
簡単な並列アルゴリズムの例 (2-2)
分散メモリ

プロセッサ0
通信
プロセッサ1
各プロセッサは固有のメモリを
持ち，自分の担当する格子点
の温度データを格納する
プロセッサ間通信


領域境界の格子点の温度の
更新には，他プロセッサの持
つデータが必要
プロセッサ間通信により，必要
なデータの送受信を行う
プロセッサ2
プロセッサ3
簡単な並列アルゴリズムの例 (2-3)
プログラム例
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
END DO
END DO
★ 結果の出力
STOP
END
プロセッサ0
プロセッサ2
通信
プロセッサ1
プロセッサ3
並列化による加速率
並列実行時間＝演算時間＋通信時間＋待ち時間
１プロセッサでの実行時間
加速率＝
pプロセッサでの実行時間
プロセッサ０
プロセッサ１
プロセッサ２
プロセッサ３
時間
：演算時間
：通信時間
：待ち時間
並列計算機で高い性能を得るには
負荷の均等化

各プロセッサの演算量を均等化して待ち時間を削減
通信の削減

ある並列計算機（日立SR2201）における演算性能と通信性能
 演算性能： 3.3ns／浮動小数点演算
 通信性能： 26.4ns／浮動小数点データ
通信は演算に比べ，長い時間がかかる
性能を出すには，通信の削減が必要
ポアソン方程式の数値解法
ポアソン方程式
   u  f ( x, y)
x  y
2
u
2
応用




2
2
熱伝導
静電場
流体力学
応力とひずみの解析
物理的意味

ある点でのu の値 = その周囲でのu の値の平均値 + 外力の項
簡単な例
２次元正方領域での熱伝導方程式
y
   u  f ( x, y)
x  y
2
u
2
2
2
1
u(0, y) = 0
u(1, y) = 0
u(x, 0) = 0
u(x, 1) = 0
0
x
1
２次元ポアソン方程式のオーダリング
５×５の２次元格子
分割を２段階行い，領域を４個の部分領域に分割
格子
行列
1
2
3
4
5
1
3
9
5
7
6
7
8
9
10
2
4
10
6
8
11
12
13
14
15
21
22
23
24
25
16
17
18
19
20
11
13
19
15
17
21
22
23
24
25
12
14
20
16
18
ND法による
オーダリング
ND法による
オーダリング
第１段階での
セパレータ
第２段階での
セパレータ
各対角ブロック
の分解は独立に
実行可能
一般の場合のオーダリング
セパレータ
Nested Dissection 法によるオーダリング
（有限要素法から生じる疎行列の場合）



セパレータと呼ばれる節点集合を取り除くこと
により，メッシュを２つの部分に分割
この分割に従って行列の行・列を並び替え，
行列を縁付きブロック対角形に変形
この処理を各対角ブロックに対して再帰的に
繰り返す
有限要素法メッシュ
0
0
置換後の行列
オーダリングによる並列性抽出


コレスキー分解のステップでは，各対角ブロッ
クを並列に分解可能
各対角ブロックの演算負荷が均等で，かつ縁
の部分が狭い（セパレータに属する節点の個
数が小さい）分割が望ましい
00
1
0
2
3
4
0
5
6
77
３段階の分割後の行列
消去木と演算の並列性
消去木とは


疎行列のコレスキー分解における消去演算の
依存関係を表現するグラフ
消去木の各節点は行列 L の各列に対応
ND法でオーダリングした行列に対する消
去木

再帰的縁付きブロック
対角行列
25
消去木と行列の対応関係
24
 鎖の部分 ⇔ 縁の部分
22
23
21
 部分木 ⇔ 対角ブロック

共通部分を持たない２つの部分木に対する分
解演算は並列に実行可能
10
20
9
19
4
8
14
18
3
7
13
17
2
6
12
16
1
5
11
15
対応する消去木
消去木を用いたデータ割り当て
25
subtree-to-subcube 割り当て


鎖の部分では，周期的に節点をプロセッサに
割り当てる
分岐点でプロセッサ群を２分割し，各部分木を
それぞれのプロセッサ群に割り当てる。この操
作を再帰的に行う
消去木が不均等な場合


単純な subtree-to-subcube 割り当てでは大
きな負荷不均衡が生じる場合あり
subtree-to-subcube 割り当ての改良が必要
24
23
22
21
10
20
9
19
4
8
14
18
3
7
13
17
2
6
12
16
1
5
11
15
コレスキー分解
処理

入力行列
各プロセッサに分散された行列
A を入力として，並列にコレス
キー分解を行う
アルゴリズム

対角ブロックの分解と縁の部分
の計算を，小さいレベルのブロッ
クから順に再帰的に繰り返す
消去木
25
24
４プロセッサで協調
して消去演算
23
22
21
２プロセッサで協調
して消去演算
各プロセッサで
独立に消去演算
（通信なし）
10
20
9
19
4
8
14
18
3
7
13
17
2
6
12
16
1
5
11
15
試作版スパースソルバの性能評価結果
概要

以上のアルゴリズムに基づく並列プログラムを開発し，２種のPC
クラスタ上で性能評価を行った
計算機環境

Alphaクラスタ（mellon）





Alpha EV5 533Mhz ×8ノード
RAM 128MB／ノード
100base-tx 接続
コンパイラは g77 –O3 を使用
Power PC G5クラスタ（muscat）




PowerPC G5 2.0Ghz × 8ノード
RAM 2GB／ノード
Gigabit Ether接続
コンパイラは g77 –O3 を使用
例題
Harwell Boeing Matrix Collectionの５種の行列と，３次元ポアソン方
程式を離散化して得られる行列に対し，コレスキー分解の性能を評価
Title
Discipline
Size(N)
Nonzero
演算量
(Gflop)
3dp24
３次元ポアソン
243
41472
1.15
3dp32
３次元ポアソン
323
98304
6.59
BCSSTK17
Elevated pressure vessel
10974
428650
0.24
BCSSTK18
R.E. Ginna Nuclear Power Station
11948
149090
0.11
BCSSTK29
Buckling model of a Boeing 767 rear
pressure bulkhead
13992
619488
0.66
BCSSTK30
Statics module of an off-shore
generator platform
28924
1036208
1.37
BCSSTK31
Statics module of an automobile
component
35538
608502
1.87
１プロセッサでの実行時間（コレスキー分解
部）
Alphaプロセッサでの実行時間
G5プロセッサでの実行時間
G5 は Alpha の10倍程度高速
Alphaの実行時間は，小嶋秀和「並列化向けスパースソルバの開発」（2005年度計算理工学専攻修士論文）より引用
G5の実行時間は，松井秀樹「並列計算機上におけるスパースソルバの最適化」（2005年度計算理工学セミナーポスター）
より引用
並列実行時の加速率
 3dp24，32，bcsstk30，31は比較的よい結果
 bcsstk29は加速率が低い
 bcsstk17，18は加速率が低いが，問題規模が小さ
いためやむを得ないと考えられる
グラフは，松井秀樹「並列計算機上におけるスパースソルバの最適化」
（2005年度計算理工学セミナーポスター）より引用
消去木による分析
消去木を用いて，各レベルでの負荷分散と演算・通信の
時間比を調べ，性能評価結果を分析
3dp24の場合


負荷分散は比較的良い
→ 加速率良好
上のレベルでの演算が多く，
独立に実行可能な演算が
少ない
→ これを改善すれば，並列
化効率を更に改善可能
レベル0：
全PUで協調
レベル1：
4PUで協調
レベル2：
2PUで協調
レベル3：
各PUが独立に計算
演算時間
グラフは，松井秀樹「並列計算機上におけるスパースソルバの最適化」
（2005年度計算理工学セミナーポスター）より引用
通信時間
面積が時間の長さを表す
消去木による分析（続き）
bcsstk30
・独立に演算できる部分が多い
→ 加速率良好
・負荷分散はやや不均衡
→ これを改善すれば，並列化
効率を更に向上可能
bcsstk29
・演算のほとんどは最上位レベルで，
独立に演算できる部分が少ない
→ 並列化効率の改善には，より
良いオーダリングが必要
消去木を用いて並列性能を解析し，性能改善に役立てることが可能
グラフは，松井秀樹「並列計算機上におけるスパースソルバの最適化」（2005年度計算理工学セミナーポスター）より引用
今後の課題
並列化効率の向上



ND法によるオーダリング部分の改良
データ割り当て方法の改良
通信の隠蔽
単体性能の向上

スーパーノードの利用による消去演算のBLAS2/3化
応用


有限要素法プログラムとの接続
複素対称行列への拡張と固有値解析プログラムとの接続
自動チューニング型ソルバに向けて


並列性能のモデル化
アルゴリズム／性能パラメータの自動最適化

Download Report