GPU とグラフアルゴリズム その３

すでに GPU とグラフアルゴリズムのその１とその２で見てきたように、グラフアルゴリズムでは、少なくとも現時点において CPU の方にかなり分があると言って良い。特に大規模なデータになると CPU の独壇場である。

1: 1対全最短路問題に対するダイクストラ法は CPU 上での実行の方が GPU 上での実行よりもはるかに速い
2: 全対全最短路問題に対する Warshall-Floyd 法でも CPU の方が優勢(小規模な問題しか GPU 上では扱うことができない)

ところで、以下は CPU 上でのダイクストラ法の計算量と実行時間の関係であるが、意外に両者が精度良くフィッティングできている。ダイクストラ法 with バイナリヒープの実行時間は with MLB(マルチレベルバケット)の方計算量にむしろフィッティングしている。



全米データ (24M点, 58M枝)で 5秒程度の実行時間なので、点数、枝数を 100 倍して 2.4G点, 5.8G枝(つまり 24億点、58億枝) の場合では、O((n+m)log(n)) の計算量で増大すると仮定すると 100 x log(100) = 664.39 倍の計算時間、つまり 5 秒 x 664.39 = 3321.9 秒になる（実際にはもっと少ないだろう）。さすがに前処理無しでこの規模のグラフの 1対全最短路問題を解くのは相当大変だろう。