超大規模ネットワーク n=2^30, m=2^31-1 その1

n=2^30, m=2^31-1 という超大規模グラフを作成し、SSSP(1対全最短路問題) を計算してみた。

まず作成方法から。generator は 9th DIMACS で公開されている Goldberg のもの。使用方法は次の通りである。

./sprand.exe #nodes #arcs minLen maxLen seed > output.gr

「2^30 点, 2^31-1 枝数, 枝長 全て1」と指定しグラフを生成する。
Nehalem-EP 系の Xeon X5550 でも次のように 23 分もかかる。

time ./sprand.exe 1073741824 2147483647 1 1 971 > rand_1G_2G-1_1.gr

1133.70s user 87.21s system 89% cpu 22:46.73 total

さてお待ちかねの SSSP 実行時間。

(1) グラフファイル読み込み時間
server1: 1045.282 seconds
server2: 1088.592 seconds

(2) グラフ表現構築時間(Bucket-Sort)
server1: 789.239 seconds
server2: 1363.551 seconds

(3) SSSP (始点1の1対全最短路問題)
server1: 868.166 seconds
server2: 1890.330 seconds

○ server1 (4cores x 2sockets = 8cores)
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
GCC : 4.4.4

○ server2 (6cores x 4sockets = 24cores)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
GCC : 4.4.4