全対全最短路問題には Warshall-Floyd 法という有名な方法があるのだが、Dijkstra(ダイクストラ)法(１対全最短路問題）を点数の数と同じだけ繰り返して全対全最短路問題を解くこともできる。ところが、Warshall-Floyd 法は以下のようにメモリ要求量が厳しいので、グラフとしては小さい規模に属する DIMACS New York(NY) データ(264,346 点, 733,846 枝)を用いて解く場合でも、教科書通りにプログラムを作成すると 260GB ものメモリが必要になる。
最近では Warshall-Floyd 法を GPU 上に実装して全対全最短路問題を高速に解くという研究を見かけるようになった。上記の理由と現状の GPU のメモリ量を考慮すると中規模のグラフに対する Warshall-Floyd 法を GPU 上で実行するのは難しいので、小規模な問題で比較してみよう。
以下はランダムに生成された 点数 8,192, 枝数 32,768 の小さな規模の問題であり、GPU は１台(GTX 280) を用いた。CPU が 1 コアでは GPU の方が速いが、CPU 側もマルチスレッドで計算すると 4 コアぐらいで逆転する。最新の Tesla C2070 と Intel Core i7-970(6コア) で同じ対決をした場合には、同程度か後者の方が速いぐらいで少なくとも GPU の性能が CPU を圧倒することは無さそうだ。
ちなみに下記の計算サーバ(24コア)では、Dijkstra法 x 点数(8192) の実行が 0.51 秒で終了する。
○サーバ (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
前にも書いたように、１対全最短路問題（ダイクストラ法）の場合では全米データ(点数 23,947,347, 枝数 58,333,344)上で実行を行うと GPU : 672秒、CPU : 5秒と 100 倍ぐらいの差がある。一方、全対全最短路問題では小さい規模の場合 GPU の方が有利と思われいるようだが、意外とそうも言えないのである。
今日、実データから生成されるグラフ上の探索では、点数は数百万から十億を越える規模まで拡大しつつあり、クラスタ計算機やスパコンの CPU 上で分散して処理するか、CRAY XMT のようなマシンの大容量共有メモリ上において大量のスレッドを生成して処理するのが有望であろう。
最近では Warshall-Floyd 法を GPU 上に実装して全対全最短路問題を高速に解くという研究を見かけるようになった。上記の理由と現状の GPU のメモリ量を考慮すると中規模のグラフに対する Warshall-Floyd 法を GPU 上で実行するのは難しいので、小規模な問題で比較してみよう。
以下はランダムに生成された 点数 8,192, 枝数 32,768 の小さな規模の問題であり、GPU は１台(GTX 280) を用いた。CPU が 1 コアでは GPU の方が速いが、CPU 側もマルチスレッドで計算すると 4 コアぐらいで逆転する。最新の Tesla C2070 と Intel Core i7-970(6コア) で同じ対決をした場合には、同程度か後者の方が速いぐらいで少なくとも GPU の性能が CPU を圧倒することは無さそうだ。
ちなみに下記の計算サーバ(24コア)では、Dijkstra法 x 点数(8192) の実行が 0.51 秒で終了する。
○サーバ (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
前にも書いたように、１対全最短路問題（ダイクストラ法）の場合では全米データ(点数 23,947,347, 枝数 58,333,344)上で実行を行うと GPU : 672秒、CPU : 5秒と 100 倍ぐらいの差がある。一方、全対全最短路問題では小さい規模の場合 GPU の方が有利と思われいるようだが、意外とそうも言えないのである。
今日、実データから生成されるグラフ上の探索では、点数は数百万から十億を越える規模まで拡大しつつあり、クラスタ計算機やスパコンの CPU 上で分散して処理するか、CRAY XMT のようなマシンの大容量共有メモリ上において大量のスレッドを生成して処理するのが有望であろう。
アクセス
トータル
