制御分野での SDP

最近いろいろな話を聞いて、何故制御系の方が MATLAB の LMI Control Toolbox を使い続けているのか少しずつわかってきた。もちろんインターフェイスの問題もあるのだが、出てくる解の質の問題が大きいと思われる。ここで詳しくは書かないが、既存のソルバーを制御系の方が望むような解を出すように改造することは可能だと推測する。
ところで、SDP だけではないが、最適化問題用のソルバーの最終結果は自己申告に過ぎないので、本当に最適解あるいは実行可能解が求められているかは検証の必要ありである。

某スパコンと SDPARA その１２

今回の某スパコンでの実行は成功と言えるのだが、Intel コンパイラ + OpenMPI のおかげでもあり、これらが無ければ成功しなかっただろう。成功したので次の展開に繋げていくこともできるだろう。実験結果については論文等に記載される予定であるが、一番早く公開されるのは某学会誌の７月号の解説記事になる。この解説記事では最適化ソフトウェアと最新の情報技術（マルチコア・プロセッサ、GPU コンピューティング, スーパーコンピュータ、クラウド・コンピューティングなど）の関係や相性についても触れる予定になっている。

OR 研究ユニット

人員も豊富に集まって予算も確保が出来たので、オペレーションズ・リサーチ(OR)の研究ユニット(センターほどは大きく無い）を学内に作ることにしました。近い内にホームページなどを作成して公開することにします。

○１ユニット、２チーム制
Ａ：超大規模データ&モデル化チーム（仮称）
Ｂ：超高速計算チーム（仮称）
○大学院生や学外の研究協力者も含める
○”超”と名前が付く以上、これままでの研究とは比較にならないほど大きなデータとモデルを扱い、高速に処理を行う
○計算機パワーとマンパワーの両方を重視する
○組み込み系からスーパーコンピュータまで計算機は何でも使う

いくら高速に計算する能力があっても、データやモデル化それにアルゴリズムが悪ければ意味がありませんので、その辺のバランスを重要視します。以前からこういったプロジェクトを行ってみたかったのですが、やっと開始まで辿り着きました。

MIPLIB 2010 募集中

MIP に関する有名なベンチマークライブラリに MIPLIB があるが、現在 MIPLIB 2010 を作成するために新たな MIP インスタンスの募集を行っている。

http://miplib.zib.de/miplib2010/

もちろん、上記のページから投稿したとしても ZIB 側の審査を経なければ MIPLIB 2010 に採用されることはない。どのような問題が望まれているかと言えば（多少想像も入るが）
１：実用的かつ新分野における問題
２：簡単には解けそうにないが、現在のアルゴリズム、計算機等のレベルでも頑張れば何とか解けそうな問題
３：数値的な条件の悪い問題（実行可能解が非常に少ないとか大小の数値が入り混ざったスケールがばらばらな問題）。あるいは本当に実行可能解が無い問題
といった感じだろうか。

適当に作成した問題が上記の条件を偶然満たすということは考えにくいので、既存のソルバーで解きながら適当な問題を作成していくことになるだろう。
MIP でなく SDP では私供のグループが作成した問題もかなり多くベンチマーク問題に採用された。SDP では上記の２の条件に合う問題は作りやすいのだが、MIP は問題が大きくてもあっさり解けてしまったり、小さくても解けないことも多いので、作成は結構大変だろうが、誰か挑戦して頂きたい。

某スパコンと SDPARA その１１

スパコンでの一連の実験に関して、メーカーに報告書を提出した。まだ一般に公開出来ない内容も多いので、こちらから公開することは現時点では行わない。今回は試用期間が短かったので、台数効果やコンパイラ等による性能差などを測定することは行わないでひたすら大きな問題を解くことに集中した。

コンパイラについては、メーカー製、Intel, PGI, GNU gcc が使用できたが、OpenMP 等の性能も考えて結局 Intel コンパイラに統一した。MPI もメーカー製、OpenMPI, MVAPICH2 が使用できたが、こちらは OpenMPI に統一した。他の組合せを調べている時間が無かったので、この組合せ(Intel コンパイラ + OpenMPI) がベストかについては何とも言えない。

○ 某スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

とにかく前処理

SDPA で問題を解く前処理として代数的な方法から、キャッシュの有効利用に関する物まで幾つか考えてきたが、だいたい考えがまとまったので、少しずつ実行に移していくことにした。当然ながら前処理には

１：コスト
２：副作用

が付いてくる。どの方法も１のコストが大きそうなので、前処理を適用するには問題のサイズがある程度大きいことが条件となる。２に関しては前処理適用後の計算量との推定を行うことで切り抜けようと考えている。MIP でも同じだが、何も前処理をしないで問題をそのまま解くというのは時代に即していないだろう。

某スパコンと SDPARA その１０

いつまで某スパコンと言っているのかという感じだが、もうしばらくの辛抱である。速度の差をまとめてみた。コア数で見ると SDPA クラスタもかなり善戦しているのだが、数は力なりということで、やはりスパコンでの実行は凄いものがある。

　　　 某スパコン　　　　　SDPA クラスタ
問題１ 27,523.8s(128 x 16) 　49,037.9s(16 x 8)
問題２ 68,593.4s(128 x 16)　 146,763.2s(32 x 4)
問題３ 72,025.6s(128 x 16)　 154,043.3s(32 x 4)
問題４ 5,943.1s(128 x 16)　　21,910.5s(64 x 2)

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.4 for x86_64

○ 某スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

適合度検定

８種類全部出てくるまで買ってみましたが、全部欲しいのであればこちらを購入した方が良いのでマネはしないで下さい。ここまで偏っていると、８種類が同数だけ入っているのか？ あるいはちゃんとかき混ぜているのか？という疑問が沸いてきます。
統計学ではこんな時に適合度検定ということをしたりしますが、

H_0 帰無仮説 : 各サウンドドロップが出てくる確率は全て同じ(= 1/8)
H_1 対立仮説 : 各サウンドドロップが出てくる確率は等しくない
有意水準 0.05
平均値 = (2 + 3 + 3 + 6 + 4 + 2 + 1 + 6) / 8 = 3.375
統計量 = {(2 - 3.375)^2 + (3 - 3.375)^2 + (3 - 3.375)^2 + (6 - 3.375)^2 + (4 - 3.375)^2 + (2 - 3.375)^2 + (1 - 3.375)^2 + (6 - 3.375)^2} / 3.375 = 23.875 / 3.375 = 7.074
カイ二乗分布の自由度 8-1 = 7 の 0.05 点は 14.07 であるので、7.074 <14.07 より H_0 は採択される。 というわけで、各サウンドドロップが出てくる確率は等しくないとは言えないという不思議な結果になりました。

新研究用ブログ

新しくこんなブログが出来ました。

http://blog.goo.ne.jp/nakatamaho/

こちらもよろしくお願いします。私もブログの方は中身を抑えて書いてまして、本当はもっと書きたいこと、重要なこと、特ダネ的なことがあるのですが、ブログでは書けません。反対にその方が安全なのかもしれませんが。

某スパコンと SDPARA その９

３月３０日のブログで以下の問題は SDPA クラスタでは解けないと言ったが、64 プロセス x 2 スレッド にすれば 116910 x 116910 の巨大 Schur complement 行列も小さく分割できるので、SDPA クラスタでも以下のように解くことができる。しかし、SDPARA はプロセス数 = CPU 数に固定して、あとは CPU 内でスレッド並列にすると最高速になるように設計されているので(Opteron では最高速にならない場合も多いが)、64 x 2 ではあまり性能は良くない。F3 式の計算で差が付いているのは、2 スレッドでは F3 式のマルチスレッド化が有効に動作しないからで、反対に言えばスレッド数が多い場合には有効に動作していると言える。

○問題名 : O2+.2Pig.DZ.pqg.dat-s
○ソフトウェア : SDPARA 7.3.2
○実験結果

SDPA クラスタ
64プロセス x 2スレッド : 21910.6s(27反復 : pFEAS)
F3 式計算時間 = 3026.7s, 13.8%
Cholesky 分解計算時間 = 17537.3s, 80.0%

某スパコン
128プロセス x 16スレッド : 5943.1s(28反復 : pFEAS)
F3 式計算時間 = 542.8s, 9.1%
Cholesky 分解計算時間 = 4796.9s, 80.7%

記号定義
mDIM : SDP の主問題における制約式の数
mDIM : 116910


○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.4 for x86_64

○ 某スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

Intel Nehalem-EX クラスタ

一般的には Intel Xeon と AMD Opteron では後者の方が安いので、同じ予算であれば後者を用いた方が大規模（コア数を多く）することができる。それでも研究では Linpack などのベンチマーク競争をしたいわけではなく、SDPARA などの実アプリが高速に動作しないと意味が無いので、全体のコア数を減らしてでも Xeon(特に Nehalem-EX) を２２年度新クラスタ計算機で採用しようと考えている。ただし、Xeon の Westmere-EP も検討中なので、こちらを採用する可能性もある。次期 SDPA(SDPARA)で採用予定のアルゴリズムは、Nehalem-EX の高いメモリバンド幅と大容量 L3 キャッシュ上で動かしてみるのが面白そうだ。

メガクエイク

今年の１月から３月まで NHK スペシャル”メガクエイク”4回シリーズが放送されて大きな反響を呼んだ。また最近単行本化されて主婦と生活社から出版されている。普段から専門家の方からいろいろな情報を頂いているので、番組内では触れていない（触れられない）ような話もたくさんあるのだが、刺激が強いので敢えて触れないのか、学術的な検証中で表に出せないのか、いろいろと理由はあるだろう。最近では NHK の番組はあまり信用していないのだが、ハイチ、チリの地震や津波を重なったこともあってタイムリーで優れた特集だったと思われる。
阪神大震災では震度７の激震地域において、ほとんど被害ゼロの建物がたくさんあったとか、死者：6,434名 行方不明者：3名 負傷者：43,792名中でマンション内での死傷者は 20 名程度とか、一般には知られていない事実に触れても良かったのではないだろうか。完璧ではないが、メガクエイク時の被害を減らすノウハウはすでに多く存在している。子供手当てなどのばらまきは即中止して、地震、津波対策の予算に転換してもらいたい。

某スパコンと SDPARA その８

関係者のご厚意によりスパコン上で二週間 SDPARA を実行したので、解析が大変なほどの大量のデータを取ることができた。

○スパコン向きの問題
1: 制約式の数(mDIM) が非常に多い = Schur complement 行列が非常に大きい
2: Schur complement 行列が密
3: 制約行列はブロック対角構造も含めて非常に疎である。

上記の 1,2,3 が成立する場合では、Schur complement 行列の生成がボトルネックとなるので、コア数に比例して性能が上がる
反対に 制約式の数(mDIM) = 変数行列のサイズ (bLOCKsTRUCT) だと、以下のクラスタ(128コア)でもスパコン(2048コア)でもほとんど性能は同じになる。
これらを考慮しても SDPARA は Intel Xeon 向きという感じはさらに強くなった。

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.4 for x86_64

○ 某スパコン
128 Nodes, 512 CPUs, 2048 CPU cores; (今回使用した分のみ)
CPU : AMD Opteron 8356 2.3GHz (quad cores) x 4 / node
Memory 32GB / node
NIC : GbE x 2 and Infiniband x 4 / node
OS : RHEL 4.x for x86_64

PowerEdge Cシリーズサーバ＆PowerEdge M910 その２

PowerEdge C シリーズ は"ばら売り"というか少ロットでの販売はされない可能性もあるそうだ。いずれにしても Nehalem-EX は搭載できないようだ。Nehalem-EX が欲しいのであれば PowerEdge M910 を選ぶことになるのだが、Nehalem-EX のクロック周波数はかなり低め(2GHz 以下)であるので、6 コアでもクロック周波数の高い Westmere-EP の方が性能が上になることもあるだろう。

1: 4-way は Nehalem-EX 搭載の PowerEdge M910 のみ
2: 8 コア搭載の Nehalem-EX のクロック周波数は低め
3: PowerEdge M1000e は 200V の電源が必要

AMD Opteron の方が安いが、SDPARA の性能を考えると Intel Xeon 系の方が高くても好ましい。

道路ネットワークデータ

全米道路データはフリーで配布されているが、日本の道路データはフリーで適当な物が見当たらないので、商用の道路ネットワークデータを購入も考えている。

MAPPLE 道路ネットワークデータ
MAPPLE ルーティング・歩行者ネットワークデータ

あとは今年度の新規研究プロジェクト用に以下のマップデータも必要になる。

MAPPLE 帰宅支援マップデータ