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

疎な 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)

SDPARA の改造 その３

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)

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 よりも相当速い。

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

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

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

問題２: theta3.dat-s
1: マシン１ : 9.103s
2: マシン２ : 37.323s

SDPA 7.3.0 v.s. SDPA 7.2.1 その２

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

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


○マシン１ (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

○マシン２ (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

○マシン３ (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

○マシン４ (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

○マシン５ (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

○マシン６ (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 その１

SDPA 7.2.1 から 7.3.0 まで改造を行ってきたが、以下の新型マシンでは 7.3.0 が高性能を発揮することが確認されている。

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

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

○マシン１ (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

○マシン２ (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

○マシン３ (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 時間 その２

マニュアルに以下のように書いてあったので、今度はマルチコアを利用して高速に make を行う。日本からだと lapack-3.1.1.tgz のダウンロード時間が長いので予めダウンロードしておくことにする。ただし各マシンでのコンパイラ(gcc/gfortran)のバージョンが異なっている。またコアが１個しか無いマシン(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)

半正定値条件の強さ

添付の図中にもあるのだが、変数の二次式 (例えば 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 の値は近い値にはならない。問題によってはいろいろな制約式を追加することによって状況が改善するのだが、一般形での制約強化という方法を見付けるのは難しそうだ。

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

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

GotoBLAS の make 時間

特に深い意味はないのだが、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

SDPA-QD と SDPA-DD

最近流行している多倍長計算（高精度計算）であるが、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 では４倍精度程度で十分であり、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;

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

今度は 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

○実験１ (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 月

そろそろ 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

○実験１ (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

○実験２ (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

現在レンタルしている 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 つくば合宿

毎年恒例のつくば合宿を５月３０日（土）、３１日（日）に行う予定です。講演＆宿泊場所は例年通りで筑波大学内の施設の予定しています。講演者は近日中に募集を開始します。今年も若手の方に講演をお願いします。

１：大学院生（修士、博士）
２：若手研究者（助教、ポスドクなど）
３：その他（元院生の現社会人あるいは自称若手など）

今年も新企画の特別セッションを行います。詳細は近日中にお知らせします

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

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