Sparse SCM のマルチスレッド計算

以下のように SCM(Schur Complement Matrix)が疎になるときの計算については、効果が薄いということでこれまでは見送ってきたのだが、様々な変更によって効果も見込めるようになってきた。これからも様々な



○問題 mater-4.dat-s
SDPA 7.3.3β (SCM シングルスレッド) : 50.07秒
SDPA 7.3.3β (SCM マルチスレッド) : 38.57秒

○問題 mater-6.dat-s
SDPA 7.3.3β (SCM シングルスレッド) : 4分12秒
SDPA 7.3.3β (SCM マルチスレッド) : 3分45秒

○サーバ (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 14 for x86_64

最新 MIP ソルバー

最新の MIP ソルバーを入手して簡単な比較実験を行った。やはり CPLEX と Gurobi が２強となっている。他のソルバーにおいて１時間以内に問題が最適に解けなかった場合では、(下界, 上界) を記しておいた。

○問題 S-20-20-2-3.mps（ロットサイズ決定問題）: 最適解 337697
CPLEX 12.2.0.2 : 280.12秒
Gurobi 4.0.1 : 110.94秒
SCIP 2.0.1 + CPLEX 12.2.0.2 : (332730, 338147) : 3600秒
SCIP 2.0.1 + SOPLEX 1.5.0 : (329558, 337887) : 3600秒
Cbc 2.6.2 : (331690, 341379) : 3600秒

○問題 gmpl-10-0.2.mps (仮想マシンマイグレーション問題)：最適解 155
CPLEX 12.2.0.2 : 228.47秒
Gurobi 4.0.1 : 348.17秒
SCIP 2.0.1 + CPLEX 12.2.0.2 : (154, 157) : 3600秒
SCIP 2.0.1 + SOPLEX 1.5.0 : (154, 156) : 3600秒
Cbc 2.6.2 : (154, 231) : 3600秒

○問題 roll3000.mps (MIPLIB2003) : 最適解 12890
CPLEX 12.2.0.2 : 59.30秒
Gurobi 4.0.1 : 41.06秒
SCIP 2.0.1 + CPLEX 12.2.0.2 : 1531.93秒
SCIP 2.0.1 + SOPLEX 1.5.0 : (12756, 12908) : 3600秒
Cbc 2.6.2 : (12666, 12960) : 3600秒

○問題 mod011.mps (MIPLIB2003) : 最適解 -5.4558535014e+07
CPLEX 12.2.0.2 : 24.67秒
Gurobi 4.0.1 : 19.48秒
SCIP 2.0.1 + CPLEX 12.2.0.2 : 82.93秒
SCIP 2.0.1 + SOPLEX 1.5.0 : 381.20秒
Cbc 2.6.2 : 36.63秒

○サーバ (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 14 for x86_64

ILP64 対応 SDPARA

ILP64 (int型 = long型 = ポインタ = 8bytes) 対応の SDPARA を作成してみた(まだ完成はしていない）。単に int を long long int 置き換えるだけでなく、関連するライブラリなどの対応も必要であるので、結構面倒な作業である。これまでの SDPARA は LP64 (int型 = 4bytes, long型 = ポインタ型 = 8bytes)であるので、2^31-1 を越える要素数を持つ配列を扱うことはできない。ILP64 型の SDPARA はこの制約が 2^63-1 まで大きく緩和されるのだが、実際には相当数のノードとメモリ量が無いとこのメリットを生かすことはできない。
ちなみに ILP64 対応 SDPARA と LP64 対応 SDPARA は実行時間、使用メモリ量共にほとんど同じである。

Westmere-EP 新クラスタ計算機での Graph500 その２

実験結果が多いので二つに分割した。前回の続きになる。プロセス数が増加するのに従って TEPS 値も上がっていくのだが、現在の実装では construction_time が大き過ぎる。

○プロセス数 = 8

SCALE: 18
edgefactor: 16
NBFS: 64
graph_generation: 5.38377 s
num_mpi_processes: 8
construction_time: 297.287 s
min_time: 0.181354 s
firstquartile_time: 0.183793 s
median_time: 0.186041 s
thirdquartile_time: 0.190867 s
max_time: 0.273179 s
mean_time: 0.188763 s
stddev_time: 0.0117479
min_nedge: 33554040
firstquartile_nedge: 33554040
median_nedge: 33554040
thirdquartile_nedge: 33554040
max_nedge: 33554040
mean_nedge: 33554040
stddev_nedge: 0
min_TEPS: 1.22828e+08 TEPS
firstquartile_TEPS: 1.75798e+08 TEPS
median_TEPS: 1.80358e+08 TEPS
thirdquartile_TEPS: 1.82564e+08 TEPS
max_TEPS: 1.8502e+08 TEPS
harmonic_mean_TEPS: 1.77758e+08 TEPS
harmonic_stddev_TEPS: 1.39381e+06
min_validate: 0.402777 s
firstquartile_validate: 0.405195 s
median_validate: 0.406648 s
thirdquartile_validate: 0.414641 s
max_validate: 0.489082 s
mean_validate: 0.41781 s
stddev_validate: 0.0249529

○プロセス数 = 16
SCALE: 18
edgefactor: 16
NBFS: 64
graph_generation: 5.3876 s
num_mpi_processes: 16
construction_time: 816.691 s
min_time: 0.202898 s
firstquartile_time: 0.207483 s
median_time: 0.21174 s
thirdquartile_time: 0.217322 s
max_time: 0.334086 s
mean_time: 0.215065 s
stddev_time: 0.0180503
min_nedge: 67108080
firstquartile_nedge: 67108080
median_nedge: 67108080
thirdquartile_nedge: 67108080
max_nedge: 67108080
mean_nedge: 67108080
stddev_nedge: 0
min_TEPS: 2.00871e+08 TEPS
firstquartile_TEPS: 3.08795e+08 TEPS
median_TEPS: 3.16937e+08 TEPS
thirdquartile_TEPS: 3.23439e+08 TEPS
max_TEPS: 3.30748e+08 TEPS
harmonic_mean_TEPS: 3.12037e+08 TEPS
harmonic_stddev_TEPS: 3.29951e+06
min_validate: 0.450214 s
firstquartile_validate: 0.451501 s
median_validate: 0.45226 s
thirdquartile_validate: 0.455349 s
max_validate: 0.51993 s
mean_validate: 0.463889 s
stddev_validate: 0.023922

○プロセス数 = 32
SCALE: 18
edgefactor: 16
NBFS: 64
graph_generation: 5.3606 s
num_mpi_processes: 32
construction_time: 2796.81 s
min_time: 0.255747 s
firstquartile_time: 0.271208 s
median_time: 0.275573 s
thirdquartile_time: 0.283241 s
max_time: 0.295788 s
mean_time: 0.276581 s
stddev_time: 0.00901031
min_nedge: 134216160
firstquartile_nedge: 134216160
median_nedge: 134216160
thirdquartile_nedge: 134216160
max_nedge: 134216160
mean_nedge: 134216160
stddev_nedge: 0
min_TEPS: 4.53758e+08 TEPS
firstquartile_TEPS: 4.73859e+08 TEPS
median_TEPS: 4.87045e+08 TEPS
thirdquartile_TEPS: 4.94884e+08 TEPS
max_TEPS: 5.248e+08 TEPS
harmonic_mean_TEPS: 4.85269e+08 TEPS
harmonic_stddev_TEPS: 1.99173e+06
min_validate: 0.606407 s
firstquartile_validate: 0.642895 s
median_validate: 0.652241 s
thirdquartile_validate: 0.656567 s
max_validate: 0.691647 s
mean_validate: 0.649346 s
stddev_validate: 0.0154449

○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64

Westmere-EP 新クラスタ計算機での Graph500 その１

新クラスタ計算機において SCALE = 18 に設定して、Graph 500 のリファレンス実装(graph500_mpi_simple)の実行を行った。プロセス数を 1 から 32 まで変化させている。

○プロセス数 = 1
SCALE: 18
edgefactor: 16
NBFS: 64
graph_generation: 5.39078 s
num_mpi_processes: 1
construction_time: 19.8175 s
min_time: 0.059428 s
firstquartile_time: 0.059502 s
median_time: 0.0595485 s
thirdquartile_time: 0.059572 s
max_time: 0.0601749 s
mean_time: 0.0595746 s
stddev_time: 0.000129671
min_nedge: 4194255
firstquartile_nedge: 4194255
median_nedge: 4194255
thirdquartile_nedge: 4194255
max_nedge: 4194255
mean_nedge: 4194255
stddev_nedge: 0
min_TEPS: 6.9701e+07 TEPS
firstquartile_TEPS: 7.04065e+07 TEPS
median_TEPS: 7.04343e+07 TEPS
thirdquartile_TEPS: 7.04893e+07 TEPS
max_TEPS: 7.05771e+07 TEPS
harmonic_mean_TEPS: 7.04034e+07 TEPS
harmonic_stddev_TEPS: 19306.6
min_validate: 0.438232 s
firstquartile_validate: 0.441083 s
median_validate: 0.445009 s
thirdquartile_validate: 0.449172 s
max_validate: 0.45422 s
mean_validate: 0.44548 s
stddev_validate: 0.00450658

○プロセス数 = 2
SCALE: 18
edgefactor: 16
NBFS: 64
graph_generation: 5.38127 s
num_mpi_processes: 2
construction_time: 66.8728 s
min_time: 0.177018 s
firstquartile_time: 0.178792 s
median_time: 0.180184 s
thirdquartile_time: 0.181535 s
max_time: 0.184387 s
mean_time: 0.180269 s
stddev_time: 0.00175187
min_nedge: 8388510
firstquartile_nedge: 8388510
median_nedge: 8388510
thirdquartile_nedge: 8388510
max_nedge: 8388510
mean_nedge: 8388510
stddev_nedge: 0
min_TEPS: 4.54941e+07 TEPS
firstquartile_TEPS: 4.62087e+07 TEPS
median_TEPS: 4.65551e+07 TEPS
thirdquartile_TEPS: 4.69176e+07 TEPS
max_TEPS: 4.73878e+07 TEPS
harmonic_mean_TEPS: 4.65334e+07 TEPS
harmonic_stddev_TEPS: 56973.8
min_validate: 0.348466 s
firstquartile_validate: 0.350293 s
median_validate: 0.351405 s
thirdquartile_validate: 0.352656 s
max_validate: 0.356819 s
mean_validate: 0.351691 s
stddev_validate: 0.00176172

○プロセス数 = 4
SCALE: 18
edgefactor: 16
NBFS: 64
graph_generation: 5.38487 s
num_mpi_processes: 4
construction_time: 150.576 s
min_time: 0.182378 s
firstquartile_time: 0.184579 s
median_time: 0.185649 s
thirdquartile_time: 0.186711 s
max_time: 0.201766 s
mean_time: 0.18641 s
stddev_time: 0.00350674
min_nedge: 16777020
firstquartile_nedge: 16777020
median_nedge: 16777020
thirdquartile_nedge: 16777020
max_nedge: 16777020
mean_nedge: 16777020
stddev_nedge: 0
min_TEPS: 8.31509e+07 TEPS
firstquartile_TEPS: 8.98556e+07 TEPS
median_TEPS: 9.03696e+07 TEPS
thirdquartile_TEPS: 9.08934e+07 TEPS
max_TEPS: 9.19903e+07 TEPS
harmonic_mean_TEPS: 9.00006e+07 TEPS
harmonic_stddev_TEPS: 213309
min_validate: 0.366741 s
firstquartile_validate: 0.370749 s
median_validate: 0.371506 s
thirdquartile_validate: 0.373391 s
max_validate: 0.37961 s
mean_validate: 0.372297 s
stddev_validate: 0.00255954

○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64

Betweenness Centrality (BC) と様々なグラフ その２

様々な中心性(Centrality)の指標がある中で、こちらのクラスタ計算機を用いて DIMACS 全米データの Betweenness Centrality (BC) の計算を行っている。これらの計算を１台の計算機のみで行うのはさすがに厳しいものがある。スパコンが必要とまでは言わないが、クラスタレベルの計算機は必要になる。



前回に続いて CAL(カリフォルニア)とNW(アメリカ北西部) の道路データの BC を求めて、指標の高い順に色付けしたものになる。過去の研究でも検証されているが、BC の計算には全ての点に対して 1対全の最短路問題を解く必要はなく、ランダムサンプリングされた一部の点のみ（下の例では 1024点)を対象にしても十分な精度を得ることができる。これらの重要点が実際の高速道路等をどの程度重なっているかを調べてみると面白いことがわかる。

Schur Complement Matrix(SCM)

SDP は元問題の種類や特性によって以下のように Schur Complement Matrix (SCM) が密になったり疎になったりする。



左のように SCM が密になる場合では SCM の各要素の計算において行単位でのマルチスレッドの計算が非常に有効だが、右のように非常に SCM が疎な場合では単純な行単位のマルチスレッド計算では反対に実行時間が遅くなってしまう。よって、このような疎な場合でも SCM の計算が高速化できないか現在考案中である（１スレッドで計算する現在の方法でも十分高速だが）。

2011年度第1回 SCOPE講演会

3月19日に2011年度第１回 SCOPE を開催して以下の２件の講演を行います。是非ご参加下さい。OR学会の春季大会の直後(次の日)に行います。

○2011年度第1回 SCOPE
日　時 ： 2011年3月19日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 3 号館 3300 号室（いつもと場所が異なります）
講演1
講演者 ： 北原知就氏 (東京工業大学 大学院社会理工学研究科 経営工学専攻)
題目 ： 単体法によって生成される実行可能基底解の個数の上界について
概要　 ： 単体法は線形計画問題に対する最初の解法で，実用上は非常に効率的であることが知られている。しかし，一般的な線形計画問題に対する単体法の反復回数の評価はほとんど知られていない．その大きな障害となっているのが，Klee-Mintyによって発表された単体法が指数回の反復回数を必要とし得るという事実である．北原-水野(2010年)はマルコフ決定問題に対するYeの解析(2010年)を応用し，単体法が生成する実行可能基底解の上界を示した。得られた上界は問題の制約式の個数、変数の個数，およびすべての実行可能基底解の正の要素の最大値と最小値の比，の多項式で表される．そして問題が非退化のとき，この上界は反復回数の上界となる。本講演では、上界を得るための解析について詳しく説明する。また，新たに開発した簡易版Klee-Minty問題を使い，良い上界が得られていることを示す．

講演2
講演者 ： 今野浩氏　 (中央大学 理工学部 経営システム工学科)
題目 ： TBA

高精度 SDP 計算の威力 その２

先日紹介した以下の多項式関数最小化に関する SDP 緩和問題は以下の通りになる。

f(x, y) = x^4 + 2y^4 - 2x^2y^2 - 2y^2

ファイルはこちらのリンクから入手可能。SDPA のバイナリが無ければ SDPA Online Solverから実行することもできる。ただし、先日報告したように高精度で解くためには、FRA(面的縮小)か SDPA-GMP などが必要になる。

14=mDIM
1=nBLOCK
6=bLOCKsTRUCT
0 0 0 0 -2 0 0 0 0 1 0 -2 0 2
0 1 1 1 -1
1 1 1 2 1
2 1 1 3 1
3 1 1 4 1
3 1 2 2 1
4 1 2 3 1
4 1 1 5 1
5 1 1 6 1
5 1 3 3 1
6 1 2 4 1
7 1 2 5 1
7 1 3 4 1
8 1 2 6 1
8 1 3 5 1
9 1 3 6 1
10 1 4 4 1
11 1 4 5 1
12 1 4 6 1
12 1 5 5 1
13 1 5 6 1
14 1 6 6 1

Centrality 計算中

以下の DIMACS 全米データを含む様々なグラフの Centrality(中心性)の並列計算をクラスタ計算機を用いて行っている。ただし、空調機の調子が依然として悪い（修理部品の取り寄せ中）ので、安定して最後まで終了するのかはわからない。



以下の中心性の指標を四つをなるべく同時に（高速かつメモリを使わずに）計算するように工夫を行っている。ここで d_G(s,t) とは、点 s, t 間の距離、また \sigma_st は s,t 間の最短路の数、\sigma_st(v) は 点 v を経由する s,t 間の最短路の数となっている。



結果や分析についてはいずれこちらのブログから公開する予定（論文にして投稿する方が先になるかもしれないが）。

高精度 SDP 計算の威力

持ち込みで以下の多項式関数の最小値を求めたいという話があった（実際にはこれはサンプルなのでもっと大きな問題を解きたいらしい）。

f(x, y) = x^4 + 2y^4 - 2x^2y^2 - 2y^2

ただし、以下のようになるので最小値は -1 になる。

f(x, y) = (x^2 - y^2)^2 + (y^2-1)^2 - 1

これの SDP 緩和問題を作成する。作り方についてはこちらの文献などを参照。

SDPA で解くとそこそこの精度の最適解を得ることができる。

15 3.7e-08 0.0e+00 7.7e-16 -1.00e+00 -1.00e+00 9.0e-01 9.0e-01 1.00e-01

phase.value = pdFEAS
Iteration = 15
mu = +3.6510441133360182e-08
relative gap = +2.1906277792458455e-07
gap = +2.1906278835359672e-07
digits = +6.6594314093642062e+00
objValPrimal = -9.9999993807601895e-01
objValDual = -1.0000001571388073e+00
p.feas.error = +0.0000000000000000e+00
d.feas.error = +7.8159700933611020e-14
total time = 0.053846

SDPA-GMP で解くと驚異的な精度の解が得られる。

37 2.6e-22 1.5e-101 1.0e-94 -1.00e+00 -1.00e+00 1.0e+00 9.9e-01 1.00e-01

phase.value = pdOPT
Iteration = 37
mu = 2.5571313253416751e-22
relative gap = 1.5342787952050050e-21
gap = 1.5342787952050050e-21
digits = 6.9043026016353465e+01
objValPrimal = -1.0000000000000000e+00
objValDual = -1.0000000000000000e+00
p.feas.error = 1.4624132610624366e-97
d.feas.error = 1.0087336504226708e-90
relative eps = 4.6816763546921983e-97
total time = 0.030

前からわかっていることではあるが、高精度計算の威力を再確認した。

2010年度第5回 SCOPE講演会

2月26日に第５回 SCOPE を開催して以下の２件の講演を行います。是非ご参加下さい。

○2010年度第5回 SCOPE
日　時 ： 2011年2月26日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6 号館
講演1
講演者 ： Thorsten Koch氏 （Zuse Institute Berlin(ZIB), Berlin）
Title: How to survive Real-World Projects as a Mathematician
(Lessons and experiences from 10 years of industry projects)

Abstract: This talks aims at sharing the experience from 10 years of
successfully employing integer programming in industry projects with the
audience. After numerous research-industry collaboration projects we
found that there are several reoccurring topics during these projects.
The problems encountered seem to be universally the same, as there are
very common misunderstandings between the partners. We will try to draw
some general conclusions and using the projects of the author as
examples to show some common pitfalls. We will talk about acquiring
projects, getting them running and how to explain the results to
practitioners. Listening to this talk requires no particular knowledge
of mathematics.

講演2
講演者 ： 品野勇治氏　（Zuse Institute Berlin(ZIB), Berlin）
Title: Parallel MIP solvers developed at ZIB: current state of the art
Abstract:
混合整数計画(MIP: Mixed Integer Programming)ソルバの近年の性能向上は著しく，
様々な現実問題が混合整数計画問題に定式化され解かれるケースも増えつつある．
商用の混合整数計画ソルバの多くは，既にマルチ・スレッド化され並列化されて
いる．本講演では，ZIB(Zuse Institute Berlin)で開発されている並列混合整数
計画ソルバ群について紹介する．並列混合整数計画ソルバは，既存の混合整数計画
ソルバを並列化する共通のソフトウェア・フレームワーク上に構築されている．
そのフレームワークの概要と，北ドイツ最大のスーパーコンピュータHLRN IIによる
最新の数値実験結果（１ジョブの実行に最大7,168コアを利用）について報告する．

MIP ソルバーの性能

学生に対する演習で以下のようなサイズの MIP を作成した。
38 rows, 764 columns, 2803 non-zeros, 760 integer variables

そんなに簡単な問題では無いと思っていたのだが、やはり GLPK (4.45) では簡単に解くことは出来ない。6分たっても上界と下界の差は以下の通りである。

Time used: 360.0 secs. Memory used: 3.0 Mb.
+1964415: mip = 1.170000000e+02 >= 1.165000000e+02 0.4% (503; 218386)

CPLEX 12.2 で解くと以下のように一瞬で終了する。

MIP - Integer optimal solution: Objective = 1.1700000000e+02
Solution time = 0.16 sec. Iterations = 38 Nodes = 0

Gurobi 4.0.0 でも同じく非常に高速だ。

Explored 0 nodes (58 simplex iterations) in 0.07 seconds
Thread count was 24 (of 24 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 1.1700000000e+02, best bound 1.1700000000e+02, gap 0.0%

CPLEX や Gurobi よりは遅いものの Cbc や SCIP でも短時間で解くことができる。最近の MIP ソルバーの性能向上は大変めざましい。


○計算サーバ： Istanbul (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 14 for x86_64

2010年度理研シンポジウム ペタフロップス時代のセンターシステム

以下のシンポジウムが 2月16日に開催される。参加には事前登録が必要となっている。

2010年度理研シンポジウム ペタフロップス時代のセンターシステム

2012年に運用が開始される「京」の構築が進む中、国内外でペタフロップス規模のシステムの運用が始まっています。ペタフロップスシステムの計画やハードウエア、アプリケーション、運用に関する具体的な取り組みなどついての講演とともに、理研のスーパーコンピュータのRICCの運用状況とより高度な利用のための取り組みをご紹介します。
日時

2011年2月16日（水）　午前10時～午後5時30分
会場

独立行政法人　理化学研究所　和光キャンパス
鈴木梅太郎記念ホール
主催

独立行政法人　理化学研究所
情報基盤センター

Debian パッケージ SDPA

Debian の unstable (sid) から SDPA の パッケージ 7.3.4 を apt-get でインストールすることができる。

パッケージ: sdpa (7.3.4.dfsg-1)

Debian パッケージの都合で SDPA も正式公開版からバージョンアップが続いてすでに 7.3.4 になっている。
同じマシンで SDPA 7.3.2 をソースから make して作成したバイナリと性能を比較してみた。パッケージインストールよりも現地でバイナリを作成した方が一般的には性能の良いバイナリが出来るだろう。

○問題１ : theta6.dat-s
sdpa 7.3.4.dfsq-1 : 53.5s
sdpa 7.3.2.RC3 : 40.2s

○問題２： mcp500-1.dat-s
sdpa 7.3.4.dfsq-1 : 5.3s
sdpa 7.3.2.RC3 : 3.9s