大規模最適化問題に対するソフトウェア開発と 高速＆安定計算

--理論からスパコンまで--

藤澤克樹 中央大学理工学部 & JST CREST

２０１２年１２月１２日：北大 ERATO

はじめに

1990年代半ばに誕生した半正定値計画問題(SDP)に対

する理論（主双対内点法）がその後どのような経緯を辿って、ソフトウェア化されて、スパコン上で大規模計算が行われるようになったのか

優れた（綺麗な）理論が高速、高性能な実装（ソフトウェア）になるまでのお話

SDP に対する主双対内点法がここまで達したのは必然ではなかった

内容は最適化理論から応用分野、ソフトウェア化、大規模計算までと多岐に渡る

SDPが注目される理由とは？

主双対内点法などのアルゴリズムによって多項式時間で最適解を求めることができる(つまり高速で安定したアルゴリズムが存在する)

SDP は線形計画問題(LP), 凸二次計画問題や二次錐計画問題(SOCP) などを含んだより大きな凸計画問題の枠組である

非凸最適化問題に対する強力な緩和値を導き出すことができる. そのためSDP を繰り返して解くことによって非凸最適化問題(例えば双線形行列方程式(BMI) など) を扱える可能性を持っている

組合せ最適化問題, 整数計画問題, ノルムなどを用いた配置問題, システムと制御, ロバスト最適化, 量子化学など非常に多くのSDP の応用が存在する(つまり非常に多彩な応用分野を持っている).

多くのSDP に対するソフトウェアが開発され, インターネットより公開されている. つまり公開されているソフトウェアで実際に大きな問題を解くことができる

２１世紀の線形計画問題として大きな期待を受けている

構造最適化問題

データマイニング 組合せ最適化問題

システムと制御 量子化学

SDP(SemiDefinite Programming)

Primal

Dual

SDPA 1.x(1995) could solve SDPs with n = m = 20 ～30 (very small size!!)

SDPで表現することができる制約条件（１）

SDPで表現することができる制約条件（２）

SDP緩和(rank = 1 条件の緩和)

内点法と SDP

内点法とは文字通り、内部を通る（通過する）方法

実行可能性を満たしつつ最適解に向かう ⇒ 何か指標が必要 対数ポテンシャル関数や対数障壁関数など

大域的収束性の保証 ポテンシャル減少法やパス追跡法

主双対内点法の登場 パス追跡法と双対定理の組合せ

主双対問題の内点の対数障壁関数の最小点として中心パスを定義して、Newton 法の適用で中心パスを追跡する

理論的にも実装的にも最強の手法

実際には理論よりも長いステップを取って速い収束を得る

SDPの双対定理

弱双対定理 が主問題の実行可能解

が双対問題の実行可能解 主問題の目的関数値 双対問題の目的関数値

強双対定理 主問題に内点実行可能解が存在 双対問題に内点実行可能解が存在 (i) (SDP) 主・双対問題に最適解が存在する (ii) がSDPの最適解である

(no duality gap) 相補性条件

ñX(ñY ;ñz)

ëCèñXïPmi=1 biñzi ë

(XÉY É;zÉ)m

XÉèY É= C èXÉÄmXi=1

bizÉi = 0

SDPの最適性条件

仮定 ・SDPの主・双対問題に(内点)実行可能解が存在 ・制約行列 が線形独立 Karush-Kuhn-Tucker 条件

主問題実行可能

双対問題実行可能 相補性条件

A1, A2; . . . ;Am

(Ai èX = bi; (i = 1; 2; . . . ;m)

X ó O8><>:mXi=1

Aiyp + Y = C;

Y óO(X èY = C èX Ä

mXi=1

bizi = 0

実は SDP は３目的を持つ最適化問題

実行可能領域の境界

中心パス

最適解

探索方向

実行可能領域

実行可能初期解

実行不可能初期解

ステップサイズ

主・双対パス追跡内点法 （実装）

・Step ０ 内点実行可能解 を選び、

・Step １ もし最適性条件を満たしていれば終了．そうでなければ

を計算

・Step ２ ある に対して、

を近似的に解き、探索方向 を求める

・Step ３

となるようなステップサイズ を求める

(X0,Y 0,z0), X0ü O, Y 0üO k=0

ñk = XkèY kn

å2 (0; 1)8>>>><>>>>:Ai èdX = Ä(Ai èXk Ä bi); (i = 1; . . . ;m) dX 2 Sn;mXi=1

Aidzi + dY = Ä(mXi=1

Aizki + Y

k ÄC); dY k 2 Sn;

dXY k +XkdY = Ä(XkY k ÄåñkI)

(dX; dY ; dz) 2 Sn Ç Sn Ç<m

Xk+1 =Xk +ãpdX üO;(Y k+1;zk+1) = (Y k;zk) +ãd(dY ; dz) üO;

ãp;ãd 2 (0; 1] k := k + 1

SDPを解くソフトウエア

SDPA プロジェクト : FAQ 集

いつから始まりましたか? 1994 年ぐらいからで、正式には 1995 年4月開始

プロジェクトの目的は何ですか？ 半正定値計画問題(SDP)に対する主双対内点法を実装した高性能なソフトウ

ェアの開発と提供。特に高速性と安定性を重視する。

ソフトウェアのライセンスは何ですか？ GPL ライセンス。よって SDPA をライブラリとして用いるとその本体にも GPL

ライセンスが適用される

SDPA, SDPARA, SDPA-GMP のように何故多数のソフトウェアが開発されているのでしょうか？ SDP の疎性や規模の大小などを考慮すると１種類のソフトウェアで全ての

SDP を高速かつ安定に解くのは難しいから

SDPA プロジェクト : ラインナップ

SDPA (SemiDefinite Programming Algorithm) 小規模から大規模な問題までを高速に解く中心的なソフトウェア。通常はこの

ソフトを用いることが多い。マルチコア化への対応により、かつてのスパコン上での SDPARA 並みの性能が出る

SDPARA (SDPA paRAllel version) SDPAのボトルネックになっている部分を MPI を用いて並列化。超大規模な

問題向き。実行には PC クラスタやスパコンなどが必要。

SDPA-GMP, SDPA-QD, SDPA-DD SDPA(倍精度)では精度が足りないときに用いる。SDPA-GMP(任意精度),

SDPA-QD (擬似８倍精度), SDPA-DD(擬似4倍精度)。ただし速度は SDPA よりもかなり遅くなる

SDPARA-C, SDPA-C 行列補完の理論を用いて特殊な疎性を持つ問題に対応。SDPA-C を MPI

並列化したのが SDPARA-C

http://sdpa.sourceforge.net/ より入手可能

SDPA Family

Primal-Dual IPM SDPA (double : 52bit) SDPA-GMP (arbitrary precision) SDPA-QD (quad-double : 208bit) SDPA-DD (double-double : 104bit)

Matrix Completion Primal-Dual IPM MPI based parallel version of

SDPA

1

2

3

SDPA&SDPA-GMP, QD, DD

SDPA-C SDPARA

SDPARA-C

A combination of SDPA-C and SDPARA

Main features of the SDPA

SDPA 7.4.0 (2012) SDPA 2.0.1 (2012) SDPA 2.0.1 (1996)

0.8 sec. 373.7 sec (≒ 6.2 min.) 133,892.5 sec. (≒ 37.2 h)

Intel Xeon E7-4870 2.40GHz, memory 512GB

Intel Xeon E7-4870 2.40GHz, memory 512GB

MIPS R4400 133MHz, memory 128MB

Implementation of the Mehrotra-type primal-dual predictor-corrector interior-point method for SDP

Written in C++ language Handle diagonal and sparse matrices Incorporates an efficient method for

computing the search direction when the problem is large scale and sparse

Sparse Schur complement matrix and Sparse Cholesky Factorization

Performance tunings and Optimized BLAS SOCP (Second Order Cone Problem)

167,365 times faster mcp500-1 Max cut problem: 500 nodes

Primal-Dual Interior-Point Methods

What difficulties in solving SDPs

ELEMENTS : Computation of all elements of Schur complement matrix B (Step 2) ⇒ O(m2n2+mn3)

CHOLESKY : Cholesky factorization of B (Step 2) ⇒ O(m3)

Other O(n3) operations (ex. Matrix-matrix mul.)

n : size of matrices X and Y

m : # of constraints of primal problem

Two major bottleneck parts!!

Bottlenecks of IPM

Dense Sparse

n = m (n >> m) ELEMENTS ELEMENTS

n << m ELEMENTS ELEMENTS

Dense Sparse

n = m (n >> m) ELEMENTS Other O(n3) parts

n << m ELEMENTS CHOLESKY or Other O(n3) parts

ELEMENTS :: O(m2n2+mn3)⇒ Computation of all elements of Schur complement matrix B

CHOLESKY:: O(m3)⇒ Cholesky factorization of B

If we don’t exploit the sparsity….

If we exoloit the sparsity(ex. SDPA 7.x)

SDPA開発の方針： なるべく汎用的なモデルを作る

アルゴリズムの選択 Mehrotra タイプの主双対内点法

データ構造の選択 密行列、疎行列、対角行列などを想定。ブロック対角

行列のデータ構造 各データ構造専用の計算方法の実装 SDPA自身によるデータ構造と計算方法の自動選択（計

算量の推定）

入力データの特徴（大小、密や疎）をとらえて、想定される多くの問題に自動的に対処させる

疎で大規模なSDPにおいては Schur complement equation がネック

は密行列と疎行列の両方に成り得る

上記の連立線形方程式を非常に効率良く解く必要がある

は コレスキー分解 Cholesky factorization や反復法 Conjugate gradient で解くのが一般的

Bdz = g

Bij = Ai èXkAj(Y k)Ä1 (i; j = 1; . . . ;m)

Bdz = g

B

Exploitation of Sparsity in Schur complement matrix

The SDPA automatically selects a formula when computing each row of B by estimating computational costs of F1, F2 and F3

F1

F2

F3

ＳＤＰＡにおける行列 B の計算方法

入力データ(行列の大きさ、制約式の数、非零要素）が与えられたときに F1, F2, F3 の計算時間の見積もりを行う（なるべく汎用的なモデルを作る)

パラメータ κ : 疎行列からデータを1 個持ってくる時間と密行列からデータを1個持ってくるときのレイテンシの比率(トレードオフ関係の見極め)

κ の適正値 (2.2 : 1997年) ⇒ (7 ～ 10 : 2009年)

相当疎な行列でも密行列に変換して GotoBLAS 等で処理した方が有利

F1: Bij =XAiY Ä1 èAj

F2: Bij =nX

ã=1

nXå=1

[Aj ]ãå

†nX

ç=1

Xãç[AiYÄ1]çå

!

F3: Bij =nX

ç=1

nXè=1

0@ nXã=1

nXå=1

[Ai]ãåXãçYÄ1åè

1A [Aj ]çè

Schur complement 行列の計算

F1

F2

F3

Ai

密

疎

Aｊ 密 疎

行列Bに対するマルチスレッドコンピューティング

F3

F1

F1 式(CPU演算能力に依存), F3式(メモリバンド幅に依存) ⇒ 両式を行単位でマルチスレッドで並列に動作させる

F1 式の計算部分だけは他のスレッドが一時停止して、F1 式から呼び出されBLAS が マルチスレッドで動作するようにしている

SDPA 本体と BLAS 側でスレッドの競合が起きないように工夫する

メモリバンド幅の大きな最新の CPU (Westmere-EX, SandyBridge-EP) などでは特に有効

結果として SDPA の高速化に寄与

F1式ではBLASが マルチスレッドで動作

F1: Bij =XAiY Ä1 èAj

F2: Bij =nX

ã=1

nXå=1

[Aj ]ãå

†nX

ç=1

Xãç[AiYÄ1]çå

!

F3: Bij =nX

ç=1

nXè=1

0@ nXã=1

nXå=1

[Ai]ãåXãçYÄ1åè

1A [Aj ]çè

Schur complement 行列のマルチスレッドコンピューティング(2)

F3式は演算量が非常に少ないので、データ

移動量の比率が大きくなる

各行では右から左方向に計算を行う

一番先のスレッドがアクセスしたデータの多くはその後に続くスレッドで再利用される ⇒ コピールーチンとして働く

共有キャッシュのバンド幅が大きな CPU では非常に有効

コピールーチンとして動作する ⇒ L2(L3)キャッシュにおいてデータ共有される

半正定値計画問題に対する ソフトウェア開発で用いられる新技術について

入力されたインスタンス（特性）に対してソフトウェアが自動的にトランスフォームする

入力問題の特性によって以下の操作が行われる。 1: 定数行列を保持するデータ構造の決

定（Dense か Sparse か？)

2: Cholesky 分解時の Fill-in 回数最小化のため ordering(並び替え）決定

3: Schur complement 行列の各行を F-1, F-2, F-3 式のどの組合せでマルチスレッド計算するかを決定

4: コンピュータの計算能力やメモリバンド幅などに応じて、マルチコア CPU 上で自動的に Schur complement 行列

の並列計算が行われる（動的負荷分散も含む)

© パラマウント ピクチャーズ（配給元)

記号 定義

n SDP の行列 X;Z;Ai(i = 0; . . . ;m) 2 Sn などの大きさm SDP の主問題における制約式の数

#nonzero 定数行列 Ai(i = 0; . . . ;m) における非零要素の合計数

ELEMENTS 係数行列 B の全要素の計算に要する計算時間 : O(mn3 +m2n2)CHOLESKY 係数行列B の Cholesky 分解 : O(m3)DMATRIX Cholesky 分解後の探索方法 dX; dZ の計算 : O(n3)DENSE 行列 XとZ の固有値計算などの O(n3) の計算時間合計

用語等の定義

1995 1998 2009 2010～

データ量 数Mbyte

適用例 組合せ最適化

１～２Tbyte

2002

数十Mbyte

制御系(BMI)

＞数百Mbyte

施設配置

＞数十Tbyte

量子化学 多項式最適化

1CPU 数十CPU 数千CPU

クラスタ計算機

＞数万CPU

スパコン ＰＣ、ワークステーション

ブロック対角行列の例

半正定値計画問題に対する ソフトウェア開発で用いられる新技術について(2)

安定して高精度で計算する CG やゲーム等の世界では単精

度でも十分 GPGPU

数理計画法、特に SDP の世界では倍精度(仮数部 52bit)でも足りない

高精度数値演算ライブラリ GMP(任意精度)

QD(擬似8倍精度: 仮数部 208 bit), DD(擬似4倍精度 : 仮数部 104bit)

long double x 2 = 仮数部 128 bit で４倍精度エミュレーション

高速化が重要(ベクトル化、マルチスレッド化)

4 or 8倍精度と任意精度計算

double の変数２個で double-double(QD ライブラリ) 4倍精度演算 a = a.hi + a.lo, |a.hi| > |a.lo|。仮数部は 104

bit(52 × 2)。 IEEE の 4倍精度にやや劣る

double 変数4個で quad-double (仮数部 208bit)もある

gmp (GNU Multi Precision - 任意精度数演算ライブラリ) 基本的な四則演算が行える(計算コストは高め)

BLAS, LAPACK などの該当場所も GMP も用いて書き換え

○実験結果 (gpp124-4.dat-s) SDPA 7.3.1(仮数部52bit) ; 0.120s ; relative gap = +4.5142123662482953e-09 SDPA-GMP 7.1.2(仮数部256bit) ; 1m33.775s ; relative gap = 9.0228025522551977e-11 SDPA-QD 7.1.2(仮数部208bit) ; 1m4.486s ; relative gap = 9.0228025522551977e-11 SDPA-DD 7.1.2(仮数部104bit) ; 7.299s ; relative gap = 9.0219191406178191e-11

SDPA(52bit) and SDPA-GMP(384bit)

SDPA-GMP(7.1.2) Relative gap 6.9124757680300082e-117 Objective Function -7.3430762652465377e+00 (Primal) -7.3430762652465377e+00 (Dual) Feasibility 6.0861792610998578e-96

(Primal) 2.4151803415600079e-52

(Dual) Computation time 325.27 sec. (76 iterations)

Benchmark problem : gpp124-1(SDPLIB)

SDPA(7.4.0) Relative gap 4.0248805036000342e-08 Objective Function -7.3430761595594655e+00 (Primal) -7.3430764551094621e+00 (Dual) Feasibility 2.7284841053187847e-12

(Primal) 7.1838159865222906e-07

(Dual) Computation time 0.55 sec. (19 iterations)

SDPA-DD with GPU SDPA-DD 7.1.8 can support

GPU based parallel computing

Accelerate some BLAS functions(ex. gemm) by GPU (Takao Yasuyoshi)

Problem : mcp1000-1.dat-s : Max cut problem(# node = 1000)

SDPA-DD 7.1.2 (CPU) : 997.370s

SDPA-DD 7.1.8 (CPU + GPU) : 341.310s

SDPA 7.4.0 (CPU) : 4.140s

CPU: Intel Xeon 2.93GHz x 2

GPU: NVIDIA Tesla M2050 GPU

CUDA Toolkit 4.2

Memory: 54GB

Main features of the SDPARA

SDPARA is a parallel implementation of the

interior-point method for SDP

Parallel computation for two major

bottleneck parts for computing search

direction ELEMENTS ⇒Computation of Schur

complement matrix CHOLESKY ⇒ Cholesky factorization of

Schur complement matrix

Hybrid (2-layers) parallel computing

Multi-processing(MPI)

Multi-threading(pthread, OpenMP)

With libraries

MPI library(MPICH, OpenMPI)

ScaLAPACK (Scalable Linear Algebra

PACKage), BLACS, BLAS, MUMPS

スーパーコンピュータ上での最適化問題の実行

どのような最適化問題（アルゴリズム）がスーパーコンピュータでの実行に適しているのか？ 1. 解くべき問題の規模が非常に大きいこと

2. アルゴリズムの演算量がある程度大きいこと

3. 演算量データ移動量の比が十分程度大きいこと

4. 並列計算数に合わせて演算量やデータ移動量がほぼ均等になるように各プロセスに割り振ることができること

5. 並列に動作しているプロセス同士が高速かつ高い信頼性で頻繁に通信を行ったり, 同期を取る必要がある場合

上記の条件を（ほぼ）満たす最適化問題 SDP, MIP, TSP など

計算量とデータ移動量の正確な推定を行う。またデータの

特性(疎性，サイズ) と性能値の関係を見極める

超大規模 SDP(量子化学への応用)

分子の基底状態エネルギーは化学反応モデル等の理論的なエネルギー予測に役立つ基本的な値

従来のアプローチではSchrödinger方程式の最小固有値解を近似した波動関数から基底状態エネルギーを算出するHartree-Fock (HF) 法等

縮約密度行列法では分子の基底状態が２次の縮約密度行列 ⇒基底状態エネルギーの下界値(SDP)

SDPの最適変数に相当するのが２次の縮約密度行列であり,目的関数では分子を構成する原子の種類や幾何構造等の情報を持った線形関数を最小化する.

A large-scale SDP (2003) : quantum chemistry

n = 630 (matrix size)

m = 24,503 (# of constraints)

95,600 (# of nonzero elements)

153

324

153

ELEMENTS : 191.5s ⇒Computation of Schur complement matrix

CHOLESKY : 1248.1s ⇒ Cholesky factorization of Schur complement matrix

Total : 1948.7s 64CPUs SDPARA 1.0.1

Tokyo Institute of Technology. Presto III Cluster(Tokyo, Japan) : (2003) Athlon 1U (Appro 1124)x 128 + ATX Dual Athlon x 128

256 PC machine, 512 CPU (Athlon MP 1900+) Each machine has 2 CPU with 768MB memory Performance : 760.2 GFLOPS (LINPACK) The 68th ranking in the 20th TOP500 list (Nov. 2002)

100

1000

10000

100000

1 2 4 8 16

53763

27854

14273 7895

4650

5803 2992 1630 931 565

#nodes

PCSDP

SDPARA(1)

SDPARA(2)

SDPARA(4)

SDPARA(8)

SDPARA 7.3.1 (2008) 16nodes x 8threads

565s

# of threads which SDPARA used

PCSDP (Ivanov and de Klerk)

Performance Comparison (SDPARA and PCSDP)

for Quantum Chemistry (2008)

SDP: N.4P.DZ.pqgt11t2p(m=7230)

seco

nd

PCSDP 1.0 (2008)

16nodes x 1threads : 4650s

n = 19,640 (matrix size)

m = 36,795 (# of constraints)

6,731,930 (# of nonzero elements)

4965

4965

1575

1575

1575

1575

490

A large-scale SDP (2010) : quantum chemistry

ELEMENTS : 68217.6s ⇒Computation of Schur complement matrix

CHOLESKY : 511.7s ⇒ Cholesky factorization of Schur complement matrix

Total : 72025.7s 128nodes x 16cores

SDPARA 7.3.2

Super computer (Kyoto University in Japan) SDPARA for extremely large-scale SDPs : (2010)

CPU AMD Opteron 8356 2.3GHz x 4

Memory 32GByte

NIC GbE x 2 & Infiniband x 4

Molecule Computation time

H2O 27,523.8s = 7.6 hours

CH3 68,593.4s= 19 hours

NH3 72,025.6s = 20 hours

O2 5,943.1s = 1.6 hours

T2K Open Supercomputer and specifications

Computation time of SDPARA for extremely large-scale SDPs arising from quantum chemistry

128node x 16 cores = 2048 cores Very large-scale computation

SDPARA 7.5.0-G (CPU + GPU) : 2012 1. For large and dense problems, we accelerate the Cholesky

factorization (CHOLESKY) by using a large-number of

GPUs efficiently. We also introduce techniques to overlap

communication and computation (based on HPL library

for TSUBAME 2.0)

2. Employ the ILP64 programming model for extremely

large-scale matrix computation(necessary for indexing huge arrays, with more than 231-1 elements). We

partially modify source codes of SDPARA, MUMPS, and

ScaLAPACK.

3. Solved the largest SDP problem (which has over 1.48

million constraints), and created a new world record in

2012. we also achieved 533 TFlops in double precision for

large-scale Cholesky factorization using 4,080 GPUs.

TSUBAME 2.0 Specification

Specification

CPU Intel Westmere EP (Xeon X5670, L2 Cache: 256 KB, L3:

12MB) 2.93 GHz processors, 12 CPU Cores (24 cores with

Hyper Threading) x 2 sockets per 1 node (24 CPU Cores)

RAM 54 GB

OS SUSE Linux Enterprise 11 (Linux kernel: 2.6.32)

# of Total Nodes 1466 nodes (We used up to 1360 nodes)

Network Topology Full-Bisection Fat-Tree Topology

Network Voltaire / Mellanox Dual-rail QDR Infiniband

(40Gbps x2 = 80 Gbps)

GPGPU Three NVIDIA Fermi M2050 GPUs, CUDA 4.1

C/C++ Compiler Intel icc 11.1 & gcc 4.3.4

MPI MVAPICH 1.5.1

TSUBAME 2.0 System Configuration

1360 nodes, 2720 CPUs, 4080 GPUs

○ Each node has 2CPUs and 3GPUs ◯ 1360 nodes, 2720 CPUs, 4080 GPUs

○ CHOLESKY occupied over 95% of the entire computation time ◯ 1360 nodes, 2720 CPUs, 4080 GPUs (TSUBAME 2.0 in TITECH) ◯ Performance of Cholesky Fac. : 1 Exa flops / 2045 sec. ≒ 533 TFLOPS

Quadratic Assignment Problem

QAP(sko42) : 2012

We have challenged to solve largest SDPs in 2012!!

CHOLESKY : Cholesky factorization of Schur complement matrix

• For symmetric and positive semidefinite matrix

• Time complexity is O(m3)

• Ex. Matrix (1.48million x 1.48 million) ≒ 1.0 Exa(1018) Flops

• Our implementation is based on pdpotrf function

(ScaLAPACK library) and HPL Library for TSUBAME 2.0

• ScaLAPACK and HPL library employ the 2-D block-cyclic distribution for Cholesky factorization

– In ELEMENTS , we directly computes all elements of the 2-D block-cyclic distribution of the SCM

Data Decomposition in Cholesky

• The dense matrix B(m x m) is uniformly distributed with 2D Block-Cyclic distribution with block size nb(= 1024)

• CHOLESKY algorithm consists of mb(=⌈m/nb⌉) steps.

• MPI processes conceptually composes a 2D grid(ex. 6 (=2 x 3), 4080(=68 x 60) processes)

• Can use 4080GPUs in parallel!!

m

nb=1024

Matrix distribution on

6 (=2x3) processes

N

nb

Matrix distribution on

6 (=2x3) processes

B B’

Each process has a

“partial-matrix”

L’

L

''' LLBB

• The k-th step proceeds as follows: We need mb(=⌈m/nb⌉) steps. 1. Diagonal block factorization 2. Panel factorization 3. Panel broadcast and transposition 4. Update: the most computation-intensive part

B‘ = B‘– L x L‘ We need call DGEMM function on GPU once.

For Accelerating CHOLESKY by using massively parallel GPUs, we need optimization techniques to overlap computation, PCI-Express communication and MPI communication.

Parallel Algorithm of Cholesky Factorization Version 1: No overlapping

• Diagonal block factorization Panel factorization Panel broadcast and transposition

• Update: Each process updates its own part of the rest matrix, taking the corresponding part of L and Lt(trace of L). Then B‘ = B‘– L x Lt(Lt ) is computed.

Update: B‘ = B‘– L x Lt(Lt )

Parallel Algorithm of Cholesky Factorization Version 2: GPU computation and PCIe communication are overlapped

• Diagonal block factorization Panel factorization Panel broadcast and transposition

• Update: Each process updates its own part of the rest matrix, taking the corresponding part of L and Lt(trace of L). Then B‘ = B‘– L x Lt(Lt ) is computed.

Parallel Algorithm of Cholesky Factorization Version 3: GPU computation, PCIe communication, and MPI

communication are overlapped

• Diagonal block factorization Panel factorization Panel broadcast and transposition

• Update: Each process updates its own part of the rest matrix, taking the corresponding part of L and Lt(trace of L). Then B‘ = B‘– L x Lt(Lt ) is computed.

Performance of GPU Cholesky factorization obtained by using up to 64 nodes (192 GPUs).

Version 3 and Version 2 of CHOLESKY are compared

42 Tflops (v2)

46 Tflops (v3)

Performance of GPU Cholesky factorization on the full TSUBAME 2.0 system (up to 1,360 nodes and 4,080 GPUs)

533 TFLOPS : 24%

420 780

1360 largest size

Accelerate CHOLESKY by using massively parallel GPUs • In order to achieve scalable performance

with thousands of GPUs • Utilize high performance BLAS kernel

coupled with optimization techniques to overlap computation, PCI-Express communication and MPI communication.

SDPARA can solve the largest SDP problem which has over 1.48 million constraints (DNN relaxation problem : sko42a QAPLIB, and create a new world record in 2012. • Using 1360 nodes, 2720 CPUs, 4080 GPUs • Computation Time : 2700 sec./iteration => About 30 iterations are needed • Performance of CHOLESKY (= 1 Exa Flops : 1.48m x 1.48m) :

=> 2045 sec./iteration --> 533 TFLOPS

• One of the fastest and largest result as mathematical optimization problems

533 TFLOPS

• 並列数の爆発的増大、不均質化、高密度化 – プロセッサのマルチコア・メニーコア化

– ヘテロジニアスプロセッサ(ベクトル・スカラ)の台頭

• 記憶装置の多階層化・大容量化 – 次世代メモリ、Flash/NVRAM, 並列FS

– ノード内外のデータ転送性能バランスの逆転

次世代（ポストペタ）の予想と課題

通信最適化

局所性の活用

生産性

耐故障

数千万並列規模の

スケーラビリティ

不均質性

並列アルゴリズム

省電力

技術的課題

ストレージの

階層性の深化

大規模データI/O

次世代（100ペタフロップス級）スパコンの 想定アーキテクチャ（２０１５年頃？）

１ノードあたりで

10TFlops, 200W

• 演算はレジスタで行われる – メインメモリへのアクセスはコスト大 → キャッシュメモリで改善

メモリアクセスに必要な電力 >> 演算に必要な電力

• １個のデータ移動に必要な電力は、１個のデータの演算に必要な電力の１００倍になることもある。 – 必要以上にデータ移動させたら負け – 今後は既存のアルゴリズムの一大転換が必要（高速性と省電力性の両立）

– 今後のスパコンの主要なアプリケーションの一つはビッグデータ処理（グラフ解析等も含む）

‘03 ‘05 ‘07 ‘09 ‘11

データソース

データソース

超大規模センサー

• 観測データ

• スマートグリッド

• 交通・輸送

• SNS (Twitter)

大規模グラフ可視化

超大規模グラフ最適化システム

防災計画策定 交通・災害復興・

避難・ロジスティクス ソーシャル

ネットワーク解析 エネルギー・省電力

Indexing

中心性 解析

クラスタ リング

最短経路問題

最速 フロー問題

半正定値計画問題

混合整数 計画問題

X10言語処理系 リアルタイム

ストリーム処理系

リアルタイム大規模グラフストリーム処理

グラフ最適化ライブラリ

による大規模グラフ処理

大規模グラフ用階層型メモリストア

超大規模グラフ最適化システムの提案

100PF級ヘテロジニアススパコン

大規模グラフ解析:５年後（終了時）の目標と想定 超大規模ネットワークに対する探索アルゴリズムとクラスタリングアルゴリズムの高速実装

最短路(中心性), 最大フロー, PageRank, グラフ分割, 中心性, その他

数理計画問題(SDP, MIP)

グラフクラスタリング, 高速グラフレイアウト, グラフＵＩ

数百万頂点〜数兆頂点、数億枝〜数百兆枝からなる超大規模なグラフ解析

242頂点 数PB以上のワーキングデータセット

グラフ解析：例：890億個のニューロンとその接続100兆枝 ペタバイト級のストア領域：(2023年:エクサスパコン)

数百万人の被災者の避難経路の計算では数千万頂点のグラフ(１スレッドあたりのメモリ要求量1Gbytes)に対して、同時に数百万スレッド単位で各被災者毎の最短路計算と各点の重要度判定

5億頂点250億辺のグラフのインタラクティブな操作のための計算性能

ベクトル・スカラープロセッサから成る不均質でかつ分散共有メモリから成る大規模並列環境における大規模グラフ処理:数百万スレッドまでスケールさせる

大規模グラフ処理を PGAS 言語 X10 を用いて一元的に記述

メモリ多階層を考慮して、高速性と省電力性を両立したアルゴリズムの確立

世界最高性能の最適化ソルバーの開発：密データと疎データの分離と多階層並列(MPI , OpenMP, OpenACC等)及びアクセラレータ(GPU, MIC等)の活用

•世界最高レベルの性能を持つ最適化ソルバー(グラフ探索(最短路、幅優先等), 半正定値計画問題(SDP), 混合整数計画問題(MIP)) の開発 •グラフ問題等の良質な近似解を高速に探索する高性能最適化基盤の開発

•高精度線形代数演算ライブラリ：線形代数演算は問題規模が大きくなれば数値的に不安となるので, 高精度ライブラリをアクセラレータにより高速化する

巨大 SDP のデータ構造

IP に対する分枝操作

高精度線形演算ライブラリの開発と高速化

スーパーコンピュータ

上の大規模グラフ処理基盤での実行

大規模グラフデータ 数理計画問題 並列化支援 高精度量子化学計算

超大規模ネットワークにおける高速探索技術の開発

超大規模最適化問題に対する高速計算システムの構築と評価

数千万頂点のグラフ(１スレッドあたりのメモリ要求量1Gbytes)

に対して、同時に数百万スレッド単位での最短路計算

疎性の追求と前処理さらに並列計算の適用（大規模スレッド並列＆CPU + GPU による高速化)変数と制約条件 100 万以上

前処理による変数の削除と並列計算の適用（大規模スレッド並列) 整数変数10万以上

数理計画問題（最適化問題）とポストペタスパコン • 非常に応用が広範（企業、社会、公共政策） 高性能なソルバーを

作ること自体が最適化問題

• センサーデータによる最適化問題の複雑＆巨大化

• 半正定計画問題(SDP)と混合整数計画問題(MIP)が２大注目数理計画問題

• 汎用ソルバーの必要性（個別の問題に対する仮定やチューニングは効果が低い）

• 入力は疎データと密データの混合 – 疎データ：多数のCPUコアによる処理（浮動小数点演算性能に非依存：密デー

タへ変換）

– 密データ：GPU 系による処理

– 理論的性能限界等からボトルネック箇所を特定

– 数値演算能力とメモリバンド等のトレードオフ関係を把握

– 計算量とデータ移動量の正確な推定、疎性やサイズなどのデータ特性と性能値の見極め

• 計算量とポストペタスパコンでの想定：

– 計算量O(n3) 数百万程度, O(nlogn) 10億以上