サーバ群

AMD Opteron (Shanghai 2384 2.7GHz)のサーバが二台納入されたので、Online Solver 用の外部向けサーバや計算サーバの一部を交代させることにした。現在でも最適化問題の規模と計算量が爆発的に増大しているので、多少計算サーバを増強しても焼け石に水的な感はあるが、それでも中小規模の問題では効果は非常に大きい。この AMD Shangahi マシンだが、以下のように性能を測定してみると、メモリバンド幅も大きく、高負荷（マルチスレッド）時の性能では Penryn 系 Xeon に匹敵する(
Nehalem には負ける）。

stream 8 スレッド
Function Rate (MB/s) Avg time Min time Max time
Copy: 21536.8626 0.0015 0.0015 0.0015
Scale: 21519.5972 0.0015 0.0015 0.0015
Add: 21420.0013 0.0023 0.0022 0.0023
Triad: 21212.3688 0.0023 0.0023 0.0023

1: Shanghai (AMD Opteron 2384 : 問題 theta6.dat-s)
SDPA 7.2.0 (１スレッド : GotoBLAS)
1m20.945s (18反復)
SDPA 7.2.0 (４スレッド : GotoBLAS)
41.415s (18反復)
SDPA 7.2.0 (８スレッド : GotoBLAS)
36.715s (18反復)
SDPA 7.x 開発版　(４スレッド: Pthread + GotoBLAS)
24.793s (18反復)
SDPA 7.x 開発版　(８スレッド: Pthread + GotoBLAS)
14.811s (18反復)

CSDP 6.0.1 (１スレッド : OpenMP + GotoBLAS)
1m15.116s(17反復)
CSDP 6.0.1 (４スレッド : OpenMP + GotoBLAS)
25.776s (17反復)
CSDP 6.0.1 (８スレッド : OpenMP + GotoBLAS)
18.217s (17反復)

SDPA, CSDP, Nehalem, Penryn

通常の SDPA は本体はマルチスレッド化されておらずに、SDPA から呼び出す BLAS がマルチスレッドで動作するようになっているが、Schur complement 行列の作成部分を pthread でマルチスレッド化した開発版がある。一方 CSDP だと BLAS だけでなく、本体も OpenMP でマルチスレッド化されているらしい（ソースは見ていないが）。SDPA 7.x 開発版は Nehalem 上では非常に性能が良い。現在の pthread による並列化は広いメモリバンド幅を要求するので、Nehalem の広いバンド幅が効を奏しているのではないだろうか。

1: Penryn (Intel Xeon 5460 : 問題 theta6.dat-s)
SDPA 7.2.0 (１スレッド : GotoBLAS)
1m1.036s (18反復)
SDPA 7.2.0 (４スレッド : GotoBLAS)
28.564s (18反復)
SDPA 7.x 開発版　(４スレッド: Pthread + GotoBLAS)
24.035s (18反復)

CSDP 6.0.1 (１スレッド : OpenMP + GotoBLAS)
56.696s (17反復)
CSDP 6.0.1 (４スレッド : OpenMP + GotoBLAS)
20.324s (17反復)


2: Nehalem (Intel Core i7 965 : 問題 theta6.dat-s)
SDPA 7.2.0 (１スレッド : GotoBLAS)
55.515s (18反復)
SDPA 7.2.0 (４スレッド : GotoBLAS)
24.402s (18反復)
SDPA 7.x 開発版　(４スレッド: Pthread + GotoBLAS)
17.096s (18反復)

CSDP 6.0.1 (１スレッド : OpenMP + GotoBLAS)
51.939s (17反復)
CSDP 6.0.1 (４スレッド : OpenMP + GotoBLAS)
24.318s(17反復)

SDPA Online Solver とクラウドコンピューティング

クラウドコンピューティングの技術を用いて最短路問題に対する大量のクエリを処理する構想を持っているが（開発の方も進んでいる）、SDPA Online Solver の方でも計算サーバとしてクラウドが使えるのではないか、あるいは現在のシステムよりもクラウドの方が向いているのではないかと思い始めた。現時点ではお金を払ってまで SDP を解く人はいないようだが、大学の計算機センターのスパコン等を借りて SDP を実験する人もいるので、クラウドのように元手がかからなければ無理な構想でもない。SDP 以外の他の最適化ソフトウェアでも同じようなサービスを考えることも出来そうだ。

stream によるバンド幅測定 その２

CPU が Dual Core AMD Opteron(tm) Processor 270 のマシンがあって、2005 年製と今では古い型になっている。結果から言うと購入してもあまり役に立たなかった（計算速度が遅いので）。それでもメモリのバンド幅の値は Penryn 系の Xeon (X5460) よりも大きい。

1: Opteron : Dual Core AMD Opteron(tm) Processor 270 2.0GHz
Function Rate (MB/s) Avg time Min time Max time
Copy: 8726.2030 0.0037 0.0037 0.0037
Scale: 8724.5013 0.0037 0.0037 0.0037
Add: 8678.2444 0.0056 0.0055 0.0056
Triad: 8593.0510 0.0056 0.0056 0.0057

このマシン上で SDPA の性能はイマイチだったが、このメモリバンド幅の広さを活用したアプリケーションがあったのだろう。ちなみに Intel 初の 64bit Xeon (nocona コア)だと以下のようにバンド幅の値は低いが、SDPA の性能はこちらのマシン上での方が上である。

2: Xeon : nocona コア 2.8GHz
Function Rate (MB/s) Avg time Min time Max time
Copy: 2870.7832 0.0112 0.0111 0.0113
Scale: 2902.7581 0.0111 0.0110 0.0113
Add: 3234.0582 0.0149 0.0148 0.0149
Triad: 3098.3332 0.0155 0.0155 0.0156

最後は Cell (PS3) マシンを用いる。メモリバンド幅のカタログスペックは 25.6GB/s だが、PPE だけだとメモリバンド幅が使い切れないのだろうか。

3: Cell : Cell BE 3.2GHz
Function Rate (MB/s) Avg time Min time Max time
Copy: 2763.3305 0.0118 0.0116 0.0121
Scale: 2453.0335 0.0131 0.0130 0.0132
Add: 3289.9190 0.0147 0.0146 0.0149
Triad: 3249.1945 0.0152 0.0148 0.0180

stream によるバンド幅測定

STREAM というメモリのバンド幅を測定するプログラムを用いて、幾つかの手持ちのマシンでバンド幅を測定してみた。とにかく Nehalem (特に 965 3.2GHz) のバンド幅が大きいことがわかる。Barcelona のバンド幅も大きい。反対に Harpertown ではメモリバンド幅の値がかなり小さくなっている。それでも SDPA などは Harpertown では　Barcelona よりも高速である。メモリバンド幅だけで性能が決まらないという好例であろう。

1: Penryn : Intel Core 2 E8200 2.66GHz : メモリ 4GB
Function Rate (MB/s) Avg time Min time Max time
Copy: 7101.8428 0.0045 0.0045 0.0046
Scale: 7130.1385 0.0045 0.0045 0.0045
Add: 7370.8205 0.0066 0.0065 0.0066
Triad: 7417.8030 0.0065 0.0065 0.0066

2: Phenom : AMD Phenom 9950 BE 2.6GHz : メモリ 8GB(DDR2-1066)
Function Rate (MB/s) Avg time Min time Max time
Copy: 9714.6589 0.0033 0.0033 0.0033
Scale: 9624.1021 0.0033 0.0033 0.0034
Add: 9619.0441 0.0050 0.0050 0.0051
Triad: 9621.3425 0.0050 0.0050 0.0050

3: Nehalem : Intel Core i7 940 2.93GHz : メモリ 6GB(DDR3-1600) 19.2GB/s
Function Rate (MB/s) Avg time Min time Max time
Copy: 19499.8878 0.0016 0.0016 0.0017
Scale: 19533.9438 0.0017 0.0016 0.0017
Add: 18677.6688 0.0026 0.0026 0.0026
Triad: 18903.9054 0.0026 0.0025 0.0026

4: Nehalem : Intel Core i7 965 3.2GHz : メモリ 12GB(DDR3-1600) 25.6GB/s
Function Rate (MB/s) Avg time Min time Max time
Copy: 23021.9087 0.0014 0.0014 0.0014
Scale: 23057.5035 0.0014 0.0014 0.0014
Add: 21543.7766 0.0022 0.0022 0.0022
Triad: 22007.7167 0.0022 0.0022 0.0022

5: Atom : Intel Atom 330 1.6GHz : メモリ 2GB
Function Rate (MB/s) Avg time Min time Max time
Copy: 2911.1949 0.0110 0.0110 0.0111
Scale: 2875.0879 0.0112 0.0111 0.0114
Add: 2873.5490 0.0168 0.0167 0.0169
Triad: 2905.9004 0.0167 0.0165 0.0168

6: Barcelona : AMD Opteron 2356 2.3GHz : メモリ 32GB
Function Rate (MB/s) Avg time Min time Max time
Copy: 17076.0468 0.0019 0.0019 0.0019
Scale: 16923.1784 0.0019 0.0019 0.0019
Add: 17266.4316 0.0028 0.0028 0.0028
Triad: 16979.5557 0.0028 0.0028 0.0029

7: Harpertown : Intel Xeon X5460 3.16GHz : メモリ 48GB
Function Rate (MB/s) Avg time Min time Max time
Copy: 6145.5004 0.0052 0.0052 0.0053
Scale: 6146.6261 0.0052 0.0052 0.0052
Add: 6290.0800 0.0076 0.0076 0.0076
Triad: 6588.9901 0.0073 0.0073 0.0073

Tesla C1060

Intel Core i7 のマシンに NVIDIA Tesla C1060 を搭載してみた。ちょっと古い Intel Core2 のマシンに GeForce 8800 GTX が搭載してあるので、CUDA の bandwithTest で結果を比較してみよう。ホストのメモリから GPU 側のメモリ間のバンド幅は確実に上がっているが（マザーボードもチップセットの違うので）、GPU デバイス上でのメモリバンド幅は GeForce 8800 GTX でも Tesla C1060 でもあまり変わらない。

1: GeForce 8800 GTX
CPU : Intel Core2 E8200 2.66GHz
メモリ : 4GB
OS : CentOS 5.2 for X86_64

./bandwidthTest
Quick Mode
Host to Device Bandwidth for Pageable memory
.
Transfer Size (Bytes) Bandwidth(MB/s)
33554432 2434.6

Quick Mode
Device to Host Bandwidth for Pageable memory
.
Transfer Size (Bytes) Bandwidth(MB/s)
33554432 2256.4

Quick Mode
Device to Device Bandwidth
.
Transfer Size (Bytes) Bandwidth(MB/s)
33554432 65789.5


2: NVIDIA Tesla C1060
CPU : Intel Core i7 965 3.20GHz
メモリ : 8GB
OS : Fedora 10 for X86_64

./bandwidthTest
Running on......
device 0:Tesla C1060
Quick Mode
Host to Device Bandwidth for Pageable memory
.
Transfer Size (Bytes) Bandwidth(MB/s)
33554432 5295.2

Quick Mode
Device to Host Bandwidth for Pageable memory
.
Transfer Size (Bytes) Bandwidth(MB/s)
33554432 4650.6

Quick Mode
Device to Device Bandwidth
.
Transfer Size (Bytes) Bandwidth(MB/s)
33554432 73741.2

集合知プログラミング

O'REILLYのシリーズで集合知プログラミングという本が出版されている。原題は Programming Collective Intelligence という名前で Collective Intelligence のことを集合知と呼ぶらしい。初めに手にしたときは Python で書かれていたので躊躇したが、本当に性能が必要であれば C/C++ 等で作り直せば良いし、この本で書かれているアルゴリズムやデータ量であれば Python でも十分であろう。Python でも主要な機能、関数は C で書かれているので速いという人がいるが、反対に言えば高速化したい部分はやはり C 等で書かないと駄目ということになる。
中身については５章の最適化の部分から推測するに平易で理解しやすい（分野外の人だと難しいかもしれない）。この本の内容で授業等をすれば良いと思っているが、今の環境では誰も興味無いようだ（とにかく数学とコンピュータが出てくるとアウトという人が多い）。確かに数学とコンピュータに関する広範な知識が要求されるが、そこが非常に興味深いところになっている。

巨大な SDP

以前も紹介した SDP の新しいベンチマーク集のサイトがある。簡単に言うと n_SDP とは SDP の変数行列のサイズで m_SDP は制約式の数になる。例えば以下の Truss502_ful は性質的には low rank になっているので、陽に行列として扱わなくでも良いのだろうが、それにしてもサイズが大きすぎる。こんな問題を普通に解こうとすれば現在の枠組ではまず無理なので、全く新規に開発を行う必要がある（速度が遅くなっても良いとか、ストレージを使って良いならば出来ないことはないが）。一方 r3_l のように n_SDP と m_SDP が数万程度ならばクラスタ計算機などで SDPARA を使えば解くことができる。この問題は小さなブロックが多いのでメモリ消費量は減って、その点では解きやすい部類に入る。

Instance	Size (MB)	Optimal value	n_SDP	m_SDP	n_max	Structure
r3_l	37.279	-3.9587422e-01	72932	27555	11
Truss502_full	309.305		4557679	1141303	1509	symmetry   low rank

講演と展示

某シンポジウムに参加して、Intel, AMD, Microsoft の方の講演(CPU や HPC 系)を聞いた。仕方の無いところだろうが、講演で聞くことができる内容はインターネットで入手できるものばかりで、それ以上の情報を話すことは禁じられているようだ。というわけなので、もうこの種の講演を聞きに行くのは止めようかと思った。CEATEC Japan などの展示会に行っても、技術系の方が会場にいなかったり、上記と同様の理由で話せなかったりと特に得られた情報は無かった（展示会は直接現物が見られるのでそれだけでも行く価値はある）。もっとも講演者の方も話したいけれど話せないといった感じなので気の毒であるが。

Harpertown vs. Barcelona vs. Phenom vs. Nehalem

以下の四つのマシンの性能を比較したいのだが、今回は少し変わったアプリケーション(SDPA 5.01 + Meschach 1.2b) を用いることにする。

1: Harpertown
CPU : Intel Xeon 5460 3.16GHz
メモリ : DDR2-667 (4GB x 12)
OS : CentOS 5.2 for X86_64

2: Barcelona
CPU : AMD Opteron 2356 2.3GHz
メモリ : DDR2-667 32GB (2GB x 16)
OS : CentOS 5.2 for X86_64

3: Phenom
CPU : AMD Phenom X4 9950BE 2.6GHz
メモリ : DDR2-1066 8GB (2GB x 4)
OS : Fedora 10 for X86_64

4: Nehalem
CPU : Intel Core i7-940 (Nehalem) 2.93GHz
メモリ : DDR3-1600 6GB (2GB x 3) トリプルチャンネル
OS : Fedora 10 for X86_64

A: theta6.dat-s
1: 12m19.953s
2: 13m43.989s
3: 9m15.295s
4: 6m5.727s

B: CH4.1A1.STO6G.pq.dat-s
1: 4m49.249s
2: 5m44.317s
3: 4m4.784s
4: 2m41.756s

よって Nehalem > Phenom > Harpertown > Barcelona という結果になった。ほとんどメモリアクセスに対するベンチマークのようなプログラムになっている。しかし、その割には Barcelona が振るわないというか、Phenom が健闘している。

Kissing Numbers その２

A New Library of Structured Semidefinite Programming Instances の中の Kissing Numbers に関する SDP がある。この問題はこのホームページでは、* indicates numerical difficulties, i.e., the optimal values are uncertain or only known with low accuracy となっているので、数値的には非常に不安定で難しいと言われる SDP に属している。しかし SDPA-GMP (仮数部 128bit) で以下のようにかなり高い精度で解くことができる。これは結構すごい結果であろう。

Instance	Size (MB)	Optimal value	n_SDP	m_SDP	n_max	Optimal Value of SDPA-GMP
kissing_3_5_5	0.231	-11.872060	220	297	56	-11.872059507
kissing_3_10_10	9.206	-11.4385*	1210	1792	286	-11.438143281954662
kissing_4_7_7	1.283	-23.579687	488	695	120	-2.35796874
kissing_4_10_10	9.209	-23.14*	1210	1792	286	-23.135533635788739
kissing_5_10_10	9.213	-44.15*	1210	1792	286	-44.158868754266274
kissing_6_10_10	9.213	-77.9*	1210	1792	286	-77.912852356665081
kissing_7_10_10	9.215	-134.3*	1210	1792	286	-134.32853967140357
kissing_8_10_10	9.217	-238.929e+02*	1210	1792	286	-238.99981527380351
kissing_9_10_10	9.218	-365*	1210	1792	286	-365.21946908983952
kissing_10_10_10	9.219	-562.9*	1210	1792	286	-562.89594739422410
kissing_11_10_10	9.220	-889.74*	1210	1792	286	-889.74203646172571
kissing_12_10_10	9.221	-1369.485*	1210	1792	286	-1369.5287719561750

SDPA and SDPA-GMP on the NEOS Solvers

数理計画問題に対するソフトウェアを中心として、様々なソフトウェアが登録されている NEOS Solvers. 登録されているソフトウェアは Online で使用することができる。SDPA はすでに Version 5.x のとき(1999年)に登録が行われているが、本年に SDPA-GMP も NEOS Solvers に登録されることになった。

SDPA on NEOS
http://neos.mcs.anl.gov/neos/solvers/sdp:sdpa/SPARSE_SDPA.html

SDPA-GMP on NEOS
http://neos.mcs.anl.gov/neos/solvers/sdp:sdpa-gmp/SPARSE_SDPA.html

SDPA もすでにバージョン 7.2.0 に更新されている（速い！！）。

SDPA サーバの交替

sdpa.indsys.chuo-u.ac.jp のサーバを交替して能力アップさせた。図中のゲートウェイ＆Webサーバがこのサーバに相当して CPU : AMD Opteron 2356 2.3GHz (Barcelona) x 2 個、メモリ : 32 GB になった。また図中の組合せ最適化問題用の Online Solver と SDPA Online Solverは CPU : AMD Opteron 2384 2.7GHz (Shanghai) x 2 個、メモリ : 32GB だが、これは納期が遅れているので、導入は当初の予定よりも遅くなりそうだ。

SDPA クラスタと SDPARA

SDPA クラスタ計算機が連日フル稼働状態になっている。以前自作 PC でクラスタ計算機を作ったときには、高負荷で長時間実行を行うと数台ぐらは止まってしまったものだが、初めからサーバ仕様で作られているだけあって、現在まで SDPA クラスタにはトラブルらしいトラブルは起きていない。現在は SDPARA を用いて未解決の SDP の解を求めるのに挑戦しているので、しばらく高負荷の状態が続くことになろう。

○ SDPA クラスタ : Dell PowerEdge 2900III
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%

Nehalem v.s. Penryn v.s. Phenom その２

今度は、SDPA 7.2.0 + GotoBLAS 1.27 を用いて Schur complement 行列計算の並列化（マルチスレッド化）を試みる。これで複数コア間の共有キャッシュ(２次 or ３次）の性能(バンド幅など)を推定することができる。

1: Nehalem
CPU : Intel Core i7-940 (Nehalem) 2.93GHz
メモリ : DDR3-1600 6GB (2GB x 3) トリプルチャンネル
OS : Fedora 10 for X86_64

2: Penryn
CPU : Intel Core 2 Quad Q9450 2.66GHz
メモリ： DDR2-800 4GB (2GB x 2)
OS : CentOS 5.2 for x86_64

3: Phenom
CPU : AMD Phenom X4 9950BE 2.6GHz
メモリ : DDR2-1066 8GB (2GB x 4)
OS : Fedora 10 for X86_64

問題例 : D256.dat
1 スレッド
1: 55.315s
2: 53.930s
3: 1m46.022s

2 スレッド
1: 35.668s numactl --physcpubind=0,1
2: 33.183s numactl --physcpubind=0,2
3: 57.936s numactl --physcpubind=0,1

4 スレッド
1: 32.138s numactl --physcpubind=0,1,2,3
2: 24.468s numactl --physcpubind=0,1,2,3
3: 37.688s numactl --physcpubind=0,1,2,3

これだけの結果では断定できないが、SDPA をマルチスレッド化していくと高速、大容量２次キャッシュを持つ Penryn 系が有利になることもある。この辺は詳しく調べてみると面白そうだ。何故か Nehalem では 2 スレッド から 4 スレッドになっても実行時間の減少があまり見られない。