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 程になってしまったため、実行不可能。もう少し小さいものでリトライしよう。
./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 程になってしまったため、実行不可能。もう少し小さいものでリトライしよう。