速報！！ 主要点間最短路問題

全米のグラフデータに対して主要点間最短路問題をクラスタ計算機やクラウド・コンピューティングの技術(Amazon EC2)を用いて高速に計算する作業を行っている。
実際には全米データでは点数は 2400 万点であるが、この中から主要点は 3109 点選択している。

○ 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%

この環境下で 16 ノード x 4 コア = 64 コアで実行を行った。実時間で約 52 分30秒である。以前として I/O 関係がボトルネックになっている。

SDPA 7.2.1 とマルチスレッド その４

先日の SDPA 7.2.1 とマルチスレッドの説明が文章だけだと、やはりわかりにくいようなので、説明用の図を追加した。この SDPA は SDP(半正定値計画問題)という最適化問題を解くためのプログラムであるが、このマルチスレッド化された部分も含めて実行を高速しようとすると前処理や計算方法の部分などが、また別の最適化問題になる。この部分(別の最適化問題)を作るにあたっては、汎用的なモデルを重視して、個別のアーキテクチャに対するチューニングとは切り離して考えることにする。

新オンライン・ソルバーのシステム

近い内に Lucie (クラスタの遠隔構築、設定の技術)とクラウドの技術を用いた最短路問題用オンライン・ソルバーが完成する予定になっている。これに加えて現行の SDPA Online Solver についても同様の技術を用いて新システムを開発する予定である。今までは Ninf などを用いていたが、今後は Ninf に依存しないシステムに変更する。よって、しばらくの間は
1: 現行の SDPA Online Solver (安定版) : http://sdpa.indsys.chuo-u.ac.jp/portal/
2: 新 SDPA Online Solver (開発版) : http://laqua.indsys.chuo-u.ac.jp/portal/
の二台体制になる。2 の方は最新のソフトウェア、それに Nehalem などの新サーバなどを予告無しに入れたりするし、Lucie EC2 などの技術も関係してくる。両者は見かけはそっくりだが、裏のシステムはかなり異なったものになるだろう。

三大名機

先日、某 N 社(写真を見ればすぐにわかるが)で講演を行ったときに、N 社の三大名機という話をしたら（少しだけ？）評判が良かった。TK-80 も入れようかと思ったが、三つぐらいが良いと思ってこれだけにした。講演後もいろいろと話をしたが、この中で一番語りやすい（思い入れのある）マシンというと同じマシンを選ぶ人が多い。残りの二つについては”皆が使っていたので使った、別に好きで使っていたわけではない”というのと”噂は聞いているが、自分では使ったことが無いので良くわからない”という評判になる。

Windows 7 Beta 64bit

Windows 7 Beta の 64bit も使用しているが、32bit 版と同様に以下のソフトウェアが動作する。現時点で確認出来ていないだけで実際にはかなり多くのソフトウェアが動作するのではないかと思われる。プリンタドライバも Vista 64bit 版のものが使用できた。適当にインストールしておいた環境であるが、Windows マシンが足りなくなって意外と役に立った。

ブラウザ
1: FireFox 3.0.5
2: Opera 9.63
3: Safari 3.2.1
4: Google Chrome 1.0.154.43
5: Internet Explorer 8.0.7000.0

Office
1: Microsoft Office 2007

プレイヤー
1: RealPlayer 11.0.6

セキュリティ
1: AVG Free 8.0.176
2: Spybot 1.6.0.30

仮想マシン
1: VMware Player 2.5.1

Nehalem-EP

Nehalem-EP Intel Xeon X5570 などのベンチマーク結果が掲載されている。どのような内容のベンチマークテストなのか把握していないが、予想通りに Nehalem-EP の性能は良いようだ。現在 Core i7 の 965 や 940 などを所有しているが、これらは非常に高速なので、Nehalem-EP Xeon の性能も期待できそうだ。業者の方に聞いたところ2月には現物が出てくるということであるが、しばらく様子を見てから購入を行うことにしよう。

ヘッドホン

写真のように 2006年型と2009年型では外見はほとんど同じだが互換性はない。2008 年のメモリカードを 2009年の機器に挿しても使うことができる（その反対も可)。ところが 2006年のメモリカードを 2008, 2009 年の機器に挿しても再生できない（その反対も不可）。試験終了後は機器とヘッドホンは持ち帰っても、置いたままで帰ってもどちらでもよい。実際にどうするのか観察していると、
1; 真面目な人: 両方持ち帰る。家で復習等するのかもしれない。
2; 理系的な人: 両方持ち帰る。メモリカードをパソコンで読み取ろうとするのだろう（実際には不可）。あるいは機器を開けてどこのメーカー製が確かめるのかもしれない。
3; 普通な人: もう二度と見たくないといった感じで置いたまま帰る。何も考えていないのかもしれないが。
4; ちょっと賢い人: ヘッドホンだけ持って帰る

実はこのヘッドホンは結構高級なもので携帯音楽プレーヤーに付けてみたら、現在使っているヘッドホンよりも音質が良かった。

SDPA 7.2.1 とマルチスレッド その３

SDPA 7.2.1 の改造も revision 3 まで来た。いろいろなアイデアがあるので、まだまだこれからといった感じになる。

Nehalem マシン
CPU : Intel Core i7-965 (Nehalem) 3.2GHz
メモリ : DDR3-1600 12GB (2GB x 6) トリプルチャンネル
OS : Fedora 10 for X86_64

○問題 theta6.dat-s
SDPA 7.2.1 (１スレッド : GotoBLAS 1.29)
54.687s (18反復)

SDPA 7.2.1 (４スレッド : GotoBLAS 1.29)
23.186s (18反復)

SDPA 7.2.1.rev2 (４スレッド : Pthread + GotoBLAS 1.29)
16.078s (18反復)

SDPA 7.2.1.rev3 (４スレッド : Pthread + GotoBLAS 1.29)
15.815s (18反復)

SONY VAIO Type P

VAIO には過去何回か痛い目にあっていて、偶然ではなく購入１年後（保証期間後）に壊れるという事態も２回経験している。それでもしばらくするとまた興味が出てくるので不思議だ。新しい VAIO の Type P は非常に小型でズボンのポケットにも入るサイズと宣伝している（入っているようには見えないが）。機能やソフトウェアは良いとして CPU が Intel Atom プロセッサー Z520(1.6GHz) で OS が Windows Vista Basic というのはかなりバランスが悪い。Atom + Vista のミニノートを１台持っているが、動作速度が遅すぎてほとんど使用していない。いっそのこと Vista を 7 Beta あたりに変更したらと思っていたら以下のようにすでに試している方もいた。
1: VAIO type PにWindows 7をインストール、起動
2: Windows 7ベータ版をVAIO type Pで試す
やはりハードウェアのスペック的に厳しいものがあるようで、性能的に現行の Atom では少し無理があるのではないだろうか。

Windows 7 Beta その２

ついでに主要なアプリケーションが正常に動作するのか試してみた。簡単な動作確認なので実際の使用方法によっては不具合が発生する可能性もある。

以下のソフトウェアは正常に動作するようである。
ブラウザ
1: FireFox 3.0.5
2: Opera 9.63
3: Safari 3.2.1
4: Google Chrome 1.0.154.43
5: Internet Explorer 8.0.7000.0

Office
1: Microsoft Office 2007
2: OpenOffice 3.0.0

プレイヤー
1: RealPlayer 11.0.6
2: QuickTime 7.5.5 (少し動作が重い)

セキュリティ
1: AVG Free 8.0.176
2: Spybot 1.6.0.30

2009年8月1日まで使えるようなので、Vista を消して 7 Beta にしてしまうかもしれない。普通は OS の入れ替えにはリスクが伴うのだが、この場合だと現状のままの方がリスクが高そうだ。

Windows 7 Beta その１

Windows 7 の Beta 版の公開が始まっている。試しにダウンロードしてインストールしてみようと思ったが、新しいマシンで空いているのが無かったので、Windows XP の仮想マシン上にインストールした。

CPU: Intel Core2 Quad 9450 (2.66GHz)
メモリ: 4GB
ビデオカード: NVIDIA GeForce 9600GT
OS: Windows XP SP3

インストールは無事に終わって Windows 7 が起動したのだが、WMware tools の関係でネットワークに繋がらない、画面の高解像度にならない(アクセラレーションが効かない）という状態で使い物にならない。そこで以下の古いマシンに直接インストールした。

CPU: Intel Pentium 4 2.6GHz (HT 有効)
メモリ: 1GB
ビデオカード: NVIDIA GeForce 6200

今度はかなり貧弱な仕様ではあるが、それでもそこそこ高速に Windows 7 は動作する。見かけは Vista にそっくりだが、安定しているので別の OS に見える。動作の速度は XP > 7 > Vista のようだ。改めて Vista とは何なのかと思わせる Windows 7 Beta である。

SDPA 7.2.1 とマルチスレッド その２

SDPA 7.2.1 マルチスレッド改造版(rev2)についても少し数値実験を行ったみた。Schur complement 行列が密になるときに、各行の計算をマルチスレッドで行うものなので、行列が疎になったり、この行列の計算部分がボトルネックになっていない場合では効果はあまりない。基本的には F1, F2, F3 の計算式がマルチスレッドで計算されるのだが、F1 式の計算部分だけは他のスレッドが一時停止して、F1 式から呼び出されるBLAS(GotoBLAS) が マルチスレッドで動作するようにしている（この方が一般的には速い）。まだまだ改造は始まったばかりであるが、現時点での性能は一応合格点と言ったところか。

メタ戦略アルゴリズム

この前、メタ戦略アルゴリズム（メタ解法、メタヒューリスティックスとも言われる）は CUDA(つまり GPGPU)で速くすることは出来ませんかと聞かれたのだが、アルゴリズムの都合上、非連続メモリアクセス、代入、大小比較、整数演算などが構成上多くを占めているので、GPGPU での高速化は難しいのではないだろうか。むしろデータやパラメータなどで分割して、グリッドやクラウドで並列分散処理した方が効果が期待できる。グリッド系技術でメタ戦略アルゴリズムの並列化というのも作ったことがあるのだが、実装も実行も結構面倒な上に性能を上げるのは難しい。この種のアルゴリズムは、コンピュータの性能を使い切るように実装するのは大変困難であるが、またそのように実装出来たとしても、それが最終的な解の良さにどれだけ貢献できるかというとこれも怪しいところだ。

理系の人々

理系の人々という本（漫画）を読んでみて、自分にとっても半分ぐらいは当てはまることに気が付いた。食事に行っても、買い物に行っても、乗り物に乗っても情報端末などを見ると、OS が Linux, Windows CE, TRON のいずれかなのか気になってしまう。写真のように Windows だと壊れないように慎重に扱わなければならないような気がしてくる（これは職業病みたいなものである）。変なところが気になって、笑う時に笑えなかったり、楽しむときに楽しめなかったりする（これも職業病か）。

SDPA 7.2.1 とマルチスレッド

SDPA 7.2.1 に Schur complement 行列生成のマルチスレッド化を行ってみた。現時点では、OpenMP や Intel Threading Building Blocks などで並列化するのとあまり違いは無いが、これからの拡張で差が出てくるはずだ(多分)。

Nehalem マシン
CPU : Intel Core i7-965 (Nehalem) 3.2GHz
メモリ : DDR3-1600 12GB (2GB x 6) トリプルチャンネル
OS : Fedora 10 for X86_64


1: 問題 theta6.dat-s
SDPA 7.2.1 (１スレッド : GotoBLAS 1.28)
55.524s (18反復)
SDPA 7.2.1 (４スレッド : GotoBLAS 1.28)
23.966s (18反復)
SDPA 7.2.1 (４スレッド: Pthread + GotoBLAS 1.28)
16.350s (18反復)

CSDP 6.0.1 (１スレッド : OpenMP + GotoBLAS 1.28)
51.933s (17反復)
CSDP 6.0.1 (４スレッド : OpenMP + GotoBLAS 1.28)
19.617s (17反復)


2: 問題 large.dat-s
SDPA 7.2.1 (１スレッド : GotoBLAS 1.28)
1m59.259s (18反復)
SDPA 7.2.1 (４スレッド : GotoBLAS 1.28)
43.794s (18反復)
SDPA 7.2.1 (４スレッド: Pthread + GotoBLAS 1.28)
34.262s (18反復)

CSDP 6.0.1 (１スレッド : OpenMP + GotoBLAS 1.28)
2m16.980s (19反復)
CSDP 6.0.1 (４スレッド : OpenMP + GotoBLAS 1.28)
46.499s (19反復)