最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

SCOPE 第2回研究会のお知らせ

2009年05月31日 15時20分08秒 | Weblog
第2回研究会のお知らせです。場所は前回と同じになります。詳細が決まりましたらまた連絡致します。

日 時 : 2009年7月25日(土)14:00~
会 場 : 中央大学 後楽園キャンパス 6号館4階 6402号室

講演者
中田真秀氏(理化学研究所)

第一部 : 量子化学からでてくる半正定値計画と多倍長計算(仮題)
第二部 : オープンソースコミュニティでのソフトウェア開発について(仮題)

山田雄二氏(筑波大学)TBA
コメント
この記事をはてなブックマークに追加

SCOPE in つくば 2009 : 連絡 5月25日

2009年05月30日 00時19分20秒 | Weblog
現時点では新型インフルエンザ流行が大きく拡大する状況ではありませんので、予定通りつくば合宿は開催する予定でおります。

また特に30日のみ宿泊予定の方に連絡ですが、1日目終了後に筑波大学などのスタッフの方が誘導致しますので、懇親会前にチェックインを済ませるためバスで速やかに宿泊施設に移動してください。また日帰りで懇親会に参加される方はしばらく時間が空いてしまいますが、懇親会場付近に到着の後、適当な場所でお待ちくださるようお願いします。
コメント
この記事をはてなブックマークに追加

SDPA 7.3.x とマルチスレッド

2009年05月29日 03時05分53秒 | Weblog
今回は SDPA とマルチスレッドの内容になる(ほとんど業務連絡)。

例えば 8 コア(4 コア x 2 CPU) のマシンで動作させるとする。例えば OMP_NUM_THREADS=8 とすると、GotoBLAS も Schur complement 行列の計算も 8 スレッドで動作する。

1:行列全部が F3 式で計算される場合には BLAS を用いないので、8 コア上にちょうど 8 スレッドで収まる。
2:行列の一部が F1 式で計算されるとする。簡単のため 1 行だけ F1 式で計算されるとすると、ある 1 スレッドから GotoBLAS が呼び出されて DGEMM などでは、さらに 8 スレッドが生成される。このとき他の 7 スレッドは排他処理で一応停止させてあるが、コア数を大幅に越えるスレッドが存在するのでスレッド間の衝突(資源の奪い合い)が起こる。上記の排他制御から同時に 2 個のスレッドから F1 式が呼び出されることはない。
3:F2 式についても同様の排他制御を行っているが、F2 式の計算量が少ないので省略する。

○対策について
1: OMP_NUM_THREADS=4 に設定すると非常に高速になる。しかし Schur complement 行列の計算以外でも GotoBLAS を呼び出しているので、その部分は反対に遅くなることもある。GotoBLAS のスレッド数を動的に変更できると良い(上記の例では Schur complement 行列計算では OMP_NUM_THREADS=4、その他では OMP_NUM_THREADS=8)。

2:以下のように変更して GotoBLAS を作成する。しかし Schur complement 行列の計算以外での GotoBLAS の性能がかなり落ちてしまう。特に Schur complement 行列が疎になる場合では致命的に遅くなる。

変更1: 以下を 1 に変更する
# If you want to use legacy threaded Level 3 implementation.
USE_SIMPLE_THREADED_LEVEL3 = 1

変更2: 以下を 26 から 1 に変更する
CCOMMON_OPT += -DTHREAD_TIMEOUT=1
コメント
この記事をはてなブックマークに追加

AMD Istanbul Demo

2009年05月28日 02時46分26秒 | Weblog
AMD Istanbul Demo 24 コア(6コア x 4 CPU)のデモを見た。普段は Youtube の英語のコメントを読むことはほとんど無いが、いろいろと書いてあって面白かった。全く CPU とは関係の無い Istanbul City の説明なども書いてある。

http://www.youtube.com/watch?v=D11uY5dOE2c

Shanghai とソケット互換なので CPU 差し替えたら動作するらしいのだが、自作マシンならばともかく Dell のサーバで保証が効かなくなる危険を犯してまで自分で差し替える勇気はない。SDPA も Istanbul で動作させても多分それなりに性能が出るだろう。
コメント
この記事をはてなブックマークに追加

EQ

2009年05月27日 01時04分13秒 | Weblog
IQ(Intelligence Quotient =知能指数)だけでは指標としては十分ではないということで、EQ(Emotional Intelligence Quotient)テストが広く採用されている。某所でテストをしたところ参加者の平均が全国平均を下回ったそうで、一応相談を受けたのだが専門でないので EQ 自体がほとんどわからない。特にビジネスでは IQ よりも EQ だと言われているのに EQ も低かったら参加者は相当ショックだろうと思っていたら、そうでもないようだった。
試しに EQ テストをやってみると、例えば”やや当てはまる”と”かなり当てはまる”の境界がどの辺にあるのかを考えると、10回テストすれば10回とも自分の解答が異なるではないかと思うようになり、そうするとデータの信頼性がどの程度のあるのか気になった。また直前に良いことがあった場合と悪いことがあった場合では答えが異なるような気がして、習熟効果は別として IQ ほどの客観性は無いように思えた。EQ のことは深く知らないのでテスト自体を否定するわけではないが、二度とやってみたいとは思わない。
コメント
この記事をはてなブックマークに追加

シングル CPU 頂上対決 その2

2009年05月26日 12時47分34秒 | Weblog
Intel Core i7 965 はコストパフォーマンスが悪いので、手持ちの Intel Core i7 940 (2.93GHz)も加えてみた。おそらく 920(2.66GHz) でも マシン3や4よりは速いだろう。

○実行マシン1:Intel Core i7 965 (3.2Hz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン1:Intel Core i7 940 (2.93Hz) : メモリ 6GB : Fedora 10 for x86_64
○実行マシン3:Intel Core 2 Quad 9650 (3.0GHz) : メモリ 8GB : Fedora 10 for x86_64
○実行マシン4:AMD Phenom II X4 955 (3.2GHz) : メモリ 8GB : Fedora 10 for x86_64

○ソフトウェア
SDPA 7.3.1 + GotoBLAS 1.34 + LAPACK 3.2.1 + MUMPS 4.8.4 (OMP_NUM_THREADS=4)

○問題 mcp500-1.dat-s
マシン1: 1.404s
マシン2: 1.591s
マシン3: 1.891s
マシン4: 1.880s

○問題 theta6.dat-s
マシン1: 15.812s
マシン2: 17.275s
マシン3: 21.375s
マシン4: 21.319s

○問題 mater-4.dat-s
マシン1: 5.038s
マシン2: 5.617s
マシン3: 6.808s
マシン4: 6.917s

○問題 rabmo.dat-s
マシン1: 34.818s
マシン2: 38.455s
マシン3: 43.629s
マシン4: 44.303s
コメント
この記事をはてなブックマークに追加

シングル CPU 頂上対決

2009年05月25日 02時36分30秒 | Weblog
シングル CPU を持つノードの頂上対決を行ったのだが、予想通り Core i7 965 > Core 2 Quad 9650 = Phenom II X4 955 となった。

○実行マシン1:Intel Core i7 965 (3.2Hz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン2:Intel Core 2 Quad 9650 (3.0GHz) : メモリ 8GB : Fedora 10 for x86_64
○実行マシン3:AMD Phenom II X4 955 (3.2GHz) : メモリ 8GB : Fedora 10 for x86_64

○ソフトウェア
SDPA 7.3.1 + GotoBLAS 1.34 + LAPACK 3.2.1 + MUMPS 4.8.4 (OMP_NUM_THREADS=4)

○問題 mcp500-1.dat-s
マシン1: 1.404s
マシン2: 1.891s
マシン3: 1.880s

○問題 theta6.dat-s
マシン1: 15.812s
マシン2: 21.375s
マシン3: 21.319s

○問題 mater-4.dat-s
マシン1: 5.038s
マシン2: 6.808s
マシン3: 6.917s

○問題 rabmo.dat-s
マシン1: 34.818s
マシン2: 43.629s
マシン3: 44.303s
コメント
この記事をはてなブックマークに追加

SCOPE in つくば 2009 : 連絡 5月21日

2009年05月24日 02時20分32秒 | Weblog
新型インフルエンザの影響について問い合わせがありましたが、現時点では開催する予定で準備を進めております。しかし、今後の状況によっては変更や中止の可能性もあります。中止の場合はメイルでもお伝えしますが、それ以前の検討状況についてはブログまたはホームページで連絡する予定です。来週の始めには状況がさらに明確になってくると思います。
コメント
この記事をはてなブックマークに追加

HugeTLBfs と数値実験

2009年05月23日 01時22分51秒 | Weblog
数値計算の高速化と安定化のために HugeTLBfs を再度用いてみた。問題はいつもの theta6.dat-s を用いる。いずれの場合においても Dynamic Link を行うことによって以下のように HugeTLBfs の効果を確認できた。

○実行マシン:Intel Xeon 5550 (2.66GHz) x 2 : メモリ 72GB : Fedora 10 for x86_64

1: SDPT3-4.0-beta
○MATLAB Version 7.8.0.347 (R2009a) 64-bit (glnxa64)
HugeTLBfs なし: 25.765s
HugeTLBfs あり: 24.278s

2: CSDP 6.0.1 + GotoBLAS 1.34 + LAPACK 3.2.1
HugeTLBfs なし: 18.969s
HugeTLBfs あり: 17.464s

3: SDPA 7.3.1 + GotoBLAS 1.34 + LAPACK 3.2.1 + MUMPS 4.8.4
HugeTLBfs なし: 13.481s
HugeTLBfs あり: 12.665s
コメント (2)
この記事をはてなブックマークに追加

SCOPE in つくば 2009 : 連絡 5月17日

2009年05月22日 23時32分56秒 | Weblog
今日の連絡事項は以下の二つになります。

1: 2日間のプログラムを作成しました。こちらからダウンロードできます。

2: 昨年よりも懇親会の参加人数が増えることが予想されますので、昨年とは懇親会の場所を変更しました。17時半ごろには一日目が終了する予定ですが、その後に宿泊施設のチェックイン作業等を行い、つくばエクスプレス駅近辺に移動します。懇親会は19時半ごろに開始する予定です。

楼外楼 学園店
http://www.rogairo.com/shop-g.html
コメント
この記事をはてなブックマークに追加

ノーフリーランチ定理とトランスフォーマー

2009年05月21日 03時08分17秒 | Weblog
またトランスフォームしてリベンジになるようだ。前作は見に行ったが、人類側のあまりの弱さ、無力さにがっかりした。実際にはロボット等で映画のような高度のトランスフォームは無理だが、ウイルスというのは状況に応じてトランスフォームする能力を持っている。
最適化等に関するノーフリーランチ定理というのがあるが、全てのインスタンス(問題例)に対して、他を優越するような汎用戦略は作れない(理論的に存在しない)というものである。もちろんある特性を持ったインスタンス集合に対する優越戦略を作ることは可能である。実は SDPA は入力されたインスタンス(特性)に対してソフトウェアがトランスフォームするように作られている。例えば入力問題の特性によって以下の操作が行われる。

1: 定数行列を保持するデータ構造の決定(Dense か Sparse か?)
2: Cholesky 分解時の Fill-in 回数最小化のため ordering(並び替え)の決定
3: Schur complement 行列の各行を F-1, F-2, F-3 式のどれで計算するかを決定
4: コンピュータの計算能力やメモリバンド幅などに応じて、マルチコア CPU 上で自動的に Schur complement 行列の並列計算が行われる

SDP 自体は数理計画問題であっても、ソフトウェア内の戦略決定では組合せ最適化的な問題を考えることもある。
コメント
この記事をはてなブックマークに追加

SCOPE in つくば 2009 : 連絡 5月14日

2009年05月20日 03時07分24秒 | Weblog
5月14日現在での連絡事項です。

1: 宿泊箇所は大学会館、天久保、ホテルグランド東雲の3箇所になりました。ホテルグランド東雲に宿泊の予定に方にはすでに連絡を送っております。大学からはやや離れますので、車での送迎を予定しています。

2: プログラムは決定しました。近日中に発表します。2日目(31日)の終了は16時前になる予定です。また各セッションの座長を発表者に交代でお願いします。
コメント
この記事をはてなブックマークに追加

SDPA 7.3.0 : BLAS, ATLAS, GotoBLAS

2009年05月19日 01時13分12秒 | Weblog
前回(低中速マシンとマルチスレッド化)と同じような実験を複数の BLAS について行ってみた。結論から言えば BLAS/LAPACK 3.2.1 を用いるときは 1 スレッド(OMP_NUM_THREADS=1)に設定しておいた方が良い。

○実行マシン:Intel Xeon 5550 (2.66GHz) x 2 : メモリ 72GB : Fedora 10 for x86_64

○問題 theta6.dat-s

1: BLAS/LAPACK 3.2.1
1 x 1 ; 349.11 秒
1 x 8 ; 454.24 秒

2: ATLAS 3.9.11
8 x 1 ; 24.54 秒
8 x 8 ; 16.63 秒

3: GotoBLAS 1.33
8 x 1 ; 19.47 秒
8 x 8 ; 13.76 秒
コメント
この記事をはてなブックマークに追加

低中速マシンとマルチスレッド化

2009年05月18日 01時20分50秒 | Weblog
最新の SDPA 7.3.1 について低中速のマシン上でのマルチコア化の効果を調査した。具体的には以下のマシンを利用している。例えば 2 x 1 とは GotoBLAS 1.33 が2コアで計算、Schur complement 行列が1コアで計算することを示している。これらのようなマシンでもマルチコア化の効果を確認することができる。

○実行マシン1:AMD Athlon MP 2400+ (2.0GHz) x 2CPU : メモリ 2GB : Ubuntu 8.04 for x86
○実行マシン2:AMD Opteron 240 (1.4GHz) x 2CPU : メモリ 2GB : Ubuntu 9.04 for x86_64
○実行マシン3:Intel Xeon 5160 (3.0GHz) x 4コア : メモリ 8GB : CentOS 5.3 for x86_64
○実行マシン4:AMD Opteron 270 (2.0GHz) x 4コア : メモリ 4GB : Fedora 10 for x86_64
○実行マシン5:Intel Atom 330 (1.6GHz) x 2コア : メモリ 2GB : Fedora 10 for x86_64

○問題 theta6.dat-s

○マシン1
1 x 1 ; 374.09 秒
2 x 1 ; 270.93 秒
2 x 2 ; 210.55 秒

○マシン2
1 x 1 ; 294.24 秒
2 x 1 ; 190.27 秒
2 x 2 ; 157.50 秒

○マシン3
1 x 1 ; 62.32 秒
2 x 1 ; 39.34 秒
2 x 2 ; 41.67 秒
4 x 1 ; 28.61 秒
4 x 4 ; 25.64 秒

○マシン4
1 x 1 ; 204.83 秒
2 x 1 ; 126.34 秒
2 x 2 ; 104.12 秒
4 x 1 ; 92.47 秒
4 x 4 ; 61.64 秒

○マシン5
1 x 1 ; 489.89 秒
2 x 1 ; 303.14 秒
2 x 2 ; 270.02 秒
コメント
この記事をはてなブックマークに追加

SDPA 7.3.0 : Shanghai, Penryn, Nehalem-EP

2009年05月17日 02時42分38秒 | Weblog
論文用として SDPA 7.3.0 の数値実験をいろいろと行っている。マルチスレッド化の効果ということで、三つの場合に分けている。8スレッド時の Shanghai の性能が思っていたよりも良い。8 スレッド時ではメモリバンド幅が重要な要素の一つになるのだろう。

Case 1; Schur complement (1 スレッド) & GotoBLAS 1.33 (1 スレッド)
Case 2; Schur complement (1 スレッド) & GotoBLAS 1.33 (8 スレッド)
Case 3; Schur complement (8 スレッド) & GotoBLAS 1.33 (8 スレッド)

○実行マシン1:AMD Opteron 2384 (2.7GHz) x 2 : メモリ 32GB : Ubuntu 9.04 for x86_64
○実行マシン2:Intel Xeon 5460 (3.16GHz) x 2 : メモリ 48GB : CentOS 5.3 for x86_64
○実行マシン3:Intel Xeon 5550 (2.66GHz) x 2 : メモリ 72GB : Fedora 10 for x86_64
コメント
この記事をはてなブックマークに追加