距離変数を unsigned long long 型に その２。

以下のようなものについて実験を行った。
USA-road-d.USA.gr　23947347 nodes 58333344 arcs / length range(1, 368855)
USA-road-d.LKS.gr　2758119 nodes 6885658 arcs / length range(1 - 138911)
USA-road-d.NY.gr 　264346 nodes 733846 arcs / length range(1 - 36946)


やはり mbpC.exe(goldberg) はメモリ使用量が多い。また、距離しか求めていないようで、距離のみにしてしまえば上記のような構造体の問題もなくなるが、Web サービスを考えると外せない。コンパイル時に ON/OFF はできるようにしてあるので、こちらも必要なときだけ演算するようにしたい。

以下は、全米データについてである。

Graph : USA-road-d.USA.gr
Query : USA10.p2p
　(957498, 10453327)
　(19200797, 7727679)
　(13006257, 40639)
　(4314559, 22779984
　(17261435, 8424294)
　(8077810, 13186938)
　(3048748, 1475829)
　(21869636, 3531883)
　(13446936, 4981527)
　(18549540, 3230879)



データ構造　(距離配列のデータ型)　要求されるメモリ量

bucket (unsigned int) 903.2MB
　22.37[sec]
bucket (unsigned long long int) 1085.9MB
　27.73[sec]

heap (unsigned int) 993.2MB
　35.71[sec]
heap (unsigned long long int) 1358.6MB
　40.89[sec]

mbpC.exe　(unsgined long int) 2796.8MB
　35.73[sec]



図は、USA-road-d.USA.gr 以外にも、USA-road-d.LKS.gr、USA-road-d.NY.gr について、それぞれを実行した結果である。ちょうど点数が 10 倍ずつになっているものを選んだ。mbpC.exe を基準にどれほどの実行時間であるか[%]を示している。

距離変数を unsigned long long 型に その１。

点情報などを格納する変数は、42 億ほどの非負整数を扱える unsigned int (以下 UINT)で良いとしても、やはり距離情報を格納する変数には、1848 京ほどの非負整数まで扱える unsigned long long int (以下 ULLONG) を用いた方が良いと思い、新たに追加した。

グラフを読み取った際に、「UINT で十分」であるか、あるいは 「ULLONG が必要」になるか判断し、適宜使い分けようと思っている。

全米に対してのデータのみ載せるが、やはり ULLONG にすることで、低速化してしまう。距離配列だけが２倍になっても、そのままでは構造体のアライメントが崩れてしまうために、4byte 分の Padding される。そのために構造体を 展開する/しない といったものを何パターンか作成したが、やはりこの状態が一番高速であった。にしても、構造体を１つ持ってくるのに、以前の倍かかってしまうので、その分が低速化に影響させているのではないかと推測される。

typedef struct {
　uint32_t potential; // 4byte
　uint32_t prev_node; // 4byte
} node_t; // 8byte

typedef struct {
　uint64_t potential; // 8byte
　uint32_t prev_node; // 4byte
　/* padding(4byte) */
} node_t; // 16byte

n-heap。

n-heap とは、１つのノードに対して n 個のノードを子に持つデータ構造である。n が増えることで比較回数が多くなってしまうが、swap 回数が減ることになるので、heap を配列で実装している場合は有効ではないかと考えた。

意外にも n = 2 のときが最も実行時間が短かった。n = 2 のときはもちろん通常のヒープになる。今回の実装では、容易に n を変更できるように実装していたのだが、こういった結果を得られた。

結局、通常のヒープ法が一番良いようだ。

Graph : USA-road-d.USA.gr
Query : USA10.p2p
　(957498, 10453327)
　(19200797, 7727679)
　(13006257, 40639)
　(4314559, 22779984
　(17261435, 8424294)
　(8077810, 13186938)
　(3048748, 1475829)
　(21869636, 3531883)
　(13446936, 4981527)
　(18549540, 3230879)

■unsigned int
n = 2　44.1[sec]
n = 4　41.0[sec]　
n = 8　44.1[sec]

■unsigned long long
n =　2　42.5[sec]
n =　4　48.4[sec]
n =　8　46.8[sec]
n = 10　48.2[sec]
n = 12　53.9[sec]

Armadillo-500。

最短路ソルバーをカーナビのような低スペックなハードで動かすために研究室で Armadillo-500 を購入した。

A5 ほどの大きさで、とにかくコンパクトというイメージである。そのため端子がより大きく所狭しと並んでいるように見える。ファンもないのでものすごく静音である。標準で Linux が搭載されているため、モニターと USB キーボード、LAN ケーブルをつなげれば、もうほとんど PC である。もちろん X を上がらないが。

また、メモリが 64MB しか搭載されていないため、工夫をしなければ大きなグラフデータを格納することは難しいだろう。ちなみに全米で 1GB ほど必要である。OS 自体で 20MB 使用しているので、さらに制限は厳しくなる。DIMACS の webpage においてあるような道路ネットワークの特性をもつグラフならば、どうにか点数が 100 万点程まで格納できそうなので、とりあえずは現状のプログラムをそのまま動かしてみようと思う。その後、さらに小メモリに改善という流れだろう。

枝長による実行時間の変化 その３。

前回の続きでもあるが、他のグラフで同じような実験をしてみた。

用いたグラフは USA-road-d.FLA.gr で、点数 1,070,376 、枝数 2,712,798 となっている。
今回の heap 法と bucket法の切り替えは n = 2 付近である。前回の結果も踏まえてみると、n = 2～3 とも言えるのだが、各時点でのバケットサイズ（最大枝長）も踏まえながら見ていくと、実は点数とバケットサイズが等しくなる地点ではないかと気づいた。

まだ NY.gr と FLA.gr の２つしか試していないのだが、道路ネットワークにおいては、「heap 法と bucket 法の切り替えポイント」は、「bucket サイズと点数が等しくなる」付近であるかもしれない。用いているグラフは実際の道路ネットワークを DIMACS フォーマットに変換したものなので、特性の似ているグラフ(特に USA-road-d.XXX.gr)であれば、同様の結果を得られるかもしれないため、より大きな全米グラフ等で、試していこうと思う。

ちなみに、この点はメモリ要求量の点からも切り替えポイントになっており、ここでデータ構造を切り替えることで、速度とメモリ要求量の両方の面で有効である。

枝長による実行時間の変化 その２。

２レベルバケットの方に少々手を加えたので、再びデータを取った。前回の結果と比べ、枝長を長くした時における１レベルバケット法との差が大きくなった。

またグラフより、バケット系とヒープ系の実行時間が等しくなるのは、3（length * 2^3）付近である事がわかる。USA-road-d.NY.gr の点数および枝数はそれぞれ 264346 / 733846 であり、このときの最大枝長は 295568 であるため、最大枝長と点数が最も近づく値となっている。他のグラフで同様な結果が得られれば、この値でデータ構造を動的に切り替えるようにしてもよいだろう。

枝長による実行時間の変化。

グラフの枝長を 2^n (n = [-10, 10]) 倍に変化させ、実験を行った。
　2^(-10), 2^(-9), 2^(-8), ... , 2^(0), 2^(1), 2^(2), ... , 2^(10)
の 21 通りについてである。


■実行環境
CPU : Xeon 2.33 GHz
OS : CentOS 4.1 64bit
GCC : gcc 4.1.2

graph : USA-road-d.NY.gr
query : p2p x 256 (random)



用いたデータ構造は以下の４つである。

・ヒープ
実行時間・メモリ要求量ともに安定している。

・１レベルバケット
枝長によって、実行時間・メモリ要求量が影響を受けてしまうが、条件によってはとても高速である。

・２レベルバケット
１レベルバケットをベースに、バケット配列と補助配列の２段階にすることで、枝長の影響を軽減している。

・マルチレベルバケット (by goldberg)
実験的に高速であるといわれているデータ構造。



ヒープの実行時間はグラフからも安定しているのがわかる。また、今回用いたデータ構造の中で最もメモリ要求量が少ない。図からはわかりづらいが、2^4 からは４つの中で最も実行時間が短い。

１レベルバケット法・２レベルバケット法では、ともに枝長に影響を受けていることが良く分かる。２レベルでは小さいながらも１レベルに比べ、その影響が抑えられている。2^5 あたりで、交差している。


マルチバケットではうまく適切なレベルを選択しているのだろうか、枝長が小さいときは実行時間も短くなり、枝長が大きくなっても実行時間が抑えられている。

データ構造の比較と自動選択。

様々なデータ構造が発表されているが、大きく分けると「枝長に依存してしまう」バケット系か、「安定している」ヒープ系のどちらかの特徴を持っている。そのため、短所を補うために、複数組み合わせたデータ構造も多く存在する。しかしながら、１レベルバケット法、２分ヒープ法はいづれもシンプルであるために最適化しやすく、そういった組み合わせのデータ構造に引けを取らない。

よって以下のような場合それぞれを適宜選択すべきであるといえる。

バケット系
・用いるグラフが道路ネットワークのような特性を持っている場合。

ヒープ系
・用いるグラフの特性が分からない場合。
・メモリ使用量を小さくしたい場合。


つまり、複数のデータ構造を組み合わせた新しいデータ構造を作成するというよりも、グラフの特性を読み取り適宜自動的に選択できるようなアルゴリズムが望ましいといえる。しかしグラフ読み込みの段階では、現在以下の情報しか取得していないが、自動選択機能の為に新たに取得しなければならない情報があるとすれば、そのコストがボトルネックになるという本末転倒になってしまいかねない。

■現在の実装で取得しているもの
・点数
・枝数
・最短枝数
・最長枝数

■比較的に容易に追加できるもの
・最大枝数（１点から出てくる最も多い枝の数）


こちらも考えていかなければならない。

ヒープ系データ構造。

実行時間・メモリ要求量がグラフによって影響を受けにくいヒープ系データ構造について、まとめていく。

ある資料によると、元の Dijkstra 法が 1959 年、候補枝を格納するためのデータ構造に binary heap を採用したのは 1964 年に Williams によって行われたようだ。

まず、計算量は O(m x log(n)) (n : 点数、m : 枝数）である。

特徴としては以下のようで、「良くも悪くも安定している」データ構造であるということだ。

・木構造により、最悪時でもあまり低速化されない。
・グラフの特性を用いてないので、あまり効率的でない？



実際に実装し、実験を行って得た情報を踏まえると以下のようにいえる。

・実行時間はヒープに格納されている点数によって決まる。（それでも log が効くため安定する）
・配列で実装しても、ハードウェアプリフェッチに乗せるのは難しい。
・データの局所性はある程度守られる。



ヒープ系データ構造は、やはり安定した動作をするデータ構造であるといえる。どうようなグラフであっても、安定した実行時間で解けるので、特性が分からない場合でも使いやすい。また、Multi-Level-Bucket の３分の１程度しかメモリ要求がなく、それ以上の実行速度も併せ持つので、本当に安定したデータ構造を使いたい場合だけでなく、メモリ要求量も抑えたい場合でもおすすめしたい。

バケット系データ構造。

枝長によって簡単に実行時間に影響が受けてしまうバケット系データ構造について、まとめていく。

ある資料によると、Dijkstra 法が生まれたのは 1959 年で、候補枝を格納するためのデータ構造に 1-level bucket を採用したのは 1969 年に Dial によって行われたようだ。

まず、計算量から見ていくが O(m+nU) (n : 点数、m : 枝数、U : 最大枝長）である。これだけみると最大枝長によって、実行時間が決まってしまうようにも思えるが、そうでない。まずは、良く知られているものが挙げていくが、以下のようになる。

・シンプルながら、高速に実行できる
・実行時間は枝長に依存に依存しまい、枝長が大きくなると低速化してしまう
・枝長分だけのバケット配列を要するために、メモリ要求量が大きくなってしまうこともある



実際に実装し、実験を行って得た情報を踏まえると以下のようにいえる。

・道路ネットワークと相性がとても良い（ほぼ理想）
　１．バケット内にある程度分散して格納されている。
　２．最小ポテンシャル点（次探索点）を求める動作が、ハードウェアプリフェッチ (Intel CPU) にのりやすい。

・枝長によって、大きく影響を受ける
　１．最大枝長が０の場合、バケットが働かないため、ある程度大きさの値で置き換える。
　２．枝長が極端に大きい場合、最小ポテンシャル点（次探索点）を求めるコストが大きくなる。

・ポインタを用いての実装では、高速化は難しい。



つまり、まとめると道路ネットワークを解くために出来たようなデータ構造といってもよい（実際そうかもしれないが）ほど、理想的な動きをする。ただし、前処理によって疎化されたグラフなどでは、思ったほどの実行時間を望めないだろうし、実用的な時間内に解けない可能性も出てくる。またメモリ要求量が多めであるため、実行時間・メモリ要求量が安定しているヒープ系に比べ、扱いが難しいともいえる。

また、他のデータ構造と組み合わせる事で、計算量を下げることに成功したデータ構造も存在する。しかしながら、凝った実装（ポインタを用いた実装）になることは避けられず、分岐の増加・データの局所性の低下により、それほどまでに実行時間が短縮されるとも思えない。