SDPA-QD, DD 7.1.2 バグ修正

昨日に引き続いて SDPA-QD 7.1.2 と SDPA-DD 7.1.2 のバグが修正されたので、この二つの修正版も upload した。多倍長計算は計算結果の検証が難しいので（他の計算では得られない高精度な値なので)、バグの発見というのもまた難しい。多倍超計算の検証方法というのもこれからは考えていく必要があるだろう。

SDPA-GMP 7.1.2 バグ修正

SDPA-GMP で幾つか精度の関する問題が発生したので修正版を SDPA のサーバに置いた。本来(普通の SDPA)ならばそれほど致命的ではない精度の問題であるが、高精度計算を目的とする SDPA-GMP なので再実験を行った方が良い場合もある。具体的には LP 部分(対角部分)があり、その入力が非整数だと、このバグの影響を受けることになる。

KSMAP 合宿 in 明日香村 発表

KSMAP の合宿で発表を行うことにした。"最適化ソフトウェア：今後の世界での戦い方" という題名での内容だが、戦わないで(海外のソフトを使うだけで)生きていきたい人も日本には多いようなので、みんなで戦おうという意味ではない。自分の技術や成果を世界中で広く使ってもらいたいという人に対する提案になる。
前にも書いたように海外(特に最適化研究と応用がさかんな所）では、最適化問題を解くという試みは理論から実装、パラメータ設定、並列化までの総力戦になっているのだが、横の繋がりが希薄な国内では全く状況が異なる。

Linear Programming と Exact computation

以前に Linear Programming と Exact computation の話題(特に ISMP 2009)での発表について触れたが、一つの方法として幾何学的なアプローチで多面体の全ての端点の座標を厳密に求めるというのも考えられるそうだ。しかし端点の数は制約式や変数の数の指数オーダになるので、実行時間的に見れば実用的ではないだろうが、何か上手なアプローチも考えられるのかもしれない。単体法で部分的に多倍長計算を用いるという方法が採用されているが、精度面で見れば係数行列の値が変化しない内点法の方が単体法よりも有利に思える。速度面だけでなく精度面での両者の比較があれば面白い。

Optimization 98

もう１０年以上前に参加した国際会議 Optimization 98 のホームページがまだ残っていたのでちょっと驚いた。国際会議が終わるとホームページを閉める所も多いが、プログラムなどの情報を中心に可能ならば残しておく方が良いのではないか。
ホテルの予約等も Web 等ではなく Fax で行ったり、何の暗号化もなくクレジットカードの番号をメイルで送ったりと時代の違いを感じる。すでに PowerPoint や液晶プロジェクターというものは数年前から出現していたが、会場には OHP しか用意されていなかったので、せっかく PowerPoint で作成した資料を OHP シートにカラー印刷して持っていった。

オンラインソルバー追加

オンラインソルバーに関しては制約充足問題(CSP)のプログラムを追加することになった。インターフェイスの部分に関しては検討中だが、普通にテキストファイルでの入出力を予定している。また CSP のプログラムを用いることによって、他の最適化問題を解くこともできる。混合整数計画問題(MIP)では ParaSCIP(SCIP の並列版)の登録を予定しているが、これはデータファイルの提供を許可して下さる方のみが使用できるようになる。このデータファイルは SCIP の性能解析などに使われる予定になる。

RAMP 2009 シンポジウム

RAMP 2009 シンポジウムが松江で開催される。この前の ISMP 2009 シンポジウムを見ていると海外では以下の流れが非常に強くなっているが、日本の方は変わることが出来るだろうか？

1: 理論的な研究であっても数値実験による評価、検証が必須
2: 最適化問題を解くという試みは理論から実装、パラメータ設定、並列化までの総力戦

SDP ソルバーとメモリ使用量

各 SDP ソルバーのメモリ使用量についての実験結果を幾つか掲載する。画像が見にくい方はこちらの PDF ファイルを参照していただきたい。実験に用いた環境は以下の通りである。

CPU : Intel Xeon X5550 2.67GHz (2 CPUs, 8 total cores)
Memory : 72GB
OS : Fedora 11 64bit Linux
Compiler : gcc/g++/gfortran 4.4.1
MATLAB version : 7.8.0.347 (R2009a)
Numerical Libraries : GotoBLAS 1.34(for SDPA and CSDP) and
MUMPS 4.9 (for SDPA).

Table 12 は量子化学系の問題で Schur complement 行列が密になるので、この計算のマルチスレッド化が有効になる。SDPA のメモリ使用量が CSDP よりも大分多めになるのは、このマルチスレッド計算のためであって、各スレッドで二つほど途中計算に必要な行列を確保している（それでも速度は速い）。SDPT3 と SeDuMi は MATLAB 上で動作しているのだが、MATLAB 側に原因があるのかメモリ消費量が多めになる。

Table 13 の方はセンサーネットワーク系の問題で、特に SDPA の場合では Schur complement 行列が疎になる。SDPA のメモリ使用量は他に比較して少なく、しかも速度も速い。SDPT3 のメモリ使用量が非常に多いが、これは一種のバグなので次期バージョンで修正されるそうだ。

並列計算と精度

並列計算を行う場合にはデータ移動量に対する計算量の比がある程度大きいことが必要になるので、最適化問題においても半正定値計画問題や整数計画問題などは並列化に向いているのだが、例えば線形計画問題は単独ではあまり並列計算に向いていないと言える。ここで言う並列化とはスレッド並列だけでなく、ある程度大きな数でのプロセス並列も指している。ところが線形計画問題での並列計算研究というのを見かけたので、中身を見てみると精度を上げるために並列計算を行っている。精度を上げるためには、例えば多倍長計算などのように計算量を増やすことになるが、計算量が増えるということは全体として遅くなる一方、並列計算には敵した構造になっていく。今後は精度を上げるために並列化するという研究が増えていくかもしれない。

CEATEC Japan 2009

今年も１０月６日から１０日まで幕張メッセで CEATEC Japan 2009 が開催される。毎年展示等を見学に行っているが、今年は前後にいろいろとあって忙しいので参加できるのかわからない。仕事として見た場合には興味がある、あるいは必要であると思われる技術や製品が多いのだが、特にデジタル家電関係で個人的な興味が湧くものがあまり無い。今以上に高精細化、大容量化、デジタル化しても規制も厳しくなったり、費用が増えるなど扱いにくくなるだけで、わざわざ率先して進んでいこうという気持ちになれない。やはり、より不便になる、より時間を取られるようになる、よりお金がかかるようになるという方向には進んでいかない。

イノベーションジャパン 2009 発表の元ファイル

イノベーションジャパン 2009 の発表はスライド 24 枚、発表時間 20 分という制限があるので、中身をかなり削ることになった。そこで元のファイルを以下の場所に置いた(38 枚 : 6.5Mbytes)。

http://sdpa.indsys.chuo-u.ac.jp/~fujisawa/innovation-japan-2009-org.pdf

今後の研究キーワードに "超大規模データ + 最先端理論 + 超高速計算" を採用することになった。SDPA による計算などはこれに相当する。他にもこのキーワードで研究したい内容が幾つかある。

OpenMPI と MPICH2-MX それに Intel Fortran

SDPA クラスタの方は、SDPARA の数値実験でフル稼働中なので、サブの POWER クラスタで実験を行う。

○ POWER クラスタ
4 Nodes, 6 CPUs, 32 CPU cores;
CPU : Intel Xeon E5345 2.33GHz (quad cores) x 2 / node
Memory : 16GB / node
HDD : 2TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.3 for x86_64

1: OpenMPI 1.33 v.s. MPICH2-MX 1.1.1

○OpenMPI :
> export OMP_NUM_THREADS=4
> time mpirun -np 4 --mca mtl mx --mca pml cm -machinefile ~/.openmpi/hostfile ./sdpara.openmpi ~/data/quantum/LiH.1Sigma+.STO6G.pqgt1t2p.dat-s out

ALL TIME = 18.771264

○MPICH2-MX :
> export OMP_NUM_THREADS=4
> time /usr/local/mpich2-mx/bin/mpiexec -n 4 ./sdpara.mpich2.gcc ~/data/quantum/LiH.1Sigma+.STO6G.pqgt1t2p.dat-s out2

ALL TIME = 17.833036

やはり MPICH2-MX の方がやや速い


2: Intel Fortran Compiler 11.1 v.s. GNU gfortran 4.1.2

○Intel Fortran Compiler 11.1 :
> export OMP_NUM_THREADS=4
> time /usr/local/mpich2-mx/bin/mpiexec -n 4 ./sdpara.mpich2.intel ~/data/d3s1Kn0r03a8.dat-s out-1

ALL TIME = 39.507785

○GNU gfortran 4.1.2 :
> export OMP_NUM_THREADS=4
> time /usr/local/mpich2-mx/bin/mpiexec -n 4 ./sdpara.mpich2.gcc ~/data/d3s1Kn0r03a8.dat-s out-2

ALL TIME = 35.657532

何で gfortran の方が速いのか？ 通常は Intel Fortran の方が速いのに SDPA 関係は Intel コンパイラであまり解くをしたことがない。

OpenMPI と Myrinet その２

前回でインストールが終わったので、今度は SDPARA の実行を行う. mpich2-mx で SDPARA を作るのも、OpenMPI で SDPARA を作るのもほとんど一緒だが、最後に mpicxx を用いて mpif90 でコンパイルしたバイナリも一緒にくっつけるのでリンク時に以下のオプションが必要になる.

mpicxx ..... -lmpi_f77 -lmpi_f90

OpenMPI + Myrinet で SDPARA を実行するときは以下のように指定する.

mpirun -np 16 --mca mtl mx --mca pml cm -machinefile ~/.openmpi/hostfile ./sdpara ~/data/quantum/LiH.1Sigma+.STO6G.pqgt1t2p.dat-s out

しかし、mpich2-mx + Myrinet の方が OpenMPI + Myrinet よりも安定して高速なようだ。一般的には OpenMPI の方が mpich2 よりも速いと言われているので、Myrinet との相性の問題なのだろうか？ もう少し調べてみることにする.

OpenMPI と Myrinet その１

SDPA クラスタでは、これまで Myricom 社から提供されている mpich-mx, mpich2-mx を用いてきたが、ユーザからの要望もあったので、OpenMPI も使えるようにインストールを行った。

○ 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.3 for x86_64

1: まずは http://www.open-mpi.org/ から最新版をダウンロードする。

2: OpenMPI の configure & make & install
> tar xvzf openmpi-1.3.3.tar.gz
> cd openmpi-1.3.3
> mkdir build
> ../configure --prefix=/usr/local/openmpi --with-mx=/opt/mx --with-mx-libdir=/opt/mx/lib
Myrinet を OpenMPI から使用するので mx の場所を上記のように指定する.
> make all
> make install

3: クラスタの全てのノードにおいて以下の作業を行う
3-1: /usr/local/openmpi/bin にパスを通す
3-2: /etc/ld.so.conf に /usr/local/openmpi/lib を追加して /sbin/ldconfig を実行する

4: 自分のホームディレクトリに .openmpi というフォルダを作る
4-1: ~/.openmpi/mca-params.conf というファイルを作って、plm_rsh_agent = /usr/bin/rsh を１行書き込む
4-2: ~/.openmpi/hostfile というファイルを作って、以下のようにクラスタのノード名を書き込む.
sdpa01
sdpa02
sdpa03
sdpa04
sdpa05
sdpa06
sdpa07
sdpa08
sdpa09
sdpa10
sdpa11
sdpa12
sdpa13
sdpa14
sdpa15
sdpa16

sdpa01 で同時に４プロセス走らせるならば以下のような書き方も可能. これでインストールは終わり.
sdpa01 slot=4

オンラインコアロケーション(On-line Resource Co-allocation)

オンラインコアロケーション(On-line Resource Co-allocation)の問題はネットワークフローの問題に変換して整数計画問題として定式化できるので、オンラインのシステムでは整数計画ソルバーを持った最適化エンジンを加えることによって対応が可能である（もちろん整数計画問題のサイズがあまりにも大きいと実用的な時間では解けない）。
このシステムで現在想定しているサイズの整数計画問題を様々な整数計画ソルバーを用いて解いてみよう。

1: CPLEX 11.2 : 0.24s

2: SCIP 1.1.0 : 0.41s

3: Cbc 2.3.0 : 0.58s

4: lp_solve 5.5.0.15 : 0.04s

5: glpk 4.39 : 3.07s

やはり GLPK だけ遅いが、残りのソルバーではこの程度のサイズならばかなり速く解ける。特に lp_solve が意外と速いようだ。