Fatal Error

以下の計算サーバが SDPA の計算中に暴走したので、IPMI ツールでログを取得したところ、やはり内部にエラーが発生していた。これは修理が必要になる。

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

「IPMIツールを使用したログ取得方法（PowerEdge 第9世代・Windows OS用）」

Severity : normal
Date and Time : Wed Dec 16 16:56:24 2009
Description : System Board SEL: event log sensor for System Board, log cleared was asserted

Severity : critical
Date and Time : Fri May 14 09:22:44 2010
Description : CPU3 Status: processor sensor for CPU3, thermal tripped was asserted

Severity : critical
Date and Time : Wed Nov 24 07:18:09 2010
Description : CPU3 VCORE: voltage sensor for CPU3, state asserted

Severity : critical
Date and Time : Wed Nov 24 07:18:14 2010
Description : System Board PFault Fail Safe: voltage sensor for System Board, state asserted

SCMのメモリ消費量

SDPA の入力ファイルには mDIM というパラメータがあって、これによって SCM(Schur complement matrix)のサイズが決定される。



以下は QAPLIB の esc32a に対する DNN 緩和問題である。

102208 = mDIM
14 = nBLOCK
-101740 193 129 129 161 65 193 225 225 161 193 193 225 257 = bLOCKsTRUCT

SCM はサイズが 102208 x 102208 の行列になる。各要素は double 型なので、SCM だけで 79.7GiBytes のメモリが必要になる。もちろん SCM 以外にもメモリ上にデータ保存が必要だが、この場合では SCM 以外の保存に対してはあまり大きなメモリ量は必要ではなく、全部で 90GiBytes ぐらいのメモリ量になる。

もし、mDIM = 493056 ならば(esc32a に対する Fully DNN 緩和問題)、1811GiBytes となるので、新クラスタ計算機でもメモリに全データを保存するのはかなり大変である。
mDIM = 379350 だとすると(tai30a に対する Fully DNN 緩和問題)、1072GiBytes　なので約 1TB となり、このくらいであれば新クラスタ計算機でも解けそうな範囲である。とりあえず mDIM の上限は 40万強ぐらいだろう。

○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1

HOKKE-18

おそらく以下の研究発表会に参加する予定。省電力や GPU 関係の研究発表はどこの研究会に参加しても多くなっている。

第18回ハイパフォーマンスコンピューティングとアーキテクチャの評価に関する北海道ワークショップ
未来の情報処理基盤のためのハードとソフトの研究協力・共創へ向けて
（第184回計算機アーキテクチャ・第128回ハイパフォーマンスコンピューティング合同研究発表会（HOKKE-18））

日　　程　：　 2010年12月16日（木）～2009年12月17日（金）

会　　場　：　北海道大学 学術交流会館
　　　　　　　　 http://www.hokudai.ac.jp/bureau/map/map4.htm

最短路問題でよく見かける話題

最短路問題に関してアルゴリズムの教科書や授業や講演等で使用されている資料に以下のように書いてあるのを見かけることが多い。

１：ダイクストラ法においてはポテンシャル最小の点を見つける際に優先キュー（ヒープ、特に2-ヒープ)などを使用すると実行時間が速くなるが、フィボナッチヒープを使うとさらに速くなる。

○点数を n, 枝数を m とする。2-ヒープでは計算量が O(m log n)、 フィボナッチヒープを使うと O(m + n log n) になるのだが、実際にはフィボナッチヒープを使うと実行があまり速くならない（むしろ遅い）。実用的に高速なのは ヒープ(heap)、バケット(bucket)、マルチレベルバケット(MLB)あたりのデータ構造である。

２：全対全最短路問題に対しては、１対全最短路問題に対するダイクストラ法を点の数だけ繰り返すよりもワーシャル・フロイド法(Warshall-Floyd)を使うのが良い。

○ ワーシャル・フロイド法はメモリ要求量が非常に大きいので大規模な問題には向かない。それに多くの場合では１対全最短路問題に対するダイクストラ法を点の数だけ繰り返す方が速い場合が多い。

理論と実際の計算はまた異なる世界なので、教科書などを鵜呑みにせずに実際に計算して試してみることを推奨したい。

SDPA 改造中 その３

前回の話の続きであるが、SDPA の SCM のマルチスレッド計算の部分を現在変更＆改善中である。これまで採用していた動的な負荷分散は一旦止めにして事前に各スレッドに計算する行を割り当てるようにしている。



○行番号順にスレッドに仕事を割り当てていく。割り当て量が”全仕事量 / スレッド数”を越えたら次のスレッドに割り当てる。最後のスレッドの仕事量は少なめになる。
スレッド番号: 仕事量（計算量）
1: 1162478024280.000000
2: 1163614234076.000000
3: 1163861405672.000000
4: 1162783829258.000000
5: 1162850520444.000000
6: 1162479025872.000000
7: 1162599575326.000000
8: 1147114595742.000000

○なるべく各スレッドの仕事量が均等になるように割り当てていく。各スレッドに割り当てられた行番号が連続しているとは限らない。
スレッド番号: 仕事量（計算量）
1: 1163258562622.000000
2: 1163285102594.000000
3: 1163161737610.000000
4: 1163160694252.000000
5: 1163185723086.000000
6: 1163186821016.000000
7: 1163105552090.000000
8: 1163117203174.000000

後者の方が確かに各スレッドに均等に割り付けられてはいるものの、仕事量の合計ではむしろ大きくなってしまう。各スレッドの実行は完全に同期されて始まるわけではなくわずかに時間差があるので、少し仕事量が多めのスレッドがあっても、それが小さい番号のスレッドの場合には全体にあまり悪い影響を与えないようだ。他にもいろいろと判明してきたことがあるので、変更と改善はしばらく続ける予定。

TEPS その４

様々な計算機を用いて TEPS 値の測定を行った。データは DIMACS USA グラフで p2p 最短路問題を解いた。



○結果１
CPU : Intel Atom 330 1.6GHz
Memory : 2GB
OS : Fedora 13 for x86_64

やはり遅い Intel Atom。しかし浮動小数点演算よりは上位の CPU との性能差が少ない。



○結果２
CPU : Intel Core 2 Duo 1.4GHz
Memory : 2GB
OS : Mac OS X 10.6.5

意外？と速いかもしれない MBA。もちろん数値計算向けではない。



○結果３
CPU : Intel Core 2 Quad 9650 3.0GHz
Memory : 8GB
OS : Fedora 13 for x86_64

メモリバンド幅が低い割には健闘している Intel Core 2 quad。



○結果４
CPU : Intel Core i7 965 3.2Hz
Memory : 12GB
OS : Fedora 13 for x86_64

さすがに Nehalem 系は速いが、高性能なためには高クロックも必要になる。

MIPLIB2003 ：Gurobi 4.0.0 と CPLEX 12.2

すでにこちらのブログで報告したように、CPLEX 12.2 で MIPLIB2003 の ds インスタンスの最適解を求めることができた。計算機環境や CPLEX のログファイルは以下の通りである。

○ CPLEX 12.2 ログファイル

○計算サーバ １(2 CPU x 6 コア = 12 コア)
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64

計算機環境が異なるので単純な比較は出来ないのだが、Gurobi 4.0.0 を用いて ds インスタンスを途中まで解いたみた。CPLEX 12.2 で最適解を求めることができたので、こちらのプロセスは停止した。

○ Gurobi 4.0.0 ログファイル

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

Gurobi 4.0.0 の方は停止時で以下のようになっているので、830190s 時で Gap が 60.4% もある。

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
1123081 744175 142.94245 1799 265 202.48500 80.25328 60.4% 579 830190s

CPLEX 12.2 を実行した計算サーバ１の方が、コア数も多く CPU 単体の性能も高いのだが、それでも 831850s 時には Gap は 4.78% しかない。
Elapsed real time = 831850.54 sec. (tree size = 62314.36 MB, solutions = 84)
Nodefile size = 62175.09 MB (27485.56 MB after compression)
3118352 1764904 94.7152 197 95.4575 90.8962 1.79e+09 4.78%

また、CPLEX 12.2 で Gap 60.4% になるのは、49324s 後である。総合的に判断すると、このインスタンスに関しては CPLEX 12.2 の方が優れていると言えよう。

Elapsed real time = 49324.68 sec. (tree size = 2944.38 MB, solutions = 60)
Nodefile size = 2807.03 MB (1216.27 MB after compression)
115979 89792 cutoff 189.4900 74.9944 1.08e+08 60.42%

TEPS その３

以下は非常に巨大なネットワークデータ上での BFS(幅優先探索)を行った結果だが、一つのデータを各プロセッサで分散して生成＆保持＆計算を行う形でグラフ探索を行っている。つまり、大量のクエリを並列に処理する（1コアで1クエリを処理)タイプのベンチマークでは無いようだ。そのために最適化出来る余地が現在では少なく、アルゴリズムや実装の工夫による性能向上はあまり無いと予想され、スパコン自体の性能に極度に依存したベンチマークになっていると推測される。

http://www.graph500.org/Results.html

一方、1コアで1クエリの処理ではかなり性能を上げていくことができる。データの大きさによってキャッシュメモリ(特に L3 キャッシュ)の利用効率が異なるので、TEPS 値も異なっている。ただし、これは最短路ソルバーでの TEPS 値になるので、BFS よりは遅めになる。

○データ１：NY (NewYork) : #nodes: 264,346 | #arcs: 733,846
21.41 ME/s (最大値)

○データ２：USA : #nodes: 23,947,347 | #arcs: 58,333,344
12.16 ME/s (最大値)

○データ３：Random : #nodes: 1G | #arcs: 2G
2.37 ME/s (1クエリ)

上記のベンチマークデータでは、おそらく 1 コアで 1 ME/s も性能が出ていないのではないだろうか。CRAY XMT は 1 プロセッサで 128 スレッドを生成できるので、1 node での CPU 数がわからないが、1 node = 1 CPU としても 128 x 128 = 16384 個のスレッドが生成されていることになる。その割には性能が良くないという感じもするが、詳細なデータが無いのでは現時点では推定が多い。

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

MIPLIB2003 ：Gurobi 3.0.2 と CPLEX 12.2 その５

MIPLIB2003 の ds 問題を CPLEX 12.2 を用いて解きつづけていたが、合計 1643718.77秒 (= 約19日) で終了し、最適解を求めることができた。これによって、既に ParaSCIP で求められていた解が最適解であることの追試にもなった。下記の Iteration 数がオーバーフローしているのが、ちょっと気になる。

Elapsed real time = 1643521.25 sec. (tree size = 1311.96 MB, solutions = 95)
Nodefile size = 884.47 MB (343.55 MB after compression)
8994003 14679 cutoff 93.5200 93.5097 3.77e+09 0.01%

Clique cuts applied: 428
Cover cuts applied: 6
Zero-half cuts applied: 23

Root node processing (before b&c):
Real time = 156.51
Parallel b&c, 12 threads:
Real time = 1643562.26
Sync time (average) = 40166.08
Wait time (average) = 126856.09
-------
Total (root+branch&cut) = 1643718.77 sec.

Solution pool: 95 solutions saved.

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 9.3520000000e+01
Current MIP best bound = 9.3510648316e+01 (gap = 0.00935168, 0.01%)
Solution time = 1643719.60 sec. Iterations = -2147483648 Nodes = 8994890 (13756)

○サーバ (2 CPU x 6 コア = 12 コア)
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64

TEPS その２

本来は BFS (幅優先探索）での測定になるが、最短路のプログラム(1対全:優先キュー付きダイクストラ法)を用いて traversed edges per second (TEPS) の値を測定した。

http://www.graph500.org/Specifications.html

We measure TEPS through the benchmarking of kernel 2 as follows. Let timeK2(n) be the measured execution time for kernel 2. Let m be the number of input edge tuples within the component traversed by the search, counting any multiple edges and self-loops. We define the normalized performance rate (number of edge traversals per second) as:

TEPS(n) = m / timeK2(n)

以下の Intel Core i7 の計算サーバ１を用いて、全米データ 256 クエリの最短路探索を行い、1 クエリ単位で TEPS 値を測定する。



○１コアのみ：TEPS 値
最大値：21.01 ME/S
最小値：12.22 ME/S
平均値：14.27 ME/S

１コアのみで計算を行うと Core i7 では最大の場合、１秒間に 2100万枝の探索を行うことができる。

○４コア同時計算：TEPS 値
最大値：20.04 ME/S
最小値：9.90 ME/S
平均値：12.43 ME/S

4コア同時計算でも意外と性能低下は少ない。

○計算サーバ1 (1CPU x 4 コア = 4 コア)
CPU : Intel Core i7 965 3.2GHz x 1
メモリ : 12GB
OS : CentOS 5.5 for x86_64

上記の場合では、おそらく優先キューのサイズが L3 キャッシュのサイズと比較して小さいのだが、例えば超大規模グラフ(点数=1,073,741,824, 枝数=2,147,483,647 つまり点数 1G, 枝数 2G)になると L3 キャッシュから溢れてしまい、単純にメモリバンド幅に依存した性能になってしまう。

○１コアのみ：TEPS 値（計算サーバ２）
2.08 ME/S

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

ちなみに以下は BFS (幅優先探索）の結果なので最短路探索よりは性能上は有利である。
http://www.graph500.org/Results.html

SDPA 改造中 その２

SDPA の SCM のマルチスレッド計算の部分を現在変更＆改善中である。下記の説明図は少し古いので最新の計算方法と乖離が大きくなってきた。



まだ改善の第一歩という感じではあるが、結果が出てきたので以下に記す。今後に期待が出来る内容になっている。
Make bMat time = 37.837696, 22.692260
とは、SDPA 全体の中での SCM (bMat)に作成にかかる時間(37.837696秒)と全体に占める割合(22.692260%) を示してる。

○問題 nug12_r2 (QAP に対する DNN 緩和)
SDPA 7.3.2 : 167.72 秒
Make bMat time = 37.837696, 22.692260

SDPA 7.3.3β : 151.88 秒
Make bMat time = 21.765915, 14.421360

○問題 theta6 (Lovasz 数の計算)
SDPA 7.3.2 : 16.28 秒
Make bMat time = 5.284072, 33.325996

SDPA 7.3.3β : 13.70 秒
Make bMat time = 2.717404, 20.392052

○問題 NH3+.2A2".STO6G.pqgt1t2p.dat-s (量子化学)
SDPA 7.3.2 : 434.53 秒
Make bMat time = 396.927715, 91.822555

SDPA 7.3.3β : 424.83 秒
Make bMat time = 388.019430, 91.807977

いずれの問題においても SCM の計算部分の高速化に成功している。

○サーバ (2 CPU x 4 コア = 8 コア)
CPU : Intel Xeon 5460 (3.16GHz / 6MB L2 x 2) x 2
Memory : 48GB (12 x 4GB)
OS : CentOS 5.5 for x86_64

TEPS

Graph 500 List に関して traversed edges per second (TEPS) という指標が新しく定義された。

http://www.graph500.org/Specifications.html
We measure TEPS through the benchmarking of kernel 2 as follows. Let timeK2(n) be the measured execution time for kernel 2. Let m be the number of input edge tuples within the component traversed by the search, counting any multiple edges and self-loops. We define the normalized performance rate (number of edge traversals per second) as:

TEPS(n) = m / timeK2(n)

TEPS という指標は kernel 2 の性能によって計測されるのだが、kernel 2 はグラフに対する Breadth-First Search(BFS : 幅優先探索)アルゴリズムとなっている。m が BFS で通過した枝数なので、結局 TEPS とは単位時間あたりに何本の枝を探索（通過）できるかという指標になる。

現在の計算結果については以下に記されている。
http://www.graph500.org/Results.html
上位１０位の中に CRAY が 5 台(XMT が 3 台)含まれている。やはり CRAY XMT はグラフ関係の探索に強いのだろうが、データキャッシュメモリ等が無いのでプログラミングの工夫の余地が通常の CPU よりも少なくなっている。

ちなみにダイクストラ法 と BFS では後者の方がアルゴリズム的にも単純であるが、前者でも CPU 1 コアで 10ME/s (1000万枝 / 秒) 程度は現在のプログラムでも出ているかもしれない（もっと値が良い可能性もある）。

MacBook Pro v.s. MacBook Air

xbench というベンチマークソフトを用いて MacBook Pro と MacBook Air の性能比較を行った。比較結果は以下の通り。



Disk 以外は MacBook Pro の方が優れた結果になっているが、Disk は MacBook Air の方がかなり優れた結果になっている。やはり SSD は HDD よりもかなり性能面で有利な点が多いようだ。

追記：実験結果への画像のリンクが切れていましたので修正しました。

MIPLIB2003 ：Gurobi 3.0.2 と CPLEX 12.2 その４

MIPLIB 2003 の ds 問題を以下のサーバで解き続けているのだが、Nodes Left の値も減少傾向にあり（最高時は 2642729 個)、実行の山は越えたのではないだろうか。http://miplib.zib.de/miplib2003/ds.php によると最適目的関数値は 93.5200 となっている。

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap
Elapsed real time = 1292661.45 sec. (tree size = 78101.38 MB, solutions = 94)
Nodefile size = 77969.16 MB (33598.02 MB after compression)
5274419 2255197 93.1957 224 93.5425 91.8625 2.78e+09 1.80%
5275108 2255275 cutoff 93.5425 91.8625 2.78e+09 1.80%
5276566 2254872 92.9681 195 93.5425 91.8643 2.78e+09 1.79%
5277658 2255072 cutoff 93.5425 91.8643 2.78e+09 1.79%
5278227 2255193 cutoff 93.5425 91.8643 2.78e+09 1.79%
5279264 2254822 cutoff 93.5425 91.8660 2.78e+09 1.79%
5280512 2255089 cutoff 93.5425 91.8660 2.78e+09 1.79%
5281707 2255377 93.0427 171 93.5425 91.8660 2.78e+09 1.79%
5282920 2255358 cutoff 93.5425 91.8681 2.78e+09 1.79%
5283964 2255423 92.7510 137 93.5425 91.8681 2.78e+09 1.79%
Elapsed real time = 1294471.57 sec. (tree size = 78085.23 MB, solutions = 94)
Nodefile size = 77952.62 MB (33578.66 MB after compression)
5284725 2255608 93.3743 252 93.5425 91.8681 2.78e+09 1.79%

○サーバ (2 CPU x 6 コア = 12 コア)
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB（16 x 4GB / 800MHz）
OS : Fedora 13 for x86_64

2010 年度第４回 SCOPE 講演会

今週の土曜日に第４回 SCOPE を開催して以下の２件の講演を行います。是非ご参加下さい。

日　時 ： 2010年11月20日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6410号室
講演1
講演者 ： 高野 祐一氏（筑波大学, 日本学術振興会PD）
講演題目 ： コンスタント・リバランス・ポートフォリオ選択問題に対する多項式最適化アプローチ
講演概要：
ポートフォリオ選択問題とは、手持ちの資金を各金融資産に投資して運用する際の投
資比率を決定する問題である。本発表では、コンスタント・リバランス戦略を採用し
た多期間ポートフォリオ選択問題を扱う。コンスタント・リバランスとは、計画期間
の複数時点で一定比率にリバランス（投資比率の修正）を行う投資戦略であり、実務
で採用されることも多く、理論的にも好ましい性質を持つ。しかし、この戦略を採用
した多期間ポートフォリオ選択問題は非凸計画問題となるため、その大域的最適解を
得ることは難しい。一方で、平均‐分散基準を利用することで問題は多項式計画問題
として定式化され、本発表では Lasserre (2001) によって提案された「多項式計画
問題に対する半正定値計画緩和」を利用して求解を試みる。さらに、次数の高い多項
式計画問題を解くことを目的に、Lasserre (2001) の半正定値計画緩和を利用した切
除平面法を提案し、数値実験によってその性能を検証する。

講演2
講演者 ： Mozart Menezes氏　（Zaragoza Logistics Center, Zaragoza (Spain)）
講演題目 ： Correlation and Disruption Induced Effects on Location Problems
講演概要：
In this work we study a class of locations models where facilities may fail.
The problems are defined in a network and some important properties of the
objective functions are analyzed. Asymptotic results were obtained suggest
behavioral consistency of location patterns as function of the probability
of failure. In order to go beyond those asymptotic results and, in order to
accept the fact that failures may be correlated, we shift methodology and also
present results developed in a continuous location setting: a simple (yet classic)
2-facility problem on a unit segment, with customer demand distributed uniformly
over the segment. We analyze problems with Median and Center objectives under complete
and incomplete customer information regarding the state of facilities. Managerial
insights are discussed.