クラウドで学ぶオペレーションズ・リサーチ

Excel で学ぶ ???? というような本はたくさん出版されている。Excel で学ぶ OR といったような本もあるのだが、普通に考えれば Windows や Excel のシェアが高いので Excel 上で学習ツールを作るのが良いのだが、Office 2003 以前と 2007 とでは仕様も変更されていて移植作業が必要になる場合もある。どうせ移植が必要ならば OpenOffice やクラウドの Google ドキュメント用に作り替えるという方法もある。以前ならば Excel 対応で問題は無かったのだが、Office 2007 の評判が良くない、さらに OpenOffice や Google ドキュメントなども伸びてきているという事情もあって、どの辺のプラットフォームを対象にするのか難しい。
Google ドキュメントやオンライン・ソルバーなどを利用して、クラウドで学ぶオペレーションズ・リサーチという方に持って行きたいが、まずはどこまで出来るかの基礎研究から開始している。

Paralle Cholesky Factorization とブロックサイズ

SDPARA 7.3.1 で Paralle Cholesky Factorization に関するブロックサイズを大きめに変えたら、以下のようになった。MUMPS に合わせて少なめにしていたのだが、もっと大きい方が良い。

非負かつ半正定値(DNN : doubly non‐negative)制約
1: nug16ak.dat-s (QAP : 二次割当問題)

SDPARA 7.3.1 (サイズ 48) : 1145.1s (29反復)
Cholesky bMat = 905.9s, 79.1%

SDPARA 7.3.1 (サイズ 160) : 907.7s (30反復)
Cholesky bMat = 709.9s, 78.2%


非負かつ半正定値(DNN : doubly non‐negative)制約
2: new-199901-0.481.dat-s (Portfolio Selection)

SDPARA 7.3.1 (サイズ 48) : 1401.5s (68反復)
Cholesky bMat = 1125.7s, 80.3%

SDPARA 7.3.1 (サイズ 160) : 1135.5s (70反復)
Cholesky bMat = 902.4s, 79.4%

Dell PowerEdege と AMD Istanbul

Dell のサーバ PowerEdge で、やっと AMD Opteron (通称 Istanbul) が購入できるようになった。PowerEdge R805 が 2 ソケット, R905 が 4 ソケットになっている。以前実験してもらった SDPA の結果からは 2 ソケットの方がコストパフォーマンス的にははるかに良いということになっている。

CPU は以下の二つが選択可能。CPU だけ購入してきて現在の Shanghai マシンの CPU と取り替えるというのも可能になっている。

[Six-Core] AMD Opteron 2435 (2.6GHz/6MB L3キャッシュ)
[Six-Core] AMD Opteron 2427 (2.2GHz/6MB L3キャッシュ)

ただし、R805 の方は RAID 1 だと最大 300GB までしか HDD の容量がない(iSCSI や NFS 等すればもっと増やせるが)。メモリ 64GB で HDD が 300GB というのはちょっとバランスを欠いている。

Yellow Dog Linux 6.1 と PS3

久しぶりに PS3 を触って Linux を Fedora 8 から Yellow Dog Linux 6.1 に入れ替えた。相変わらずメモリが少ないせいもあって、かなり速度が遅い。この環境で SDPA 7.3.1 + GotoBLAS 1.29 + MUMPS 4.8.4 で動作確認を行った。

問題 theta6.dat-s

1: PS3 + Yellow Dog Linux 6.1 : 427.6s (2スレッド)

2: Intel Xeon 5550 2.66GHz + Fedora 11 : 12.5s (8スレッド) (GotoBLAS 1.38)
3: Intel Atom 330 1.6GHZ + Fedora 11 : 267.4s (2スレッド) (GotoBLAS 1.38)

SPE を使っていなので Cell と比べてもあまり意味が無いのだが、倍精度演算では SPE を全部使っても最新の Xeon には勝てない。HPC の世界では Cell もあまり流行らないで終わってしまうのだろうか。

ブラウザ別のアクセス数

パソコン用の無償 OS としてグーグル・クロムＯＳ(Google Chrome OS)が話題になっているが、マイクロソフトとグーグルの比較でブラウザの世界シェアが IE 65.9%, Google Chrome 1.7% となっている。しかし普段に身の回りにいる人の間では FireFox が圧倒的なシェアを誇っている。IE は Windows Update の時にしか使わないという人も多いので、このブログに過去１ヶ月間の間のブラウザ別のアクセス数を調べてみた。結果は添付の画像のようにやはり FireFox (3.0, 3.5, 2.0) が一番多数派であった。また各ブラウザも最新バージョンであることが多い。

SDPARA 7.3.1 と水分子 その２

以下の SDPA クラスタでは、32ノード(MPI) x 4 スレッド(pthread) よりも、 16ノード(MPI) x 8 スレッド(pthread) の方が速かった。結果は以下の通りである。14時間を切ったのはなかなか凄い。

問題名 : H2O.1A1.DZ.pqgt1t2p.dat-s

SDPARA 7.3.1 :
32 x 4 : 55510.9s(37反復 : pdOPT) : 約15時間25分
16 x 8 : 49917.4s(37反復 : pdOPT) : 約13時間52分


○ 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

大規模データ + 最先端最適化理論 + 超高速計算シリーズ

前回から名前を少し変更して”超大規模データ + 最先端最適化理論 + 超高速計算”になった。申請書を出す前にまず内部的な審査があるので、そのための研究計画書を一気に作ってしまった。超が二つも付くと馬鹿っぽいという意見もあったが、本当に超大規模なデータを超高速計算するので仕方がない。
扱う問題の特徴は
１：突発的な事態に対処する
２：超大規模なデータが必要
ということに設定した。

SDPARA 7.3.1 と水分子

SDPARA 7.3.1 で一番大きな水分子の問題を解いたので結果をアップする。とりあえずはこれも成功した。一番初めにこの問題を解いたときには約 28 日かかった（ただし計算機もSDPARA のバージョンも異なる)。

問題名 : H2O.1A1.DZ.pqgt1t2p.dat-s

SDPARA 7.2.1 : 98238.6s(37反復 : pdOPT) : 約27時間17分
SDPARA 7.3.1 : 55510.9s(37反復 : pdOPT) : 約15時間25分

以下のように F3 式の計算時間は激減したが、まだ限界ではないだろう。Cholesky 分解の時間が増えているのが少し気になる。

◯SDPARA 7.2.1
Make bF3 time = 95187.824051, 96.904600
Cholesky bMat = 577.523914, 0.587940

◯SDPARA 7.3.1
Make bF3 time = 50551.003448, 91.082482
Cholesky bMat = 746.676910, 1.345358


実験は以下のクラスタで全て 32 ノード(MPI) x 4 スレッド(pthread + GotoBLAS) で動作させた。

○ 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

SDPA 7.3.1 と SDPARA 7.3.1

もうすぐ SDPA 7.3.1 と SDPARA 7.3.1 の正式版をリリースする予定である。コアとなる部分(アルゴリズム)は両者で共通化されている。もう少しデバッグやパフォーマンスチューニングを行う必要がある。

1: SDPA 7.3.1 は 7.3.0 よりも性能的には少し上がっているが、その他にもバグ fix やメモリリークの解消などが行われている。SDPA 7.3.1 は GotoBLAS などと適切に組み合わせることにより、他の SDP ソフトウェアよりもかなり優れた性能を示す

2: SDPARA は 7.3.0(7.3.1β) と 7.3.1 では後者の方が F3 式の計算時間がかなり減少している。階層化とマルチスレッド計算で F3 式がボトルネックなる件はかなり改善されているので、これからは Parallel Cholesky Factorization がボトルネックになる場合が多くなってくるだろう。


問題１: N.4P.DZ.pqgt1t2p.dat-s

SDPARA 7.3.1 : 635.8(39反復)
SDPARA 7.3.0 : 1358.5s(39反復)
SDPARA 7.2.1 : 2113.1s(39反復)
PCSDP 1.0 : 1958.8s(36反復)

F3式の計算時間は
SDPARA 7.3.0 : 1057.64秒 (77.95%)
SDPARA 7.3.1 : 350.99秒 (55.37%)
と激減した。

問題２: HLi2.2A1.STO6G.pqgt1t2p.dat-s

SDPARA 7.3.1 : 1759.4s(41反復)
SDPARA 7.3.0 : 4955.4s(41反復)

これもF3式の計算時間は
SDPARA 7.3.0 : 4291.60秒 (86.66%)
SDPARA 7.3.1 : 1097.12秒 (62.47%)
と激減した。

実験は以下のクラスタで全て 32 ノード(MPI) x 4 スレッド(pthread + GotoBLAS) で動作させた。

○ 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

It's Lucie!

研究室の前を通る方から Lucie さんって誰ですかという質問をたまに受けるが、この Lucie は人間ではなくソフトウェアである。

Lucie ホームページ
http://lucie.is.titech.ac.jp/trac/lucie/

ホームページの内容も今後はさらに充実していくそうだ。インストールの様子、状態を示す画面が以前の物から新しい物に更新された。設定とインストールが本当に簡単かどうかはもちろんユーザーのレベルに依存する。仮想マシンというのは着せ替え人形のように OS や環境等を入れ替えることが出来るのが大きな魅力の一つだが、この Lucie によって実マシンを仮想マシンのように使うことも出来るだろう。

PRIME NEWS とクラウドコンピューティング

最近はほとんどテレビ見ないのだが、夕食食べながら見ることが多いのが BSフジLIVE　PRIME NEWS になる。７月６日の放送は、

世界を変える IT 革新 "クラウド"の正体！ 日本経済浮上の新戦略

となっている。題名にはちょっと笑ってしまったが、多分番組は見ると思う。BS はあまり視聴率を気にしなくても良いようなので、このような番組を７時から９時まで放送することが出来るのが大きな特徴。

1997 年と 2009 年の SDPA

1997 年当時の SDPA (3.x)の実験結果が出てきたので、2009 年の SDPA (7.x) と比較してみた。

1997年 SDPA 3.01 : CPU DEC Alpha 21164A 437MHz ; メモリ 8GB
2009年 SDPA 7.3.1 : CPU Intel Xeon 5550 2.67GHz ; メモリ 72GB

1: control11.dat-s
1997 年 ; 6903.0s
2009 年 ; 37.3s

2: m1250.05.dat-s
1997 年 ; 111615.9s
2009 年 ; 13.8s

3: g1250.05.dat-s
1997 年 ; 112375.7s
2009 年 ; 23.1s

4: b300-90.b.dat-s
1997 年 ; 19028.7s
2009 年 ; 13.4s

大規模データ + 最適化理論 + 大規模高速計算シリーズ

特に首都圏だと平日は毎日遅延が出ている路線もあるようなので、大規模な災害等が発生しなくても毎日運行ダイヤが乱れが発生しその都度状況の回復が行われているが、現時点では自動化は難しいようだ。大規模データ + 最適化理論 + 大規模高速計算は大規模災害、鉄道＆道路ネットワークなどと絡んでくるのだが、とにかく扱うべきデータの数が多い。しかしそれらのデータを集めることは可能なようだ。現時点ではこれらを扱う方法（アルゴリズム）は決まっていなので、どの程度の計算機資源が必要かも不明である。しかし、これまで無かったような大規模な計算になることになるだろう。

CPU + GPGPU と SDPARAの計算

スパコンにアクセラレータとして GPGPU を搭載するというのまだ少数派であって、知っている範囲では日本では東工大だけが積極的に推進している。一応推進派と慎重派の両者の意見を聞いたことがあるが、CPU + GPGPU の混在マシンでソフトウェアの性能をあげるためには新しいモデルが必要になるだろう。NVIDIA の Tesla だけではなく近い将来 CPU も複合コアになる可能性があるので研究しておいて損はない。
SDPARA は ノード(MPI) と CPUコア(pthread) の２階層で性能が出るようになってきたので、これに GPGPU を加えるモデルを考え始めた。どこで（CPU か GPGPU か)、どのタイミングで（同期や並列）、何を（どのデータ：密や疎など）を行うかが鍵になるが、アイデアを出したら実機で GPU 系にも詳しい方の協力を得て実際に動かしてみるのが良い。
GPGPU というのは単精度演算性能が突出していて倍精度演算がその数分の一ぐらいになっているのだが、無理にこれらを使いこなそうとすると PCI Express や GPGPU 内のメモリのバンド幅等に引っ張られて失敗しそうなので、反対にバンド幅に見合った計算をさせる予定である。

SDPARA 7.3.0 v.s. 7.2.1 v.s. PCSDP 1.0

SDPARA 7.3.0, 7.2.1 と PCSDP 1.0の比較実験結果を掲載する。三つのソフトウェアは全て BLAS, LAPACK として GotoBLAS 1.34 を利用している。全て 32 プロセス x 4 コア(OMP_NUM_THREADS=4)で実行を行った。

1: N.4P.DZ.pqgt1t2p.dat-s (量子化学)

SDPARA 7.3.0 : 1358.5s(39反復)
SDPARA 7.2.1 : 2113.1s(39反復)
PCSDP 1.0 : 1958.8s(36反復)

非負かつ半正定値(DNN : doubly non‐negative)制約
2: nug16ak.dat-s (QAP : 二次割当問題)

SDPARA 7.3.0 : 1031.3s(31反復)
SDPARA 7.2.1 : 1226.4s(31反復)
PCSDP 1.0 : 2855.2s(64反復)

非負かつ半正定値(DNN : doubly non‐negative)制約
3: new-199901-0.481.dat-s (Portfolio Selection)

SDPARA 7.3.0 : 1133.8s(62反復)
SDPARA 7.2.1 : 1325.3s(63反復)
PCSDP 1.0 : 1532.7s(61反復)

上記の結果から見ると SDPARA 7.3.0 の開発は一応成功ということになろう。次期 SDPARA は大きく変わる(変える)予定になっている。

○ 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