完全パイプライン化シフト QR 法による実対称三重対角行列の固有値並列計算

研究集会
「超大規模行列の数理的諸問題とその高速解法」
2007 年 3 月 7 日
完全パイプライン化シフト QR 法による
実対称三重対角行列の
固有値並列計算
宮田考史
山本有作
張紹良
名古屋大学大学院工学研究科計算理工学専攻
目次
• はじめに
• 固有値問題の数値解法
– シングルシフト QR 法
• QR 法の並列化
– マルチシフト法
– 遅延シフト法
– 提案法
• 性能差理論解析
• 数値実験
• まとめ
2
はじめに
• 本研究で扱う問題
標準固有値問題
• 計算機を用いた固有値計算
- 行列を扱いやすい形に相似変換
- 固有値は不変
三重対角化
実対称行列
0
0
三重対角行列
対角化
0
0
対角行列
対角成分に固有値
3
シングルシフト QR 法
(1) シングルシフト QR 法
(2) シフトの更新
0
・・・
0
相似変換
0
0
固有値
非対角成分
4
シフトの更新
Wilkinson シフト
右下 2 × 2 の小行列の固有値
シフト
= 右下対角成分に近い値
0
0
0
・・・
0
0
0
シフト
0
シフト
0
シフト = 固有値
固有値の近似度増加
収束を速めるには？
更新された新しいシフトを用いる
5
QR 法の並列化
• マルチシフト法
• 遅延シフト法
• 提案法
6
QR 法の並列化
シングルシフト QR 法の演算順序
左上から右下まで
逐次的に実行
（並列化困難）
複数のシフト
QR 法の 1 反復に相当
マルチシフト法（並列化可能）
例： 2 シフト
シフト 1 ：
計算開始
プロセッサ
2
プロセッサ
1
シフト 2 ：
計算開始
m
m
右下 m × m
小行列の固有値
→ m 個のシフト
7
マルチシフト法の問題点（プロセッサの待ち時間）
計算過程
待ち時
間
同期箇所
PU 1
△ CPU 使用効率
（並列化不向き）
PU 2
Time
①
①
②
③ ④
②
待ち時
間
③
④
8
並列処理の効率化
 マルチシフト法（Z.BAI and J.DEMMEL 1989）
待ち時
間
PU 1
△ CPU 使用効率
（並列化不向き）
PU 2
Time
( Step i-1 )
( Step i )
古いシフト
 遅延シフト法（R. A. Van De Geijn 1993）
PU 1 ・・・・
・・・・
PU 2 ・・・・
○ CPU 使用効率
△ 収束性低下
Time
( Step i-2 )
( Step i-1 )
( Step i )
9
収束性の改善
 遅延シフト法（R. A. Van De Geijn 1993）
PU 1 ・・・・
・・・・
PU 2 ・・・・
○ CPU 使用効率
△ 収束性低下
Time
( Step i-2 )
( Step i-1 )
( Step i )
シフト更新回数増大
（新しいシフト）
 提案法
PU 1 ・・・・
・・・・
PU 2 ・・・・
Time
( Step i-2 )
( Step i-1 )
( Step i )
○ CPU 使用効率
○（？）収束性改善
克服△ シフト計算量増大
10
性能差理論解析
11
解析準備
• 実行時間のモデル化
– 行列サイズ，シフト数（= プロセッサ数）
– 計算機環境固有のパラメータ
– 平均反復回数（実測値）
• マルチシフト法
• 遅延シフト法，提案法
予備的な実験
• 相対誤差 = |予測時間 – 実測時間| / （実測時間）×100
4 種類の計算機環境，8 種類の問題で比較
モデル時間は実測時間とほぼ一致（相対誤差 10 % 程度）
12
解析結果
性能差 = （従来法の実行時間） / （提案法の実行時間）
1.
プロセッサ数増加に伴い，性能差増大
（提案法はより高速に成り得る）
性能差
1.6
名古屋大学
情報連携基盤センター
（n = 200000）
1.4
2.
1.2
1.0
0
4
8
12 16 20 24 28 32 36
マルチシフト法と比較
遅延シフト法と比較
性能差は収束性にのみ依存
（計算機環境に依存しない）
プロセッサ数
プロセッサ数
13
数値実験
14
数値実験
• 評価項目
-
• 実験環境
- 名古屋大学情報連携基盤センター
並列計算機 Fujitsu PRIMEPOWER HPC2500
（SPARC64V 2.0GHz ，Memory 512 GB）
- C 言語 + OpenMP（共有メモリ型並列計算機に実装）
0
- 収束判定条件
0
マシンイプシロン
三重対角行列
15
テスト問題
性能差 1 = （マルチシフト法の実行時間） / （提案法の実行時間）
性能差 2 = （遅延シフト法の実行時間） / （提案法の実行時間）
従来法と同程度
提案法が優勢
16
実験結果
25
1.8
1.05
倍
相対反復演算量
20
高速化率
従来法と同程度
( RANDOM )
15
10
5
1 割減
1.6
1.4
1.2
1.0
0
0
4
8 12 16 20 24 28 32 36
プロセッサ数
マルチシフト法
遅延シフト法
提案法
0
4
8 12 16 20 24 28 32 36
シフト数（
＝プロセッサ数）
• 提案法について
– 高速化率：遅延シフト法と同程度
– 反復回数：遅延シフト法と同程度
17
実験結果
25
相対反復演算量
高速化率
1.8
1.04
倍
20
従来法と同程度
( PARSEC/CO )
15
10
5
1.6
1 割減
1.4
1.2
1.0
0
0
4
8 12 16 20 24 28 32 36
プロセッサ数
マルチシフト法
遅延シフト法
提案法
0
4
8 12 16 20 24 28 32 36
シフト数（
＝プロセッサ数）
• 提案法について
– 高速化率：遅延シフト法と同程度
– 反復回数：遅延シフト法と同程度
18
実験結果
1.24
倍
25
2 割減
1.8
相対反復演算量
20
高速化率
提案法が優勢
( SINH-UPPER )
15
10
5
1.6
1.4
1.2
1.0
0
0
4
8 12 16 20 24 28 32 36
プロセッサ数
マルチシフト法
遅延シフト法
提案法
0
4
8 12 16 20 24 28 32 36
シフト数（
＝プロセッサ数）
• 提案法について
– 高速化率：遅延シフト法の 1.2 倍
– 反復回数：遅延シフト法の 2 割減
19
実験結果
1.66
倍
25
3 割減
1.8
相対反復演算量
20
高速化率
提案法が優勢
( TRIDIAG(-1,2,-1) )
15
10
5
1.6
1.4
1.2
1.0
0
0
4
8 12 16 20 24 28 32 36
プロセッサ数
マルチシフト法
遅延シフト法
提案法
0
4
8 12 16 20 24 28 32 36
シフト数（
＝プロセッサ数）
• 提案法について
– 高速化率：遅延シフト法の 1.7 倍
– 反復回数：遅延シフト法の 3 割減
20
まとめ
•
•
本研究では QR 法の並列化を行った．
従来法に対して
1. マルチシフト法に比べて，多くのプロセッサを用いるほど，
提案法はより高速となった．（並列処理の効率化）
2. 遅延シフト法に比べて，提案法は良い収束性を示した．
そのため，遅延シフト法の性能を上回った．
提案法は並列計算機向けの
有力な固有値解法となる可能性がある．
今後の課題
• 収束性の理論解析
• 分散型への実装
21

Download Report