新 SDPA サーバ

現在の SDPA サーバは自作マシン（しかも適当に？急いで作ったマシン）なので、本当はサーバには向かない（それでも現在まで異常は発生していないが）。よって、SDPA サーバも以下の仕様の PowerEdge SC1435 を購入して交替させる予定である。研究室の新しいマシンはみんな Intel Xeon になってしまったので、一台くらい AMD Opteron (Barcelona)があった方が良い。あと AMD Phenom は演算性能で Intel Core2 に劣り、TDP の値も大きいのだが、メモリバンド幅が大きい（最高で17.1GB/s)のが魅力なので、疎データ時の SDPA の性能評価用に一台購入しても良いだろう。


○ Dell PowerEdge SC1435
プロセッサ
[Quad-Core] AMD Opteron 2360SE (2.5GHz/2MB L3キャッシュ) x 2個
メモリ
16GB (2GBx8/2R/667MHz/SDRAM DIMM ECC)
RAID構成
RAID1 (HDD x2 SAS5iR)
ハードディスク
1TB 7,200 RPM (SATA HDD/3.5インチ) x 2個
ラックレール
1U ツールレスラックキット固定式(デルラック用)

高速エレベーター

以前、台北 101 ビルに行ったときに、いろいろな資料の中に施工やエレベーターなどで日本の技術のたくさん発見することができた。５階にチケット販売所があって、ここからエレベータで展望台まで登るのだが、このエレベータが最高速度は時速 60km/h ということもあって大変速い。しかし、このエレベータ下りは随分と遅くて、時速 36km/h になる。なんでこんなに上りと下りに速度差があるかと不思議に思っていたのだが、両方乗ってみるとその理由はわかるだろう。技術的にはまだまだ速くできるそうだが、速ければ良いというわけではない。これから中東に 1000m を超える超高層ビルが登場するようだが、技術的には可能でも個人的にはあまりそばには出来て欲しくないと思っている。

MUMPS

疎な半正定値行列の Cholesky 分解の用のソルバーとして MUMPS : a parallel sparse direct solver を試している。SDPA 7.x には自前の Sparse Cholesky Solver が含まれているのだが、場合によってはこの部分がボトルネックになることもある。この MUMPS は MPI による並列化を行うこともできるので、SDP の conversion の高速化から、次期 SDPARA などに使うことも可能である。

N = 50000, NonZeros = 4985507 なので相当疎な行列になるが、このくらい疎だと並列化による効果は以下のようにあまり期待できない。以下の結果は Mehrotra型 の predictor-corrector 主双対内点法の Linear Equation の部分のシミュレーションになっている。

1: time mpiexec -machinefile ./hosts -n 1 numactl --physcpubind=0 ./simple_example
29.273s
2: time mpiexec -machinefile ./hosts -n 2 numactl --physcpubind=0,1 ./simple_example
26.056s
3: time mpiexec -machinefile ./hosts -n 4 numactl --physcpubind=0,1 ./simple_example
19.564s
4: time mpiexec -machinefile ./hosts -n 8 numactl --physcpubind=0,1 ./simple_example
17.031s
5: time mpiexec -machinefile ./hosts -n 16 numactl --physcpubind=0,1 ./simple_example
19.660s
6: time mpiexec -machinefile ./hosts2 -n 16 numactl --physcpubind=0 ./simple_example
18.107s

仮想マシンクラスタ その２

VMware Server を使おうと考えていたのだが、WMware Server のバージョンが 2.0.0 で、VMware Player のバージョンが 2.5.0 なので後者を使うことにしている。以下のように VMware Player のバージョンで随分と性能が異なる。

SDPARA 7.0.1 + GotoBLAS 1.26 の性能。
SDP の問題名 : b200-8.dat-s

VMware Player 2.0.5
1 CPU : 4m9.124s
2 CPU : 2m57.695s
4 CPU : 2m9.682s

VMware Player 2.5.0
1 CPU : 3m58.687s
2 CPU : 2m16.944s
4 CPU : 1m53.701s

仮想マシンクラスタ

図中の4台で構成されるクラスタ計算機(CPU : Intel E5345)の各ノードで仮想マシン(VMware)を動作させて、その上で CentOS 4.6 (64bit)を動作させるようにした。たった 4 台の仮想マシンであるが、クラスタ計算機として動作するようになっている。
1: 各ノードではシングルコアで OS を動作させる(SMP にはしない)。
2: NFS は行わない(ファイル共有はしない)。
3: メモリ 3GB
ネットワークは遅めなので MPI の性能は期待できないが、それでも SDPARA 7.0.1 + GotoBLAS 1.26 の性能は以下の通りである。
SDP の問題名 : b200-8.dat-s
1 CPU : 4m9.124s
2 CPU : 2m57.695s
4 CPU : 2m9.682s
いろいろな用途で使う予定になっている。

低価格 PC と Linux

日経 Linux の 11 月号に Linux が超低価格 PC に採用されない理由という記事があった。詳細は記事を見ていただくとして, Linux やフリーソフトに対する理解が足りないのが大きな理由の一つになっている。別な見方をすれば何故 Linux は無償で Windows は有償なのかがわかっていないユーザが問題を起こすために Linux 採用に踏み切れないとも言える。Dell などは低価格のミニノートに Ubuntu-8.04 をインストールして販売しているのだが、Ubuntu などを使用したければ Windows などのホスト OS 上で仮想マシンを用いれば良いので、個人的には Windows XP モデルを購入した。
日経 Linux の同号の DVD に Windows Home Server の試用版が入っていた。Linux の雑誌に Windows が付いているのは初めて見た。これも仮想マシン上で使ってみたのだが、Linux に慣れている人には魅力に乏しい。

Ninf-G 5.0.0

Ninf-G は、Ninf-G Ver.1 から使用を開始して、Ver. 2.4.0 まで使用したのだが、その後しばらく使用をお休みしていた。実はいまだに Ninf-1 を SDPA Online Solver で使用している。Ninf-G は Ver.1 から 4 までは Globus が必須とされていた(Ninf-G の G は Globus の G)。しかし、個人的には Globus の認証手続きがかなり面倒なことと、大量のポートを外部に対して開ける必要があるので、使用を敬遠していたのだが、そのように感じていた人は結構多かったらしい。
というわけで、Ninf-G 5.0.0 では、Globus を使わなくても ssh の server を用いるだけで（つまり 22 番のポートを開けるだけで)、使用ができるようになった(Ninf-G の G は Grid の G に変わったそうだ)。実際に使用してみるとインストールや実行もかなり簡単になっている。最短路問題用プログラムのクラスタ計算機での実行に使うことを想定している。
Ninf-G も Ver. 5.0.0 まではハイペースで進んできたのだが、ここで一度開発のペースを落とすらしい（開発とサポートを打ち切るわけではない）。configure & make & install が簡単なことがソフトウェア普及の重要な条件の一つであり、どこのソフトウェアとは言わないが、かなり複雑なことも多い。

仮想マシンでの実行

仮想マシンで実行を行ったときに、どの程度性能が低下するのかを調べた。ホストとゲストの OS が異なるが、それほど大きな影響はないだろう。おおよそ１割程度の性能低下でこれが大きいのか小さいのかは判断が分かれるところかもしれない。仮想マシン上では、演算能力、メモリや I/O の性能などの特性がホストのマシンとは異なる可能性があるので、作り方を変える必要があるだろう。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

○ Xeon (仮想マシン : VMware-player 2.0.5)
CPU : Intel Xeon X5460 3.16GHz
メモリ : 3GB
OS : CentOS 4.6 for x86_64

1: GLPK 4.32 整数計画問題
○ stein45.mps
Xeon : 58.661s
仮想マシン : 1m5.264s
○ air06
Xeon : 11.230s
仮想マシン : 12.768s
○ min_rep_under_thput_39600.0_test18.dat(ファイル配置最適化問題)
Xeon : 0.309s
仮想マシン : 0.360s


2: 最短路問題
○ FLA 10 クエリ(データ名は最短路問題オンライン・ソルバーと同じ)
Xeon : 0.795s
仮想マシン : 0.940s
○ LKS 1000 クエリ
Xeon : 3m28.110s
仮想マシン : 3m42.676s


3: SDP (半正定値計画問題) : SDPA 7.2.0 + GotoBLAS 1.27b5 : 1 スレッド
○ mcp500-1.dat-s
Xeon : 3.929s
仮想マシン : 4.395s
○ theta5.dat-s
Xeon : 22.860s
仮想マシン : 25.686s
○ mater-4.dat-s
Xeon : 7.039s
Opteron : 7.773s

CPLEX 対 GLPK

研究室のサーバに MATLAB 7.7.0.471 と CPLEX 11.2.0 をインストールした。両方とも遠隔からインストールしたので結構面倒だった。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

せっかくインストールしたので、CPLEX 11.2.0 と GLPK 4.32 を比較してみよう。ただし CPLEX 11.2.0 は 4 スレッド並列版である。いずれも CPLEX の方が良いことがわかる。

1: MIPLIB : stein45.mps
CPLEX : 3.17s
GLPK : 57.67s

2: MIPLIB : air06
CPLEX : 0.40s
GLPK : 10.91s

3: ファイル配置問題 : min_rep_under_thput_39600.0_test18
CPLEX : 0.07s
GLPK : 0.32s

4: ロットサイズ決定問題 : S-5-20-1-1
CPLEX 0.01s
GLPK : 309.8s

SDPA クラスタと最短路問題

グリッド・コンピューティングとクラウド・コンピューティングの違いを考えていたのだが、両者にはもともと厳密な定義があるわけではないので、まさに雲を掴むようなところがあり、結局考えてもあまり面白くないことに気がついた。グリッドの方はユーザに提供するハード＆ソフトウェアに対する定義や情報開示があって、これが大変面倒なのだが、クラウドの方は、その辺のグリッドで大変な部分が曖昧でも良いので全体的に楽なところがあるのではないだろうか。ただし、グリッドでも様々な技術が開発されて、大変な部分が楽になってくると、ますます両者の差がわからなくなってくるということになるかもしれない。自分は情報系分野の人間ではないので、個人的には自分の研究がどちらに分類されても構わないと思う。
突然の思い付きで、最短路問題のプログラムとクラウド・コンピューティング関連の技術を絡ませた新しいサービスを考えているので、SDPA クラスタを最短路問題用にも使うことにした。このクラスタは全ノードが Myrinet-10G で接続されているので、大量にファイルアクセスするアプリケーション以外はほとんど高性能で動かすことができる。しかし Amazon EC2 などでノードを複数借りた場合を想定すると、そこそこのバンド幅と演算能力で動かせるように考えておく必要がある。

様々なブラウザでの動作検証 その２

Internet Explorer 8 Beta (Ver. 8.0.6001.18241) が公表されたので、最短路 Online Solver の動作の検証を行った。IE 7 よりは相当速くなっているが、以下のように FireFox や Google Chrome の方がかなり速い。最短路 Online Solver では、今のところ IE は使わない方が良さそうだ。


1: Internet Explorer 7.0.5730.11
実行時間 : 1分20秒以上
途中でスクリプトの実行を中止するかの判断を求められる(距離と時間で２回）。実行は遅め。

2: Internet Explorer 8.0.6001.18241
実行時間 : 33秒以上
上記と同じ

3: FireFox 3.0.3
実行時間 : 20.55秒

4: GoogleChrome 0.2.149.30
実行時間 : 20.35秒

行列の conversion その２

先日の conversion の続き。今度は以下のような別のグラフを考える。よって無向枝は (1,2), (1,6), (2,6), (3,4), (3,5), (3.6), (4,5) の７本になる。

octave:13> A
A =

100 1 0 0 0 1
1 100 0 0 0 1
0 0 100 1 1 1
0 0 1 100 1 0
0 0 1 1 100 0
1 1 1 0 0 100

octave:14> B = transpose(chol(A));
octave:15> B
B =

10.00000 0.00000 0.00000 0.00000 0.00000 0.00000
0.10000 9.99950 0.00000 0.00000 0.00000 0.00000
0.00000 0.00000 10.00000 0.00000 0.00000 0.00000
0.00000 0.00000 0.10000 9.99950 0.00000 0.00000
0.00000 0.00000 0.10000 0.09900 9.99901 0.00000
0.10000 0.09900 0.10000 -0.00100 -0.00099 9.99851

max. clique は (1,2,6) と (3,4,5,6) なので、元のグラフに対して fill-in が発生している((6,4) と (6.5))。
今度は fill-in が起こらないように、点を 1,2,6,3,4,5 の順番で並べる。

octave:31> C
C =

100 1 1 0 0 0
1 100 1 0 0 0
1 1 100 1 0 0
0 0 1 100 1 1
0 0 0 1 100 1
0 0 0 1 1 100

octave:32> D = transpose(chol(C));
octave:33> D
D =

10.00000 0.00000 0.00000 0.00000 0.00000 0.00000
0.10000 9.99950 0.00000 0.00000 0.00000 0.00000
0.10000 0.09900 9.99901 0.00000 0.00000 0.00000
0.00000 0.00000 0.10001 9.99950 0.00000 0.00000
0.00000 0.00000 0.00000 0.10001 9.99950 0.00000
0.00000 0.00000 0.00000 0.10001 0.09900 9.99901

今度は max. clique は (1,2,6), (3,6), (3,4,5) なので fill-in が発生しなかった。

Ubuntu 8.04 で SDPARA

海外から Ubuntu 8.04 で SDPARA を実行したいという要望があったので、試しに SDPARA のバイナリを作ってみたところ結構大変だった。ここ数年は RedHat 系の Linux(RHEL, CentOS, Fedora, Vine など)しか使ったことがないので、Ubuntu などの debian 系は /etc 以下の構成が異なり、経験がある人ならばわかると思うのだが、これが結構戸惑うものだ。SDPARA を make するだけならば簡単だが、MPI のため rsh の設定などが必要になる。

SDPARA 1.0.1 + ATLAS 3.8.2 では以下のように動作が変になっている。

opt-ubuntu:~/tmp$ /usr/local/mpich/bin/mpirun -np 1 ./sdpara ./data/b200-9.b.dat-s out
SDPARA start at Tue Oct 14 02:18:42 2008
let me see your ...
data is ./data/b200-9.b.dat-s : sparse
parameter is ./param.sdpa
out is out

mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 -0.00e+00 +2.00e+04 7.7e-01 9.0e-01 2.00e-01
Cannot cholesky decomposition X or Z :: iam = 0 :: line 308 in rsdpa_algebra.cpp
1 1.0e+04 1.0e+00 1.0e+00 -0.00e+00 +2.00e+04 7.7e-01 9.0e-01 2.00e-01

phase.value = noINFO

一方で SDPARA 7.0.1 + ATLAS 3.8.2 or GotoBLAS 1.26 では正常に動作。というわけでライブラリの作成は成功しているようだ。

○SDPARA 7.0.1 + ATLAS 3.8.2
................
21 4.9e-11 1.1e-16 4.7e-17 +4.94e+01 +4.94e+01 1.8e-05 1.8e-05 1.00e-01

phase.value = pdFEAS
Iteration = 21
mu = 4.9497163467186202e-11
relative gap = 1.9966281288414327e-10
gap = 9.8994326934372405e-09
digits = 9.6997028147642563e+00
objValPrimal = 4.9401170306289949e+01
objValDual = 4.9401170296426372e+01
p.feas.error = 1.0658141036401503e-14
d.feas.error = 1.3411494137471891e-13
total time = 33.202
file read time = 0.077144
main loop time = 33.106304
total time = 33.202076

○SDPARA 7.0.1 + GotoBLAS 1.26
................
21 9.5e-11 7.0e-17 1.8e-17 +4.94e+01 +4.94e+01 3.4e-06 3.4e-06 1.00e-01

phase.value = pdFEAS
Iteration = 21
mu = 9.5228586846044132e-11
relative gap = 3.8577399824982333e-10
gap = 1.9045717369208827e-08
digits = 9.4136670478097493e+00
objValPrimal = 4.9401170307502554e+01
objValDual = 4.9401170288444867e+01
p.feas.error = 1.0658141036401503e-14
d.feas.error = 6.5702998597316764e-13
total time = 17.956
file read time = 0.075698
main loop time = 17.862916
total time = 17.956211

SDPA クラスタで Linpack 測定 その１０

Myrinet-10G 関係のドライバを変更したり、その他の設定を変更したりして、1GFlops だけ値が上がった。ここまで来ると 1GFlops 上げるのが非常に大変。ということで 1.435TFlops で 88.69% になった。

●新 SDPA クラスタ (2008年)
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%

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 200 4 8 13839.66 1.435e+03
----------------------------------------------------------------------------
||Ax-b||_oo / ( eps * ||A||_1 * N ) = 0.0120914 ...... PASSED
||Ax-b||_oo / ( eps * ||A||_1 * ||x||_1 ) = 0.0008527 ...... PASSED
||Ax-b||_oo / ( eps * ||A||_oo * ||x||_oo ) = 0.0001409 ...... PASSED
============================================================================

行列の conversion

今日は話が変わって、行列補完(matrix completion) のための conversion の話。詳しくは添付の図を参照のこと。

1: SDP で A_0 と A_i(i = 1,2,...,n)から aggregated sparsity pattern を作成する(行列 A*)

2: ここからは matlab あるいは octave を使う

3: A* の要素では非零要素 * を 1 (対角部分は大きめに 100) として、以下の A のような行列を作る。
A =

100 1 0 0 0
1 100 1 1 0
0 1 100 0 1
0 1 0 100 1
0 0 1 1 100

4: A を Cholesky 分解して転置する
octave:21> B = transpose(chol(A));
octave:22> B
B =

10.00000 0.00000 0.00000 0.00000 0.00000
0.10000 9.99950 0.00000 0.00000 0.00000
0.00000 0.10001 9.99950 0.00000 0.00000
0.00000 0.10001 -0.00100 9.99950 0.00000
0.00000 0.00000 0.10001 0.10002 9.99900

5: ここから先は行列 B の非零要素のみに注目する.
行列 B の一列目を見る.
1 行目, 2行目が非零要素なので、max. clique は {1,2}

6: 二列目を見る. max. clique は {2,3,4}

7: 三列目を見る. max. clique は {3,4,5}

8: 四列目を見る. clique {4,5} は max. clique {3,4,5} に含まれる

9: 五列目を見る. clique {5} は max. clique {3,4,5} に含まれる

というわけで、添付の図のように max. clique は {1,2},{2,3,4},{3,4,5} となる.