mpack-0.6.6 の make その２

前回と同様に mpack-0.6.6 の make を様々なコンパイラと Linux で行ってみた。
make の仕方は基本的に以下の二つのみ。

./configure
make

1: CentOS 5.5 + gcc 4.1.2 成功
2: Fedora 8 (AmazonEC2 extra large タイプ) + gcc 4.1.2 成功
3: Fedora 13 + gcc 4.4.4 : 失敗

Fedora 12 では成功するが、13 では失敗。gcc 4.5.0 と 4.4.3 では成功するが 4.4.4 では失敗と何かややこしいことになっている。

Amazon EC2 での SDPA 7.3.2 64bit その２

その１で用いた AmazonEC2 のマシンの性能に最も近い計算サーバを用いて、同じ BLAS と同じ問題を使って実験を行った。その１の方と比較して参考にして頂きたい。

○計算サーバ
CPU : X5460 @ 3.16GHz 8 コア
Memory : 48GB
gcc : 4.1.2
Intel コンパイラ 11.1
OS : CentOS 5.5 for x86_64
OMP_NUM_THREADS=4

○BLAS ライブラリ
BLAS : 3.2.1
ACML : 4.4.0
MKL : 11.1.072
GotoBLAS2 : 1.13

-------------------------------------------------------------

○ theta6.dat-s
BLAS : 10m7.087s
ACML : 29.191s
MKL : 24.179s
GotoBLAS2 : 24.343s

○ mcp500-1.dat-s
BLAS : 5.104s
ACML : 2.469s
MKL : 2.270s
GotoBLAS2 : 2.664s

○ LiH.1Sigma+.STO6G.pqgt1t2p.dat-s
BLAS : 37.397s
ACML : 36.384s
MKL : 35.570s
GotoBLAS2 : 37.975s

○ mater6.dat-s
BLAS : 54.927s
ACML : 1m48.672s
MKL : 56.487s
GotoBLAS2 : 3m23.126s

Amazon EC2 での SDPA 7.3.2 64bit その１

AmazonEC2 を借りて SDPA 7.3.2 + 各 BLAS で数値実験を行った。その２の方は仮想マシンではなく実機上での実験なので結果を比較していただきたい。

○AmazonEC2 extra large タイプ
CPU : E5430 @ 2.66GHz 4 コア
Memory : 16GB
gcc : 4.1.2
Intel コンパイラ 11.1
OS : Fedora 8 for x86_64
仮想マシン : Xen
OMP_NUM_THREADS=4

○BLAS ライブラリ
BLAS : 3.2.1
ACML : 4.4.0
MKL : 11.1.072
GotoBLAS2 : 1.13

----------------------------------------------------------------

○ theta6.dat-s
BLAS : 13m11.976s
ACML : 52.608s
MKL : 57.941s
GotoBLAS2 : 1m0.018s

○ mcp500-1.dat-s
BLAS : 8.058s
ACML : 7.544s
MKL : 7.954s
GotoBLAS2 : 9.174s

○ LiH.1Sigma+.STO6G.pqgt1t2p.dat-s
BLAS : 1m8.771s
ACML : 1m39.709s
MKL : 1m31.970s
GotoBLAS2 : 1m23.251s

○ mater6.dat-s
BLAS : 1m31.411s
ACML : 17m31.359s
MKL : 1m57.124s
GotoBLAS2 : 17m18.225s

とっても大きな SDP その５

終わりそうで終わらないが、mu が 1.0e-11 レベルで終わると思われるので、あと半日ぐらいで終了ではないだろうか。

44 1.2e-09 3.8e-11 1.8e-12 -9.10e+01 -9.10e+01 8.2e-01 5.6e-01 1.00e-01
45 6.1e-10 3.8e-11 7.8e-13 -9.10e+01 -9.10e+01 9.9e-01 7.2e-01 1.00e-01
46 2.1e-10 3.8e-11 2.2e-13 -9.10e+01 -9.10e+01 1.1e+00 8.9e-01 1.00e-01

計算資源はいくらあっても足らない状況。

mpack-0.6.6 の make

mpack-0.6.6 の make を様々なコンパイラと Linux で行ってみた。
make の仕方は基本的に以下の二つのみ。

./configure
make

1: Vine Linux 5.1 + gcc 4.5.0 (デフォルトは 4.1.2) : 成功
2: Fedora 12 + gcc 4.4.3 : 成功

3: Fedora 13β + gcc 4.4.4 : 失敗
4: Fedora 11 + gcc 4.4.1 : 失敗
5: Fedora 11 + icc 11.1 : 失敗
6: CentOS 5.5 + gcc 4.4.3 : 失敗
7: CentOS 5.5 + icc 11.1 失敗

とっても大きな SDP その４

mDIM の値自体は以前解いていた SDP よりも小さいが、各行列のサイズが以下のように非常に大きいので、総合的に見ればこの SDP の方がサイズが大きいと言うことができる。

76554 (= mDIM)
22 (= nBLOCK)
18 18 18 18 153 153 324 153 153 324 648 324 324 816 2754 2754 816 8604 8604 2754 2754 -694 (= bLOCKsTRUCT)

現在は以下の指標まで進んでいる。あと数反復で終わりそうである。
38 1.5e-07 3.8e-11 4.9e-10 -9.10e+01 -9.10e+01 7.7e-01 5.8e-01 1.00e-01
39 7.0e-08 3.8e-11 2.0e-10 -9.10e+01 -9.10e+01 8.1e-01 5.4e-01 1.00e-01
40 3.6e-08 3.8e-11 8.9e-11 -9.10e+01 -9.10e+01 9.3e-01 6.2e-01 1.00e-01
41 1.6e-08 3.8e-11 3.6e-11 -9.10e+01 -9.10e+01 9.4e-01 7.2e-01 1.00e-01
42 5.6e-09 3.8e-11 1.1e-11 -9.10e+01 -9.10e+01 8.0e-01 6.3e-01 1.00e-01
43 2.4e-09 3.8e-11 3.8e-12 -9.10e+01 -9.10e+01 7.1e-01 5.4e-01 1.00e-01

メモリ的にはそろそろ限界に近づいているが、SDPARA を完全 64bit 化すれば、もっと大きな問題を扱うこともできるだろう。今は Schur complement 行列(mDIM x mDIM) を分割しているのだが、int = 32bit の制約から、この分割数を多くする必要があるので、メモリを多く消費する傾向にある。

MSC における SDP セッション

The 2010 IEEE Multi-Conference on Systems and Control (MSC) 国際会議において SDP 関係のセッションを提案しておりましたが、無事に採択されました（一部の講演は変更)。９月８日（初日）の一番初めのセッションになります。

WeA01
Room 417
Recent Trends and Researches in Conic Programming Invited CACSD Session

Organizer: Fujisawa, Katsuki Chuo Univ.

10:30-10:50, Paper WeA01.1
Efficient Parallel Software for Large-Scale Semidefinite Programs (I)
Yamashita, Makoto Tokyo Inst. of Tech.
Fujisawa, Katsuki Chuo Univ.

10:50-11:10, Paper WeA01.2
Linear Matrix Inequalities with Chordal Sparsity Patterns and Applications to Robust Quadratic Optimization (I)
Andersen, Martin Univ. of California, Los Angeles
Vandenberghe, Lieven Univ. of California at Los Angeles
Dahl, Joachim MOSEK

11:10-11:30, Paper WeA01.3
On Optimization Over the Doubly Nonnegative Cone (I)
Yoshise, Akiko Univ. of Tsukuba
Matsukawa, Yasuaki Univ. of Tsukuba, Graduate School of Systems and Information Engineering

11:30-11:50, Paper WeA01.4
Semidefinite Programming Relaxations for Sensor Network Localization (I)
Kim, Sunyoung Ewha W. Univ.
Kojima, Masakazu Tokyo Inst. of Tech.

11:50-12:10, Paper WeA01.5
Lowrank Exploitation in Semidefinite Programming for Control
Falkeborn, Rikard Linköpings Univ.
Löfberg, Johan Linköpings Univ.
Hansson, Anders Linkoping Univ.

12:10-12:30, Paper WeA01.6
A Numerical Evaluation of Highly Accurate Multiple-Precision Arithmetic Version of Semidefinite Programming Solver: SDPA-GMP, -QD and -DD (I)
Nakata, Maho RIKEN (The Inst. of Physical and Chemical Res.

SDPが注目される理由

現在 SDP が注目されている理由を簡単にまとめてみた。

１：主双対内点法などのアルゴリズムによって多項式時間で最適解を求めることができる(つまり高速で安定したアルゴリズムが存在する)
２：SDP は線形計画問題(LP), 凸二次計画問題や二次錐計画問題(SOCP) などを含んだより大きな凸計画問題の枠組である
３：非凸最適化問題に対する強力な緩和値を導き出すことができる. そのためSDP を繰り返して解くことによって非凸最適化問題(例えば双線形行列方程式(BMI) など) を扱える可能性を持っている
４：組合せ最適化問題, 整数計画問題, ノルムなどを用いた配置問題, システムと制御, ロバスト最適化, 量子化学など非常に多くのSDP の応用が存在する(つまり非常に多彩な応用分野を持っている).
５：多くのSDP に対するソフトウェアが開発され, インターネットより公開されている. つまり公開されているソフトウェアで実際に大きな問題を解くことができる

OR学会誌７月号

日本オペレーションズ・リサーチ学会誌７月号特集のタイトル名は半正定値計画に対するソルバーと応用例になる。最終校正がまだ残っているが、原稿自体はほぼ完成した。タイトルと著者は以下の通りである。

半正定値計画の問題記述＆解決能力 　　　　　　　　　　　　 (東京工業大学：中田)
半正定値計画問題に対するソルバーの紹介 　　　　　　　　(東京工業大学：福田)
主双対内点法に対する高速化・並列化の技術 　　　　　　　(東京工業大学：山下)
半正定値計画法に対する高精度・安定計算の技術　　　　　(理化学研究所：中田)
多項式最適化問題に対する半正定値計画緩和 　　　　　（電気通信大学：脇）
最適化ソルバー開発への最新の情報技術の適用について　（中央大学：藤澤）

SDPARA と BLAS と シングルスレッド

SDPARA から BLAS を呼び出すときにマルチスレッドにすると SDPARA 本体のマルチスレッドの部分とどうしても衝突が起きるので、BLAS をシングルスレッドで起動してみることにする。BLAS をシングルスレッドで起動すれば確かに F3 式の計算部分の時間は減るものの、その他の Cholesky 分解や行列積の部分の計算時間が増えて全体としては計算時間が増えてしまう。

○NH.3Sigma-.DZ.pqgt1t2p.dat-s
1: SDPARA (マルチスレッド) + BLAS (シングルスレッド)
Make bF3 time = 36063.936600, 87.072999
Cholesky bMat = 1746.809805, 4.217509
makedXdZ = 1348.697155, 3.256303
Total = 41425.130523, 100.017100

2: SDPARA (マルチスレッド) + BLAS (マルチスレッド)
Make bF3 time = 36197.104115, 96.419518
Cholesky bMat = 485.222597, 1.292505
makedXdZ = 251.026045, 0.668667
Total = 37547.964911, 100.017854

E1414

PowerEdge R905 (4-Way) の CPU 3 に以下のエラーが発生してサーバが止まった。いわゆる熱暴走になる。トラブルはいつも AMD Opteron サーバに発生している（RAID, Disk 関係も含めて）。Intel Xeon サーバではトラブルらしきものは一度も発生していない。

E1414

CPU # temp exceeding range. Check CPU heatsink.

表示されているプロセッサの温度が許容範囲を超えている。

プロセッサヒートシンクが正しく取り付けられていることを確認します。「プロセッサのトラブルシューティング」および「システム冷却問題のトラブルシューティング」を参照してください。

CentOS 5.5

RHEL 5.5 の発売から少し時間が経ち、CentOS 5.5 もリリースされたので、研究室の CentOS 5.4 のマシン 26 台をすべて 5.5 にアップグレードした。ただし、現在計算中のクラスタ計算機はまだ reboot を行っていない。ちなみに ACML-GPU を使う場合では RHEL(CentOS) 5.x が良いらしい。

とっても大きな SDP その３

SDPA が完全に 64bit 化されたので、以下のような巨大 SDP に挑戦しています。使用メモリは約 80Gbytes に達していますが、１日経っても１反復も進んでいません。とりあえず何日かは様子を見てみます。

102208 (= mDIM)
14 (= nBLOCK)
-101740 193 129 129 161 65 193 225 225 161 193 193 225 257 (= bLOCKsTRUCT)


追記；少し勘違いしておりまして、もう解けてました。SDPARA と某スパコン（２０４８コア）で解けなかった問題が SDPA 64bit と下記の計算サーバ１台で解けてしまいました。

phase.value = pdOPT
Iteration = 47
mu = +2.2389660137779845e-10
relative gap = +6.1062266354383610e-16
gap = +6.1062266354383610e-16
digits = +1.4646499419044991e+01
objValPrimal = +2.7056545000777804e-01
objValDual = +2.7056545000777743e-01
p.feas.error = +3.5100219220039225e-08
d.feas.error = +1.5058346581182299e-09
total time = 143548.847829
main loop time = 143546.522675
total time = 143548.847829
file check time = 0.000000
file change time = 0.024329
file read time = 2.300825
SDPA end at [Fri May 14 09:04:34 2010]
ALL TIME = 143695.387471

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

ブログ５周年

ブログ開設からちょうど５年になりました。初めの頃に考えていたことと、現在行っていることに随分とギャップがありますが、妥当な進路変更であると思います。当時の人間関係が原因で無理やりいろいろなソフトウェアを使おうとした傾向が見られますが、今振り返ると使わなくて良かったというのが正直な感想です。クラスタという言葉は今でも頻繁に使われていますが、グリッドという言葉はほとんど消えてしまいました。最近のソフトウェア開発が割と順調なのは、この５年間で人間関係が大きく変わったのも原因ではないかと思っています。

SDPA クラスタ越え その２

予算を集めたり価格の交渉を行ったりといろいろと努力して、新クラスタの計画が以下のように変更になった。これが実現すれば新クラスタは現(SDPA)クラスタを性能的に越えることはほぼ確実となろう。SDPA(SDPARA)だけでなく、時空間ネットワーク上の最短路検索、それに MIP などにも使用する予定になっている。

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.4 for x86_64

○新クラスタ
14 Nodes, 28 CPUs, 168 CPU cores;
CPU : Intel Xeon X5680 3.33GHz (hexa cores) x 2 / node
Memory : 96GB / node
NIC : GbE x 1 and Infiniband QDR x 1 / node
OS : 未定