Opteron クラスタ引退

新しいクラスタ計算機の搬入に伴って、2005年から稼働している Opteron のクラスタを停止することになった。電源や空調的には今後も稼働させることは不可能ではないのだが、５台で 58GFlops(Linpack)という性能なので、新クラスタの PowerEdge2900 1台(90GFlops) にも劣ることになる。というわけでこれらを稼働させることは明らかに資源の無駄遣いなので停止させた。これで旧大学から移動してきたクラスタ計算機のノードは全て停止することになった。スペックは以下のようになるので、別の用途ではまだまだ現役で使うことができる。

CPU : AMD Opteron 270 2GHz(Dual Core) × 2 個
メモリ : 4GB
PCI-Express 16 x 1 or 8 x 2 (SLI 可能)

SDPA とボトルネック

SDPA において、Schur complement 行列を疎行列で保持、計算したり、図にあるような F3 の計算式を使用した場合には、CPU とメモリ間のバンド幅がボトルネックになると思っていたのだが、どうもそんなに簡単ではないらしい。その理由の一つは、最近の Intel Xeon には 2コアに対して 6MB という大きな L2 キャッシュが存在していることにある。同時に複数コアで SDPA を実行しても、同じ L2 キャッシュを共有していない限りそれほど顕著な性能低下は見られない。よって、問題となるのは L2 キャッシュの量よりもバンド幅という推理が成り立つ。反対に、古い CPU で例えば L2 キャッシュが 512KB ぐらいだと、割と小さい問題でも CPU とメモリ間のバンド幅の問題が現れてくる。
また F3 の計算は CPU 内の演算能力によって律速されていないのは確かで、これに関しては幾つか改善案を思いついた。L2 キャッシュの量が増えるとレイテンシも大きくなる傾向があるので、これから出現する CPU では L2 キャッシュの量とレイテンシ減らして、その代わりに大容量の L3 キャッシュを搭載する設計になっているものが多い。L3 キャッシュは全コアで共有なので、これに対する同時アクセスが新たなボトルネックにならなければ良いのだが。

新経路検索システム

パーソナルナビゲーションシステム（いわゆる簡易型カーナビ）の販売が昨年から伸びてきているそうだ。低価格でコンパクト、取り外しも自由などと利点はいくらでもあるのだが、簡易型ではデータ記憶用には HDD でななく、フラッシュメモリなどを使用している。HDD は電気的なノイズが大きいので、GPS アンテナなどは外部に出す必要があるが、フラッシュメモリでは GPS アンテナを内蔵することもできる。またフラッシュメモリを取り外して、パソコン等でデータの更新や登録を行うこともできる。
話は少し変わって、今でもカーナビなどでは様々なタイプの経路検索を行うことができる。各種インターネットサービスを行っている会社では新しい経路検索システムを考えているようである。それらも今後の進展次第だが、query よりも前処理に重心を置くという方法よりも、動的に条件が変化する中での前処理なしの高速最短路検索の方が柔軟性や発展性が高いと思う。条件の追加によって、データの量と種類が増える傾向にあるので、少し余裕を持たせた設計が必要になる。それに、本当に速度が必要ならば多少最適性を犠牲するのも選択肢の一つになるかもしれない。

CUDA と最適化

CUDAの資料を見ていると面白そうだと思うのだが、どうも実際に取り組み気がしないのは以下の理由による。
１：現在取り組んでいる最適化ソフトウェアでは役に立ちそうにない。
1-1 : SDPA では倍精度以上の精度で高速な BLAS が必要。
1-2 : 最短路問題では演算量はそれほど多くなく、データのスキャンと更新などの方が重要。またアルゴリズムの性質上、スレッド並列にするのが困難。
２：CUDA が新しい HPC の本命になるのかどうかを見極めてから使用したい。
実際に物が出てこないと評価できないが、NVIDIA の CUDA には Intel の Larrabee などの強力なライバルが存在する。Cell もそうだが、基本的に CUDA を用いるためにはソースコードを大きく変更する必要がある。その点 Intel の Larrabee の方が開発が楽そうだ。

メモリにデータが入れば速い

全米データを 1 query (経由点なし）で解くと以下のような実行時間になる。
real 0m4.460s user 0m3.623s sys 0m0.836s
一方、図のように経由点 14 個, 15 query で解いてみる。
real 0m28.025s user 0m27.209s sys 0m0.809s

基本的に p2p タイプなので二点間の距離にも影響される。よって、単純に両者を比べにくいのだが、1 query あたりの平均時間は後者の方が明らかに早い。また system 時間はほぼ同じであり、この時間は経由点の数に影響を受けないことがわかる。

Core 2 対 Atom その３ (最短路問題)

今度は最短路問題を用いて比較を行う。ダイクストラ法でもヒープやバケットを利用したソフトウェアを開発しているが、今回はメモリ量が少なめなのでヒープを用いることにする。

○ダイクストラ法 with ヒープ sp.heap

1: NY 10 クエリ(データ名は最短路問題オンライン・ソルバーと同じ)
Atom : 2.63(s)
Core 2 : 0.58(s)
Xeon : 0.16(s)

2: FLA 10 クエリ
Atom : 12.92(s)
Core 2 : 2.77(s)
Xeon : 0.79(s)

ちなみに cygwin 等には、posix_memalign という関数がないので、そのままでは make できない。

http://www.gnu.org/software/gnulib/manual/html_node/posix_005fmemalign.html

This function is missing on some platforms: MacOS X 10.3, FreeBSD 6.0, NetBSD 3.0, OpenBSD 3.8, AIX 5.1, HP-UX 11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin, mingw, Interix 3.5, BeOS.

Core 2 対 Atom その２ (SDPA)

両者とも VMware 上の Vine Linux 4.2 を用いる（ただし Core 2 は Windows XP, Atom は Windows Vista)。SDPA 7.1.1 を用いて両者の性能を比較する。参考までに以下の高速環境も実験に用いる。

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

○SDPA 7.1.1 + LAPACK(BLAS) 3.1.1

1: mcp500-1.dat-s
Atom : 110.84(s)
Core 2 : 28.14(s)
Xeon : 8.37(s)

2: theta4.dat-s
Atom : 393.96(s)
Core 2 : 125.44(s)
Xeon : 38.99(s)

3: mater-3.dat-s
Atom : 26.90(s)
Core 2 : 5.56(s)
Xeon : 1.41(s)

やはり Atom の計算能力（浮動小数点演算）は Core 2 の数分の一程度。

Core 2 対 Atom その１

前々から Intel Atom の性能が気になっていたので、工人舎の Ultra Mobile PC を購入して性能評価と最適化問題用ソルバーの適用について探っていくことにした。このPCのスペックは以下の通り。

工人舎 SC3KP06GA
CPU : Intel Atom Z520 (1.33GHz)
メモリ : 1GB; PC2-4200 (DDR2-533 SO-DIMM)
OS : Windows Vista Home Premium SP1
HDD : 60GB

これと対決する Intel Core2 PC のスペックも以下の通り。

Panasonic CF-W7
CPU : Intel Core 2 Duo U7700（1.33GHz)
メモリ : 2GB; DDR2 SDRAM
OS : Windows XP Professional SP3
HDD : 160GB

両者に cygwin と Vine Linux(VMware) をインストールしてみたが、後者の方が使い勝手良く、性能低下も前者に対して数パーセント程度なので後者を用いることにした。

整数計画問題の解き方、扱い方 その２

現在では相当大きな整数計画問題でも商用のソルバーで解くことができるのだが、オンラインの動的なシステムで定期、不定期に整数計画問題を解きたい場合には、
１：無償であり、ソース組み込んで再配布が可能なライセンス形態であること。GNU の GLPK などが好ましい
２：秒数を指定して、その範囲内で最適解もしくはある程度良い近似解を算出すること
という条件が必要になる。よって商用のソルバーでは少なくても１の条件を満たさないし、GLPK でも２の条件を満たさない。最適解の高速求解という目標では商用ソルバーに勝るものをつくるのは大変だろうが、上記の１と２を満たす高速近似解法を作れば、結構人気がでるだろう。整数計画問題に対する近似解法には部分的に整数計画ソルバーを用いて最適に解くことがあるが、部分的にしても最適に解く（分枝限定法を用いる）と指定時間に対する解の出力保証が難しくなるように思う。

経由点付き最短路問題 Online Solver その２

経由点付き最短路問題 Online Solverの公開を開始した。公開後に何件か最短路問題に関する問い合わせをいただいた。その一つは一方通行や経由点に関するものだが、また一方で子問題（サブルーチン）として最短路問題を使用したいという件も何件かあった。現在では想定する最短路問題の大きさが小さいので何とでもなるレベルだが、大きい最短路問題を子問題として解く場合も十分想定されるので高速化しておいた方が良い。それに道路やコンピュータネットワーク以外にも最短路問題を使用する場合（主問題や子問題として）も結構多いようだ。

経由点付き最短路問題 Online Solver

某社からの質問がきっかけで最短路問題 Online Solverで幾つか経由点を指定できるようにしている。経由点を指定された順番に巡るのであれば、単に最短路問題を複数回解くだけで済む。複数クエリも一つの入力ファイルで済むようになっているので、実際には経由点を一つ指定しても実行時間は２倍になるわけではない。また経由点を巡る順番は任意で全体の移動距離を最小にするとなると、これは運搬経路問題 + 最短路問題に近い形になる。今までは運搬経路問題では二点間の距離は近似だったが、最短路問題が動的かつ高速に解けるのであれば、二点間の距離を相当正確に求めることができる。いずれにしても将来的には、この最短路問題用の高速ダイクストラ法を同時並行的にサブルーチンとして多数回解く場合も考えられるので、今よりもさらに高速化する必要があり、しかもなるべくメモリバンド幅を飽和させない工夫も必要になる。

最短路問題オンライン・ソルバーとブラウザ

最短路問題オンライン・ソルバーだが、様々なブラウザからでもサービスが利用できるように開発が進められている。Firefox, Opera, Safari, IE などで試しているのだが、意外と優れているのが Safari で Mac でも Windows でも高速描画が見られ、png 画像ファイルの縮小画も非常に綺麗に表示できている。
ちなみに、
1: Windows 95, IE 5.0 ×, Netscape 6.2 ×
2: Windows 98, IE 6.0 ○
3: Windows 2000, IE 6.0 ○
ということなので、Windows 98 以降ならば問題なく利用することができる。

整数計画問題の解き方、扱い方

突然だが、整数計画問題に対する解き方、扱い方について。

１：整数計画ソルバー：
整数計画問題に対しては CPLEX, Gurobi 等の有償整数計画ソルバーが有名であり、世界中で広く使用されている。他にも NUOPT や MATLAB の
Optimization Toolboxなどの有償整数計画ソルバーが使用されている。また無償のソルバーでは GLPK や LP_SOLVE なども存在する.
現在では相当規模が大きな問題でも CPLEX などで最適に解くことができるようになっている.まずは整数計画ソルバーを試して解けない場合には以下の方法を試すという方針もある. ナップサック問題や施設配置問題などは結構大きな規模まで解くことができるだろう.

２：分枝限定法や分枝カット法：
整数計画ソルバーも分枝限定法や分枝カット法を採用しているが,多くの場合では一般の整数計画問題を想定している.よって手間はかかるが個別の問題に対して分枝限定法や分枝カット法を設計して実装した方がより大きな効果を期待できる. 巡回セールスマン問題(分枝カット法)や二次割当問題(分枝限定法)がこれに当てはまる.

３：メタヒューリスティックスなどの近似解法 :
メタヒューリスティックスは組合せ最適化問題に対する汎用的な解法として知られている.整数計画ソルバーでは扱えないような巨大な整数計画問題を解いたり,あるいは短時間にある程度良い解が欲しい場合には近似解法が適用されることが多い.メタ解法は近傍探索法の拡張であるが,整数変数の値の取り方について様々な方法が考案されている. 制約充足問題にタブー探索法などのメタ解法が適用されている.

４：その他の近似解法(列生成法などや容量スケーリング法など) :
列生成法は元問題の列の部分集合からなる部分問題をLP緩和問題として解いて,双対問題から得られる情報によって新たな列を生成する反復解法であり,集合分割問題や集合被覆問題などで利用されている. またロットサイズ決定問題のように整数変数が実数変数の上限を規定しているときは容量スケーリング法という反復解法を使用することができる.
列生成法の概略は以下の通りである.
A: 全変数の中から一部の変数(列)を選び出す.その変数のみを用いてLP緩和問題を解く
B: LP緩和問題の最適解の双対変数の情報から考慮していない残りの変数の 被約費用(reduced cost)を計算する. 被約費用が正の変数(列)を部分問題に追加して(最大化問題の場合),LP緩和問題を解く.このとき変数を一つずつ加える場合と複数同時に加える方法がある.
C: LP緩和問題の最適解が収束するまで列を追加していく.

５：上記の手法の複合(ハイブリッド型) :
元問題は大きすぎて整数計画ソルバーで解けない場合でも分割して部分問題にした場合には整数計画ソルバーで最適解が得られることもある.また上記の容量スケーリング法で得られた実行可能解をメタヒューリスティックスなどを用いてさらに改善する方法も考案されている.

たまに来る質問

ブログにグリッドというキーワードが入っているので、たまに NAREGI などに関する質問が来たりしますが、以下のプロジェクトには全く関わっておりません。よって何の研究をしているかについてもほとんど知りません（噂程度）。
1: NAREGI
2: 情報爆発
3: 情報大航海

今後の開発について その３

以前アップしたボトルネックに関する図と説明だが、いろいろと指摘をいただいたので少し改訂した。AMD のマニュアルなどを調べても L1, L2 キャッシュと TLB が複雑な構造と関係になっていて、簡単に図示するのは難しい。最近の CPU (Penryn 系)では 6MB といった大容量の L2 キャッシュを搭載しているので、ある程度大きなデータをブロッキングすることは難しくはないのだが、TLB ミスが発生すると CPU がストールして非常にコストが高いので、実際にはブロッキングは 1MB 以下にするのが好ましい。さらに 16K から 32Kbytes ぐらいで出来れば、L1 キャッシュに全部を載せたり、組み込み系の機器などへの適用も可能になる。