超大規模グラフとダイクストラ法

超大規模グラフ(点数=1,073,741,824, 枝数=2,147,483,647 つまり点数 1G, 枝数 2G)を作成して１対全の最短路問題をダイクストラ法で解いてみた。インターネット等で調べた範囲ではこのような大規模なグラフに対して前処理無しで厳密にダイクストラ法を実行している例は見当たらない。この大きさになるとデータの読み込みにかかる時間が非常に多くを占めるようになる。

グラフデータの読み込み時間：1834秒
ダイクストラ法の実行時間：868秒
使用メモリ量：約 40Gbytes

ただし、ダイクストラ法の実行時間自体は 868 秒程度なので、一度メモリ上にデータを格納してしまえば、次からは 868 秒程度で別の始点を持つ１対全最短路問題を解くことができる。ダイクストラ法 with binary heap なので計算量が O((n+m)log(n)) だと仮定して、それぞれの場合について octave で計算すると 240 秒ぐらいが妥当なところで 868 秒というのは少し多めである。

> ((1073741824 + 2147483647) * log2(1073741824)) / ((23947347 + 58333344) * log2(23947347))
> 47.912

> 47.912 * 5
> 239.56

全米データ 24M点、58M枝 : 5秒
今回のデータ 1G点、2G枝 : 868秒

計算サーバ (4 CPU x 6 コア = 24 コア)：今回は１コアのみ使用
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64

ただし、計算量の中で log n の部分は binary heap に関するものなので、実際には全部の点(n 個)が全て heap に入ることはあまり起こらない。というわけで log n の n は実際の点数よりもかなり小さな値になると推測される。さらにグラフの巨大化によって L3 キャッシュのヒット率等にどのような変化があるのかを調べていく必要がある。



ダイクストラ法程度の計算量だと、計算時間よりも先にメモリ量が限界に達してしまう。128Gbytes メモリ搭載のマシンでももう少し枝を増やすとメモリが足らなくなってしまう。