大規模最短路問題。

大規模グラフかつ大規模クエリの最短路問題をいかにして解くかということを考えている。クエリ数が大きいのであればクラスタのような並列計算機が必要になってくるが、たとえば需要が変動することを考えるとどのくらいの計算機を用意するか難しい。

足りないリソースを補うために、Amazon EC2 などのクラウドコンピューティングを利用しようというわけだ。Amazon EC2 は Xen での割り当てなので、実機ではないため手持ちのソルバーの性能の出方が変わることが予想される。

仮想マシン上でも性能の出る実装に対する何らかの知見が得られればと思っている。

枝長の推移６。

「random」系も見ていく。

大きく分けて３種類のグラフを見てみたが、どれも枝長のバラツキは同じようであった。これだけでは何か有用なグラフ特製の情報を得る事は難しいのだろうか。

枝長の推移５。

次は「Square」系について。
こちらも「Long」系と比べて、ほとんど変わらないようである。

枝長の推移４。

ベンチマークグラフにも、枝長ごとの枝数をプロットしてみた。
まずは、「Long」系から。
色々選んでみたが、ランダムで作成しているせいか、かなり規則性がある。

枝長の推移３。

枝長の推移を表した４種類のグラフに関してのデータを載せておく。

g USA-road-d.NY.gr
c 264346 nodes 733846 arcs
s [degree] min:1, max:8, mean:2.77608, var:0.963078
s [length] min:1, max:36946, mean:1293.3, var:1.27709e+06

g USA-road-d.USA.gr
c 23947347 nodes 58333344 arcs
s [degree] min:1, max:9, mean:2.4359, var:0.896251
s [length] min:1, max:368855, mean:2950.32, var:1.49023e+07

g USA-road-t.NY.gr
c 264346 nodes 733846 arcs
s [degree] min:1, max:8, mean:2.77608, var:0.963078
s [length] min:2, max:92366, mean:3126.7, var:6.47587e+06

g USA-road-t.USA.gr
c 23947347 nodes 58333344 arcs
s [degree] min:1, max:9, mean:2.4359, var:0.896251
s [length] min:1, max:922138, mean:7077.65, var:4.61467e+07

枝長の推移２。

前回の続きで time についておこなった。こちらも time 同士であれば、同じような特性があるのが良く分かる。

しかしながら distance と time を比べてみると、いくつか異なった点がある。特に道の制限速度に応じて枝長を x0.4, x0.6, x0.8, x1.0 しているため、よりバラツキが大きくなっているのが良く分かる。

それにしても大きな枝長はほとんどないようだ。

枝長の推移１。

ふと、枝長の推移を視覚したらどうかと思い、やってみた。
図は USA-road-d.NY.gr（上段）と USA-road-d.USA.gr（上段）についてのものだが、各枝長がどのくらいあるかというグラフになっている。それぞれ左側が全体を表していて、右側が枝長が 1 ～ 10000 の部分だけを抜き出したものになっている。

かなり大きさの異なるグラフではあるが、こう見てみるとそこまで性質が異なっているようには見えない。distance のグラフということもあるのかもしれない。time の方もやってみると面白いかもしれない。

The Design and Analysis of Computer Algorithms.

Goldberg の論文にも出てくる RAM-model がどんなものかを知るため、「The Design and Analysis of Computer Algorithms (Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman)」を大学の図書館から借りてきた。なんともインパクトのある名前である。

tape を使っていた頃(1974/06)の本であるので、今とは状況が違うものもあるがなかなか面白い本である。じっくり見てみよう。

最短距離のＣ言語。

現在、”最短”路問題ソルバーを”Ｃ言語”で開発しているので、なんとなく気になってはいたのだが、購入してみた。

「最短距離のＣ言語」を出版しているのは「暗黒通信団」で、他には円周率がひたすら書いてある本、ホームページの URL が (www.mikaka.org)など、なかなか面白いところである。

ざっと読んだが、このようなＣ言語の本があってもいいと思う。Ｃ言語関係の本はどれも応用の利かないサンプルを扱っていて、それで簡単簡単というのだからどうしようもない。特にアルゴリズム系のサンプルはどうしようもなく、”２分木”を”２分岐”と書いてある本すらあった。

realloc。

１スレッドでは気にならないほどでメモリ再確保できた realloc について。

・一度にメモリ確保
　○少しでも高速に実行したい
　×無駄な部分が多い

・こまめにメモリ確保
　○最短路は要求メモリが大きいため、少しでも無駄を省きたい。
　×realloc のコスト

とどっちの機能も欲しい。

ちなみにマルチスレッドではかなり遅くなってしまう

メモリ管理２。

不本意ながら、以下のような構造体で動的確保したメモリを扱っている。

typedef struct {
  void *ptr;
  int fd;
} mem_t;

というのも、さまざまなメモリ確保方法をサポートしているため、
mmap() などで open() したものを close() するために file descriptor が必要なためである。

これでは他のプログラムへの応用は難しいだろう。ひとまず、構造体の利用は良くない。思い切って fd は持たずに OS にお願いするというのも１つの手だが、そうするとメモリ解放が問題になってしまう。どうにかならないものか。

メモリ管理１。

最短路ソルバーでは以下のように色々サポートしている。

・malloc()
・posix_memalign()
・mmap()
・HugeTLBfs (hugetlbfs を mmap())

posix_memalign() は Mac や Playstation3 上では使用できず、
またアラインメントの効果が薄い（ない？）こともあって外そうかと考えている。

Yellow Dog Linux。

「フィックスターズ、米Terra Soft Solutionsから「Yellow Dog Linux」を含む全事業を買収。買収した事業、従業員およびコロラド州の支社は、フィックスターズが新たに設立した子会社Fixstars Solutions Inc.（米国カリフォルニア州、サンノゼ市）が引き継ぐそうである。」だそうだ。

使用したことはないのだが、Yellow Dog Linux は PPC 系の CPU に対応している Redhut 系の Linux である。
また Fixstars は、かなり Cell に力を入れており、情報サイトや無料セミナーなど大変お世話になった。
Cell 関係の情報と言えば、ここという企業である。

Cell は卒業研究～M1 くらいまででそれからほとんど触っていないので、ひと段落ついたらもう一度色々いじってみたい。

Web ブラウザ。

以前から、Firefox と Safari で行ったり来たりしてきた。
そこに Google Chrome が加わっている状態だ。

というのも、Firefox では、なぜか検索時に異常終了するので、なんというか気持ちが悪い。
Safari は、Safari で文字エンコードが弱いようで、うまく変換されなかったりする。

なら、Google Chrome しかないのだが、まだ Beta 版なのでどうなのかという問題もある。
Google の Beta というのは、他とは違うのだろうか。Gmail もいまだに Beta 付き。

というのことで、結局決まらない。

幅優先探索 (Breadth first search)。

幅優先探索 (Breadth first search) について触れていく。
というのも、BFS の機能を持っているためである。
比較しているため、こちらもやってみようと思い作成してみた。
MLB ではうまく実行できないようであるが、なぜだろう。

ひとまず、やるべきことは単純で枝長がすべて１であると仮定して、最短路ソルバーを動かすだけ。
また枝長がすべて１であるために、以下のことが言える。

・最大枝長が１であるため、バケット法が効果的
・データ構造内での更新はない

この部分を利用する事によって高速化が可能になる。