PS3 と SDPA 7.0.5

ソニーのゲーム事業が 2007 年 10 ～ 12月に黒字になり、PS3 についても販売台数が上向き始めたこともあって最悪の時期は脱しつつあるようだ。PS3 がブルーレイを搭載していることも追い風になると言われている。結構前から PS3 に搭載されている Cell には注目していて、Cell 上での最適化もいろいろと試してきた。PS3 上で SDPA を動かすという目的も 7.0.5 で一応達成した。Cell 本来の SPE をフルに活用するところまでは到達していないが、SPE が単精度計算を中心に設計されていることや、PS3 のメモリが256Mbyte に限定されていることもあって、本格的な活用は今後の課題になる。
現状では Intel & AMD 系の CPU を積んだ PC の方が速くて、メモリも多いのでメリットは少ないが、PS3 に Fedora 8 などの Linux を搭載することによって、簡単に SDPA 7.0.5 を用いることができる。詳しい方法はマニュアルを参照していただくことにして、基本的に
yum install lapack-devel blas-devel
configure
make clean
make
で終わるはずである。ただこれでは速度が遅いので、ATLAS や GotoBLAS を用いた方が良いが、前者はチューニングが終了するまでに何時間もかかるので、後者の方をお勧めする（性能も良い）。

最短路プロジェクトのホームページ

最短路プロジェクトのホームページを公開することにした。とりあえずミラーサーバの方のアドレスを以下に掲載しておく。

最短路プロジェクトのホームページ

通常の公的な予算をもらう研究とは異なり、とにかく出来る出来ないに係わらず、いろいろなアイデアを出して試してみようということになっている。本格的な実装、検証実験、最適化等については、また来年度以降に行う予定である。

検索エンジン

SDPA 7.0.5 のソースファイルをマニュアルを 2月16日の午前 1時15分ごろにサーバから公開した。各検索エンジンが SDPA 7.0.5 を見付けた時間は以下の通り。

1: Google 16日午前 9時49分 (約8時間35分)
2: Yahoo 19日午前1時6分　　(約72時間)
3: 百度(baidu) 19日午前3時11分 (約74時間)
4: msn (まだ発見できていない)

やはり Google はこの中では優秀か。

スカルトレール

Intel の新しいデュアルCPUプラットフォームで Skulltrail(スカルトレール)というのがある。すでにサーバでは Penryn コアの Xeon 54xx シリーズをデュアルで搭載したモデルが発表されているが、このようにクアッドコアの CPU を２個搭載したマシンを一般の？ハイエンドユーザに提供しようというものらしい。サーバモデルと異なるのは、４本も PCI Express x16 が搭載されていて、SLI でも CrossFire の両方をサポートする。すでに ATI Radeon HD 3870 x2 は１枚の基板中に２個の GPU を搭載しているので、これらの組み合わせたら凄そうなマシンが出来そうだ。
ただし、このマシンは熱も音も凄そうな予感がするのだが、例えば Dell の PowerEdge2900 も熱と騒音はかなりなものだ。内蔵のファンが全てフル回転したときの迫力と不快感はとてもブログでは伝わらない。よくこれらのサーバが並んでいると、冬は暖かくでいいでしょと言われるが、暖かいどころか冬でも冷房しないといけない。それにサーバの熱で部屋が暖まった場合には、たいてい人間にとって快適な温度にならないので（暑すぎたり涼しかったりして）、暖房として使うのは難しい。

MPEG 教科書

次世代 DVD は BD(ブルーレイ)陣営の勝利になったと伝えられているが、本格的に普及する前に勝負がついたというのでは、本当に勝利なのか難しいところだ。次世代 DVD は、個人的には Windows Vista と並んで pass したい製品（規格）だが、ビデオにしても高圧縮の動画をネットで配信して、大容量 HDD に貯めていく方が、ブルーレイよりも柔軟で普及しやすい(と思ったが、世界中どこの都市でも広帯域で通信できるわけではない）。動画圧縮技術も MPEG4 H.264/AVC などが主流になってきていて、これは現在の DVD にハイビジョン並みの高画質動画を割りと長時間詰め込めるという優れた技術だが、これの処理が大変重い。教科書を参考にして、MPEG H.264/AVC からリアルタイムで様々な情報を取り出して分析しようと思ったが、普通に作ると今の PC でも相当きついものがある。こんなものを苦もなく？リアルタイムできれいに再生してしまう PS3(Cell) は本当にすごい。
1996年頃(博士課程時)に、当時はまだ研究用で普及していなかった MPEG2 で同じような研究をしていた。とは言っても自分の研究ではなく、後輩の研究のお手伝いだった。郵政省の研究所で当時はまだ珍しく大変高価だったデジタルカメラを借りてきて、羽田空港のビッグバードまで撮影に行った。今だと空港で許可なく機材を持ち込んで撮影していたら捕まりそうだ。これも MPEG の教科書を参考にしてプログラムを作成した。

SDPA 7.0.5 公開中

ソースファイルとマニュアルの整備を続けていたが、とりあえず完成ということで SDPA 7.0.5 の公開を開始した。

SDPA 7.0.5 のソースファイル(tar.gz)

SDPA 7.0.5 のマニュアル

lapack と blas のライブラリがインストールされていれば(最近では多くのディストリビューションにも含まれている）、configure & make だけで終了する。ただし、これらのライブラリの性能はあまり高くないので、可能限り高速 BLAS (GotoBLAS, Intel MKL, ATLAS 等)とリンクすることをお勧めする。
ちなみにダウンロード第1号は UCLA から。第2号は Google だった。

メモリ4GB の認識

ソフマップでメモリが安かったので、DDR2-800 1GB のメモリを購入。家のパソコンに付けて 2GB から 4GB に増設した。このマシンは Windows MCE 2005 (32bit), Vine Linux 4.2(32bit), Fedora 8 (64bit)がインストールしてある。メモリを 4GB 搭載しても 32bit OS では 3GB ぐらいしか認識しないのは良く知られているが、64bit OS の Fedora 8 が起動に異様に時間がかかり、非常に動作が不安定になった。32bit OS はメモリ 3GB しか認識しないものの正常に動作。
そこで、マザーボード ASUS P5N32-SLI SE Deluxe の BIOS を最新の物に update したが、これでも状況は変わらない。さらに BIOS 設定画面で詳細設定 → チップセット → メモリリマップ機能を有効にすると BIOS 設定画面ではメモリ 3072MB となっているが、Fedora 8 ではメモリ 4GB を認識するようになった。

Online Solver と gfarm

以前から計画しているのが、Online Solver と gfarm の組合せだ。開発者の方から直接 gfarm の開発＆公開は今後も継続すると保証？をもらったので、gfarm v2 が登場したのを契機に本気で導入を考えることにした。
現行の Online Solver の問題点はいろいろあるが、例えば
1: 実行中の状態(途中経過等)がユーザに伝わらない
2: PHP や Ninf 経由なので、あまり大きなデータファイルを扱えない
よって、例えば Web サーバとクラスタ計算機を gfarm で共用ファイルシステムにすると、1 と 2 の問題の解決が容易になる。Ninf call で送るのは、ソルバーの種類、CPU 数、ファイル名などの情報だけにした方がより頑健なシステムになるように思える。いろいろと問題も発生しそうだが、とにかくやってみるのが解決への近道だ。

整数計画問題に対する高速近似解法

組合せ最適化問題に対する近似解法（メタ解法）と言えば、日本の某研究室（今はみんな分散配置されているが）が有名だが、主要メンバーが整数計画問題に対する高速な近似解法とソフトウェアの作成にも興味を持っているそうだ（急かしているみたいだが）。整数計画問題に対するソフトウェアと言えば CPLEX, XPress-MP などが有名で、オープンソースでは glpk も存在する。
今から CPLEX 並の最適解法とソフトウェアに挑戦するのも良いが、同じようなものを作っても面白くないので、メタ解法ベースの高速近似解法を実装してみるのはどうだろうか。CPLEX も超高速と言われているが、厳密解法なので、突然計算時間の指数的な要素が突出してきたりして、実時間のシステムでは使用にリスクが伴う。それに実データには、元来かなりの誤差が含まれているので、ある程度の良い近似解でも十分だろう。ただし何でも良いというわけではないので、これまでのメタ解法の知見が必要になる。
かなり古い話になるが、私はもともと研究室では SDP の内点法実装の担当ではなく、Borland C++ から NEWS OS 上の gcc/g++ への SDP ソフトの移植を手伝っているうちに、いつの間にか配属替えになって今日に至っている（今考えればこのときに LAPACK/BLAS対応にすべきだったか)。それまではメタ解法の研究をしていて、SDP でやることが無くなったら、整数計画問題に対するメタ解法に戻ろうと思っていた。でも SDP の内点法の世界ではネタが尽きないようだ(LP/QP に対する内点法だと、やることが無くなっていたかもしれない)。

sizeof とバイト数

たまに忘れてしまうので、32bit, 64bit と long double 等のバイト数についてのおさらいをする。-m32 では -m96bit-long-double がデフォルト、-m64 では -m128bit-long-double がデフォルトになっていることがわかる(gcc 4.1.2)。

> gcc -m32 sizeof.c ; ./a.out
sizeof(char) = 1
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 4
sizeof(float) = 4
sizeof(double) = 8
sizeof(long double) = 12
sizeof(int*) = 4

> gcc -m96bit-long-double -m32 sizeof.c ; ./a.out
sizeof(char) = 1
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 4
sizeof(float) = 4
sizeof(double) = 8
sizeof(long double) = 12
sizeof(int*) = 4

> gcc -m128bit-long-double -m32 sizeof.c ; ./a.out
sizeof(char) = 1
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 4
sizeof(float) = 4
sizeof(double) = 8
sizeof(long double) = 16
sizeof(int*) = 4

> gcc -m64 sizeof.c; ./a.out
sizeof(char) = 1
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 8
sizeof(float) = 4
sizeof(double) = 8
sizeof(long double) = 16
sizeof(int*) = 8

> gcc -m96bit-long-double -m64 sizeof.c ; ./a.out
sizeof(char) = 1
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 8
sizeof(float) = 4
sizeof(double) = 8
sizeof(long double) = 12
sizeof(int*) = 8

> gcc -m128bit-long-double -m64 sizeof.c ; ./a.out
sizeof(char) = 1
sizeof(short int) = 2
sizeof(int) = 4
sizeof(long int) = 8
sizeof(float) = 4
sizeof(double) = 8
sizeof(long double) = 16
sizeof(int*) = 8

最速マシンと最遅マシン

いつの間にか東芝のパソピア(PASOPIA)が処分されていたので、手持ちで最も遅いマシンは Compaq の 486DX2 40MHz(20MHz × 2) 搭載のノートパソコンか、PC-9801 DA(Turbo-486 : 486DX2 66MHz)になった(多分後者の方が遅い)。ともに MS-DOS と Windows 3.1 が動くという貴重なマシン(しかも SDPA 0.1 が DOS 窓で動く)。古いマシンと古い OS は意識的に保存しておかないと、あっという間に仮想マシンかエミュレータでしか動かなくなってしまう。こんなマシンでも Windows 3.1 上で SimCity 2000 が快適に動作する。たまには初心に帰って資源の無駄遣いを戒めるのもよい。
ただし、こんなマシンで SDPA 7.0.5 は動かないので、2006年11月9日のブログに書いた FMV DESKPOWER C2/465(Celeron 466MHz) が手持ちの再遅マシンになる。Celeron といえば元々廉価版 Pentium II のことだったが、こんなに長く続くとは思わなかった。手持ちの最速マシンは Intel X5365 3GHz なのだが、このくらい性能が異なる。

○SDPA 7.0.5 + GotoBLAS 1.23
1: theta3.dat-s
X5365 3GHz : 1.9秒 Celeron 466MHz : 64.6秒
2: mcp500.dat-s
X5365 3GHz : 4.9秒 Celeron 466MHz : 135.2秒

ちなみに論文用のデータを取るのが目的なので単に遊んでいるわけではない。

MATLAB で SDPT3 と SeDuMi

MATLAB Version 7.5.0.338で SDPT3(4.0beta) と SeDuMi (1.1)を使ってみよう。

1: SDPT3 4.0beta

> Installmex
> startup
> [blk,At,C,b] = read_sdpa('./sdplib/theta5.dat-s');
> [obj,X,y,Z] = sqlp(blk,At,C,b);

2: SeDuMi 1.1

SeDuMi の最新版は 64 bit版の Matlab では動作しない。理由は以下の通り。でも SDPT3 は 64bit 対応済み。昨年カナダで会ったときに作者に直接聞いたら SDPT3 の方は１日ぐらいで対応できたそうだ。

NOTE2: Matlab is now using a different interface for sparse matrices in 64 bit versions. They changed it without advance notice and there is no backward compatible workaround. Thus, SeDuMi will NOT work in 64 bit versions of Matlab under linux. We are testing the Windows versions right now.

ということで、まず Matlab を 32bit で起動する(SDPA フォーマットファイルの実行)

> mex -setup
> matlab -glnx86
> install_sedumi
> fname='./sdplib/mcp500-1.dat-s';
> [At,b,c,K]=fromsdpa(fname);
> [x,y,info]=sedumi(At,b,c,K);

SDPA と SDPARA (with GotoBLAS) の比較実験

こちらの英語のページに SDPA 6.2.1 と 7.0.5 と 7.1beta 及び SDPARA 7.0beta の実験結果を掲載した。問題によっては SDPA 6.x と SDPA 7.x はあまり結果が変わらないが、非常に疎な問題ではかなり結果が変わってくるので、SDPA 6.x を選ぶメリットはほとんどない。あまり身内のソフトだけで比較実験を行うと、中傷合戦みたいになってしまう。

SDPA と Vine Linux その２

調査を続けていると SDPA 7.0.5 と Vine Linux の問題と言うよりも gcc 3.3.x のバグである可能性が高くなった。gcc 3.4.x では異常は発生しない。しかし gcc も 4.2.3 までリリースされているので、今更こんな古いバージョンの gcc のバグ報告を送る必要もないだろう。Vine Linux では gcc 4.0.2 も使えるので、こちらを用いるか、自分で新しい gcc を make して用いることを勧めたい。

SDPA と Vine Linux

Vine Linux (3.x と 4.x) で SDPA 7.0.5 を make するときに、 gcc のオプションで -funroll-all-loops を付けると以下のようなエラーが発生する。もちろん -funroll-all-loops 外せば問題なく make & 実行することができる。

SDPA start at Tue Feb 12 04:37:56 2008
data is ./example1.dat-s : sparse
parameter is ./param.sdpa
out is out

block struct :: line 429 in sdpa_main.cpp

Vine 3.x の gcc は 3.3.2, Vine 4.x の gcc は 3.3.6 になる。Vine 4.x 上でも例えば gcc 4.2.2 を用いると上記のエラーは発生しない。