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

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

PS3 と SDPA 7.0.5

2008年02月29日 06時53分46秒 | Weblog
ソニーのゲーム事業が 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 を用いた方が良いが、前者はチューニングが終了するまでに何時間もかかるので、後者の方をお勧めする(性能も良い)。
コメント
この記事をはてなブックマークに追加

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

2008年02月28日 15時57分55秒 | Weblog
最短路プロジェクトのホームページを公開することにした。とりあえずミラーサーバの方のアドレスを以下に掲載しておく。

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

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

検索エンジン

2008年02月27日 05時02分37秒 | Weblog
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 はこの中では優秀か。
コメント
この記事をはてなブックマークに追加

スカルトレール

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

MPEG 教科書

2008年02月25日 02時54分54秒 | Weblog
次世代 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 公開中

2008年02月24日 22時27分45秒 | Weblog
ソースファイルとマニュアルの整備を続けていたが、とりあえず完成ということで 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 の認識

2008年02月23日 22時22分09秒 | Weblog
ソフマップでメモリが安かったので、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

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

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

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

コメント (2)
この記事をはてなブックマークに追加

sizeof とバイト数

2008年02月20日 14時50分54秒 | Weblog
たまに忘れてしまうので、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
コメント
この記事をはてなブックマークに追加

最速マシンと最遅マシン

2008年02月19日 02時29分49秒 | Weblog
いつの間にか東芝のパソピア(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

2008年02月18日 00時54分46秒 | Weblog
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 の方は1日ぐらいで対応できたそうだ。

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) の比較実験

2008年02月17日 04時48分34秒 | Weblog
こちらの英語のページに SDPA 6.2.1 と 7.0.5 と 7.1beta 及び SDPARA 7.0beta の実験結果を掲載した。問題によっては SDPA 6.x と SDPA 7.x はあまり結果が変わらないが、非常に疎な問題ではかなり結果が変わってくるので、SDPA 6.x を選ぶメリットはほとんどない。あまり身内のソフトだけで比較実験を行うと、中傷合戦みたいになってしまう。
コメント
この記事をはてなブックマークに追加

SDPA と Vine Linux その2

2008年02月16日 02時50分10秒 | Weblog
調査を続けていると 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

2008年02月15日 04時41分49秒 | Weblog
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 を用いると上記のエラーは発生しない。
コメント
この記事をはてなブックマークに追加