アルゴリズムやデータ構造の性質から、グラフアルゴリズムは GPU との相性は良くない。しかし、以下の論文では苦手のグラフアルゴリズムを GPU でどれだけ高速化できるかということについて挑戦を行っている。多くの GPU の研究(特に国内)は明らかに GPU で性能が出しやすい題材しか扱っていないので、以下の論文のチャレンジ精神は賞賛に値する。 Large Graph Algorithms for Massively Multithreaded Architectures 以下は CPU 上でのダイクストラ法(最短路問題)の実験結果になるが、これと比較すると例えば全米データで1対全の最短路問題を解いたときに CPU では 5 秒程度で終了するが、GPU(Tesla) 上では 672秒かかっている(上記の論文の23ページ)。ただし、5秒というのはかなり手間隙かけてプログラムを作成した場合の結果
![GPU とグラフアルゴリズム その1 - 最適化問題に対する超高速&安定計算](https://cdn-ak-scissors.b.st-hatena.com/image/square/3279cffe14ce2c50d7d5bc67a6209ef70f59729a/height=288;version=1;width=512/http%3A%2F%2Fblogimg.goo.ne.jp%2Fuser_image%2F7f%2F33%2F42df6c2bea9198d1f981e6dfc94ab35a.png)