最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

mpack-0.6.6 の make その2

2010年05月31日 01時52分11秒 | Weblog
前回と同様に 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 では失敗と何かややこしいことになっている。
コメント (1)
この記事をはてなブックマークに追加

Amazon EC2 での SDPA 7.3.2 64bit その2

2010年05月30日 23時51分34秒 | Weblog
その1で用いた AmazonEC2 のマシンの性能に最も近い計算サーバを用いて、同じ BLAS と同じ問題を使って実験を行った。その1の方と比較して参考にして頂きたい。

○計算サーバ
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 その1

2010年05月29日 23時17分16秒 | Weblog
AmazonEC2 を借りて SDPA 7.3.2 + 各 BLAS で数値実験を行った。その2の方は仮想マシンではなく実機上での実験なので結果を比較していただきたい。

○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 その5

2010年05月28日 17時40分53秒 | Weblog
終わりそうで終わらないが、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

2010年05月27日 23時10分21秒 | Weblog
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 失敗
コメント (4)
この記事をはてなブックマークに追加

とっても大きな SDP その4

2010年05月26日 22時43分18秒 | Weblog
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 セッション

2010年05月25日 22時43分37秒 | Weblog
The 2010 IEEE Multi-Conference on Systems and Control (MSC) 国際会議において SDP 関係のセッションを提案しておりましたが、無事に採択されました(一部の講演は変更)。9月8日(初日)の一番初めのセッションになります。

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が注目される理由

2010年05月24日 01時22分17秒 | Weblog
現在 SDP が注目されている理由を簡単にまとめてみた。

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

OR学会誌7月号

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

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

コメント
この記事をはてなブックマークに追加

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

2010年05月22日 23時53分27秒 | Weblog
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

2010年05月21日 10時03分57秒 | Weblog
PowerEdge R905 (4-Way) の CPU 3 に以下のエラーが発生してサーバが止まった。いわゆる熱暴走になる。トラブルはいつも AMD Opteron サーバに発生している(RAID, Disk 関係も含めて)。Intel Xeon サーバではトラブルらしきものは一度も発生していない。

E1414

CPU # temp exceeding range. Check CPU heatsink.

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

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

CentOS 5.5

2010年05月20日 01時55分51秒 | Weblog
RHEL 5.5 の発売から少し時間が経ち、CentOS 5.5 もリリースされたので、研究室の CentOS 5.4 のマシン 26 台をすべて 5.5 にアップグレードした。ただし、現在計算中のクラスタ計算機はまだ reboot を行っていない。ちなみに ACML-GPU を使う場合では RHEL(CentOS) 5.x が良いらしい。
コメント
この記事をはてなブックマークに追加

とっても大きな SDP その3

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

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


追記;少し勘違いしておりまして、もう解けてました。SDPARA と某スパコン(2048コア)で解けなかった問題が SDPA 64bit と下記の計算サーバ1台で解けてしまいました。

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
コメント (2)
この記事をはてなブックマークに追加

ブログ5周年

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

SDPA クラスタ越え その2

2010年05月17日 22時25分31秒 | Weblog
予算を集めたり価格の交渉を行ったりといろいろと努力して、新クラスタの計画が以下のように変更になった。これが実現すれば新クラスタは現(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 : 未定
コメント
この記事をはてなブックマークに追加