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

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

SDPA 2.01, 3.20, 4.50, 5.01, 6.21, 7.3.1 その2

2009年10月31日 03時29分57秒 | Weblog
以前も行った SDPA の比較実験だが、一応今でも全ての以下のバージョンのソースファイルをコンパイルすることはできる。しかし、SDPA 0.x と 1.x ではコンパイルに成功してバイナリが出来ても問題を解くことが出来ない。具体的には数値的に安定して内点法アルゴリズムを進めることが出来ないので、1反復内に Cholesky 分解のエラーが発生して停止する。修正する気になれば出来そうだが、そこまでする必要は無さそうなので。theta6.dat-s という問題だと SDPA 3.x から 5.x までほとんど性能に変化は無い。

SDPA 0.x ; 1995 年
SDPA 1.x ; 1995 年
SDPA 2.x ; 1996 年
SDPA 3.x ; 1997 年
SDPA 4.x ; 1998 年
SDPA 5.x ; 2000 年
SDPA 6.x ; 2002 年
SDPA 7.x ; 2008 年

○実行マシン:Intel Xeon 5550 (2.66GHz) x 2 : メモリ 72GB : Fedora 10 for x86_64
問題1: mcp500-1.dat-s
SDPA 2.01 ; 569.2s
SDPA 3.20 ; 126.8s
SDPA 4.50 ; 53.6s
SDPA 5.01 ; 23.8s
SDPA 6.21 ; 1.6s
SDPA 7.3.1 ; 1.5s

問題2: theta6.dat-s
SDPA 2.01 ; 2643.5s
SDPA 3.20 ; 216.3s
SDPA 4.50 ; 217.6s
SDPA 5.01 ; 212.0s
SDPA 6.21 ; 20.7s
SDPA 7.3.1 ; 14.2s
コメント
この記事をはてなブックマークに追加

オープンキャンパス

2009年10月30日 15時04分33秒 | Weblog
また来週(11月3日)にオープンキャンパス(研究室公開)が行われます。オープンキャンパスと言いますと普通は高校生対象ですが、理工系に興味があるもっと若い方々(中、小学生)も歓迎致します。単に大学の宣伝というわけではなくて、理工系人材の発掘と育成という役目もあります。写真はオープンキャンパスにおいて 1.435TFlops のクラスタ計算機上で単に GIMP で遊んでいる小学1年生。
コメント (2)
この記事をはてなブックマークに追加

クラスタ計算機からスパコン

2009年10月29日 04時17分29秒 | Weblog
開発やデバッグ等は中規模のクラスタ計算機で行って、大規模実証実験はスパコンで行うというのが良く言われる方法だが、実はあまり上手くいかない場合もある。簡単に言うとクラスタ計算機は自分達で管理するので何でもアリ(好きなソフトウェア環境を構築できる)だが、スパコンでは開発環境や実行環境は良くない場合が多い。

1: スパコンは良くも悪くもベンダー製なので、コンパイラや MPI などのソフトウェアに独自のベンダー製品がインストールされていて、バグが残っていたり性能が上がらないことが多い。通常はクラスタ計算機上で gcc や icc それに OpenMPI や MPICH2 などを使用しているが、そのままスパコンに開発したソフトウェアを移行してもコンパイルやパフォーマンスチューニングで苦労することが多い。デバッグやチューニングしている間に使用時間が終わってしまうということが起きる。

2: 複数のユーザが同時に使用しているので、実行に関して性能が上がらない、あるいは実行の再現性が無いということが起きる。スパコンの実行キューを見ていると1プロセスのジョブを大量に投入している人がいるが、スパコンの使い方としてはあまり勧められない。そのためにスパコン以外のアプリケーションサーバも用意されていることが多い。

というわけであまりスパコンに過度の期待を持たない方が良い。計算機センター関係者で様々な特権を持っていれば別だが、一般ユーザに出来ることは結構限定されている。やはり自分の所のクラスタ計算機の使い勝手が一番良い。

コメント (2)
この記事をはてなブックマークに追加

HyperThreading

2009年10月28日 08時00分20秒 | Weblog
Intel 新 Core i7(860, 870) では、メモリがトリプルチャンネルからデュアルチャンネルに移行しているが、実際の使用において性能低下は見られない。各種ベンチマーク結果から見ると新 Core i7 は結構お得な内容になっている。ところで TurboBoost はともかく、HyperThreading の方は SDPA などでは恩恵を受けることができない。むしろ機能を ON にした方が遅くなる。SDPA では L3 キャッシュの能力などで飽和しているので、その方が納得がいく。逆に ON にした方が性能が良くなるものを少し調べてみようと思う。
コメント (4)
この記事をはてなブックマークに追加

いろいろなアイデア

2009年10月27日 13時13分02秒 | Weblog
先日のご講演から最適化で使えそうなアイデアをいろいろと頂いた。

1: 文字列データの高速類似性解析と可視化技術

SDPA において計算順序の並び替えなどの前処理に応用できるかもしれない。キャッシュの有効利用やメモリアクセス回数の減少などのためにまともに順列系の最適化問題を解くのはさすがに無駄すぎる。そこで類似性解析を用いることが出来るか?

2: 最適制御法の思考型ゲームへの応用:名人を超える将棋プログラム作成への取り組み

将棋をマクロ的には一種の配置最適化問題として考えることができる。というわけなので、多数物の配置問題を少数物間の配置問題の目的(評価)関数の合成で評価して近似的に扱うこともできるかもしれない。メタ解法などには使えそうなアイデアである。
コメント
この記事をはてなブックマークに追加

Windows 7 64bit

2009年10月26日 12時36分35秒 | Weblog
これは何でしょうとか中学入試に出るかもしれない。
[1] → [2] → 3 → 95 → 98 → 2000 → (Me) → XP → (Vista) → 7
括弧[]が付いているのは、ヘビーユーザーを見付けるのがかなり困難なもので、括弧()は M 社自身が忘れたいと思っているもの(おそらく)である。[1]はシングルタスクの OS 上で、(疑似)マルチタスクを実現して、GUI 付、マルチウィンドウ(タイル型)、それに従来のソフトも動作させた上に全体で使えるメモリは 640Kbytes 以内ということだったので、当時困難なプログラムを書いていたプログラマは、世の中にはもっとやばい仕事があるのだと随分と勇気づけられた。
Windows 7 Professional 64bit インストール版と Windows 7 Ultimate 64bit DSP 版 を購入した。OS の機能自体は良いと思うが、何しろ見掛けは Vista そっくりなので過去の苦しい思い出が思い起こされる。互換性の問題があっても今更 32bit 版を使うのは気が進まないので、これからは Windows でも全て 64bit にしていく。
コメント
この記事をはてなブックマークに追加

第3回 の SCOPE 研究会

2009年10月25日 08時03分55秒 | Weblog
10月24日の SCOPE 研究会ですが、大変盛況で二つのご講演の評判も大変良かったと思います。最適化関連と新分野への展開が期待できる内容ですので、まさに”計算と最適化の新展開”という目標に合致していました。来なかった人はともかく来れなかった人には大変な損であったと思います。聴衆の反応というのも重要なので他所で同じ講演をしていただいても今回の SCOPE とは異なった雰囲気になるかもしれません。
コメント
この記事をはてなブックマークに追加

CentOS 5.4

2009年10月24日 13時20分25秒 | Weblog
Linux の CentOS のバージョンが 5.4 に上がった。CentOS (というよりも RHEL) がマイナーバージョンアップするときには傾向があって、しばらく update ファイルが無ければ(つまり yum update で更新無し)、その後で大量の update(つまりマイナーバージョンアップ)になる。CentOS は Fedora ほど頻繁には更新されないが、それでもしばらく更新無しが続けば何かあると思った方が良い。数えたら研究室には全部で 24 台の CentOS 搭載のマシンがあった。しかし、5.4 になっても kernel は 2.6.18, gcc は 4.1.2 のままに据え置きである。割りと安定指向で保守的な Vine Linux でもカーネルは 2.6.31 になっている。
コメント (4)
この記事をはてなブックマークに追加

RAID 5 でも壊れた

2009年10月23日 22時28分13秒 | Weblog
laqua サーバは RAID 5 で HDD 4台構成(HDD 0 から 3)になっているが、HDD 0 が壊れたので OS が起動しなくなった。そこで HDD 0 の交換を行ったが、RAID 5 を再構成してもディスクの状態は元には戻らず、結局 OS の再インストールとなった。何があったのか良くわからないが、RAID 5 は 1 台壊れても復元できると思っていたのに大損害を受けてしまった。SDPA Online Solver の laqua.indsys.chuo-u.ac.jp の方の復旧予定日は未定。
コメント (2)
この記事をはてなブックマークに追加

SDPA 7.3.1 と GotoBLAS 1 と 2 : その3

2009年10月22日 13時05分49秒 | Weblog
最後は F1 式が複数登場するという大変厄介な問題を扱う(まれにしか見られないが)。

計算機
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB
OS : Fedora 11 for x86_64

問題1: theta6.dat-s
○GotoBLAS 1.34 : 32.59s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 28.254926, 86.689105
Make bF1 time = 18.670187, 57.282111
Make bF2 time = 0.308177, 0.945520
Cholesky bMat = 3.094509, 9.494281
makedX = 0.037847, 0.116119
symmetriseDx = 0.002594, 0.007959
makedXdZ = 0.233238, 0.715599
xMatTime = 0.014437, 0.044294
zMatTime = 0.016453, 0.050480
Main Loop = 32.593399, 100.000000

○GotoBLAS2 1.06 : 65.64s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 63.443991, 96.648102
Make bF1 time = 56.535994, 86.124728
Make bF2 time = 0.997443, 1.519466
Make bF3 time = 6.825352, 10.397475
Cholesky bMat = 1.283635, 1.955439
makedX = 0.023401, 0.035648
symmetriseDx = 0.002569, 0.003914
makedXdZ = 0.216320, 0.329533
xMatTime = 0.017046, 0.025967
zMatTime = 0.017768, 0.027067
Main Loop = 65.644322, 100.000000

この場合では実行時間に約2倍もの差が付いてしまった。SDPA のソースは全く同じなのでリンクする GotoBLAS のバージョンが異なるのみである。いろいろと改善案があるのだが、簡単に実現できるものでは効果はイマイチ低い。
コメント (2)
この記事をはてなブックマークに追加

SDPA 7.3.1 と GotoBLAS 1 と 2 : その2

2009年10月21日 12時45分26秒 | Weblog
今度は別の問題(F3 式の計算がボトルネックとなる問題)を用いてみる。これでスレッド競合?の問題がより深刻になってくるはずだ。

計算機
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB
OS : Fedora 11 for x86_64

問題1: theta6.dat-s
○GotoBLAS 1.34 : 13.68s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 4.031290, 29.452967
Make bF2 time = 0.029927, 0.218649
Make bF3 time = 11.391436, 83.226854
Cholesky bMat = 8.423746, 61.544645
makedX = 0.094700, 0.691887
symmetriseDx = 0.004541, 0.033177
makedXdZ = 0.116215, 0.849077
xMatTime = 0.028065, 0.205045
zMatTime = 0.041598, 0.303919
Main Loop = 13.687212, 100.000000

○GotoBLAS2 1.06 : 19.29s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 10.960035, 56.799159
Make bF2 time = 0.131228, 0.680074
Make bF3 time = 10.320384, 53.484239
Cholesky bMat = 7.316893, 37.918982
makedX = 0.077818, 0.403283
symmetriseDx = 0.004536, 0.023507
makedXdZ = 0.098682, 0.511408
xMatTime = 0.028489, 0.147641
zMatTime = 0.040801, 0.211447
Main Loop = 19.296122, 100.000000

makedX や Cholesky bMat などは GotoBLAS2 1.06 の方が減少しているが、やはり Make bMat の部分の実行時間が大きく増大してしまう。ちなみに SDPA 7.3.2β と GotoBLAS2 1.06 の組合せは以下の通り。まだまだ性能を上げていけそうな感じである。

○ SDPA 7.3.2β + GotoBLAS2 1.06 : 11.88s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 3.543514, 29.826474
Make bF2 time = 0.001390, 0.011700
Make bF3 time = 8.216612, 69.160886
Cholesky bMat = 7.313807, 61.561793
makedX = 0.077734, 0.654303
symmetriseDx = 0.004556, 0.038349
makedXdZ = 0.098493, 0.829036
xMatTime = 0.028260, 0.237870
zMatTime = 0.040589, 0.341646
Main Loop = 11.880432, 100.000000
コメント
この記事をはてなブックマークに追加

SDPA 7.3.1 と GotoBLAS 1 と 2 : その1

2009年10月20日 11時50分29秒 | Weblog
SDPA 7.3.1 と GotoBLAS 1.34, GotoBLAS2 1.06 の組合せについて少し実験を行った。

計算機
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB
OS : Fedora 11 for x86_64

問題1: mcp2000-10.dat-s
○GotoBLAS 1.34 : 46.21s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 3.372745, 7.298230
Make bF3 time = 1.377120, 2.979929
Cholesky bMat = 2.300575, 4.978178
makedX = 14.032249, 30.364165
symmetriseDx = 1.323849, 2.864656
makedXdZ = 15.919398, 34.447737
xMatTime = 2.953929, 6.391961
zMatTime = 4.833561, 10.459267
Main Loop = 46.213189, 100.000000

○GotoBLAS2 1.06 : 43.83s

Time(sec) Ratio(% : MainLoop)
Make bMat time = 6.758184, 15.465595
Make bF3 time = 4.523686, 10.352115
Cholesky bMat = 0.763858, 1.748031
makedX = 13.860057, 31.717696
symmetriseDx = 1.312581, 3.003743
makedXdZ = 15.674731, 35.870441
xMatTime = 2.872068, 6.572511
zMatTime = 4.725387, 10.813692
Main Loop = 43.698183, 100.000000

GotoBLAS2 1.06 の方が、makedX, Cholesky bMat などが減少していることから、BLAS 自体は高速化しているようだが、bF3 式のマルチスレッド部分の時間は反対に増加している。SDPA 7.3.1 の pthread を用いた独自の Schur complement 行列計算のマルチスレッド化の部分と GotoBLAS2 との相性があまり良くない。SDPA 7.3.2 以降ではこの部分も改善できる見込みになっている。
コメント
この記事をはてなブックマークに追加

メタ戦略アルゴリズム その2

2009年10月19日 00時53分22秒 | Weblog
SDPA からも BLAS Level 1 の関数を呼び出していて、その Level 1 の関数の性能はメモリのバンド幅に律速されていることを確認している。メタ戦略アルゴリズムは CPU の計算能力に律速されるということは考えにくいが、意外とデータの局所参照性もあるようなのでメモリバンド幅に律速される現象もこれまで確認できていない。以下の結果は最大クリーク問題(最大安定集合問題)に対する Tabu Search アルゴリズムの結果になる。相変わらず性能的には Intel > AMD になるが、それ以外にもクロック周波数にも比例する傾向があるので、演算以外の CPU 内の処理(比較等)に律速されている可能性もある。この辺は詳細に調べるといろいろと傾向がわかって面白いだろう。

問題 A : keller6.clq.b
問題 B : MANN_a45.clq.b

マシン1
CPU : AMD Opteron 2435(2.6GHz / 6MB L3)x 2
Memory : 64GB
問題 A : 31.90s
問題 B : 633.81s

マシン2
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB
問題 A : 24.98s
問題 B : 443.54s

マシン3
CPU : AMD Opteron 2384 (2.7GHz / 6MB L3) x 2
Memory : 32GB
問題 A : 30.09s
問題 B : 589.86s

マシン4
CPU : Intel Xeon 5460 (3.16GHz / 6MB L2 x 2) x 2
Memory : 64GB
問題 A : 22.57s
問題 B : 389.88s
コメント
この記事をはてなブックマークに追加

第3回 の SCOPE 研究会のお知らせ(再送)

2009年10月18日 20時31分47秒 | Weblog
次の土曜日に第3回の SCOPE 研究会を行います。期日が迫ってきたので再送します。
この SCOPE 研究会では ORや最適化だけでなく様々な分野から講師の先生をお呼びしておりますが、実際にはこの世界(敢えてどの世界とは言いませんが)の方々は自分の研究分野以外には興味が無い人が多いようです。分野を越えて新しいこと、面白いことを行ってみたいという方が少ないように見えますので、この分野の将来が心配されます。

---------------------------------------------------------------------------

次回(第3回)の SCOPE 研究会は以下の日時、内容で行う予定です。今回は検索技術、データベースそれに学習や将棋など非常に興味深い内容ですので、皆様の参加をお待ちしております。

日 時 : 2009年10月24日(土)14:00~
会 場 : 中央大学 後楽園キャンパス 6号館4階 6418号室(前回とは部屋が変わります)

講演者
1: 宇野毅明氏 (国立情報学研究所情報学プリンシプル研究系)

文字列データの高速類似性解析と可視化技術

近年の検索技術の発達により、ゲノムのような巨大な文字列データベースにおいても、ある程度の曖昧性を許容する検索が短時間で可能となっている。しかし、文章データの中から類似する物を見つける、ゲノムとゲノムを比較して、部分的に類似する領域を見つける、といったような巨大な問題の場合、多くの検索が必要となるために莫大な計算時間が必要となる。本講演では、巨大な文字列データから類似する部分文字列の組を高速で発見する、複数分類法という新しい手法と、類似する領域を可視化する方法をの紹介する。また、ランダムプロジェクションの利用により、ベクトルデータの類似性の検出に使えることも示す。

2: 保木邦仁氏(東北大学大学院理学研究科)

最適制御法の思考型ゲームへの応用:名人を超える将棋プログラム作成への取り組み

将棋や囲碁のようなゲームは人工知能研究の基本的なモデルで、人知を超えるコンピュータの作成は計算科学における大きな目標の一つです。特に、チェスを指すプログラムは1960年代のコンピュータ技術黎明期から真剣に研究されています。本研究では優劣の判断がより難しい将棋の思考アルゴリズムを最適制御法の枠組みに沿って設計する手法を開発しました。これは、チェスやその変種のゲームとしては"実用に耐え、役に立つ"初めての機械学習の手法です。
コメント
この記事をはてなブックマークに追加

laqua 故障

2009年10月17日 05時16分18秒 | Weblog
SDPA Online Solver の第二サーバである laqua.indsys.chuo-u.ac.jp (Dell PowerEdege 2970) に異常が発生したために停止させました。おそらく RAID コントローラーかマザーボードの異常だと思われます(またか!)。現在別のマシンを laqua.indsys.chuo-u.ac.jp として運用していますが、このマシン上での SDPA Online Solver の復旧には時間がかかりそうです。
コメント
この記事をはてなブックマークに追加