SDPARA + マルチスレッド その３

前回に引き続いて SDPARA の特性を見る実験を行った。最近では意外と 16 CPU, 8 スレッドでの実行が良いような気がしてきた。

20709 (mDIM)
22 (nBlock)
13 13 13 13 78 78 169 78 78 169 338 169 169 286 1014 1014 286 3211 3211 1014 1014 -374 (BlockStruct)

○ソルバー SDPARA 7.2.1.rev8 + GotoBLAS 1.31 + MUMPS 4.8.4 + LAPACK 3.2.1

1: 16 CPU x 8 スレッド(OMP_NUM_THREADS=8) ; 32460.84s(34反復)
2: 32 CPU x 4 スレッド(OMP_NUM_THREADS=4) ; 33021.99s(32反復)
3: 64 CPU x 2 スレッド(OMP_NUM_THREADS=2) ; 37034.22s(33反復)
4: 128 CPU x 1 スレッド(OMP_NUM_THREADS=1) ; 38472.63s(32反復)

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.2 for x86_64
Linpack : R_max = 1.435TFlops, R_peak = 1.618TFlops, R_max / R_peak = 88.69%

非負制約と並列計算

現在 finance 関係で巨大な SDP などを解いているのだが以下の印象を受けた。

1: 半正定値制約 と 半正定値制約 + 非負制約 では後者の方がはるかに強力（緩和の性能が良い）。ただし、現在の仕組みでは後者の場合では非常に SDP のサイズが大きくなる。数値精度も悪くなる傾向がある。

2: 特に半正定値制約 + 非負制約の場合では並列計算(SDPARA や SDPA マルチスレッド)が有効。自分達で作った環境とはいえ感動的な速さになる。

ライブラリのバージョンアップ

SDPA (SDPARA) 7.2.x 以上では、外部ライブラリとして LAPACK, BLAS, MUMPS を利用している。この中で LAPACK は最近バージョンアップして 3.2.1 に、MUMPS も 4.8.4 になった。例えば以下のような組み合わせで比較しても特に性能差は見られない。

1: SDPA 7.3.1β + GotoBLAS 1.31 + LAPACK 3.1.1 + MUMPS 4.8.3
2: SDPA 7.3.1β + GotoBLAS 1.31 + LAPACK 3.2.1 + MUMPS 4.8.4

それでも今後は新しいライブラリに変更していくことにする。

SDPARA + マルチスレッド その２

QAP(二次割当問題)に対する SDP 緩和(半正定値制約 + 非負制約)問題で非常に大きなものがある。

80621 (mDIM)
2 (nBlock)
400 -80200 (BlockStruct)

非負制約を等式標準形に変換するために大量のスラック変数を導入している。そのために制約式の数は大変多めに(80621個)なっている。SDPARA 7.2.1.rev8 でこの問題を解いてみると以下のようになった。

○ソルバー SDPARA 7.2.1.rev8 + GotoBLAS 1.31 + MUMPS 4.8.3

1: 32 CPU x 4 スレッド(OMP_NUM_THREADS=4) ; 11509.28s
2: 64 CPU x 1 スレッド(OMP_NUM_THREADS=1) ; 15062.96s
3: 64 CPU x 2 スレッド(OMP_NUM_THREADS=2) ; 11085.31s
4: 128 CPU x 1 スレッド(OMP_NUM_THREADS=1) ; 11924.64s

全コアに１ずつプロセスを割り当てるよりも適当にマルチスレッド化(Schur complement, GotoBLAS など)した方が速くなっているので一応成功した形になっている。

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.2 for x86_64
Linpack : R_max = 1.435TFlops, R_peak = 1.618TFlops, R_max / R_peak = 88.69%

SCOPE つくば合宿 一般講演募集中

SCOPE つくば合宿では一般講演者を募集しています。〆切は５月８日ですが、すでに申込をされた分については情報をホームページに掲載しています。

http://www.indsys.chuo-u.ac.jp/~jgoto/SCOPE/mirai09.html

幾つか質問がありましたが、一般講演の対象は大学院修士課程、博士課程、各種ポスドク、助教または元大学院生の社会人の方などになっております。また初日（３０日）もおそらく午前中から開始しますので、特に遠方の方は２９日から宿泊された方が便利です。３０日の夜には懇親会がありますが、おそらく２９日の夜にも前夜祭があります。

Apollo Domain

1988 年ごろにちらっと雑誌で見たのは世の中に 64bit のコンピュータがあるらしいということだった。当時に所有していたのはまだ 8bit 機だったし、ハイエンドでようやく 32bit パソコン(Intel 386)が登場し始めたころだったので、すごいと言うか実感が湧かなかった。何かの雑誌に Apollo Domain シリーズの DN10000 が掲載されていて、スペックは当時としては驚異の 144MIPS, 128Mbytes メモリ, 3Gbytes HDD となっていた(当時は 1 MIPS, 640Kbytes メモリ, HDD 無しぐらいが標準だったので)。こちらのページにはいまだに写真やカタログが保存されている。後に大学に入ってから聞いた話では値段も信じられないほど高かったらしい。残念ながら研究室にあった Apollo は壊れていたので使用したことはないが、NEXT computer, SONY NEWS, SUN Sparc Station などの WS を使うことができた。

SDPA 7.3.1β と theta6.dat-s その３

以下の三つのマシンについて 4 スレッドで実行したときの結果を示す。やはり Nehalem は速いし、マシン３は４スレッドを８スレッドにしても F3 式の計算はほとんど速くならない。

○実行マシン１：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64
○実行マシン２：Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン３：Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64

○マシン１ (8スレッド:OMP_NUM_THREADS=4)
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 25.109s

F3式の計算 : 10.06 秒
Cholesky 分解 : 14.75 秒

○マシン２ (4スレッド:OMP_NUM_THREADS=4)
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.379s

F3式の計算 : 2.49 秒
Cholesky 分解 : 11.36 秒

○マシン３ (8スレッド:OMP_NUM_THREADS=4)
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 23.275s

F3式の計算 : 13.76 秒
Cholesky 分解 : 12.30 秒

SDPA 7.3.1β と theta6.dat-s その２

三つのマシンでほぼ同じ実行時間になったのだが、その内訳を見てみよう。数値は複数スレッドの実行時間の合計になる。マシン２だけ 4 スレッドなので Cholesky 分解が遅いのは仕方がないところだが、F3 式の計算は非常に速い。

○実行マシン１：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64
○実行マシン２：Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン３：Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64

○マシン１ (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.579s

F3式の計算 : 4.65 秒
Cholesky 分解 : 8.13 秒

○マシン２ (4スレッド:OMP_NUM_THREADS=4)
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.379s

F3式の計算 : 2.49 秒
Cholesky 分解 : 11.36 秒

○マシン３ (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.353s

F3式の計算 : 13.03 秒
Cholesky 分解 : 7.56 秒

SDPA 7.3.1β と theta6.dat-s その１

何回かこのブログでも扱ってきた SDPLIB に収録されている theta6.dat-s (lovash 数) だが、最新のマシンと最新とソフトウェアでは以下のような結果になった。何故か皆同じくらいの実行時間になっているのだが、内訳はかなり異なる。Intel Nehalem-EP 8 コアだと頭一つ抜け出ることが出来るだろうか。

○実行マシン１：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64
○実行マシン２：Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン３：Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64

○マシン１ (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 16.224s
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.579s

○マシン２ (4スレッド:OMP_NUM_THREADS=4)
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 15.743s
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.379s

○マシン３ (8スレッド:OMP_NUM_THREADS=8)
SDPA 7.3.0 + GotoBLAS 1.30b9 + MUMPS 4.8.3 ; 15.981s
SDPA 7.3.1β + GotoBLAS 1.31 + MUMPS 4.8.3 ; 15.353s

Nehalem-EP と Mac その２

Mac Pro で Intel Xeon (Nehalem-EP)が選択できるようになっている。

http://store.apple.com/jp/browse/home/shop_mac/family/mac_pro?mco=MTE2NjQ

CPU を X5550 (2.66GHz) 2個、メモリ 32GB, HDD RAID 5 (1TB x 3) などの仕様にすると 120 万円以上になる。某社だと X5550 (2.66GHz) 2個、メモリ 72GB, HDD RAID 5 (1TB x 3) でも 100 万円以下だったりする。いろいろなキャンペーン等あるのだが、どのくらいが適正価格なのかがわからない。

半正定値制約 + 非負制約 その２

X succeq O と X ge O の両方の制約を入れて KKT 条件から線形方程式系を作ろうすると非常に複雑でサイズの大きな線形方程式になりそうだ。その場合には通常の方法（非負条件 → スラック変数 → 等式標準形)
から生成される線形方程式系よりも同程度あるいはより複雑になるかもしれないので、どちらが得になるかはさらに検討が必要になる。X succeq O と X ge O を個別に考慮して探索方向を二つ作り、何らかの形で線形結合して探索方向を近似的に生成する方法もあるかもしれない。

SDPAのホームページ

SDPA のホームページは以下の二つを運用していたのだが、mac.com のサービスが近日中に停止するそうなので、とりあえずは以下の２のホームページのみの運用を行うことにする。またもう１箇所サーバ上に設置することになるかもしれない。

1: http://homepage.mac.com/klabtitech/sdpa-homepage/index.html

2: http://sdpa.indsys.chuo-u.ac.jp/sdpa/

SCOPE in つくば 2009 : 特別セッションについて

SCOPE つくば合宿の特別セッション（チュートリアル）ですが、４名の講師の先生方が決定しました。いずれもそれぞれの分野の第一線でご活躍の先生です。講演では”主観性”も重視して、今後の流行や展開についても予想していただくことになります。

講演される内容は以下の通りです。４名を２日に分けて１日に２名ずつ講演をお願いする予定です。

１：松井知己先生(中央大学) : 組合せ最適化
２：今堀慎治先生(東京大学) : メタ戦略アルゴリズム、近似解法
３：久保幹雄先生(東京海洋大学) : サプライ・チェイン最適化
４：矢部　博先生(東京理科大学) : 非線形(連続)最適化

# 日時：2009年5月30日（土）～5月31日（日）
# 会場：筑波大学総合研究B棟 1階 0110公開講義室

SCOPE つくば合宿ホームページ
http://www.indsys.chuo-u.ac.jp/~jgoto/SCOPE/mirai09.html

SCOPE つくば合宿 ホームページ

5月30,31日に筑波大学で開催される SCOPE つくば合宿のホームページ がオープンしました。
１：特別セッション
２：一般講演
３：宿泊
４：旅費補助
などの情報が記載されています。一般講演の申込を予定している方や宿泊施設を申し込まれる方は早めにご確認下さい。

半正定値制約 + 非負制約

扱う最適化問題によっては "completely positive matrix 錐"と"半正定値行列錐 + 非負対称行列錐" の集合の大きさがかなり近くなるらしい（もちろん後者の方が大きいが)。現在の主双対内点法アルゴリズムでは、半正定値制約というのは自動的に考慮されるのだが、対称行列の非負制約は直接考慮されないので、スラック変数等を用いて等式標準形に変換する必要がある。
そこで現在のアルゴリズムを少し変更して非負制約も実行終了時に満たされるようにすれば、上記のような最適化問題に対して、かなり高速に"半正定値制約 + 非負制約"を用いた緩和問題が解けるようになる。予想（ほとんど思い付きだが）では、以下の 1 と 2 はほぼ同じくらいのメモリ量で解くことができる。１反復自体の実行時間は１の場合でもそれほど悪化しないと思われる。

1:半正定値制約 + 非負制約
2:半正定値制約

副作用としては、以下のようなものが考えられる。

１：各反復で十分な大きさのステップサイズが取れない（最悪途中で動けなくなってしまう）
２：双対ギャップが発生してしまう(Y ge 0 の制約のために XY を十分 0 に
近づけることができない）

理論的には難しいところもあるが、現在のソフトウェアで用いているアルゴリズムも元の理論とは大きく異なっていることを考えると意外と上手くいきそうな気もする。非負制約を内部に組み入れても、スラック変数を用いて等式標準形に変換しても数学的には等価なはずなので（最適解という意味では）、その辺の違いがどうなるかは興味があるところだ。