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

以前も行った SDPA の比較実験だが、一応今でも全ての以下のバージョンのソースファイルをコンパイルすることはできる。しかし、SDPA 0.x と 1.x ではコンパイルに成功してバイナリが出来ても問題を解くことが出来ない。具体的には数値的に安定して内点法アルゴリズムを進めることが出来ないので、１反復内に 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
問題１： 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

問題２: 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

オープンキャンパス

また来週（11月3日）にオープンキャンパス（研究室公開）が行われます。オープンキャンパスと言いますと普通は高校生対象ですが、理工系に興味があるもっと若い方々（中、小学生）も歓迎致します。単に大学の宣伝というわけではなくて、理工系人材の発掘と育成という役目もあります。写真はオープンキャンパスにおいて 1.435TFlops のクラスタ計算機上で単に GIMP で遊んでいる小学1年生。

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

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

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

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

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

HyperThreading

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

いろいろなアイデア

先日のご講演から最適化で使えそうなアイデアをいろいろと頂いた。

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

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

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

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

Windows 7 64bit

これは何でしょうとか中学入試に出るかもしれない。
[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 にしていく。

第３回 の SCOPE 研究会

10月24日の SCOPE 研究会ですが、大変盛況で二つのご講演の評判も大変良かったと思います。最適化関連と新分野への展開が期待できる内容ですので、まさに”計算と最適化の新展開”という目標に合致していました。来なかった人はともかく来れなかった人には大変な損であったと思います。聴衆の反応というのも重要なので他所で同じ講演をしていただいても今回の SCOPE とは異なった雰囲気になるかもしれません。

CentOS 5.4

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 になっている。

RAID 5 でも壊れた

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 の方の復旧予定日は未定。

SDPA 7.3.1 と GotoBLAS 1 と 2 : その３

最後は F1 式が複数登場するという大変厄介な問題を扱う(まれにしか見られないが)。

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

問題１: 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

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

SDPA 7.3.1 と GotoBLAS 1 と 2 : その２

今度は別の問題(F3 式の計算がボトルネックとなる問題)を用いてみる。これでスレッド競合？の問題がより深刻になってくるはずだ。

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

問題１: 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 : その１

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

問題１: 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 以降ではこの部分も改善できる見込みになっている。

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

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

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

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

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

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

マシン４
CPU : Intel Xeon 5460 (3.16GHz / 6MB L2 x 2) x 2
Memory : 64GB
問題 A : 22.57s
問題 B : 389.88s

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

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

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

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

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

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

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

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

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

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

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

laqua 故障

SDPA Online Solver の第二サーバである laqua.indsys.chuo-u.ac.jp (Dell PowerEdege 2970) に異常が発生したために停止させました。おそらく RAID コントローラーかマザーボードの異常だと思われます（またか！）。現在別のマシンを laqua.indsys.chuo-u.ac.jp として運用していますが、このマシン上での SDPA Online Solver の復旧には時間がかかりそうです。