まずは shortest path solver を探しているのだが、やはり MLB 位しか internet 上に公開されていない。公開されていても授業に用いているレベルのものがほとんどで実際に性能を考慮した実装を行っているようではないものが多い。また前処理により高速化されたという論文も多いのだが、ソフトウェアとして公開しているかと言えば、そうでない。
排他処理を行う際にどちらを使うべきなのか、以前から迷っている。変数をインクリメントすることやファイルへの書き込みなどロックの数は１で、かつあまり実行時間に影響をしめすほど数は多くない。もちろんそれぞれの役割を考えるなら、mutex を用いるのが一般的だろう。
簡単に１変数を複数のスレッドからインクリメントするというプログラムを作成してみて実験を行ってみたが、どちらも同程度である。いずれ機能、性能に差が出るようなプログラムを作成する際にまた考えてみる事にしよう。
簡単に１変数を複数のスレッドからインクリメントするというプログラムを作成してみて実験を行ってみたが、どちらも同程度である。いずれ機能、性能に差が出るようなプログラムを作成する際にまた考えてみる事にしよう。
Bucket-Sort のメモリ要求量を減らす工夫を行った。
1. 各データの頻出回数をカウントする。
2. 1 により、区切りを計算する。
3. 区切りにしたがい、データを書き出す。（区切りは移動してしまう）
4. 区切りを格納しているデータをソート前に戻す
区切りは要素が１つずつずれた形になっているため、簡単に元に戻すことができる。
このような流れなら、forward-star + 枝情報配列程度のメモリ領域で抑えることができる。
結果、それぞれ次のような実行時間で forward-star を構成することができた。
工夫を行ったもの(*)と Quick-Sort との比較である。
確かに Quick-Sort の方が省メモリだが、ダイクストラ法実行時のメモリ要求量は更に大きい（1267.2 MB）ので、Bucket-Sort を採用してもよいだろう。
1. 各データの頻出回数をカウントする。
2. 1 により、区切りを計算する。
3. 区切りにしたがい、データを書き出す。（区切りは移動してしまう）
4. 区切りを格納しているデータをソート前に戻す
区切りは要素が１つずつずれた形になっているため、簡単に元に戻すことができる。
このような流れなら、forward-star + 枝情報配列程度のメモリ領域で抑えることができる。
結果、それぞれ次のような実行時間で forward-star を構成することができた。
工夫を行ったもの(*)と Quick-Sort との比較である。
確かに Quick-Sort の方が省メモリだが、ダイクストラ法実行時のメモリ要求量は更に大きい（1267.2 MB）ので、Bucket-Sort を採用してもよいだろう。
data: USA-road-d.USA.gr (n=24M, m=58M) Quick-Sort 6.7 [sec] 758.9 MB Bucket-Sort* 1.3 [sec] 1204.0 MB
Bucket-Sort を in-place ではなくしたところ、予想通りの性能が出てくれてほっとしている。
なぜ in-place では性能が出なかったのかを考えてみると、やはり配列の要素を使って辿るという操作が良くないということになるだろう。要素データがメインメモリから来なければ、次の要素を参照する事ができないため、完全にメインメモリのバンド幅に依存する。にしてもあまりにも遅いが。
それでは in-place ではなぜ性能が出るのか。
まず移動元は連続に並んでおり、データは塊（64byte）でロードされるためキャッシュヒット率は高いと思われる。移動先に関してはかなり不連続だが、１度書き出されればその後はその要素にアクセスしないため、書き込みに対しての待ちもない。
なぜ in-place では性能が出なかったのかを考えてみると、やはり配列の要素を使って辿るという操作が良くないということになるだろう。要素データがメインメモリから来なければ、次の要素を参照する事ができないため、完全にメインメモリのバンド幅に依存する。にしてもあまりにも遅いが。
それでは in-place ではなぜ性能が出るのか。
まず移動元は連続に並んでおり、データは塊（64byte）でロードされるためキャッシュヒット率は高いと思われる。移動先に関してはかなり不連続だが、１度書き出されればその後はその要素にアクセスしないため、書き込みに対しての待ちもない。
data: USA-road-d.USA.gr (n=24M, m=58M) Quick-Sort 6.7 [sec] Bucket-Sort 17 [sec](in-place) Bucket-Sort 1.5 [sec]
in-place Bucket-Sort を調べているが、あまりにも性能が出ない。どうもデータアクセスに異常なほど時間がとられているのだが、ここまで遅いと他にも原因があるのではないかとも思える。
in-place に限らず、Bucket-Sort は条件さえそろえばとても効率的である。というのも、無駄なスワップはなく各データが書き込むのは１度だけ（事前に１回読み込み、各データの頻出回数を格納しなければならないが、それは誤差の範囲ほどの時間しかかからない）という効率さである。
しかしながら、そうなると当然とびとびのデータアクセスのためのコストが問題になっては来るのだが、次のようにあまりにも時間がかかりすぎている。in-place でなれば、かなり改善と思うため、こちらも作成し検討してみようと思う。しかしながら、数百メガバイト分の補助領域が必要となってくるためにトレードオフだろう。
in-place に限らず、Bucket-Sort は条件さえそろえばとても効率的である。というのも、無駄なスワップはなく各データが書き込むのは１度だけ（事前に１回読み込み、各データの頻出回数を格納しなければならないが、それは誤差の範囲ほどの時間しかかからない）という効率さである。
しかしながら、そうなると当然とびとびのデータアクセスのためのコストが問題になっては来るのだが、次のようにあまりにも時間がかかりすぎている。in-place でなれば、かなり改善と思うため、こちらも作成し検討してみようと思う。しかしながら、数百メガバイト分の補助領域が必要となってくるためにトレードオフだろう。
data: USA-road-d.USA.gr(n=24M, m=58M) Quick-Sort 6.7[sec] in-place Bucket-Sort 17[sec]
ダイクストラ法の探索候補点を保持するデータ構造に対して Heap を使うとかなりメモリ要求量を節約できる。
Heap 自体は、点 ID と Potential を保持しておけば済む話なので、それぞれ int なら sizeof(int) * n 程度。long long でも、sizeof(long long) * n ほどあれば十分である。
全米であるとそれぞれ 8byte * 24M = 192MB、16 byte * 24M = 384 MB ほどとなる。
Heap 自体は、点 ID と Potential を保持しておけば済む話なので、それぞれ int なら sizeof(int) * n 程度。long long でも、sizeof(long long) * n ほどあれば十分である。
全米であるとそれぞれ 8byte * 24M = 192MB、16 byte * 24M = 384 MB ほどとなる。
forward-star で保持すれば、n+2m+2 程の領域でグラフを格納する事ができる。
点番号・枝長がともに int であれば、sizeof(int) * (n+2m+2) となり、全米データのように 24M 点 58M 枝であると、560 MB ほどの領域となる。また、点番号・枝長がともに long long であると、その倍の 1120 MB になる。
もしこれが距離行列でなら、24M * 24M の 576 TB となり、格納など不可能である。
点番号・枝長がともに int であれば、sizeof(int) * (n+2m+2) となり、全米データのように 24M 点 58M 枝であると、560 MB ほどの領域となる。また、点番号・枝長がともに long long であると、その倍の 1120 MB になる。
もしこれが距離行列でなら、24M * 24M の 576 TB となり、格納など不可能である。
forward-star 用のソートルーチンをあれこれ工夫している。Quick-Sort では、全米（2500万点、5800万枝）で 7 秒（Xeon 3.16GHz）程かかってしまう。ファイル入力に 30 秒ほどかかるので、短いともいえる。もちろん早ければ早いほどいいので改善できるところはすべてしたい。
さまざまな条件から Bucket-Sort だと思っているのだが、どうもうまくいかない。比較回数、代入回数ともに Quick-Sort を勝っていても実行時間は Quick-Sort の圧勝になる。これは in-place での結果であるが、in-place でないとどうなるかやってみる価値はあるだろう。
さまざまな条件から Bucket-Sort だと思っているのだが、どうもうまくいかない。比較回数、代入回数ともに Quick-Sort を勝っていても実行時間は Quick-Sort の圧勝になる。これは in-place での結果であるが、in-place でないとどうなるかやってみる価値はあるだろう。
さまざまなグラフデータに対し実験を行ってみた。各グラフでの枝長や次数（１点に対する接続枝数）の平均や分散も比べたりしているのだが、結局実行時間はトポロジーによって決まる部分が大きいようである。一般的にデータ構造内に格納されるデータ数によって、実行時間というのは決定されるが、それはグラフの接続状況によって決まるためである。
ベンチマーク問題集には、以下のように様々の種類の問題が用意されている。
ランダムに生成 : Long-C、Long-n、Random4-C、Random4-n、Square-C、Square-n
道路ネットワーク : USA-road-d、USA-road-t
ここで USA-road-d や USA-road-t は以前からかなり使用させてもらっているが、道路ネットワークになっている。TIGER/Line による交差点をノード、その間の距離を枝長としたデータをグラフデータに直し、実際に解けるように変換したものだ。
*-C となっているものは、1048576 nodes 4063200 arcs のグラフに対し、最大枝数を 4^X (X=[0, 15]) として与えられている。最も大きいものは Long-C.15.0.gr や Random4-C.15.0.gr や Square-C.15.0.gr といったグラフで、最大枝長は 1G (10 億) にも及ぶ。また *-n は、点数・最大枝数の大きさを 2^X (X=[14, 20])、枝数はその４倍程になっている。いまだにグラフ特性が良く分かっていないので、分かり次第載せていく。
ランダムに生成 : Long-C、Long-n、Random4-C、Random4-n、Square-C、Square-n
道路ネットワーク : USA-road-d、USA-road-t
ここで USA-road-d や USA-road-t は以前からかなり使用させてもらっているが、道路ネットワークになっている。TIGER/Line による交差点をノード、その間の距離を枝長としたデータをグラフデータに直し、実際に解けるように変換したものだ。
*-C となっているものは、1048576 nodes 4063200 arcs のグラフに対し、最大枝数を 4^X (X=[0, 15]) として与えられている。最も大きいものは Long-C.15.0.gr や Random4-C.15.0.gr や Square-C.15.0.gr といったグラフで、最大枝長は 1G (10 億) にも及ぶ。また *-n は、点数・最大枝数の大きさを 2^X (X=[14, 20])、枝数はその４倍程になっている。いまだにグラフ特性が良く分かっていないので、分かり次第載せていく。
Goldberg 氏によるベンチマーク問題について、いろいろ実験を行っている。
Heap と MLB は、異なるアルゴリズムではあるが、どちらも log によって計算量が抑えられているため、同じグラフ特性に対しては同じような性能を示している。枝長の分散が大きいグラフでは、MLB のほうが有効といえるが、それでも 20％ 向上する程である。
また、Heap に比べ MLB は 1.77 倍 もメモリ要求量が多いため、2 threads で実行してもまだ Heap のほうがメモリ要求量が少ない（グラフデータは共有しているため）。現在の計算機では SMP が当たり前になりつつあると思われるので、厳しい条件ではないと思われる。
Bucket は、あまりにも時間がかかりすぎてしまい、正直ソルバーとしては使いづらい。
Heap と MLB は、異なるアルゴリズムではあるが、どちらも log によって計算量が抑えられているため、同じグラフ特性に対しては同じような性能を示している。枝長の分散が大きいグラフでは、MLB のほうが有効といえるが、それでも 20％ 向上する程である。
また、Heap に比べ MLB は 1.77 倍 もメモリ要求量が多いため、2 threads で実行してもまだ Heap のほうがメモリ要求量が少ない（グラフデータは共有しているため）。現在の計算機では SMP が当たり前になりつつあると思われるので、厳しい条件ではないと思われる。
Bucket は、あまりにも時間がかかりすぎてしまい、正直ソルバーとしては使いづらい。
[Graph] : Long-n.21.0.gr #nodes 2,097,152 #arcs 8,126,432 length [0, 2097152] [Query] : Long-n.21.0.p2p (1000) Bucket 40652.3001[sec] (126.0 MB) Heap(1) 448.1252[sec] (134.0 MB) Heap(2) 228.4283[sec] (198.0 MB) MLB 408.6989[sec] (236.0 MB)
Goldberg 氏によるテスト問題集についても、自作ソルバーとの比較を行っている。
やはり Multi-Level-Bucket は、枝長のばらつきに強い。というのも、「ポテンシャル値を 2^n により挿入するバケットを選択する」という部分がかなり効いていると言える。
それに比べ Heap は、常に少メモリで安定した実行時間である。こちらのほうが実行時間の見積もりが立てやすい。
また、２プロセス同時に実行した際に、１プロセスでの結果との差（％）を比べてみた。特に L2 キャッシュを共有した際の性能低下が大きい。
やはり並列での実行を考えるなら、Heap がよいだろう。
やはり Multi-Level-Bucket は、枝長のばらつきに強い。というのも、「ポテンシャル値を 2^n により挿入するバケットを選択する」という部分がかなり効いていると言える。
それに比べ Heap は、常に少メモリで安定した実行時間である。こちらのほうが実行時間の見積もりが立てやすい。
また、２プロセス同時に実行した際に、１プロセスでの結果との差（％）を比べてみた。特に L2 キャッシュを共有した際の性能低下が大きい。
やはり並列での実行を考えるなら、Heap がよいだろう。
最短路オンラインソルバーであるが、Google Maps で始点終点を入力できるヴァージョンも一般公開した。DIMACS 9th で公開されている枝長が distance や time になっているグラフに対し最短路を求め、比較することができる。Google Maps をインターフェイスとしているが、内部のエンジンは自前である。
time のグラフでは、制限時速によって distance のグラフを修正しているために、それぞれの最短路ではかなり異なるということも珍しくない。time はスピードを出すことのできるであろう大きな道を積極的に通るのに対して、distance は単純に距離であるので小さな道であっても気にせず突き進んでいく。Google Maps の経路探索サービスでは、どちらかというと time の方に似た挙動を示すらしい。
ぜひ遊んでもらい、できれば意見をいただきたいものである。
time のグラフでは、制限時速によって distance のグラフを修正しているために、それぞれの最短路ではかなり異なるということも珍しくない。time はスピードを出すことのできるであろう大きな道を積極的に通るのに対して、distance は単純に距離であるので小さな道であっても気にせず突き進んでいく。Google Maps の経路探索サービスでは、どちらかというと time の方に似た挙動を示すらしい。
ぜひ遊んでもらい、できれば意見をいただきたいものである。
去年の中間発表は時間が足りずに途中で終了という悲惨な結果に終わってしまったのだが、今年はどうにか時間内に終わらせることが出来、ほっとしている。思ったよりも興味を持ってもらったようで、ひと安心である。
オンラインソルバーは専門家でなくても十分に楽しめると思うし、新たな発見があっておもしろい。それが普段利用している道であるならなおさらだ。やはり日本の道路データで実行してみたいものである。
オンラインソルバーは専門家でなくても十分に楽しめると思うし、新たな発見があっておもしろい。それが普段利用している道であるならなおさらだ。やはり日本の道路データで実行してみたいものである。
ひとまず、分かっていることを並べてみる。
１．比較回数・代入回数に関して
比較回数・代入回数が多いと実行時間に影響が出てくるが、
少ないから良いというわけでもない。
これは正直驚いた。
比較回数・代入回数は、ソートアルゴリズムに関して最も大きなウェイトを占めていると感じていたが、どうやらそうでもないようである。理由に関しては前回までの記事を確認して頂きたい。
２．データアクセスの局所性
Quick-Sort と Bucket-Sort での実行結果のみでは何とも言えないが、
確かに Quick-Sort の方が局所性という意味では良いように思える。
いくつか実際に実装してみてから、比べていこう。
１．比較回数・代入回数に関して
比較回数・代入回数が多いと実行時間に影響が出てくるが、
少ないから良いというわけでもない。
これは正直驚いた。
比較回数・代入回数は、ソートアルゴリズムに関して最も大きなウェイトを占めていると感じていたが、どうやらそうでもないようである。理由に関しては前回までの記事を確認して頂きたい。
２．データアクセスの局所性
Quick-Sort と Bucket-Sort での実行結果のみでは何とも言えないが、
確かに Quick-Sort の方が局所性という意味では良いように思える。
いくつか実際に実装してみてから、比べていこう。