「e-サイエンスに向けた革新的アルゴリズム基盤」シンポジウム

「e-サイエンスに向けた革新的アルゴリズム基盤」シンポジウムのプログラムが確定しました。参加には事前申し込み等は必要ありませんが、参加予定の方はご一報いただけると幸いです。

日時：9月4日（日曜日）13時30分から17時00分まで
場所：公立はこだて未来大学（http://www.fun.ac.jp/）研究棟　R791室
プログラム（確定版）
1. 13:30～13:55 「計画概要」　加藤直樹（京都大学）
2. 13:55～14:20 「ポストペタスケールスパコンにおける超大規模グラフ最適化基盤」 藤澤克樹（中央大学）
3. 14:20～14:45　「建築・都市計画における避難計画問題と計算機技術」 瀧澤重志（京都大学）
4. 15:00～15:25 「生物高次情報データベース高速検索アルゴリズム」 渋谷哲朗（東京大学）
5. 15:25～15:50 「アルゴリズムの応用例：　物体の認識と画像検索」 徳山豪（東北大学）
6. 15:50～16:15 「ZDDを用いた新しい列挙アルゴリズムとその実応用への展開」：　湊真一（北海道大学）
7. 16:20～17:00 自由討論

SDPARA 7.3.3 と Cholesky 分解

TSUBAME 2.0 で SDPARA 7.3.3 が無事に動作することを確認した(16 ノード x 12 コア)。ただし MPI は OpenMPI のみでの確認で MVAPICH2 では動作確認が取れていない。また以前の以下のように書いたのだが、制約条件が 100 万程度ならばポストペタスパコンが無くても今のペタスパコンで解くことができる。ポストペタでは２～３百万でも可能になるのではないだろうか。

マルチスレッド計算時の性能比較 : SDPA と CSDP

前回の続きで SDPA 7.4.0 と CSDP 6.1.1 のマルチスレッド計算時の実行時間をさらに詳細に比較する。全体の実行時間(Total)と ELEMENTS (SCM の計算) 及び CHOLESKY(SCM の Cholesky 分解) の計算時間で比較を行う。スレッド数は 1 から 48 まで変化させていく。

◯問題 : Be.1S.SV.pqgt1t2p.dat-s

まずは全体の実行時間(Total)の比較。16 スレッドまではあまり大きな差は無いが、24 スレッド以降は両者の差が大きくなる。CSDP は性能が上がらない、あるいは悪化していくが、SDPA の方は順調に計算時間が減少していく。


ELEMENTS 部分の実行時間の比較。全体の実行時間の中で ELEMENTS が大きな割合を占めるので、ELEMENTS と Total の傾向はほとんど同じ。


CHOLESKY 部分の実行時間の比較。両者ともこの部分はほぼ BLAS (LAPACK) ライブラリに委託なので、ほとんど差は見られない。



○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64

マルチスレッド計算時の性能比較 : MIP その３

マルチスレッド計算時の性能比較 : MIPの数値実験(1スレッドから48スレッドまで1スレッドずつ増やしながら解いていく）をもう１回を行ってみた。青が今回の結果で赤が前回の結果となる。全体の傾向は似ているが、スレッド数によっては、１回目と２回目の結果がかなり異なることもある。



○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4
Memory : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64

マルチスレッド計算時の性能比較 : MIP その２

昨日の続きで、roll3000.mps の問題に対して、スレッド数 2, 4, 8, 16, 32, 48 でそれぞれ７回ずつ計算を行った。現時点では特に統計処理は行っていないで、結果のみを掲載した。

２スレッド
1 : 5897.00
2 : 5787.80
3 : 6236.59
4 : 6041.58
5 : 5804.74
6 : 5994.20
7 : 5760.94

４スレッド
1 : 1437.00
2 : 2853.85
3 : 4183.15
4 : 2986.87
5 : 2927.55
6 : 2826.98
7 : 3167.58

８スレッド
1 : 3044.85
2 : 2485.03
3 : 1125.37
4 : 1055.43
5 : 965.62
6 : 1163.85
7 : 1523.26

１６スレッド
1 : 406.17
2 : 837.75
3 : 2117.94
4 : 606.44
5 : 450.79
6 : 1675.71
7 : 1094.18

３２スレッド
1 : 2479.35
2 : 1998.15
3 : 1803.23
4 : 1542.21
5 : 2403.46
6 : 3262.99
7 : 2516.65

４８スレッド
1 : 5270.78
2 : 4389.12
3 : 6695.13
4 : 6877.30
5 : 4610.14
6 : 5493.50
7 : 6990.08

○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4
Memory : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64

○参考：１から４８スレッドまでの結果

マルチスレッド計算時の性能比較 : MIP

昨日と同じような実験を今度はある MIP ソルバーを用いて行ってみた。



全体的にはスレッド数 16 まで実行時間が減っていき、その後では増加していく傾向になる。
例えばスレッド数４で７回実行を行うと以下にように結構ばらつきがあるので、もう一度実験を行うとまた違った結果になる可能性はある。

1回目 : 1437.00s
2回目 : 2853.85s
3回目 : 4183.15s
4回目 : 2986.87s
5回目 : 2927.55s
6回目 : 2826.98s
7回目 : 3167.58s

○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4
Memory : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64

マルチスレッド計算時の性能比較

SDPA 7.4.0 と CSDP 6.1.1 のマルチスレッド計算時の実行時間を比較する。6 あるいは 12 スレッド時にはあまり性能差は無いが、24 スレッド時あたりから大きな性能差が見られるようになる(CSDP は48コア時ではかえって性能が悪化する)。詳細なデータについては以下の図を参照していただきたい。

◯問題：Be.1S.SV.pqgt1t2p.dat-s




○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4
Memory : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 15 for x86_64

最適化と計算に関する最新の傾向

◯アルゴリズムによる高速化と計算機による高速化が明確に分離（区別）することが出来なくなった. つまり最新のアルゴリズムでは最新の計算機アーキテクチャでの実行を前提としたものが増えてきている．
◯計算量による理論的解析の優劣とソフトウェア実装後に計算機で実行したときの計算結果が大きく異なるという現象が見られる.その理由としては以下のような原因が考えられる
◯理論的な解析時に想定されている最悪な場合という現象が計算機上で扱うことのできる問題の範囲では起こらない. 例えば，現在の計算機においては整数型の変数は大きくても $2^{64}-1$ であるので，計算機で扱うことができる範囲では $\log_2 n$関数は大きくても 64 程度である（つまり定数とみなすこともできる）．
◯計算量の評価において,演算量とデータ移動量が混同されている(一般的には後者の方がコストが高い).

全米道路ネットワークに対する全対全最短路問題

全米道路ネットワーク(点数 23,947,347, 枝数 58,333,344)に対して全対全最短路を計算することを行った。単に１対全最短路を複数回（点数の数）計算を行うのは、様々な意味でコストが大き過ぎるので、いろいろな工夫を試している。以下の結果では AMD Magny-Cours 48 コアのマシンを用いて全対全最短路の計算を行っているが、計算時間を 7.75日に減少させることに成功した。もし仮に百万コアを計算に利用できると仮定すると 30 秒ほどで計算が終了することになる。

グラフ探索と応用

大規模なネットワークデータ上における最短路計算などのグラフ探索アルゴリズムには以下のように非常に幅広い応用があることが知られている。

1. 交通ネットワークにおける経路検索(カーナビゲーションシステム等)
2. 災害時における避難や誘導等の支援システム
3. Twitter, Facebook などのソーシャルネットワークデータの解析

これらの応用においては、今後は超大規模ネットワークデータ（点数１億以上) が対象となることが予想されるので、超高速な探索アルゴリズムとソフトウェアの開発が急務となっている。例えば上記のソーシャルネットワークデータの解析においては、ネットワーク内での各点の重要度を計算することによって、各点の周辺、及び広域内における影響（情報の伝播力) を推定することができる。しかし、そのためには大規模ネットワークデータ上での短時間に大量のグラフ探索を行う必要があり、メモリ要求量を抑えた上で、大量のスレッドを生成、同時並行的にグラフ探索を行うことによって、極めて高いスループットを得ることができる。

SDPA(SDPARA)のボトルネック その２

昨日の続き。SCM (Schur Complement Matrix) が疎になる場合では以下のように様相が異なってくる。こちらの方は SCM が密な場合よりもさらに高速化は難しい。

○問題：mater-6.dat-s
11.19 6.41 6.41 1286181 0.00 0.00 dtrsm_ounucopy
10.25 12.28 5.87 325187 0.00 0.00 sdpa::Newton::compute_bMat_sparse_SDP_thread_func(void*)
9.52 17.73 5.45 25391137 0.00 0.00 sdpa::Newton::calF3_thread_2(double&, sdpa::DenseMatrix&, sdpa::DenseMatrix&, sdpa::SparseMatrix&, sdpa::SparseMatrix&
)
5.50 20.88 3.15 21126427 0.00 0.00 blas_lock
5.20 23.86 2.98 dgemm_kernel
5.09 26.78 2.92 10377180 0.00 0.00 sdpa::Lal::plus(sdpa::DenseMatrix&, sdpa::DenseMatrix&, sdpa::SparseMatrix&, double*)
4.54 29.38 2.60 550298 0.00 0.00 sdpa::DenseMatrix::initialize(int, int, sdpa::DenseMatrix::Type)
4.15 31.75 2.38 10377180 0.00 0.00 sdpa::Lal::getInnerProduct(double&, sdpa::SparseMatrix&, sdpa::DenseMatrix&)
2.86 33.39 1.64 10611994 0.00 0.00 exec_blas
2.79 34.99 1.60 dgemm_oncopy

○問題：BroydenTri1000.dat-s
26.58 2.31 2.31 41807 0.00 0.00 sdpa::Newton::compute_bMat_sparse_SDP_thread_func(void*)
5.75 2.81 0.50 22 0.02 0.03 dmumps_148_
5.06 3.25 0.44 3297360 0.00 0.00 blas_lock
4.95 3.68 0.43 537461 0.00 0.00 dtrsm_ounucopy
4.14 4.04 0.36 1358060 0.00 0.00 exec_blas
3.97 4.39 0.35 79485 0.00 0.00 sdpa::DenseMatrix::initialize(int, int, sdpa::DenseMatrix::Type)
2.99 4.65 0.26 7703891 0.00 0.00 sdpa::Newton::calF3_thread_2(double&, sdpa::DenseMatrix&, sdpa::DenseMatrix&, sdpa::SparseMatrix&, sdpa::SparseMatrix&
)
2.99 4.91 0.26 2374922 0.00 0.00 sdpa::Lal::getInnerProduct(double&, sdpa::SparseMatrix&, sdpa::DenseMatrix&)
2.88 5.16 0.25 2607985 0.00 0.00 sdpa::DenseMatrix::setZero()

SDPA(SDPARA)のボトルネック

SDPA(SDPARA)の関数レベルでは以下の２つのように F3 式の計算か行列積(dgemm)がボトルネックとなっている。小さな問題や特殊な問題を別とするとおおよそ以下の２つのパターンに分類することができる。

○問題：Be.1S.SV.pqgt1t2p.dat-s
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls Ks/call Ks/call name
79.93 5925.08 5925.08 604172027 0.00 0.00 sdpa::Newton::calF3_thread_2(double&, sdpa::DenseMatrix&, sdpa::DenseMatrix&, sdpa::Sparse
Matrix&, sdpa::SparseMatrix&)
8.63 6564.87 639.79 dgemm_kernel
6.88 7074.83 509.96 38 0.01 0.17 sdpa::Newton::compute_bMat_dense_SDP3(sdpa::InputData&, sdpa::Solutions&, sdpa::WorkVariabl
es&, sdpa::ComputeTime&)
1.25 7167.63 92.80 dgemm_otcopy
0.43 7199.18 31.55 593271 0.00 0.00 dtrsm_oltncopy
0.39 7227.87 28.69 dgemm_beta

○問題：nug12_r2.dat-s
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
59.57 1108.97 1108.97 dgemm_kernel
14.53 1379.39 270.42 dgemm_otcopy
13.88 1637.74 258.35 38 6.80 9.41 sdpa::Newton::compute_bMat_dense_SDP3(sdpa::InputData&, sdpa::Solutions&, sdpa::WorkVariabl
es&, sdpa::ComputeTime&)
5.33 1737.05 99.31 33818739 0.00 0.00 sdpa::Newton::calF3_thread_2(double&, sdpa::DenseMatrix&, sdpa::DenseMatrix&, sdpa::SparseM
atrix&, sdpa::SparseMatrix&)
2.74 1788.12 51.07 531633 0.00 0.00 dtrsm_oltncopy
2.38 1832.48 44.36 dtrsm_kernel_RN

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

以下の”超大規模グラフ解析プロジェクト”ですが、近日中に正式公表する（される）と思います。まだ公表はできませんが、現在様々な研究が開始されています。計算量や要求されるメモリバンド幅を抑えた後に、超大規模スレッド並列処理で超大規模な最適化問題等を扱っていくという方針が最新の HPC 技術と結び付く形で大幅に強化されます。

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

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

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

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

参考：全米道路ネットワークに対する全対全最短路問題

VineSeed と SDPA

Vine Linux ではその開発過程を VineSeed として公開している。Vine Linux の方は現在最新版として 6.0 が公開されているが、VineSeed はすでに 7.0 扱いとなっており、Linux のカーネルのバージョンも 3.0.1 に達している。VineSeed で SDPA の実行を行う方は少ないと予想されるが、念のため動作確認を行った。

◯ VineSeed
カーネル：3.0.1
Intel C++/Fortran : 12.0.5 (インストール可)
SDPA 7.4.0 : 動作確認 OK

Chromium OS と最短路 Online Solver

vmplayer 3.1.4 で作成した仮想マシン上に Chromium OS をインストールした。起動も速いが、起動後のブラウザ上での最短路 Online Solver の動きが非常に速い。個人的にはこれまで体験した中では最速ではないかと思われるほど。