１：利用課題概要（５００字以内）
半正定値計画問題(SDP)は組合せ最適化, システムと制御, データ科学, 金融工学, 量子化学など非常に幅広い応用を持ち、現在最適化の研究分野で最も注目されている最適化問題の一つとなっている。
SDP に対しては高速かつ安定した反復解法である内点法アルゴリズムが存在しているが、巨大な線形方程式系の計算(行列要素の計算と行列のCholesky分解)が大きなボトルネックとなっている。前回のグランドチャレンジ実施時には、申請者らが開発したソフトウェア SDPARA の拡張を行い、多数GPU の活用や計算と通信のオーバーラップ技術を応用することによって、主要なボトルネックの1つである線形方程式系のCholesky 分解の高速化と世界最大規模の SDP を高速に解くことに成功した。今回の実施では疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術によって、入力データから密と疎な部分が自動的に抽出され、前者は主に GPU、また後者は密データに変換後に CPUコアで高速に大規模並列処理されることを検証し、様々な応用問題に対して SDPARA が高性能な汎用ソルバであることを示す。
２：利用課題説明
今回開発を行った ソフトウェア SDPARA の最新版を用いて、疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術によって、入力データから密と疎な部分が自動的に抽出され、前者は主に GPU、また後者は密データに変換後に CPUコアで高速に大規模並列処理されることを検証する。さらに前者の GPU による計算部分においては前回での性能値533TFlops, 4080GPU)を更新することも目指す。
1. n : SDP の変数と定数行列の大きさ(図2)
2. m : SDP の主問題における制約式の数(図2)
3. # nonzero : 定数行列Ai(i = 0, . . . ,m) における非零要素の総数
4. SCM: 線形方程式系の左辺係数行列(サイズは m x m)
5. ELEMENTS : 係数行列（SCM）の全要素の計算（主要なボトルネックの一つ目）
6. CHOLESKY : 係数行列(SCM)のCholesky 分解（主要なボトルネックの二つ目）
内点法アルゴリズム(図3)の(1反復の)計算量は上記の n とm を用いると O(m^2n^2 + mn^3 + m^3)と表現することができる(Step 2において ELEMENTS がO(m^3n^3 + mn^3) , CHOLESKYが O(m^3))。 しかし、2-3-2 で説明した工夫等によって SDPARA では Step 2 の計算量を O(n^3 + m^3) まで減らすことに成功した。次に具体的に今回の課題で解く SDP と計算時間やメモリ量の推定を行う。
これまでの研究結果から主な SDP は以下の三つに分類して効率良く処理することが可能である。疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術によって、入力データから密と疎な部分を自動的に抽出する。その後、以下の三つの計算方法が自動的に正しく選択されて、高性能（絶対性能及びスケーリング）に並列処理されることを示す。
1. SCM が疎な場合 ⇒ SCM に対する Parallel Sparse Cholesky 分解の適用
2. SCM が密 かつ n ≧ m の場合 ⇒ CPU に対する affinity の自動設定と多数のCPUコアによる処理（浮動小数点演算性能に非依存：密データへ変換）による SCM 要素の並列高速計算
3. SCM が密 かつn < m の場合 ⇒ 多数GPU と通信の計算のオーバーラップ技術による Parallel Dense Cholesky 分解の適用
３：実験結果
○問題例１：量子化学分野に対するSDPの適用：上記の２(SCM が密 かつ n ≧ m の場合)に相当
縮約密度行列法では分子の基底状態が２次の縮約密度行列に相当し、今回は基底状態エネルギーの下界値を(固有値問題に変換して)SDPを用いて計算する。n = 33,000 , m = 76,000 程度の大きさ。
CPU 128個(768 コア) 3284.46秒 --> CPU 2720個(16320 コア) 191.49秒
768 コア --> 16320 コア（コア数 21.25 倍) の増加で 3284.46/191.49 = 17.15倍 の実行時間高速化
○問題例２：組合せ最適化問題（二次割当問題）：上記の３(多数GPU と通信の計算のオーバーラップ技術による Parallel Dense Cholesky 分解)に相当
二次割当問題(Quadratic Assignment Problem : QAP)はスケジューリング問題やLSIの回路配置, 施設配置問題などの定式化に現れる代表的なNP-困難な組合せ最適化問題の一つである。
制約数 約 233万個の SDP に対して 4080GPU による並列 Cholesky 分解等の計算：
[gpdpotrf] ### END n=2339331, nb=1024, 68x60 procs, ver 40: 4189.606902sec --> 1018545.646521GFlops ### --> 約 1.018 PFlops の性能
よって SDPARA が高性能(Peta-scale)な SDP に対する汎用ソルバであることの検証を行うことができた。つまり特定の問題や特定のアプリで性能チューニングを行ったというのではなく、実アプリ（汎用の最適化ソルバー）で1PFlopsの達成に成功した。
半正定値計画問題(SDP)は組合せ最適化, システムと制御, データ科学, 金融工学, 量子化学など非常に幅広い応用を持ち、現在最適化の研究分野で最も注目されている最適化問題の一つとなっている。
SDP に対しては高速かつ安定した反復解法である内点法アルゴリズムが存在しているが、巨大な線形方程式系の計算(行列要素の計算と行列のCholesky分解)が大きなボトルネックとなっている。前回のグランドチャレンジ実施時には、申請者らが開発したソフトウェア SDPARA の拡張を行い、多数GPU の活用や計算と通信のオーバーラップ技術を応用することによって、主要なボトルネックの1つである線形方程式系のCholesky 分解の高速化と世界最大規模の SDP を高速に解くことに成功した。今回の実施では疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術によって、入力データから密と疎な部分が自動的に抽出され、前者は主に GPU、また後者は密データに変換後に CPUコアで高速に大規模並列処理されることを検証し、様々な応用問題に対して SDPARA が高性能な汎用ソルバであることを示す。
２：利用課題説明
今回開発を行った ソフトウェア SDPARA の最新版を用いて、疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術によって、入力データから密と疎な部分が自動的に抽出され、前者は主に GPU、また後者は密データに変換後に CPUコアで高速に大規模並列処理されることを検証する。さらに前者の GPU による計算部分においては前回での性能値533TFlops, 4080GPU)を更新することも目指す。
1. n : SDP の変数と定数行列の大きさ(図2)
2. m : SDP の主問題における制約式の数(図2)
3. # nonzero : 定数行列Ai(i = 0, . . . ,m) における非零要素の総数
4. SCM: 線形方程式系の左辺係数行列(サイズは m x m)
5. ELEMENTS : 係数行列（SCM）の全要素の計算（主要なボトルネックの一つ目）
6. CHOLESKY : 係数行列(SCM)のCholesky 分解（主要なボトルネックの二つ目）
内点法アルゴリズム(図3)の(1反復の)計算量は上記の n とm を用いると O(m^2n^2 + mn^3 + m^3)と表現することができる(Step 2において ELEMENTS がO(m^3n^3 + mn^3) , CHOLESKYが O(m^3))。 しかし、2-3-2 で説明した工夫等によって SDPARA では Step 2 の計算量を O(n^3 + m^3) まで減らすことに成功した。次に具体的に今回の課題で解く SDP と計算時間やメモリ量の推定を行う。
これまでの研究結果から主な SDP は以下の三つに分類して効率良く処理することが可能である。疎性の追求、計算量やデータ移動量などによる計算方法の自動選択などの技術によって、入力データから密と疎な部分を自動的に抽出する。その後、以下の三つの計算方法が自動的に正しく選択されて、高性能（絶対性能及びスケーリング）に並列処理されることを示す。
1. SCM が疎な場合 ⇒ SCM に対する Parallel Sparse Cholesky 分解の適用
2. SCM が密 かつ n ≧ m の場合 ⇒ CPU に対する affinity の自動設定と多数のCPUコアによる処理（浮動小数点演算性能に非依存：密データへ変換）による SCM 要素の並列高速計算
3. SCM が密 かつn < m の場合 ⇒ 多数GPU と通信の計算のオーバーラップ技術による Parallel Dense Cholesky 分解の適用
３：実験結果
○問題例１：量子化学分野に対するSDPの適用：上記の２(SCM が密 かつ n ≧ m の場合)に相当
縮約密度行列法では分子の基底状態が２次の縮約密度行列に相当し、今回は基底状態エネルギーの下界値を(固有値問題に変換して)SDPを用いて計算する。n = 33,000 , m = 76,000 程度の大きさ。
CPU 128個(768 コア) 3284.46秒 --> CPU 2720個(16320 コア) 191.49秒
768 コア --> 16320 コア（コア数 21.25 倍) の増加で 3284.46/191.49 = 17.15倍 の実行時間高速化
○問題例２：組合せ最適化問題（二次割当問題）：上記の３(多数GPU と通信の計算のオーバーラップ技術による Parallel Dense Cholesky 分解)に相当
二次割当問題(Quadratic Assignment Problem : QAP)はスケジューリング問題やLSIの回路配置, 施設配置問題などの定式化に現れる代表的なNP-困難な組合せ最適化問題の一つである。
制約数 約 233万個の SDP に対して 4080GPU による並列 Cholesky 分解等の計算：
[gpdpotrf] ### END n=2339331, nb=1024, 68x60 procs, ver 40: 4189.606902sec --> 1018545.646521GFlops ### --> 約 1.018 PFlops の性能
よって SDPARA が高性能(Peta-scale)な SDP に対する汎用ソルバであることの検証を行うことができた。つまり特定の問題や特定のアプリで性能チューニングを行ったというのではなく、実アプリ（汎用の最適化ソルバー）で1PFlopsの達成に成功した。
アクセス
トータル
