超大規模グラフ作成 n=2^30, m=2^32

Goldberg による benchmark graph generator を使用して n=2^30, m=2^32 という超大規模グラフを作成してみた。作成には 1 時間ほどかかる。

./sprand.exe 1073741824 4294967296 1 1 971 > rand_1G_4G_1_931.gr  3048.89s user 201.03s system 98% cpu 54:57.39 total

大きさのイメージが掴みにくいので、全米道路ネットワークグラフの USA-road-d.USA.gr を基準に考えてみよう。このグラフは 23947347 点 58333344 枝である。

● ファイルサイズ
102769815175(96G) / 1387075114(1.3G) = 74.091 倍となる。

● 点数・枝数
点数は 2^30 / 23947347 = 44.849 倍、
枝数は 2^32 / 58333344 = 73.619 倍となる。

● SSSP, P2PSP 実行のための領域
USA : (4 * 24M + 8 * 58M) + (16 * 24M) * #threads = 560MB + 384MB * #threads + Priority Queue
(8 * 2^30 + 16 * 2^32) + (24 * 2^30) * #threads = 72GB + 24GB * #threads + Priority Queue

思ったよりも Priority Queue サイズが大きく、一時的にも 160 GB 程になってしまったため、実行不可能。もう少し小さいものでリトライしよう。