SSCA#2 v2.2 その2

【計算機環境】
CPU : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz
GCC : 4.1.2
OS : linux 2.6.18-194.26.1.el5


● SSCA#2
計算量: ( BFS* + centrality ) x 1024 = ( 7/8O(m) + O(n) ) x 1024
※ BFS* は 7/8 しか探索しない BFS : 7/8 O(m)
※ centrality は DP で計算 : O(m)

n = 262144, m = 2097152
./SSCA2 8 18 ---> Kernel4 : 16.536 M E/s (113.637 sec.)


● 最短路ソルバ
点数枝数ともに "./SSCA2 8 18" で使用したグラフよりも大きな SSSP x 1024 を厳密に計算しても 23秒で計算することができるので、centrality の計算を入れたとしてもまだアドバンテージがあるだろう。

NY(n = 264346, m = 733846)
150.533 M E/s (4.992 sec.)

FLA(n = 1070376, m = 2712798)
121.780 M E/s (22.811 sec.)

ちなみに SSCA#2 で使用されているグラフは連結を仮定していないので、あまり参考にならないかもしれないが、SSCA#2 と同一の generator によるグラフに対する SSSP x 1024 の結果。

SSCA2_18(n = 262144, m = 2097152)
58.71759e M E/s (20.758 sec.)