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

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

SDPA の数値実験 2009 年 3 月 その3

2009年03月31日 03時26分56秒 | Weblog
疎な SDP だと性能限界というのがわかりにくいので、どこまで速くなればいいのかというのは判断が難しい。例えば量子化学の SDP を解いてみる。各ソフトウェアで実行すると以下のようになる。

1: SDPA 7.2.1 ; 115.8s
2: SDPA 7.3.0 ; 22.7s
3: CSDP 6.0.1 ; 29.4s
4: SDPT3-4.0β ; 145.9s
5: SeDuMi 1.2 ; 61.2s

さらに細かく調べると F3 式の計算時間が大幅に減っていることがわかる。確証はないのだが、これ以上大きく計算時間を減らすのは難しいかもしれない(多少の改善は可能だろう)。

○F3 式の計算時間
SDPA 7.2.1 ; 108.0s
SDPA 7.3.0 ; 21.0s

○: SDPA 7.3.0 : GotoBLAS 1.30b9 + MUMPS 4.8.3
○: CSDP 6.0.1 : GotoBLAS 1.30b9
○: SDPT3-4.0β : MATLAB : 7.7.0.471 (R2008b) + Intel MKL + CHOLMOD
○: SeDuMi 1.2 : MATLAB : 7.7.0.471 (R2008b) + Intel MKL + CHOLMOD

○実行マシン:Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64 (8コア使用 : OMP_NUM_THREADS=8)
コメント (2)
この記事をはてなブックマークに追加

SDPARA の改造 その3

2009年03月30日 14時54分24秒 | Weblog
SDPARA 7.2.1 から SDPARA.7.2.1.rev8 へ改良していく過程で、SDPA 7.2.1.rev8 と同じように Schur complement 行列の計算をマルチスレッド化してあるので(多少異なるが基本的にはやり方は同じ)、以下のプロセスとスレッドの数の組合せにおける結果に変化が起きている。
以下はほんの一例だが、合計で 128 コア使用する場合でも SDPARA 7.2.1.rev8 ではプロセス数を減らしてスレッド数を多めにした方が良いことがわかる。他の例題でも 16x8, 32x4 の方が 64x2 や 128x1 よりも速くなることが多いが、これはマルチスレッド化が良い影響を与えているということでもある。いずれはさらに巨大なスパコンでの動作も予定している。

1: 16 プロセス x 8 スレッド
SDPARA 7.2.1 : 12.905s
SDPARA 7.2.1.rev8 : 11.226s

2: 32プロセス x 4 スレッド
SDPARA 7.2.1 : 11.547s
SDPARA 7.2.1.rev8 : 12.104s

3: 64プロセス x 2 スレッド
SDPARA 7.2.1 : 18.984s
SDPARA 7.2.1.rev8 : 15.844s

4: 128プロセス x 1 スレッド
SDPARA 7.2.1 : 47.441s
SDPARA 7.2.1.rev8 : 46.186s

○実験データ
mDIM = 6910
nBLOCK = 1
bLOCKsTRUCT = 1001
thetaG51.dat-s

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.2 for x86_64
Linpack : R_max = 1.435TFlops, R_peak = 1.618TFlops, R_max / R_peak = 88.69%
コメント
この記事をはてなブックマークに追加

Atom 対 Celeron (Coppermine)

2009年03月29日 01時18分20秒 | Weblog
Celeron (Coppermine) は当時(2000年ごろ)の Pentium III の L2 キャッシュ 256KB の半分だけ使えるようにした CPU なので、中身的には Pentium III とほとんど一緒である。当時は結構速いマシンだと思っていたが、さすがに Ubuntu 8.10 などの最新 Linux をインストールすると動きはかなり重い。それでもビデオカードを GeForce 6600 に変更したので、Windows 2000 と Ubuntu はそこそこの速さで動く。当時の SDPA は Ver. 5.x の時代だが、開発においてはアルゴリズム的な工夫がメインであって現在のような実装面での工夫はほとんど行わなかった。
速度は CPU だけではなく、メモリや周辺機器などの性能にも影響を受けるのだが、さすがに Atom でも Celeron (Coppermine) には圧勝する。しかし、この Celeron でも SDPA Ver.1.x の開発に用いた SONY NEWS-5000WI(CPU MIPS R4400 133MHz) よりは比較にならないほど速いし、博士論文時に用いた Pentium II 300MHz よりも相当速い。

○実行マシン1:Intel Atom 330 (1.6GHz) : メモリ 2GB : Fedora 10 for x86_64 ; 2008年
○実行マシン2:Intel Celeron (Coppermine) (600MHz ; クロックアップして 675MHz) : メモリ 512MB : Ubuntu 8.10 for X86 ; 2000年

GotoBLAS 1.30b9 make 時間
1: マシン1 : 2 コア 9m15.232s; (1 コア 18m49.992s)
2: マシン2 : 1 コア 63m12.299s

問題1: mcp500-1.dat-s
1: マシン1 : 17.533s
2: マシン2 : 1m30.785s

問題2: theta3.dat-s
1: マシン1 : 9.103s
2: マシン2 : 37.323s
コメント
この記事をはてなブックマークに追加

SDPA 7.3.0 v.s. SDPA 7.2.1 その2

2009年03月28日 14時03分35秒 | Weblog
前回の続きになる。実行マシン5と6は旧式でも低性能でもないのだが、参考にために加えておいた。SDPA 7.3.0 は 7.2.1 に対して全てのマシンで性能が上がっていることがわかる(シングルスレッドの VIA Nano を含めて)。高周波数版 Pentium と言われる Atom だが、残念ながら 2002 年の Athlon MP にも劣っている。ここ数年でマルチコア化も含めて CPU が非常に高速化したという印象を受ける。

○実行マシン1:Intel Atom 330 (1.6GHz) : メモリ 2GB : Fedora 10 for x86_64 ; 2008年
○実行マシン2:VIA Nano L2200 : メモリ 3GB : Fedora 10 for x86_64 ; 2008年
○実行マシン3:AMD Athlon MP 2400+ (2.0GHz) : メモリ 2GB : Ubuntu 8.10 for x86 ; 2002年
○実行マシン4:AMD Opteron 270 (2.0GHz) : メモリ 4GB : CentOS 5.2 for x86_64 ; 2005年
○実行マシン5:AMD Phenom 9950 (2.6GHz) : メモリ 8GB : Fedora 10 for x86_64 ; 2008年
○実行マシン6:Intel Xeon E5345 (2.33GHz) : メモリ 16GB : CentOS 5.2 for x86_64 ; 2007年


○マシン1 (2スレッド:OMP_NUM_THREADS=2)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 5m19.346s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 4m37.740s

○マシン2 (1スレッド:OMP_NUM_THREADS=1)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 5m14.815s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 5m6.156s

○マシン3 (2スレッド:OMP_NUM_THREADS=2)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 4m36.691s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 3m37.414s

○マシン4 (2スレッド:OMP_NUM_THREADS=2) 4スレッドでは非常に低速
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 2m21.498s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 2m2.988s

○マシン5 (4スレッド:OMP_NUM_THREADS=4)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 44.663s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 27.109s

○マシン6 (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 33.020s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 19.985s
コメント
この記事をはてなブックマークに追加

SDPA 7.3.0 v.s. SDPA 7.2.1 その1

2009年03月27日 14時02分34秒 | Weblog
SDPA 7.2.1 から 7.3.0 まで改造を行ってきたが、以下の新型マシンでは 7.3.0 が高性能を発揮することが確認されている。

○実行マシン1:AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64
○実行マシン2:Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン3:Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64

例えば、問題 theta6.dat-s では以下のような結果になる。

○マシン1 (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 35.181s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 16.224s

○マシン2 (4スレッド:OMP_NUM_THREADS=4)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 23.705s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 15.743s

○マシン3 (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.2.1 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 24.342s
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 15.981s

これらの高性能マシンで性能が出れば十分だが、それでも旧式 or 低性能マシンでの性能向上(あるいは悪化)も気になるので、調査してみることにしよう。
コメント
この記事をはてなブックマークに追加

GotoBLAS の make 時間 その2

2009年03月26日 12時15分49秒 | Weblog
マニュアルに以下のように書いてあったので、今度はマルチコアを利用して高速に make を行う。日本からだと lapack-3.1.1.tgz のダウンロード時間が長いので予めダウンロードしておくことにする。ただし各マシンでのコンパイラ(gcc/gfortran)のバージョンが異なっている。またコアが1個しか無いマシン(HT も含む)は測定から除いた。

1. Really really quick way to build library

Type "make" or "gmake". Also you can specify -j option to make
compile faster if you have SMP system.

$shell> make -j 4


1: Intel Xeon 5460 (3.16GHz); 8 コア 48.332s ; (1 コア 2m34.010s)

2: Intel Core i7 (3.2GHz); 4 コア 1m24.630s ; (1 コア 2m45.585s)

3: AMD Opteron 2384 (2.7GHz); 8 コア 50.341s ; (1 コア 2m55.305s)

4: Intel Xeon 5160 (3.0GHz); 4 コア 1m36.635s ; (1 コア 3m0.099s)

5: Intel Core 2 E8200 (2.6GHz); 2 コア 2m53.499s ; (1 コア 3m2.659s)

6: AMD Opteron 2356 (2.3GHz); 8 コア 1m3.309s ; (1 コア 3m41.458s)

7: Intel Xeon E5345 (2.33GHz); 8 コア 1m5.656s ; (1 コア 3m46.993s)

8: AMD Opteron 270 (2.0GHz); 4 コア 3m35.027s ; (1 コア 5m34.677s)

10: AMD Athlon-MP (2.0GHz); 2 コア 10m24.077s ; (1 コア 10m34.590s)

12: Intel Atom2 (1.6GHz); 2 コア9m15.232s; (1 コア 18m49.992s)
コメント
この記事をはてなブックマークに追加

半正定値条件の強さ

2009年03月25日 01時05分07秒 | Weblog
添付の図中にもあるのだが、変数の二次式 (例えば z z^T)を SDP の定式化に組み入れるためには Z - z z^T = O と置いてから Z - z z^T succeq O と緩和する。その後は Schur complement の仕組みを用いて図中のように Z, z, z_0(=1) に関する半正定値条件が完成する。いろいろと試してみたのだが、この仕組みだけだと条件が弱いせいなのか、Z と z z^T の値は近い値にはならない。問題によってはいろいろな制約式を追加することによって状況が改善するのだが、一般形での制約強化という方法を見付けるのは難しそうだ。
コメント
この記事をはてなブックマークに追加

ハイブリッドセル生産方式

2009年03月24日 00時49分09秒 | Weblog
多品種少量生産のためにセル生産方式などが行われてきたのだが、すでに工場現場では次の生産方式(ハイブリッドセル生産方式)が登場しようとしている。日経ビジネスの記事を見ていたらパナソニック電工ではこれまでの派遣社員をセルの中心に置く形からロボット革命ということで新しいハイブリッドセル生産方式の準備を進めている。ハイブリッドセル生産方式とはセル生産に7,8台のロボットを組み合わせて従来の3倍の生産性を目指している。派遣社員でも海外と比べると人件費が割高で国内で生産体制を維持するためにはセル生産方式でも一人あたりの生産性を上げるしかないということだろう。どこの国とは言わないが人件費の安さだけで勝負しているようでは世界のトップにまで出るのは難しい。
コメント
この記事をはてなブックマークに追加

GotoBLAS の make 時間

2009年03月23日 01時24分41秒 | Weblog
特に深い意味はないのだが、GotoBLAS(1.30b9) の make 時間を計測してみた(ただし1コアのみで make)。やはり Atom が最下位になった。ご参考までに。

1: Intel Xeon 5460 (3.16GHz); 2m34.010s

2: Intel Core i7 (3.2GHz); 2m45.585s

3: AMD Opteron 2384 (2.7GHz); 2m55.305s

4: Intel Xeon 5160 (3.0GHz); 3m0.099s

5: Intel Core 2 E8200 (2.6GHz); 3m2.659s

6: AMD Opteron 2356 (2.3GHz); 3m41.458s

7: Intel Xeon E5345 (2.33GHz); 3m46.993s

8: AMD Opteron 270 (2.0GHz); 5m34.677s

9: Intel Pentium 4 (3.06GHz); 7m0.381s

10: AMD Athlon-MP (2.0GHz); 10m34.590s

11: VIA Nano L2200 (1.6GHz); 16m58.088s

12: Intel Atom2 (1.6GHz); 18m49.992s
コメント (2)
この記事をはてなブックマークに追加

SDPA-QD と SDPA-DD

2009年03月22日 00時33分59秒 | Weblog
最近流行している多倍長計算(高精度計算)であるが、SDPA では以下のソフトウェアを採用している。GMP を採用しているのは SDPA-GMP, QD (疑似 8 倍精度), DD (疑似 4 倍精度)を採用しているのが、それぞれ SDPA-QD, SDPA-DD となる。

ライブラリ GMP (任意精度ライブラリ)
http://gmplib.org/
指数部は 32 or 64bit, 仮数部は 64bit 単位で指定する

ライブラリ qd (擬似 4倍、8倍精度ライブラリ)
http://www.cs.berkeley.edu/~yozo/
qd (仮数部 212bit), dd (仮数部 106bit)

○実験結果 (gpp124-4.dat-s)
SDPA 7.2.1.rev8(仮数部53bit) ; 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(仮数部212bit) ; 1m4.486s ; relative gap = 9.0228025522551977e-11
SDPA-DD 7.1.2(仮数部106bit) ; 7.299s ; relative gap = 9.0219191406178191e-11

仮数部の値が近いのが原因なのか SDPA-GMP と SDPA-QD の実行時間には差はあまりない(GMP は結構優秀)。SDPA-QD は SDPA-GMP, SDPA-DD よりはかなり高速であるが、通常の SDPA と比較すると数十倍以上の差がある。結局 SDPA では4倍精度程度で十分であり、SDPA-DD の高速化が大きな課題になる。

○実行マシン:Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○パラメータファイル
200 unsigned int maxIteration;
1.0E-10 double 0.0 <epsilonStar; 1.0E5 double upperBound;
0.1 double 0.0 <= betaStar < 1.0;
0.2 double 0.0 <= betaBar < 1.0, betaStar <= betaBar;
0.9 double 0.0 <gammaStar < 1.0;
コメント (4)
この記事をはてなブックマークに追加

SDPA の数値実験 2009 年 3 月 その2

2009年03月21日 12時20分55秒 | Weblog
今度は Sparse 系の問題に対する数値実験を行ったので、結果を報告する。添付の表を参照していただきたい。

○実験環境
CPU : AMD Opteron 2384 2.7GHz : 2 CPU, 8 cores
Memory : 32GB
OS : CentOS 5.2 64bit
Compiler : gcc/g++/gfortran 4.1.2
MATLAB : 7.7.0.471 (R2008b) Multi-thread : OMP_NUM_THREADS=8

○実験1 (Table 3, 4)
Sparse 系の中から主要な問題を選んで実験を行う

1: SDPA 7.3.0β : GotoBLAS 1.30b7 + MUMPS 4.8.3
2: CSDP 6.0.1 : GotoBLAS 1.30b7
3: SDPT3-4.0β : MATLAB : 7.7.0.471 (R2008b) + Intel MKL + CHOLMOD
4: SeDuMi 1.2 : MATLAB : 7.7.0.471 (R2008b) + Intel MKL + CHOLMOD
コメント
この記事をはてなブックマークに追加

SDPA の数値実験 2009 年 3 月

2009年03月20日 14時29分11秒 | Weblog
そろそろ SDPA の開発に一区切りを付けて論文等に結果をまとめようと思うので、いろいろな数値実験を行っている。現時点ではこのような感じになっているので、添付の表を参照していただきたい。

○実験環境
CPU : AMD Opteron 2384 2.7GHz : 2 CPU, 8 cores
Memory : 32GB
OS : CentOS 5.2 64bit
Compiler : gcc/g++/gfortran 4.1.2
MATLAB : 7.7.0.471 (R2008b) Multi-thread : OMP_NUM_THREADS=8

○実験1 (Table 1)
SDPLIB の中から主要な問題を選んで実験を行う

1: SDPA 7.3.0β : GotoBLAS 1.30b7 + MUMPS 4.8.3
2: CSDP 6.0.1 : GotoBLAS 1.30b7
3: SDPT3-4.0β : MATLAB : 7.7.0.471 (R2008b) + Intel MKL + CHOLMOD
4: SeDuMi 1.2 : MATLAB : 7.7.0.471 (R2008b) + Intel MKL + CHOLMOD

○実験2 (Table 2)
SDPA (pthread) と CSDP (OpenMP) との比較
1. SDPA 7.3.0β : 8 threads -→ pthread(Schur complement), GotoBLAS(DGEMM, etc.)
2. CSDP 6.0.1.OMP : 8 threads -→ OpenMP, GotoBLAS(DGEMM, etc.)
コメント
この記事をはてなブックマークに追加

Amazon EC2 での SDPA

2009年03月19日 03時18分28秒 | Weblog
現在レンタルしている Amazon EC2 の CPU は Intel(R) Xeon(R) CPU E5345 @ 2.33GHz になっているが、ちょうど同じ CPU のマシンを保有しているので、通常の環境と Amazon EC2 上での SDPA の性能を比較してみよう。

●問題 theta6.dat-s
1: Amazon EC2
SDPA 7.2.1 + GotoBLAS 1.30b7 (4スレッド) : 70.0秒(18反復)
SDPA 7.2.1.rev8 + GotoBLAS 1.30b7 (4スレッド) : 53.8秒(18反復)

2: 実機
SDPA 7.2.1.rev8 + GotoBLAS 1.30b7 (4スレッド) : 42.6秒(18反復)

仮想マシン(EC2)上でもマルチスレッドで高速動作するように様々な工夫を行ってきたが、上記の結果を見ると結構差がつまってきたように見える。
コメント
この記事をはてなブックマークに追加

SCOPE つくば合宿

2009年03月18日 02時55分26秒 | Weblog
毎年恒例のつくば合宿を5月30日(土)、31日(日)に行う予定です。講演&宿泊場所は例年通りで筑波大学内の施設の予定しています。講演者は近日中に募集を開始します。今年も若手の方に講演をお願いします。

1:大学院生(修士、博士)
2:若手研究者(助教、ポスドクなど)
3:その他(元院生の現社会人あるいは自称若手など)

今年も新企画の特別セッションを行います。詳細は近日中にお知らせします
コメント (2)
この記事をはてなブックマークに追加

最適化オンライン・ソルバーとクラウドコンピューティング

2009年03月17日 23時02分47秒 | Weblog
クラウド関係やITロードマップ(予想も含む)に関する書籍を幾つか読んだ。参考にしておいて申し訳ないのだが、やはり調査、分析だけだと物足りないというか、研究、開発の方に携わりたいという話をしていたら賛同者が多かった。
以前の最適化オンライン・ソルバーの図では今後登録される予定の最適化問題もすでに登録されているように見えるので一部修正を行った。クラウドコンピューティングという概念で考えると、Web サーバだけ手元にあれば良く、図中の計算用サーバは無くてもオンライン・ソルバーの運用はできる。さらに Web サーバも自前で持つ必要も無いので、最適化ソフトウェアさえ持っていれば多様なサービスが提供できることになる。本当はこのオンライン・ソルバー自体を配布しても良いのだが、アプリケーションごとにカスタマイズする必要があるので、この点が面倒である。ソースを配布するのはマニュアル作りやサポートが大変なので、こういった形態でサービスを行うもの良いだろう。
コメント
この記事をはてなブックマークに追加