最適化問題に対する超高速&安定計算

大規模最適化問題、グラフ探索、機械学習やデジタルツインなどの研究のお話が中心

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

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

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

ただし、ダイクストラ法の実行時間自体は 868 秒程度なので、一度メモリ上にデータを格納してしまえば、次からは 868 秒程度で別の始点を持つ1対全最短路問題を解くことができる。ダイクストラ法 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 コア):今回は1コアのみ使用
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 メモリ搭載のマシンでももう少し枝を増やすとメモリが足らなくなってしまう。
コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« Westmere-EP | トップ | 全対全最短路と媒介中心性 »
最新の画像もっと見る

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。

Weblog」カテゴリの最新記事