USA 1000 queries。

現段階での最短路ソルバーの実行時間を計測してみた。

CPU : Xeon E5345 2.33 GHz (L2 4MB) (4core x 2)
OS : CentOS 5.1 64bit
GCC : 4.1.2

Graph : USA-road-d.USA.gr
Query : USA-road-d.USA.p2p （ランダムな 1000 クエリ、こちらからいただきました）

結果としては 1, 2, 4 ではリニアに性能が伸びているが、8 スレッドにすると性能が伸びずバケット法では悪化してしまう。FSB のバンド幅がボトルネックになってしまっているのであろう。他の CPU （AMD 系など）でも試してみよう。