CPUとGPUと最短路問題

以下の論文では Tesla S1070 などの GPU を用いて様々なグラフ上での探索アルゴリズムが実装されている。例えば DIMACS 全米データ(24M 点、58M 枝)では 1 対全の最短路が GPU を用いて 672 秒で求めることができる。

http://dl.dropbox.com/u/12413370/pawan09GraphAlgorithms.pdf

そして CPU 上で動作するソフトウェア msp では、以下のサーバ(24コア)を用いて全米データを解いてみた。

○ 1分8秒 : 256　クエリ

よって 68(秒：実行時間) * 24（コア) / 256(クエリ) = 6.375 秒なので、1 コア, 1 最短路あたりの実行時間は 6 秒程度となる。

○ 計算サーバ (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64