大型書店

新宿西口にブックファースト(1090坪)が11月6日に開店したので品揃えを見るために行ってみた。ブックファーストと言えば渋谷店(920坪)の雰囲気が気に入っていたのだが、残念ながら昨年閉店してしまったので、渋谷に行く理由が無くなってしまった。日本だけでなく世界中どこに行ってもとりあえず書店とショッピングセンターは入ることにしている。書店に入れば本、雑誌の質と量でその地域の知的好奇心のレベルをおおよそ推測することができる。また新刊や注目書コーナーも配置する本の品揃えでその本屋のレベルもわかる（店員さんや社員さんがどれだけ読書しているかということ）。
ちなみに同じジュンク堂や紀伊國屋書店などでも東京と大阪では結構品揃えが異なっている。今まで行ったジュンク堂で何回も行ってみたいと思ったのは以下の店。
東京都
新宿店（2004年開店、2007年増床、1650坪）
京都府
京都店（1988年、435坪）
大阪府
大阪本店（1999年、1480坪）
兵庫県
三宮店（1976年開店、2001年と2007年に増床、1400坪）

SDPA 7.2.0

ソフトウェアはとにかく頻繁に更新することが大事である。その方がプロジェクトが活発に行われていることがユーザに伝わって、安心して使用出来るそうだ。SDPA も 6 から 7 が出るまで 2 年ぐらいかかったので、その間はすでに開発が終わったソフトウェアと思われていたかもしれない。SDPA 7.2.0 はなるべく早めに公開したいが、動作テストとマニュアルの整備がまだである。この二つが気にならない方には早期に提供可能である。
SDPA 7.1.1 から 7.2.0 となるのでマイナーチェンジのようだが、実は大きく変更される。

1: Sparse Cholesky 関係のライブラリの変更 (Spooles から MUMPS)
2: Callable Library の提供
3: SOCP (二次錐計画問題) への対応 (SDPA 7.3.0 まで持ち越しか？）

Online Solver 関係の設備

需要と供給の関係も考慮して添付の図のような設備構成に変更することにした。AMD の Opteron (Barcelona と Shanghai) の性能は Intel Xeon 系に劣ることは、これまでの実験結果や公表されているベンチマーク結果からも明らかだが、購入する理由としては”安さ”というのが大きい（あと AMD に無くなってもらっては困るというのもあるが）。Dell 社の方でも AMD Opteron 搭載のサーバに力を入れていくそうだ（これも理由は安さなのか？）。すでに CPU が発売されて Shanghai や Nehalem の情報が解禁になったので、いろいろな資料を頂いた。ただし Nehalem 系の Xeon はまだ現物が無いので評価しにくいが、SDPA 用のアプリケーションでは Shanghai を上回る可能性は高い。Shanghai の次は Istanbul(6 コア)、その次は Sao-Paulo (多数コア)と言うらしい。いつもながら都市名と CPU コード名の関係が全くわからない。

某 LAPACK と 某 BLAS

インターネット上での検索では見付からないので、一応 "某" にしておくが、現在開発中の某 LAPACK, 某 BLAS がある。開発者本人が直接 mixi に書き込んでいるところ見たので、mixi にはこの情報が出ているのだろう。何しろ LAPACK は関数の数が多いので大変根気が必要な作業になる（途中で止めたら価値が激減するので）。こういった仕事が学術的な業績をして評価されないのが、日本のソフトウェアのレベルが上がらない大きな理由の一つになっている。
でも大事なことは、とにかく発言を続けることなので、継続して論文を出す、学会発表する、ホームページを作る、会合等での宣伝などを続けていけば、ソフトウェアの性能が良ければ、いずれ評価も変わるようになる。私の博士論文の公聴会のときに、某先生（公聴会は公な場なので名前を出してもいいのだが）から”こんな研究（多分ソフトウェア開発のこと）であと何年食っていけると思っているのか？”と聞かれたが、幸い１０年経って仕事は増えることはあっても、減ることはない。
注意深くいろいろな研究室を観ていると、最適化ソフトウェアの開発に適性を持った学生も少なからず存在するのだが、才能を伸ばして育成できる研究室が無く、業績を評価できる体制も無いので、それまま埋もれてしまうことが多いようだ。

Dell に Shanghai 登場

ちょうど Dell の営業の方に来ていただいたので、AMD の 新 Opteron (Shanghai) について聞いてみたところ、すでに Dell のホームページからオンラインで見積りと注文ができるとのことだった。例えば PowerEdge 2970 だと以下のような CPU を選択することができる。ちなみに 2384, 2378, 2376 が Shanghai で 2360SE, 2356, 2352, 2344HE が Barcelona である。来年になると 2.9GHz 版も出てくるそうだ。せっかくなので Barcelona と Shanghai を１台ずつ講入してみようかと思っている。

[Quad-Core] AMD Opteron 2384 (2.7GHz/6MB L3キャッシュ) [+ 202,650円]
[Quad-Core] AMD Opteron 2378 (2.4GHz/6MB L3キャッシュ) [+ 124,950円]
[Quad-Core] AMD Opteron 2376 (2.3GHz/6MB L3キャッシュ) [+ 79,800円]
[Quad-Core] AMD Opteron 2360SE (2.5GHz/ 2MB L3キャッシ) [+ 200,550円]
[Quad-Core] AMD Opteron 2356 (2.3GHz/2MB L3キャッシュ) [+ 122,850円]
[Quad-Core] AMD Opteron 2352 (2.1GHz/2MB L3キャッシュ) [+ 51,450円]
[Quad-Core] AMD Opteron 2344HE (1.7GHz/2MB L3キャッシュ) [+ 10,500円]
[Dual-Core] AMD Opteron 2212 (2.0GHz/1MBx2 L2キャッシュ) [+ 0円]

反復解法ライブラリ Lis と並列化 その３

最後は MPI と OpenMP の組合せだが、これは組合せの数が多いので結果の良いものだけを紹介する。

1: 16 プロセス(MPI) × 4 スレッド(OpenMP)
time mpiexec -machinefile ./hosts -n 16 ./test4 200000 2.0 -precision quad
real 0m2.652s

2: 32 プロセス(MPI) × 4 スレッド(OpenMP)
time mpiexec -machinefile ./hosts -n 32 ./test4 200000 2.0 -precision quad
real 0m2.897s

3: 64 プロセス(MPI) × 2 スレッド(OpenMP)
time mpiexec -machinefile ./hosts2 -n 64 ./test4 500000 2.0 -precision quad
real 0m3.117s

反復解法ライブラリ Lis と並列化 その２

前回の続きで、今度は MPI を用いて並列化を行う(４倍精度のみ)。

C: 複数 プロセス 1 スレッド (MPI) & 1 ノード 1 プロセス
time mpiexec -machinefile ./hosts -n ?? ./test4 500000 2.0 -precision double (or) quad

○ ４倍精度
1 プロセス : real 1m44.611s
2 プロセス : real 0m51.462s
4 プロセス : real 0m24.775s
8 プロセス : real 0m11.519s
16 プロセス : real 0m5.615s

D: 複数 プロセス 1 スレッド (MPI) & 1 ノード 2 プロセス
time mpiexec -machinefile ./hosts2 -n ?? numactl --physcpubind=0,1 ./test4 500000 2.0 -precision double (or) quad

○ ４倍精度
2 プロセス : real 0m55.810s
4 プロセス : real 0m26.213s
8 プロセス : real 0m11.478s
16 プロセス : real 0m5.735s
32 プロセス : real 0m3.330s

E: 複数 プロセス 1 スレッド (MPI) & 1 ノード 4 プロセス
time mpiexec -machinefile ./hosts4 -n ?? numactl --physcpubind=0,2,1,3 ./test4 500000 2.0 -precision double (or) quad

○ ４倍精度
4 プロセス : real 0m35.390s
8 プロセス : real 0m13.410s
16 プロセス : real 0m6.069s
32 プロセス : real 0m3.566s
64 プロセス : real 0m2.992s

F: 複数 プロセス 1 スレッド (MPI) & 1 ノード 8 プロセス
time mpiexec -machinefile ./hosts8 -n ?? ./test4 500000 2.0 -precision double (or) quad

○ ４倍精度
8 プロセス : real 0m32.025s
16 プロセス : real 0m10.083s
32 プロセス : real 0m3.790s
64 プロセス : real 0m6.733s
128 プロセス : real 0m8.265s

反復解法ライブラリ Lis と並列化

反復解法ライブラリ Lis は線形方程式及び固有値問題を反復法で解くためのライブラリで内部での 4 倍精度演算(実際には仮数部 104bit) や MPI, OpenMP による並列計算に対応している。
今回はパッケージに含まれる test4 を用いてみよう。実行には次のクラスタ計算機を用いる。もちろん OpenMP による実行ではクラスタ計算機でも 1 ノードしか使用しない。

●新 SDPA クラスタ (2008年)
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%

A： 1 プロセス 1 スレッド
○ 倍精度
time ./test4 200000 2.0 -precision double
real 0m12.297s

○ ４倍精度
time ./test4 200000 2.0 -precision quad
real 0m41.726s

B: 1 プロセス 複数スレッド (OpenMP)
○ 倍精度

1 スレッド
real 0m14.147s

2 スレッド (time numactl --physcpubind=0,1 ./test4 200000 2.0 -precision double)
real 0m7.280s

2 スレッド (time numactl --physcpubind=0,2 ./test4 200000 2.0 -precision double)
real 0m9.704s

2 スレッド (time numactl --physcpubind=0,4 ./test4 200000 2.0 -precision double)
real 0m13.745s

4 スレッド (time numactl --physcpubind=0,2,1,3 ./test4 200000 2.0 -precision double)
real 0m5.058s

4 スレッド (time numactl --physcpubind=0,4,1,5 ./test4 200000 2.0 -precision double)
real 0m8.695s

4 スレッド (time numactl --physcpubind=0,4,2,6 ./test4 200000 2.0 -precision double)
real 0m12.533s

8 スレッド
real 0m9.098s

○ 4倍精度
1 スレッド
real 0m43.660s

2 スレッド (time numactl --physcpubind=0,1 ./test4 200000 2.0 -precision quad)
real 0m26.672s

2 スレッド (time numactl --physcpubind=0,2 ./test4 200000 2.0 -precision quad)
real 0m30.107s

2 スレッド (time numactl --physcpubind=0,4 ./test4 200000 2.0 -precision quad)
real 0m32.936s

4 スレッド (time numactl --physcpubind=0,2,1,3 ./test4 200000 2.0 -precision quad)
real 0m16.976s

4 スレッド (time numactl --physcpubind=0,4,1,5 ./test4 200000 2.0 -precision quad)
real 0m21.017s

4 スレッド (time numactl --physcpubind=0,4,2,6 ./test4 200000 2.0 -precision quad)
real 0m27.481s

8 スレッド
real 0m22.027s

OpenMP の場合では 4 スレッド (time numactl --physcpubind=0,2,1,3) が共に最高速ということなので予想通りの結果になった。

Cell (PS3) 対 Atom

日本よりも海外(特にアメリカ）の方が PS3 をゲーム以外の用途、例えば HPC 系などに使うという動きが多く見られる。Cell が高速と言っても PPE のみを使う範囲では低速な部類に入る。アメリカのスパコン”ロードランナー”には倍精度強化版の Cell が搭載されているが、PS3 に搭載されている Cell は古い型なので SPE を複数用いても倍精度演算の能力は高くない。ただし、メインメモリのバンド幅が 25.6GB/s あるので、これに関してはいまだに最新の CPU でも追い付けていない。
これまでのベンチマーク対決で全敗の Atom だが、PS3 と比べるとどうなるだろうか。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

○ Atom
MSI Wind PC
CPU : Intel Atom 230 1.6GHz
メモリ : 1GB
OS : Ubuntu 8.04 Server for x86_64

○ Cell
PlayStation 3
CPU : Cell 3.2GHz
メモリ : 256MB
OS : Fedora 8 for PPC

1: GLPK 4.31 整数計画問題
○ stein27.mps
Xeon : 0.641s
Atom : 3.469s
Cell : 5.052s
○ air06
Xeon : 10.786s
Atom : 1m13.975s
Cell : 1m23.967s
○ min_rep_under_thput_39600.0_test18.dat(ファイル配置最適化問題)
Xeon : 0.269s
Atom : 1.342s
Cell : 5.307s

3: SDP (半正定値計画問題) : SDPA 7.2.0 + GotoBLAS 1.27b8(Xeon & Atom & Cell) : 1 スレッド
○ mcp500-1.dat-s
Xeon : 4.283s
Atom : 28.713s
Cell : 12.834s
○ theta5.dat-s
Xeon : 23.262s
Atom : 3m2.886s
Cell : 2m19.315s
○ mater-4.dat-s
Xeon : 7.031s
Atom : 29.417s
Cell : 45.102s

4: SDP (半正定値計画問題) : SDPA 7.2.0 + MUMPS 4.8.3 + GotoBLAS 1.27b8(Xeon & Atom & Cell) : 1 スレッド
○ mater-4.dat-s
Xeon : 5.327s
Atom : 22.880s
Cell : 28.449s
○ mcp2000_01D.dat-s
Xeon : 0.290s
Atom : 1.341s
Cell : 2.116s

全体的に Atom が優勢で初勝利と言えそうだが、一部の SDP ではかなり Cell に差を付けられている。これは性能的に GotoBLAS (Cell) > GotoBLAS (Atom) であることに原因がありそうだ。

Momonga Linux 5

少し前に Momonga Linux がリリースされている。７年くらい前だが同じ研究室にいたオープンソースプログラマーとして有名な K.S さんの勧めで(今はフランスで活動中）Kondara Linux を使っていたのだが、突然 Kondara プロジェクトは解散になってしまった。それ以降はクラスタ計算機用には RedHat 系(RedHat, Fedora, CentOS), 日本語 TeX 用には Vine Linux を用いている。日本だとオープンソース系の人が活躍できる余地は少ないのだろうか。ちなみに我々の分野では活躍は無理そうな感じである。

パーソナルナビゲーション

車のカーナビの調子が悪くなってきたので、SONY パーソナルナビゲーション NV-U3V を講入した。自分の車のカーナビとして使うのが主目的だが、実は最短路検索のアルゴリズムをある程度ハッキングしてみようというのが目的でもある。SONY のパーソナルナビゲーション(通称 nav-u) は測位の精度が通常のカーナビ並ということで人気があったのだが、ワンセグ機能がないのが、欠点と言われていた。最新の NV-U3V にはワンセグ機能も付いているが、法律上カーナビとして使用する場合には、ワンセグは音声だけになっている。さっそく我が家から東京タワーまでの経路を検索したところ Google Maps と NV-U3V では随分と異なる部分がある。これは通常道路と有料道路の速度差（速度比）をどう見積もるかというパラメータにも依存してくるので、どちらかの最短路が間違っているという話ではない。
ちなみに NV-U3V には音楽やビデオや写真等の再生機能が付いているが、ビデオについては規格が決まっていて、それ以外では再生できない。Xilisoft の Video Converter で以下のように設定してビデオを変換したら NV-U3V で再生することができた。

ビデオ
Video Codec : mpeg4
Video Size : 320x480
Bit Rate : 512 (384kbps)
Frame Rate : Auto
音声
Audio Codec : mpeg4aac
Bit Rate : 64
Sample Rate : 44100

最適化ソフトウェアにおける格差

約３年半ほど前にこのブログを始めたが、この３年くらいの間に日本の最適化ソフトウェアのレベルを何とかして向上させたいという目的もあった。ところが３年経ってみると例えばアメリカとの格差が縮まるどころか、回復不可能なほどさらに広がってしまった（アメリカどころかヨーロッパ諸国にも随分と差を付けられた）。NEOS Server にしても COIN-OR にしても質はともかく、日本が中心になってこのレベルのサービスやプロジェクトを始めるのは極めて困難である。それは最適化ソフトウェアの質とか予算とかいう問題ではなく、こういったものを始めたい、作りたいという人が皆無に近いことにある。外国に良いソフトウェアがあるだから、購入したりダウンロードすれば十分という意見を私自身も何回も頂いた（アメリカの製造業が衰退した理由と似ているが）。今の時代に国単位で考えるのがそもそも間違いと言う意見であれば、これも正しいのかもしれないが。ちなみに日本の著名な先生で私の意見に賛同してくださったのは３名である（この３名とは一緒に論文を書いたことはないが）。

SDPA のマルチスレッド化と numactl その４

以前も報告したように量子化学系の巨大な SDP に対して SDPARA を適用すると、F3 の計算式がほとんど実行時間を占めてしまう。これまで調べてきたように F3 計算式を２次あるいは３次キャッシュを共有した形でマルチスレッドで計算すると高速化されるようだ。
最後のこの量子化学系の問題に対して F3 式のマルチスレッド計算がどれくらい効果があるかについて調べてみよう。

1 スレッド
23m29.021s

2 スレッド
1: numactl --physcpubind=0,4 ./sdpa.2 ~/sdp/quantum/fukuda/r22/LiOH.1Sigma+.STO6G.pqg.dat-s out
20m42.838s
2: numactl --physcpubind=0,2 ./sdpa.2 ~/sdp/quantum/fukuda/r22/LiOH.1Sigma+.STO6G.pqg.dat-s out
25m37.833s
3: numactl --physcpubind=0,1 ./sdpa.2 ~/sdp/quantum/fukuda/r22/LiOH.1Sigma+.STO6G.pqg.dat-s out
26m37.682s

結論としては F3 式については計算方法の工夫、データのブロッキング、マルチスレッド化などによって高速化できる余地がまだまだあるということになる。

SDPA のマルチスレッド化と numactl その３

次はその２のときと同様の実験を AMD Barcelona で行う。Barcelona は添付の図のように２次キャッシュが各コア専用なので、複数のコアを共有しているのは３次キャッシュのみになっている。コア番号は左から 0, 1, 2, 3 という順番になっている。というわけで今度は 0,1 or 0,2 or 0.3 とすると３次キャッシュ共有での実行になる。0,4 とすると異なる CPU での実行になる。

CPU : Quad-Core AMD Opteron(tm) Processor 8356

問題名 theta6.dat-s
A: 1 スレッド動作時; 1m43.614s
B: 2 スレッド動作時;
1: numactl --physcpubind=0,1 ./sdpa.2 ~/src/sdplib/theta6.dat-s out
1m43.469s
2: numactl --physcpubind=0,4 ./sdpa.2 ~/src/sdplib/theta6.dat-s out
1m45.576s
C: 4 スレッド動作時;
1: numactl --physcpubind=0,1,2,3 ./sdpa.4 ~/src/sdplib/theta6.dat-s out
1m31.847s
2: numactl --physcpubind=0,1,4,5 ./sdpa.4 ~/src/sdplib/theta6.dat-s out
1m32.674s
3: numactl --physcpubind=0,4,8,12 ./sdpa.4 ~/src/sdplib/theta6.dat-s out
1m33.960s

4スレッドで一つの３次キャッシュ共有時が一番速い。1 スレッドと 2 スレッド時ではほとんど変化はない。

問題名 CH4.1A1.STO6G.pq.dat-s
A: 1 スレッド動作時; 1m2.672s
B: 2 スレッド動作時;
1: numactl --physcpubind=0,1 ./sdpa ~/data/CH4.1A1.STO6G.pq.dat-s out
52.795s
2: numactl --physcpubind=0,4 ./sdpa ~/data/CH4.1A1.STO6G.pq.dat-s out
54.175s
C: 4 スレッド動作時;
1: numactl --physcpubind=0,1,2,3 ./sdpa.4 ~/src/sdplib/CH4.1A1.STO6G.pq.dat-s out
42.313s
2: numactl --physcpubind=0,1,4,5 ./sdpa.4 ~/src/sdplib/CH4.1A1.STO6G.pq.dat-s out
43.778s
3: numactl --physcpubind=0,4,8,12 ./sdpa.4 ~/src/sdplib/CH4.1A1.STO6G.pq.dat-s out
44.161s

4スレッドで一つの３次キャッシュ共有時が一番速い。今度は 1 スレッドと 2 スレッド時では 2 スレッド時の方が速い。

SDPA のマルチスレッド化と numactl その２

前回の続きで実験結果について。まずは以下の Xeon マシンを用いる。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

問題名 theta6.dat-s
A: 1 スレッド動作時; 1m4.180s
B: 2 スレッド動作時;
1: numactl --physcpubind=0,1 ./sdpa.2 ~/src/sdplib/theta6.dat-s out
1m15.581s
2: numactl --physcpubind=0,2 ./sdpa.2 ~/src/sdplib/theta6.dat-s out
1m13.513s
3: numactl --physcpubind=0,4 ./sdpa.2 ~/src/sdplib/theta6.dat-s out
0m59.129s

問題名 CH4.1A1.STO6G.pq.dat-s
A: 1 スレッド動作時; 35.602s
B: 2 スレッド動作時;
1: numactl --physcpubind=0,1 ./sdpa ~/data/CH4.1A1.STO6G.pq.dat-s out
39.506s
2: numactl --physcpubind=0,2 ./sdpa ~/data/CH4.1A1.STO6G.pq.dat-s out
37.414s
3: numactl --physcpubind=0,4 ./sdpa ~/data/CH4.1A1.STO6G.pq.dat-s out
27.433s

この場合では２次キャッシュ共有での F3 の 2 スレッド計算は高速化の効果が見られる。また予想通りだが、２次キャッシュを共有する形で F1 を２スレッドで動作させるのはやはりかえって遅くなる。

1: numactl --physcpubind=0,1 ./sdpa ~/data/D512.dat out1
9m44.071s
2: numactl --physcpubind=0,2 ./sdpa ~/data/D512.dat out2
9m56.384s
3: numactl --physcpubind=0,4 ./sdpa ~/data/D512.dat out4
14m4.294s