超大規模グラフ解析プロジェクト

以前、作成した OR (オペレーションズ・リサーチ)研究ユニットが組織改変？で大型化して”超大規模グラフ解析プロジェクト”として再出発することになりました。計算量や要求されるメモリバンド幅を抑えた後に、超大規模スレッド並列処理で超大規模な最適化問題等を扱っていくという方針が最新の HPC 技術と結び付く形で大幅に強化されます。

ーー超大規模グラフ解析プロジェクトーー
○超大規模データを伴う最適化問題に対する高速計算システムの構築と評価
ー グラフ探索(最短路、幅優先探索、重要性計算)、数理計画問題(半正定値計画問題:SDP, 混合整数計画問題 MIP or MINLP 等)

○リアルタイム大規模グラフストリーム処理系及びグラフ最適化ライブラリの開発

○大規模グラフ処理向けオンデマンド階層型データストアの開発

○大規模グラフストリームデータの対話的な閲覧システム
ーーーーーーーーーーーーーーーーーーー

参考：百万スレッドによる、全米データに対する全対全最短路計算と重要性の算出


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

e-サイエンスに向けた革新的アルゴリズム基盤

e-サイエンスに向けた革新的アルゴリズム基盤という題名と中身で以下のようにシンポジウムを開催する予定です。詳細については現在検討を行っています。オープンなシンポジウムですので、参加は無料で事前登録の必要もありません。

------------------------------------------------------
１．　シンポジウム
　テーマ：　e-サイエンスに向けた革新的アルゴリズム基盤
２．使用期間
　平成23年9月4日（日）13時30分から17時00分まで
３．使用場所
　公立はこだて未来大学 研究棟　R791(～120名収容）（PPTなど視聴覚設備完備）
-------------------------------------------------------

かなりハードな MIP その６

今回は FiberSCIP での結果。何故か AMD Opteron 系(Magny-Cours, Istanbul)では、途中で OS ごと暴走してしまうので、Intel Xeon 搭載のマシンで実験を行っている。

Time & Nodes & Nodes Left & Active Solvers & Best Integer & Best Node & Gap
446532 5008439181 29867530 8 237.0000 231.0000 2.60%
446537 5008487700 29865886 8 237.0000 231.0000 2.60%
446542 5008535036 29864202 8 237.0000 231.0000 2.60%
446547 5008581866 29862452 8 237.0000 231.0000 2.60%
446552 5008633371 29860795 8 237.0000 231.0000 2.60%
446557 5008681940 29859061 8 237.0000 231.0000 2.60%
446562 5008730913 29857541 8 237.0000 231.0000 2.60%
446568 5008780504 29855904 8 237.0000 231.0000 2.60%
446573 5008829304 29854215 8 237.0000 231.0000 2.60%
446578 5008877943 29852546 8 237.0000 231.0000 2.60%
446583 5008926936 29850892 8 237.0000 231.0000 2.60%
446588 5008976737 29849226 8 237.0000 231.0000 2.60%

左から三番目の Nodes Left の値が減少傾向に転じているので、良い意味で最後が近づいているのかもしれない。

○計算サーバ (2 CPU x 4 コア = 8 コア)
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 15 for x86_64

かなりハードな MIP その５

GLPK 4.45 を用いて、この問題を解き続けているが １４日経って上界と下界は以下の通りである（現在も実行中）。1コア(1スレッド)での実行という理由もあるだろうが、これが GLPK と他の商用ソルバーとの差ということになるだろう。いまだにどのソルバーでも最適解は見つかっていない。

GLPK 4.45 : 上界 308, 下界 119
これまでの実行時間：約１４日

○計算サーバ２ (2CPU x 4 コア = 8 コア)
CPU : AMD Opteron 2356 2.3GHz x 2
Memory : 32GB
OS : Vine Linux 5.2 for X86_64

超大規模データに対するグラフ探索アルゴリズム

超大規模データに対するグラフ探索アルゴリズムに関する話題。基本的には以下に書いてある通りなのだが、点数を n とすると O(n log n) では log n の n は実際には点数よりもかなり小さい場合が多い(さらにある値以下で抑えられる場合も多い)。この場合では計算量が O(n log n) であっても、実際の計算時間は O(n) に近い緩やかな増加曲線となることがある。

課題

某所で出題した課題ですが、今週の金曜日が締切となっています。ちょっと難しいかもしれませんが、よく考えると様々な理由が列挙できるはずです。理論計算量や O : ビッグオーの定義に戻って考えてみることもお勧めします。また計算機上での実際の実行時間はどのような要素で構成されているのかも考えてみる必要もあります。

Let's note CF-C1

Let's note CF-C1 を購入して様々なテストを行っている。CPU の仕様は以下の通りである。

インテル® Core™ i5-2520M vPro™ プロセッサー
(インテル®スマートキャッシュ 3 MB※2、動作周波数 2.50 GHz、インテル® ターボ・ブースト・テクノロジー2.0利用時は最大3.20 GHz)

このモデルの一番の特徴は画面を回転させて指操作やペン入力が出来るのでプレゼンなどでの使用が便利なことにある。
http://panasonic.jp/pc/products/c1b/convertible.html

ペン入力では特に画面の左上の部分が少しずれてしまうのだが補正作業を行ってもなかなか直らない。むしろ指操作による手入力の方が正確に操作することができる。以下のように最短路 Online Solver も iPad などよりはかなり快適に動作＆操作することができる。

SWoPP 鹿児島

2011年並列／分散／協調処理に関する『鹿児島』サマー・ワークショップ（SWoPP鹿児島2011）が 7 月 27 日から開催されます。またすでに参加申し込みは終了しておりますが、同じ鹿児島市内で 26 日に第5回戦略的高性能計算システム開発に関するワークショップも開催されることになっています。

2011年並列／分散／協調処理に関する
『鹿児島』サマー・ワークショップ（SWoPP鹿児島2011）
日程 2011年7月27日(水)～7月29日(金)
会場 かごしま県民交流センター
〒892-0816　鹿児島市山下町14-50

イノベーション・ジャパン2011‐大学見本市

先日提出した展示提案が採択されたので、イノベーション・ジャパン2011‐大学見本市で以下の展示を行うことになりました。

イノベーション・ジャパン2011‐大学見本市
会　期

2011年9月21日（水）～22日（木）
［9月21日(水）9:30～17:30］
［9月22日(木）10:00～17:00］

会　場 東京国際フォーラム（東京・有楽町）
入場料 無料

最短路検索を用いた大規模ネットワーク解析システム
大規模災害等は突発的に発生するため事前予測による防災計画だけでなく、動的なデータ収集等とスパコン上での高速計算によって速やかに避難、誘導計画を策定する必要がある。現在、首都圏道路網や鉄道網を精密なグラフデータに変換して、超大規模なグラフ処理を用いた避難、誘導計画の策定を行っている。.本システムでは、大規模グラフデータに対するリアルタイムストリーミング処理、計算量とデータ移動量を考慮したグラフ最適化アルゴリズム、ストレージの階層性を考慮した大規模グラフデータストア、超大規模グラフのリアルタイム可視化など従来実現されていなかった新しい技術によって超大規模グラフに対する高速解析システムを構築する

Excelで学ぶOR 発売

Excel で学ぶ OR の本が発売となりました。Amazon 等で購入が可能です。

出版社(オーム社)によるサポートページは以下の通りですが、その他に非公式？サポートページを作りまして、正誤表やページ数で都合で本に掲載出来なかったデータマイニングの章などの原稿が入手できるようにする予定です。

Excelで学ぶOR サポートページ

かなりハードな MIP その４

これらのハードな MIP は全部で 45 問あるが、CPLEX や Gurobi 等を用いて数十コアで数十時間の実行を行っても、現在の所最適解が得られているのはほんの数問程度となっている。
元問題を本当に解きたいのであれば、定式化を変えたり近似解法を適用するなどの方法が考えられるが、ここは反対に考えて、これらの問題を MIP ソルバーで敢えてそのまま解くことによって、難しい MIP の重要な例として求解困難となっている理由等を考察していくという方法もあると思われる。いずれにしても可能であればこれらの問題を公開していく予定となっている。

ヘテロクラスタでの SDPARA その２

前回の続きでサーバ１から４の４台のヘテロなクラスタ計算機を作ったので、以下のように SDPARA と SDPA で比較を行った。結果は以下のように予想通り。問題２や３のようなタイプの問題では、周辺で余っている普通の PC を GbE で接続してヘテロなクラスタ計算機を作って実行しても効果が期待できる。

１：問題１のように小さな問題ではヘテロなクラスタ計算機で実行するメリットは無し
２：問題２や問題３のように SCM(Schur Complement Matrix)に作成に時間がかかる場合には実行するメリットが出てくる
３：問題４のように SCM の Cholesky 分解に時間がかかる場合でもメリットは無い

○ヘテロなクラスタ計算機：サーバ１～４：SDPARA
○サーバ０: SDPA

○ 問題１：theta6.dat-s
○ SDPARA 47.96s
○ SDPA : 14.72s

○ 問題２： FH2+.1A1.STO6G.pqgt1t2p.dat-s
○ SDPARA : 88.94s
○ SDPA : 159.01s

○ 問題３：Be.1S.SV.pqgt1t2p.dat-s
○ SDPARA : 1840.38s
○ SDPA : 3877.12s

○ 問題４： nug12_r2.dat-s
○ SDPARA : 418.39s
○ SDPA : 210.28s


○サーバ０
CPU : Intel Corei7 965 3.20GHz
Memory : 12GB
OS : CentOS 5.6 for x86_64

○サーバ１
CPU : Intel Core 2 Quad 9650 3.0GHz
Memory : 8GB
OS : Fedora 15 for x86_64

○サーバ２
CPU : AMD Phenom(tm) II X4 955 3.2GHz
Memory : 8GB
OS : Fedora 15 for x86_64

○サーバ３
CPU : Intel Xeon E5530 2.4GHz
Memory : 6GB
OS : Fedora 15 for x86_64

○サーバ４
CPU : Intel Corei7 2600K 3.40GHz
Memory : 8GB
OS : Fedora 15 for x86_64

Excelで学ぶOR

Excel で学ぶ OR の本の表紙のデザイン等は出版社にお任せなので、こちらのページで初めて表紙のデザインを知った。歴代 Excel で学ぶシリーズとは少し変わった印象を受ける。値段を見ていて編集時に全体のページ数を 336 ページで制限された理由もわかった気がする。ちなみに本の発売前にすでに本文中で用いる Excel ファイルが入手できるようになっている。

Excelで学ぶOR サポートページ

ヘテロクラスタでの SDPARA

以下の４台の計算機を組み合わせてヘテロなクラスタ計算機を作成して SDPARA の実行を行った。これらの４台は GbE で接続されている。相互にパスワード(パスフレーズ）の入力無しに rsh(ssh) でログインできるようになっているが、NFS などでファイルの共有は行われていない。

○実験１
GotoBLAS でも Intel MKL でも良いのだが、CPU ごとに個別に最適化されたバイナリを用いる場合では、以下のように途中で Scalapack による Cholesky 分解実行時にエラーが発生して停止する。

[fujisawa@opt-quad sdpara.7.3.1.src]$ time mpiexec -n 4 -machinefile ./machinefile ./sdpara ~/src/sdplib/mcp500-1.dat-s out
SDPA start at [Mon Jul 18 00:13:06 2011]
param is ./param.sdpa
data is /home/fujisawa/src/sdplib/mcp500-1.dat-s : sparse
out is out
NumNodes is set as 4
NumThreads is set as 4
Schur computation : DENSE
mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 +0.00e+00 +3.12e+04 1.0e+00 9.1e-01 2.00e-01
1 1.4e+03 0.0e+00 9.2e-02 +6.92e+04 +3.16e+03 9.9e-01 9.9e-01 2.00e-01
2 1.7e+02 0.0e+00 5.1e-04 +8.24e+04 +3.30e+02 1.1e+00 1.0e+00 2.00e-01
3 1.7e+01 0.0e+00 3.4e-17 +8.94e+03 +3.14e+02 9.5e-01 8.5e+00 1.00e-01
4 2.4e+00 0.0e+00 8.0e-16 +1.58e+03 +3.89e+02 7.9e-01 1.9e+00 1.00e-01
5 6.1e-01 2.2e-18 1.3e-15 +7.71e+02 +4.67e+02 6.1e-01 8.1e-01 1.00e-01
6 2.4e-01 4.3e-18 1.7e-15 +6.46e+02 +5.24e+02 7.3e-01 4.4e-01 1.00e-01
7 1.2e-01 6.5e-18 4.0e-06 +6.09e+02 +5.50e+02 9.7e-01 6.4e-01 2.00e-01
8 5.2e-02 6.5e-18 2.5e-06 +6.02e+02 +5.76e+02 9.2e-01 8.6e-01 2.00e-01
9 1.6e-02 6.5e-18 2.7e-05 +5.99e+02 +5.92e+02 9.2e-01 9.5e-01 2.00e-01
Cholesky miss :: info = 325 :: line 2737 in sdpa_newton.cpp :: iam 0
10 3.9e-03 8.7e-18 2.7e-05 +5.98e+02 +5.97e+02 9.2e-01 9.5e-01 2.00e-01

phase.value = pFEAS
Iteration = 10
mu = +3.9160717209464190e-03
relative gap = +3.1633306982576589e-03
gap = +1.8899914694569588e+00
digits = +2.4998554040624335e+00
objValPrimal = +5.9841381886408180e+02
objValDual = +5.9652382739462485e+02
p.feas.error = +8.8817841970012523e-16
d.feas.error = +2.6439893285568061e-03
total time = 3.484980
main loop time = 3.481712
total time = 3.484980
file check time = 0.000000
file change time = 0.000058
file read time = 0.003210
SDPA end at [Mon Jul 18 00:13:10 2011]
ALL TIME = 3.838375

○実験２
最適化されていない リファレンス BLAS を用いる。正常に実行できるのだが、当然ながら実行速度は遅い。

SDPA start at [Mon Jul 18 01:40:46 2011]
param is ./param.sdpa
data is /home/fujisawa/src/sdplib/mcp500-1.dat-s : sparse
out is out
NumNodes is set as 4
NumThreads is set as 4
Schur computation : DENSE
mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 +0.00e+00 +3.12e+04 1.0e+00 9.1e-01 2.00e-01
1 1.4e+03 0.0e+00 9.2e-02 +6.92e+04 +3.16e+03 9.9e-01 9.9e-01 2.00e-01
2 1.7e+02 0.0e+00 5.1e-04 +8.24e+04 +3.30e+02 1.1e+00 1.0e+00 2.00e-01
3 1.7e+01 0.0e+00 2.0e-17 +8.94e+03 +3.14e+02 9.5e-01 8.5e+00 1.00e-01
4 2.4e+00 0.0e+00 2.4e-16 +1.58e+03 +3.89e+02 7.9e-01 1.9e+00 1.00e-01
5 6.1e-01 2.2e-18 2.2e-16 +7.71e+02 +4.67e+02 6.1e-01 8.0e-01 1.00e-01
6 2.4e-01 4.3e-18 4.5e-17 +6.46e+02 +5.24e+02 7.3e-01 4.4e-01 1.00e-01
7 1.2e-01 6.5e-18 2.6e-17 +6.09e+02 +5.50e+02 1.0e+00 5.5e-01 1.00e-01
8 5.4e-02 8.7e-18 1.3e-17 +6.02e+02 +5.75e+02 9.4e-01 7.5e-01 1.00e-01
9 1.6e-02 1.1e-17 1.0e-17 +5.99e+02 +5.91e+02 9.2e-01 9.0e-01 1.00e-01
10 3.0e-03 8.7e-18 1.8e-17 +5.98e+02 +5.97e+02 9.1e-01 9.2e-01 1.00e-01
11 5.2e-04 1.1e-17 1.8e-17 +5.98e+02 +5.98e+02 9.1e-01 9.3e-01 1.00e-01
12 8.5e-05 1.1e-17 3.1e-17 +5.98e+02 +5.98e+02 9.2e-01 9.5e-01 1.00e-01
13 1.3e-05 1.3e-17 8.5e-17 +5.98e+02 +5.98e+02 9.4e-01 9.7e-01 1.00e-01
14 1.6e-06 1.5e-17 1.1e-16 +5.98e+02 +5.98e+02 9.4e-01 1.0e+00 1.00e-01
15 1.8e-07 1.7e-17 1.2e-16 +5.98e+02 +5.98e+02 9.4e-01 1.0e+00 1.00e-01
16 1.9e-08 1.7e-17 8.3e-17 +5.98e+02 +5.98e+02 9.4e-01 1.0e+00 1.00e-01

phase.value = pdOPT
Iteration = 16
mu = +1.8891576507858064e-08
relative gap = +1.5791710607891638e-08
gap = +9.4457882369169965e-06
digits = +7.8015708232957248e+00
objValPrimal = +5.9814851893114110e+02
objValDual = +5.9814850948535286e+02
p.feas.error = +1.7763568394002505e-15
d.feas.error = +8.2156503822261584e-15
total time = 6.043066
main loop time = 6.039540
total time = 6.043066
file check time = 0.000000
file change time = 0.000071
file read time = 0.003455
SDPA end at [Mon Jul 18 01:40:52 2011]
ALL TIME = 6.318004

○実験３
最適化された BLAS を用いるが、全て同じ CPU として(例えば Core2 など)実行を行う。速度的な考察はともかく実験２よりは高速に終了する。

SDPA start at [Mon Jul 18 01:44:02 2011]
param is ./param.sdpa
data is /home/fujisawa/src/sdplib/mcp500-1.dat-s : sparse
out is out
NumNodes is set as 4
NumThreads is set as 4
Schur computation : DENSE
mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 +0.00e+00 +3.12e+04 1.0e+00 9.1e-01 2.00e-01
1 1.4e+03 0.0e+00 9.2e-02 +6.92e+04 +3.16e+03 9.9e-01 9.9e-01 2.00e-01
2 1.7e+02 0.0e+00 5.1e-04 +8.24e+04 +3.30e+02 1.1e+00 1.0e+00 2.00e-01
3 1.7e+01 0.0e+00 1.5e-17 +8.94e+03 +3.14e+02 9.5e-01 8.5e+00 1.00e-01
4 2.4e+00 0.0e+00 1.6e-16 +1.58e+03 +3.89e+02 7.9e-01 1.9e+00 1.00e-01
5 6.1e-01 2.2e-18 1.6e-16 +7.71e+02 +4.67e+02 6.1e-01 8.1e-01 1.00e-01
6 2.4e-01 4.3e-18 2.9e-17 +6.46e+02 +5.24e+02 7.3e-01 4.4e-01 1.00e-01
7 1.2e-01 6.5e-18 1.6e-17 +6.09e+02 +5.50e+02 1.0e+00 5.5e-01 1.00e-01
8 5.4e-02 7.6e-18 7.9e-18 +6.02e+02 +5.75e+02 9.5e-01 7.5e-01 1.00e-01
9 1.6e-02 8.7e-18 4.5e-18 +5.99e+02 +5.91e+02 9.2e-01 9.0e-01 1.00e-01
10 3.0e-03 8.7e-18 1.1e-17 +5.98e+02 +5.97e+02 9.1e-01 9.2e-01 1.00e-01
11 5.2e-04 8.7e-18 1.3e-17 +5.98e+02 +5.98e+02 9.1e-01 9.3e-01 1.00e-01
12 8.5e-05 1.1e-17 2.0e-17 +5.98e+02 +5.98e+02 9.2e-01 9.5e-01 1.00e-01
13 1.3e-05 1.3e-17 5.2e-17 +5.98e+02 +5.98e+02 9.4e-01 9.7e-01 1.00e-01
14 1.6e-06 1.1e-17 9.2e-17 +5.98e+02 +5.98e+02 9.4e-01 1.0e+00 1.00e-01
15 1.8e-07 1.3e-17 8.3e-17 +5.98e+02 +5.98e+02 9.4e-01 1.0e+00 1.00e-01
16 1.9e-08 1.5e-17 1.0e-16 +5.98e+02 +5.98e+02 9.4e-01 1.0e+00 1.00e-01

phase.value = pdOPT
Iteration = 16
mu = +1.8991595780448735e-08
relative gap = +1.5875318300440691e-08
gap = +9.4957980536491959e-06
digits = +7.7992775583358824e+00
objValPrimal = +5.9814851893457831e+02
objValDual = +5.9814850943878025e+02
p.feas.error = +1.5543122344752192e-15
d.feas.error = +9.9920072216264089e-15
total time = 2.625671
main loop time = 2.620902
total time = 2.625671
file check time = 0.000000
file change time = 0.000063
file read time = 0.004706
SDPA end at [Mon Jul 18 01:44:05 2011]
ALL TIME = 2.891928

○サーバ１
CPU : Intel Core 2 Quad 9650 3.0GHz
Memory : 8GB
OS : Fedora 15 for x86_64

○サーバ２
CPU : AMD Phenom(tm) II X4 955 3.2GHz
Memory : 8GB
OS : Fedora 15 for x86_64

○サーバ３
CPU : Intel Xeon E5530 2.4GHz
Memory : 6GB
OS : Fedora 15 for x86_64

○サーバ４
CPU : Intel Corei7 2600K 3.40GHz
Memory : 8GB
OS : Fedora 15 for x86_64

かなりハードな MIP その３

前回の CPLEX 12.2.0.2 での実行ではすでに報告したようにメモリ不足で停止した（上界：308, 下界 231)。今度は別の MIP ソルバー(FiberSCIP)で解いてみた。303165秒後に残念ながらメモリ不足のため手動で停止したが、それでも上界は 236 と更新された。別のサーバで挑戦すれば最後まで解ける可能性もあるだろう。

303165秒
236.0000 231.0000 2.16%

ちなみに GLPK 4.45 では、上記のソルバーとほぼ同じ時間かけて説き続けても、上界 308, 下界 118 となっている。

○計算サーバ(4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 15 for x86_64