Presentation is loading. Please wait.

Presentation is loading. Please wait.

研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.

Similar presentations


Presentation on theme: "研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻."— Presentation transcript:

1 研究集会 「超大規模行列の数理的諸問題とその高速解法」 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻

2 目次 はじめに 固有値問題の数値解法 QR 法の並列化 性能差理論解析 数値実験 まとめ シングルシフト QR 法 マルチシフト法
遅延シフト法 提案法 性能差理論解析 数値実験 まとめ

3 はじめに 本研究で扱う問題 標準固有値問題 計算機を用いた固有値計算 - 行列を扱いやすい形に相似変換 - 固有値は不変 三重対角化 対角化
 本研究で扱う問題 標準固有値問題  計算機を用いた固有値計算 - 行列を扱いやすい形に相似変換 - 固有値は不変 三重対角化 対角化 実対称行列 三重対角行列 対角行列 対角成分に固有値

4 シングルシフト QR 法 シングルシフト QR 法 (2) シフトの更新 ・・・ 相似変換 固有値 非対角成分

5 シフトの更新 収束を速めるには? 更新された新しいシフトを用いる Wilkinson シフト 右下 2 × 2 の小行列の固有値
シフト = 右下対角成分に近い値 ・・・ シフト シフト シフト = 固有値 固有値の近似度増加 収束を速めるには? 更新された新しいシフトを用いる

6 QR 法の並列化  マルチシフト法  遅延シフト法  提案法

7 QR 法の並列化 シングルシフト QR 法の演算順序 マルチシフト法(並列化可能) 左上から右下まで 逐次的に実行 (並列化困難)
複数のシフト マルチシフト法(並列化可能) プロセッサ 2 例: 2 シフト プロセッサ 1 m m 右下 m × m 小行列の固有値 → m 個のシフト シフト 1 : 計算開始 シフト 2 : 計算開始

8 マルチシフト法の問題点 (プロセッサの待ち時間)
計算過程 PU 1 PU 2 Time 待ち時間 △ CPU 使用効率 (並列化不向き) 同期箇所

9 並列処理の効率化 マルチシフト法 (Z.BAI and J.DEMMEL 1989)
待ち時間 PU 1 PU 2 △ CPU 使用効率 (並列化不向き) 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 )

10 収束性の改善 遅延シフト法 (R. A. Van De Geijn 1993) 提案法 克服 PU 1 PU 2 ・・・・ ・・・・
○ CPU 使用効率 △ 収束性低下 ・・・・ Time ( Step i-2 ) ( Step i-1 ) ( Step i ) シフト更新回数増大 (新しいシフト) 提案法 PU 1 PU 2 ・・・・ ( Step i-1 ) ・・・・ ( Step i ) ○ CPU 使用効率 ○(?) 収束性改善 ・・・・ Time ( Step i-2 ) 克服 △ シフト計算量増大

11 性能差理論解析

12 解析準備 実行時間のモデル化 マルチシフト法 遅延シフト法,提案法 行列サイズ,シフト数(= プロセッサ数) 計算機環境固有のパラメータ
平均反復回数(実測値) マルチシフト法 遅延シフト法,提案法 予備的な実験   相対誤差 = |予測時間 – 実測時間| / (実測時間)×100 4 種類の計算機環境,8 種類の問題で比較 モデル時間は実測時間とほぼ一致(相対誤差 10 % 程度)

13 性能差 = (従来法の実行時間) / (提案法の実行時間)
解析結果 性能差 = (従来法の実行時間) / (提案法の実行時間) マルチシフト法と比較 プロセッサ数増加に伴い,性能差増大 (提案法はより高速に成り得る) 遅延シフト法と比較 性能差は収束性にのみ依存 (計算機環境に依存しない) 名古屋大学 情報連携基盤センター (n = ) 性能差 プロセッサ数

14 数値実験

15 数値実験 評価項目 - 実験環境 - 名古屋大学情報連携基盤センター - C 言語 + OpenMP(共有メモリ型並列計算機に実装)
 評価項目 -  実験環境 - 名古屋大学情報連携基盤センター 並列計算機 Fujitsu PRIMEPOWER HPC2500 (SPARC64V 2.0GHz ,Memory 512 GB) - C 言語 + OpenMP(共有メモリ型並列計算機に実装) - 収束判定条件 三重対角行列 マシンイプシロン

16 テスト問題 従来法と同程度 提案法が優勢 性能差 1 = (マルチシフト法の実行時間) / (提案法の実行時間)
性能差 2 = (遅延シフト法の実行時間) / (提案法の実行時間) 提案法が優勢 従来法と同程度

17 実験結果 ( RANDOM ) 従来法と同程度 1.05 倍 1 割減 提案法について 高速化率 : 遅延シフト法と同程度
反復回数 : 遅延シフト法と同程度 マルチシフト法 遅延シフト法 提案法

18 実験結果 ( PARSEC/CO ) 従来法と同程度 1.04 倍 1 割減 提案法について 高速化率 : 遅延シフト法と同程度
反復回数 : 遅延シフト法と同程度 マルチシフト法 遅延シフト法 提案法

19 実験結果 ( SINH-UPPER ) 提案法が優勢 1.24 倍 2 割減 提案法について 高速化率 : 遅延シフト法の 1.2 倍
反復回数 : 遅延シフト法の 2 割減 マルチシフト法 遅延シフト法 提案法

20 実験結果 ( TRIDIAG(-1,2,-1) ) 提案法が優勢 1.66 倍 3 割減 提案法について
高速化率 : 遅延シフト法の 1.7 倍 反復回数 : 遅延シフト法の 3 割減 マルチシフト法 遅延シフト法 提案法

21 まとめ 本研究では QR 法の並列化を行った. 従来法に対して
 従来法に対して マルチシフト法に比べて,多くのプロセッサを用いるほど,提案法はより高速となった.(並列処理の効率化) 遅延シフト法に比べて,提案法は良い収束性を示した. そのため,遅延シフト法の性能を上回った. 提案法は並列計算機向けの 有力な固有値解法となる可能性がある. 今後の課題  収束性の理論解析  分散型への実装


Download ppt "研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻."

Similar presentations


Ads by Google