オーバークロックと最短路。

研究室の Penryn コアのマシンをオーバークロックしたので、実験行った。いつも通り p2p タイプの１０個のクエリの最短路問題を解いてみた。１０クエリであるので、始点終点のペアが１０対に対してダイクストラ法を実行したものである。用いているクエリファイルものせておく。つまり１つ１つは１～２秒で実行できる。それに比べ、グラフ読み込みが４０～５０秒とかなりかかってしまうので、どうにかならないものかと思ってしまう。

[p2p タイプの１０個のクエリ]
p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879



[環境]
CPU : Core2Duo E8200 2.66GHz
Mem : 4GB
CentOS 5.1 / gcc 4.1.2

[データの見方]
「使用したデータ構造」、「実行時間」、「オーバークロックによる高速化」、「オーバークロックした比率との割合」


[Penryn 2.66 GHz]
１レベルバケット　　　16.34 [sec]
マルチレベルバケット　 ---
ヒープ　　　　　　　　26.66 [sec]

[Penryn 3.56 GHz] (x1.34)
１レベルバケット　　　12.88 [sec] (x1.27 : 94%)
マルチバケット　　　　18.58
ヒープ　　　　　　　　20.68 [sec] (x1.29 : 96%)

[Penryn 3.92 GHz] (x1.47)
１レベルバケット　　　11.74 [sec] (x1.29 : 87%)
マルチバケット　　　　16.85
ヒープ　　　　　　　　18.80 [sec] (x1.42 : 96%)



ヒープはどちらもクロックを上げた分だけ、高速化されていることがわかる。それに比べ、バケット法はまだまだ速くなるだろう。ちなみに「マルチバケット」は Goldberg 氏のもので、9th DIMACS Implementation Challenge から持ってきたものだが、いろいろ実行してみると２レベルだけというわけではないようなので、このようにした。