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

アルゴリズムやデータ構造の性質から、グラフアルゴリズムは GPU との相性は良くない。しかし、以下の論文では苦手のグラフアルゴリズムを GPU でどれだけ高速化できるかということについて挑戦を行っている。多くの GPU の研究(特に国内)は明らかに GPU で性能が出しやすい題材しか扱っていないので、以下の論文のチャレンジ精神は賞賛に値する。

Large Graph Algorithms for Massively Multithreaded Architectures

以下は CPU 上でのダイクストラ法（最短路問題）の実験結果になるが、これと比較すると例えば全米データで１対全の最短路問題を解いたときに CPU では 5 秒程度で終了するが、GPU(Tesla) 上では 672秒かかっている（上記の論文の２３ページ）。ただし、５秒というのはかなり手間隙かけてプログラムを作成した場合の結果なので、グラフのデータ構造やアルゴリズム及びプログラミングに詳しくない人が CPU 上で作るプログラムよりは上記の論文の GPU プログラムの方が速くなっていると推測する。下記の naive Dijkstra でもアルゴリズムの教科書に載っているダイクストラ法をそのまま実装するよりも速い。