コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス	

高性能並列固有値計算アルゴリズムの開発

櫻井鉄也1), 2), 二村保徳1)，前田恭行1)，矢野貴大1)，
Du Lei1), 2)，今倉暁1)，多田野寛人1)
1)筑波大学大学院システム情報工学研究科
2)科学技術振興機構CREST

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

研究課題
n 研究課題名

Ø 計算量子科学のニーズに対応した高性能固有値計算アルゴリズムの開発n 体制Ø 代表者
Ø 連携研究者
Ø 研究協力者

櫻井鉄也（筑波大学）
多田野寛人，今倉暁（筑波大学）
Du Lei，二村保徳，前田恭行，矢野貴大（筑波大学）

n 主な実施課題
Ø 階層型固有値解法によるバンド構造計算法の高性能化
Ø 確率的推定法を利用した状態密度計算法の開発
Ø 計算量子科学分野で現れるさまざまな固有値計算への展開
Ø 実問題での性能評価とボトルネックの改善
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

関連プロジェクト：CREST

n 「ポストペタスケールに対応した階層モデルによる超並列列 　固有値解析エンジンの開発」
Ø 主たる共同研究者- 張(名古屋大)，今村(理研)，山本(神戸大)，
藏増(筑波大)，星(鳥取大)Ø アーキテクチャの超並列性を活用する階層型並列アルゴリズム- 密行列・疎行列に対応
Ø 共通基盤技術としての線形計算手法・実装技術開発- 高性能な線形計算手法，性能予測モデルによる評価，GPU／メニーコア向け実装
Ø 実問題での利用技術の開発- 基礎科学・ナノ物質分野での実問題に適用・高度利用技術を開発
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

関連プロジェクト：CRESTn 超並列固有値エンジン：z-Pares, EigenExa• GPU・MIC向け実装技術	
・ポストペタ環境での精度解析	
・耐故障性技術	
• ポストペタ環境での性能予測モデル	
• 「京」での検証	

2015

エクサへ

ポストペタ環境へ	の移行・性能評価	
ポストペタ環境に向けた	実装技術の開発	
ポストペタ環境での	性能予測	
• 実アプリで求められる問題

京での実装・性能評価	
2011

規模での性能評価	
• 各種アプリへの適用技術の開発	

• H25.12 「z-Pares」公開	
• H25.8 「EigenExa」公開	
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

固有値解析エンジンの開発

n 開発ソフトウェア(疎⾏行行列列向け)Ø z-Pares- Fortran90, MPI- 大規模分散並列環境での利用- アプリケーションへの組み込みを想定し，ReverseCommunicationインターフェース(RCI)を備える
Ø CISS- C, SLEPc- 分散並列環境でのアプリケーションに対応した手法の有効性評価
Ø SSEIG- MATLAB- 1ノード規模でのアプリケーションに対応した手法の有効性評価
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

CISS (Contour Integral Spectral Slicing) in SLEPcn SLEPc: Scalable Library for Eigenvalue Problem

Computations

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

周回積分を用いた固有値解法
Im	n 基本アイディア：有理式に対する周回積分! "n"1νidz =νi
2πi Γ i=1 z − λiΓGλ1λ2λ3λi ∈GRe	n 行列 A のレゾルベント(zI − A)

−1n!

Pi=,z − λii=1

Pi = ui uHiλi : 固有値, ui : 固有ベクトル(ここでは簡単のため A は実対称とし，固有値は相異なるとする)

周回積分によるスペクトル射影!
"1−1(zI − A) dz =Pi
2πi Γλi ∈G

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

周回積分を用いた固有値解法n 疎行列向け超並列固有値解法

Ø 複素平面上の特定領域内部の固有ベクトル成分を抽出Ø 周回積分は数値積分で近似（各積分点では線形方程式を解く）

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

階層的なアルゴリズムn 周回積分を利用

固有値問題

反復復による部分空間の構成

A B

並列列性能が得にくい部分空間

従来法
数値積分による部分空間の構成

S

固有対周回積分による解法
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

階層的なアルゴリズムn 超並列固有値エンジンの階層性Ø ポストペタ環境で想定される階層型ハードウェア構成で、性能を発揮する階層的アルゴリズム	

z-Pares	
周回積分に基づき指定領域内部の固有対を抽出	

各積分点での計算は独立した線形方程式の求解	

ハードウェアの階層性	

アルゴリズムの階層性に併せて計算リソースを割り当てる

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

固有値数の推定n 領域内の固有値数の確率的推定Ø Γ 内の固有値数：

1m=2πi!

tr(zB − A)−1 B)dzΓ	Ø 逆行列のトレースを以下のように近似する
L!
1tr((zB − A)−1 B) ≈vlT (zB − A)−1 Bvl
Ll=1

ここでベクトル vl の要素は 1 または -1 を等確率にとる
GEP: Futamura, et al. (2010), NEP: Maeda et al. (2011)	

n Sylvester慣性則による固有値番号の計算

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

計算例：RSDFTn 実空間密度汎関数法(RSDFT, Iwata et al.)Ø シリコンナノワイヤー9,924原子- 行列サイズ：8,719,488次元，「京」 27,648コア- バンドギャップ付近の固有値を計算

Futamura, et al. (2013)	
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

数値例：RSDFT} RSDFT(シリコンナノワイヤ 39,696 原子)Ø 行列の次元：34,877,952
Ø 区間：[-0.7, 0]，約80,000個の固有値がこの区間に存在Ø 「京」4,800 nodes (38,400 cores)
Eigenvalue  Density

Computational time： 7,461 sec	Futamura, et al. (in preparation)	
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

数値例：CONQUESTn CONQUEST (Miyazaki et al.)Ø SS法による固有値計算とシルベスター慣性則による固有値番号の組み合わせØ 区間 [0, 0.2] 指定した区間内の固有値のみを計算
Ø 対象：
固有値	
残差	
番号	
cDZP DNA+H2O
Ø 行列：15,776次元
Ø 言語：MATLAB

0.036698335	

6.40E-11	4823	

0.038558045	

5.80E-11	4824	

0.039932115	

5.40E-11	4825	

0.040855165	

7.60E-11	4826	

・・・	

・・・	・・・	

0.199354252	

2.90E-13	5230	

0.199492964	

7.10E-13	5231	

0.199610069	

2.60E-13	5232	

0.199879801	

6.40E-13	5233	

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

数値例：ELSESn ELSES

lculation time [sec]

100
8060

120
100806040200

Computation with distributed GPUs	

120

fact
solve
SVD
RR
misc

fact
solve
SVD
RR
misc

100

Calculation time [sec]120

金ナノワイヤー (AuNW) (Hoshi, et al.)
一般化固有値問題：9,180
バンドギャップ近傍の約1%の固有対を計算
GPUによる計算（MAGMA)
Elapsed time [sec.]	

ØØØØ

80
60
40
200112244# GPU

88

Number of GPUs	

1616(Yano et al.,2013)	

新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」
40数値例：非線形固有値問題n リニアコライダ設計:

平方根が現れるT (z) = K − z 2 M + it "!

z 2 − σj2 Wj ,j=1

Ø Cray-XT4 at NERSC @BerkeleyØ 行列：2,738,556次元

http://www.linearcollider.org/	#cores	

256	

512	

1024	

2048	

time(sec.)	

2513	

1273	

661	

334	

speedup	

-	

1.97	

1.93	

1.92	

(Yamazaki et al., 2013)	
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」

おわりにn 大規模並列で性能を発揮する解法の開発

Ø 周回積分により固有成分をフィルタリングØ 階層構造による高い並列性
n 高性能ソフトウェアの開発Ø z-Pares，CISS，SSEIGn 実アプリケーションへの適用Ø RSDFT，CONQUEST，ELSESn 今後の課題Ø さまざまなタイプの内部固有値問題に対応- 直線上，円弧，リング状領域，et.cØ 計算量子科学分野で現れるさまざまな固有値計算への適用
新学術領域「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」