以下の計算サーバが SDPA の計算中に暴走したので、IPMI ツールでログを取得したところ、やはり内部にエラーが発生していた。これは修理が必要になる。 ○サーバ (4 CPU x 6 コア = 24 コア) CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 Memory : 128GB (…

SDPA の入力ファイルには mDIM というパラメータがあって、これによって SCM(Schur complement matrix)のサイズが決定される。 以下は QAPLIB の esc32a に対する DNN 緩和問題である。 102208 = mDIM 14 = nBLOCK -101740 193 129 129 161 65 193 225 225 1…

おそらく以下の研究発表会に参加する予定。省電力や GPU 関係の研究発表はどこの研究会に参加しても多くなっている。 第18回ハイパフォーマンスコンピューティングとアーキテクチャの評価に関する北海道ワークショップ 未来の情報処理基盤のためのハードとソ…

最短路問題に関してアルゴリズムの教科書や授業や講演等で使用されている資料に以下のように書いてあるのを見かけることが多い。 １：ダイクストラ法においてはポテンシャル最小の点を見つける際に優先キュー（ヒープ、特に2-ヒープ)などを使用すると実行時…

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

様々な計算機を用いて TEPS 値の測定を行った。データは DIMACS USA グラフで p2p 最短路問題を解いた。 ○結果１ CPU : Intel Atom 330 1.6GHz Memory : 2GB OS : Fedora 13 for x86_64 やはり遅い Intel Atom。しかし浮動小数点演算よりは上位の CPU との性…

すでにこちらのブログで報告したように、CPLEX 12.2 で MIPLIB2003 の ds インスタンスの最適解を求めることができた。計算機環境や CPLEX のログファイルは以下の通りである。 ○ CPLEX 12.2 ログファイル ○計算サーバ １(2 CPU x 6 コア = 12 コア) CPU : A…

以下は非常に巨大なネットワークデータ上での BFS(幅優先探索)を行った結果だが、一つのデータを各プロセッサで分散して生成＆保持＆計算を行う形でグラフ探索を行っている。つまり、大量のクエリを並列に処理する（1コアで1クエリを処理)タイプのベンチマー…

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

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

SDPA の SCM のマルチスレッド計算の部分を現在変更＆改善中である。下記の説明図は少し古いので最新の計算方法と乖離が大きくなってきた。 まだ改善の第一歩という感じではあるが、結果が出てきたので以下に記す。今後に期待が出来る内容になっている。 Mak…

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 t…

xbench というベンチマークソフトを用いて MacBook Pro と MacBook Air の性能比較を行った。比較結果は以下の通り。 Disk 以外は MacBook Pro の方が優れた結果になっているが、Disk は MacBook Air の方がかなり優れた結果になっている。やはり SSD は HDD…

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

今週の土曜日に第４回 SCOPE を開催して以下の２件の講演を行います。是非ご参加下さい。 日 時 ： 2010年11月20日（土）14:00～ 会 場 ： 中央大学 後楽園キャンパス 6号館4階 6410号室 講演1 講演者 ： 高野 祐一氏（筑波大学, 日本学術振興会PD） 講演題…

先日も書いたように２台ある天吊り型エアコンの中の１台が不調のため現在クラスタ計算機等を停止している。１台から４方向に風が出て行くタイプのエアコンで１方向だけでも通常の家庭のエアコンと同じ程度の冷却力がある。不調の方のエアコンは突然停止して…

Gurobi 4.0.0 を入手したので、わずか４問ではあるが Gurobi 3.0.1, 3.0.2 との比較実験を行ってみた。こちらで作成した問題（上の２問）では、4.0.0 の性能は良くない。 ○問題 S-20-30-2-3.mps（ロットサイズ決定問題） Gurobi 3.0.1 : 330.30秒 3.0.2 : 50…

MIPLIB2003 の ds という問題を CPLEX 12.2 で解いているが(Gurobi 3.0.2 はメモリが不足したので断念）、4.79％まで gap が減少してきた。もう少しの間は解きつづける予定だが、いつも残り数％の gap がなかなか縮まらない。ちなみに Gurobi 4.0.0 について…

SDPA の特に SCM (Schur Complement 行列) のマルチスレッド計算の部分を改造中。動的負荷分散は成功していたのだが、それ以前に動的にすることによって計算時間が増えるという現象があるようだ。CRAY XMT のようにデータキャッシュの無い CPU であれば、計…

以下は 11 月 10 日の NEC のプレスリリースである。何千万台という自動車に関する何らかのリアルタイム処理にはクラウド上での基盤技術の開発が不可欠ということになっている。我々のグループでは以下の開発とは無関係ではあるが、これまで開発を行ってきた…

全米最短路 1000 クエリをサーバ１で解くと約 204 秒となる。よって平均すると 1 コアで 1 クエリの処理には 204 x 24 / 1000 = 4.9 秒かかる。 ○サーバ１ (4 CPU x 6 コア = 24 コア) CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 Memory : 128GB (32 x …

２台ある空調機の中で１台の調子が悪いので、現在クラスタ計算機も含めて約半分の計算機を停止させている。空調機は修理の予定。 また SDPA クラスタの中の１台で顕著な性能低下が発生している(sdpa06)。おそらくメモリ関係のエラーだと思われるが、Dell の…

Gurobi の方はメモリ量が 190Gbytes(サーバ搭載は 128Gbytes)を超えてしまったので停止した。停止時の結果は以下の通り。 ○サーバ１ + Gurobi 3.0.2 Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap…

もし SDPA(SDPA-GMP, SDPA-QD, SDPA-DD)の実行において以下のような現象に遭ったらどのようにパラメータを変えれば良いのだろうか？ 基本的に単調減少である mu が 0 から 1 反復において増加している。しかも 2, 3, 4 反復と mu, objP, objD の値がほとんど…

今度は本当に Gurobi 3.0.2 と CPLEX 12.2 の比較になる。前回と同様に MIPLIB2003 の ds という問題を扱う。サーバ２(CPLEX)の方がマシンスペックが低く、これまでの実行時間も短いにも関わらず上界と下界の間のギャップは小さい。 ○サーバ１ + Gurobi 3.0.…

MacBook Air は一番下のモデル (11インチ, Intel Core2 Duo 1.4GHz, メモリ 2GB, SSD 64GB)でも動作はかなり速い。例えば 電源ボタンを押してから使用可能になるまで：約１５秒 スリープ状態からの復帰：約１秒 MS Office(Word 2008 や Excel 2008)の起動：…

iPad で以下のオンラインソルバーを使用して動作チェックを行った。1 の方は限定的に使用可能であるが、２の方はほとんどの機能が正常に動作する。 1: SDPA Online Solver iPad からはファイルのアップロード＆ダウンロードが出来ない。それ以外の操作は可能…

正式には SC2010 期間中にアナウンスされるだろうが、以前からの予想通りに中国国防科学技術大学が開発した天河１号(１Ａ)が 2507 TFlops(2.507PFlops) で TOP500 2010 November の世界一になる見込みである。CPU + GPU システムの Linpack 性能効率は５割弱…

Graph 500 List が SC2010 の BOF セッションで発表、議論される予定になっている。Graph の Benchmark 集が出来るのは、アルゴリズムの開発、評価の面では好ましい。以下にもあるように三つのカーネル作りが競われることになろう。 1: concurrent search 2:…

MIPLIB2003 の中では以下の三つの分類がされている。 緑：instance can be solved within an hour with a commercial solver 黄色：instance has been solved 赤：optimal solution to instance is unknown ds という問題は黄色に分類されているので、既に最…