今年一年。

今年といえば、やはりハードウェアの設備増強だろう。16 nodes のクラスタを始め、さまざまな種類の計算機を導入し、比較実験をする事が出来た。これだけの計算機があっても、現在の学科ではあまり興味を示さないようである。

またソフトウェアに関しては、最短路ソルバーの最適化が落ち着き、ひとまずライブラリ化も出来た。以前ブログを見てみると１年前のちょうど今頃に構造体で変数をまとめるなどの改善をしていたようだ。なんだかずいぶん前のことのようである。それだけ濃い１年だったということだろうか。

大変刺激的な出会い、貴重な経験が数多くあり、本当に濃い１年になった。

Census データに関して。

Census の主要点を大規模最短路の始点・終点の候補に使えるかもしれないとのことだったがよくよく確認してみると、こちらで持っているデータ外のものも混ざっている事が分かった。

正直都市名ではピンとこなかったが、緯度経度を DIMACS データの ID に変換してみると同じ点になる都市がいくつも出てきた。データに含まれていないアラスカかと思ったが、それだけではなくプエルトリコなどのアメリカ合衆国の自治的・未編入領域なども含まれていた。最も近い点を探索点とするようなアルゴリズムを用いているので、エラーにはならないが、省いた方がいいだろう。

やはりイメージの付かない地名よりも、日本でやってみたい。どうにか使える形式のデータが欲しいところだ。

リンク時の注意。

忘れないためと戒めのためのメモです。C 言語では、正しくない型でも宣言した通りに使用するだけではエラーが起こらない。要するにリンクする際にはミスが分からない。

// 正しい宣言
int f (int a, int b);

// 間違った宣言
int f (int b, int a);

型が違っていればセグメンテーションエラー出てくるのでくらいなので分かりやすいが、上のような場合エラーは出ないし値が異なるだけという状況に。これは分かりづらいくハマる。というかハマった。恐ろしい。

静的ライブラリ。

静的ライブラリのビルドのサンプルをのせておく。ar は、オブジェクトファイルから lib*.a を生成する。

$ gcc -c src1.c -o src1.o
$ gcc -c src2.c -o src2.o
$ ar rcus libsample.a src1.o src2.o
$ 
$ gcc -c main.c -o main.o
$ gcc main.o -lsample -o sample

ライブラリ化。

最短路ソルバーのライブラリ化を目論んでいたが、ひとまずライブラリとして動くものが出来た。いくつか関数も加え、それなりに必要な機能は満たしていると思う。例えばデータの格納は、「ファイルから」、「データ（配列）から」のどちらかから選べる。ひとまず色々使ってみてバグを取っていくのが良いだろう。

AMD vs Intel - その２。

前回の実験結果を性能低下率([%])という視点で、見てみる。Harpertown では、8 コアでの実行時にガクッと下がる。理由は L2 を共有したコア同士での実行になってしまうのと、（確かではないが）メモリバンド幅が飽和している（１ソケットで４プロセス分は厳しい）ためであると考えられる。

このように見ていくと、Shanghai では性能低下がかなり少ない。もともと最短路ソルバーでは性能が出てないため Intel プロセッサの優位は揺るがないが、コア数分性能が伸びてくれるのはうれしい。

                     [1]    [2]    [4]    [8]
[Intel]
Harpertown [3.16GHz]   0  -0.78   5.13  49.76
Nehalem*   [2.93GHz]   0   4.01  15.12
Nehalem    [2.93GHz]   0   3.98  14.74
Nehalem EE [3.20GHz]   0   3.60  13.32

[AMD]
Phenom     [2.60GHz]   0   5.49  14.04
Barcelona  [2.30GHz]   0   5.57  12.61  30.08
Shanghai   [2.70GHz]   0   4.08   6.81  18.09

AMD vs Intel - その１。

研究室にぞくぞく新マシンが到着したので、最短路ソルバーでの実行時間を計測してみた。([sec])
グラフは全米（USA-road-d.USA.gr）、クエリはランダムな P2P x 256。

Turbo Mode と Hyper-Threading を ON にした Core i7 940 を Nehalem* としている。それぞれオフのものを 単に Nehalem としている。また Nehalem EE は Core i7 965 Extreme Edition である。

このように面白いほど、Intel の プロセッサが優位である。Harpertown(Penryn 系) では、L2 共有での性能低下がみられたが、Nehalem, Phenom, Barcelona, Shanghai には性質上それがなく、フルにコアを使用しても、性能低下が少ない。

TLB のバグ？が改善された後に、ぜひ Nehalem EE の２ソケットでの実験を行ってみたいものだ。。

                           [1]     [2]     [4]     [8]
[Intel]
Harpertown [3.16 GHz]   631.78  313.42  166.04  118.27

Nehalem*   [2.93 GHz]   591.72  307.73  170.29
Nehalem    [2.93 GHz]   611.35  317.83  175.37
Nehalem EE [3.20 GHz]   548.44  284.09  155.37

[AMD]
Phenom     [2.60 GHz]  1061.74  560.03  302.70
Barcelona  [2.30 GHz]  1194.72  630.64  336.33  194.26

Shanghai   [2.70 GHz]   987.88  514.08  263.79  145.82

最短路オンラインソルバーにおける同時実行数。

こちらで最短路オンラインソルバー(The Shortest Path Online) の開発を行っている。度々同時実行数はどのように制限するのかという議論を行うが今までどうもであった。

案とて「ファイルを用いる（PID をファイルに書き込む、ファイル名にしてファイル数を数える）」などが上がったが、実行中にブラウザを閉じたときの動作が危険なので、実行中のフラグがあるプロセスが本当に上がっているのか確かめることになり、あまりうれしくない。

よくよく考えてみると、次のようにすればよいことが分かった。
ps aux | grep -c "solver_name"

このままでは、grep 分が１つ増えるが、それでもかなりコンパクトになった。
改めて Linux や Unix のコマンドの力強さを感じることとなった。

主要点間最短路問題５。

主要点間最短路問題３，４で、新たなフォーマットについていろいろ考えてみたが、まとめるとソルバー自体を対応させるというのは微妙な気がしてきた。本質ではない部分で変更が全体に及ぶためである。ということで、すっきりそのまま実行しようと思っている。なんでもかんでも他機能というのは、きっと良くないはず。

主要点間最短路問題４。

前回、新たに「多対多」クエリ・フォーマットを考えてみたが、これをソルバー内に実装するのはなかなか面倒であるかも知れないと思いなおしている。そこで SS タイプ最短路問題を解き、その出力ファイル（使用枝の出力）と「多対多クエリファイル」を受け取り、結果をマージするといった別バイナリを開発した方が良いのではないかと考えている。クエリ行が最悪倍になるだけなら、m という紛らわしいものを付け加えるのは、良くないと思っている。

よって、以下のようになんというか SS TYPE の拡張のようなフォーマットが適していると思われる。

p : パラメータ行　（クエリ数を記述）
s : 始点の記述
c : コメント行

ここまでは DIMACS Single-Source Shortest Path Query Format であるが、これに d を加える。

d : 終点の記述


これにより p や s は最短路の計算に使用するため、読まれるが、d から始まる行は読み飛ばされるため、DIMACS フォーマットに対応したソルバーでも使用できるだろう。

c ========================================
c sample many-to-many query file
c ========================================
p sp aux ss 3
s 1
d 2
d 3
s 3
s 4

このように始点を　１，３，４　にしての最短路問題を解くことになり（クエリ数は始点数を記述）、それぞれを始点としての１対全最短路木が出力される。しかしながら、必要のないデータも数多く入っていたり、重複している枝も含まれてしまう。そのため出力ファイルと、クエリファイルから、以下の６通りのデータを抜き出すプログラムを作成しようとしている。

（１，２）、（１，３）
（２，２）、（２，３）
（３，２）、（３，３）

主要点間最短路問題３。

せっかくなので、新たなクエリフォーマットを考えている。
以下の例は ID で指定するタイプのクエリファイルになっている。

p aux sp m2m 5
s 4
m 3
d 2
d 5
s 1

これは、以下のように解釈され、

s : 始点にのみなる点　1, 4
d : 終点にのみなる点　2, 5
m : どちらにもなる点　3

このように SS タイプ 3 回の最短路を解くことになる。

(1, 2), (1, 3), (1, 5)
(3, 2), (3, 3), (3, 5)
(4, 2), (4, 3), (4, 5)

これを用いれば、主要点間の最短路も同様に指定する事ができるだろう。

全部で SS タイプを 3000 回だが、例えば 10 台のクラスタで解くのであれば、各ノードは SS x 300 の最短路を解くことになり、その際のクエリファイルは以下のようになるだろう。

p aux sp m2m 3000
m
 :　300 queries
m
d
 :
 :　2700 queries
 :
d

方向性が決まりつつあるので、さっそく作業をしていこう。

主要点間最短路問題２。

前回の記事により主要点は 3000 点ほどに決まったのだが、今度は主要点間の最短路を求めるためにどのように指定するかが問題になってくる。現在のソルバーでは、P2P（１対１）とSS（１対全）しか対応していないため、これを用いて主要点間最短路を表現しようとすると、P2P を 3000 ｘ 3000 回繰り返すことになり、かなり無駄が生じる。

要するに SS を解き、いくつかの終点から始点までのパスを生成するルーチンがあれば、うまくいく。どのように指定するかがポイントになるが、特に特別な用途ではないと思うので、何か良いフォーマットを作ろうかと考えている。

主要点の候補として Census2000 データ。

現在は全米データを用いているのだが、せっかく緯度経度情報があるのでランダムな点を用意しても面白くない。簡単に見つかるデータとしては郵便番号があるのだが、主要点ということでは多すぎる気がする。40000 ほどなので正直できないこともないのだが、数が多くなってしまったことにより、埋もれてしまう情報があるかもしれないため、もう少し少ない方が望ましい。

そこで、Census という国勢調査のデータを用いるようと考えている。各地域の人口や陸地面積などがテキスト形式でインターネット上に配布されている。いくつか種類があるが、中でも county という「州(State)の下の地方行政上の最大区画」に関してのデータを採用しようと考えている。数も 3219 であるためこのくらいがちょうどいいのではないか。

主要点間最短路問題。

大規模最短路問題での実際の応用を考えている。全米データに対し、ただ厳密解を解いたのでは、グラフ疎化による高速化に対してインパクトが薄い。

そこで、枝長の変化を考慮して、主要点間を数分おきに計算するシステムを考えている。さらにユーザから能動的に最短路を求められれば、それに対応するようにしている。需要変動が自前の計算リソースを超えてしまった際には、Amazon EC2 などのクラウド・コンピューティングの力を借りることになる。

まずは枝長の変化はランダムで行っていくつもりであるが、事故情報などに動的変化出来るような枠組みを構築すれば、データさえあればすぐに利用可能な便利なシステムになる。

Amazon EC2 c1.medium タイプノード。

新たに EC2 で c1.medium という Multi-Core CPU のノードを借りていただいたので、さっそくベンチマーク。次のように Intel Xeon である。もともと Quad-Core であるが、使用できるのは 2core となっている。ちょうど研究室に同じ CPU のマシンがあったので、比較実験を行った。

CPU : Intel(R) Xeon(R) CPU E5345 @ 2.33GHz (L2 4MB)
Mem : 1.7 GB

今回使用するグラフは USA-road-d.USA.gr であるのだが、Heap に使用する配列を static に確保してしまうと２スレッドで実行した際にメモリ上に乗りきらないため、dynamic に確保するタイプのものも同時に実験してみた。

USA-road-d.USA.gr では、メモリ要求量はそれぞれ以下のようになっている。

[Use Memory]
static   [1] 1.27 GB, [2] 2.00 GB
dynamic  [1] 0.90 GB, [2] 1.29 GB

[EC2-Xeon5345]
           |   s[1]     s[2]  |   d[1]     d[2]
NY256.p2p  |  8.77s    4.69s  |  8.29s    4.37s
USA10.p2p  | 43.51s      -    | 42.06s      -
USA10.ss   | 91.51s  (75.81s) | 88.53s   53.20s

[Xeon5345]
           |   s[1]     s[2]  |   d[1]     d[2]
NY256.p2p  |  6.36s    3.16s  |  6.61s    3.27s
USA10.p2p  | 34.15s      -    | 34.98s      -
USA10.ss   | 73.24s   37.79s  | 74.57s   38.21s

このように、dymamic にすることで多少性能低下するが、メモリに載らないとそれ以上に性能低下するため、Heap は dynamic で確保しよう。それにしても Opteron の時に比べてこちらはかなり性能が良い。