長崎大学のGPUスパコンのアルゴリズム

エントリを変えて、長崎大学のGPUスパコンで使われたアルゴリズムについてみてみたい。資料はhttp://www.ssken.gr.jp/MAINSITE/activity/sectionmeeting/sci/2009-2/lecture-1/ppt.pdfにある。
このアルゴリズムは、一般的にはTree法とかFMMと言われている物で、詳しくはhttp://www.artcompsci.org/~makino/papers/doboku/doboku.htmlあたりを参照するといいと思う。重要なのは、大体FFTなんかと同じような計算量だという点だ。上の記事にあるMathmaticaのベンチマークの中に、FFTの結果もある。Discrete Fourier Transformと書かれているのがそれだ。これが64bitで高速になっていることからもわかるように、実はこの問題はかなりI/O boundな問題なのだ。Tree法やFMMについても同様の性質があり、やはりI/O boundと考えてよいと思う。
先に書いたように、一般のN体問題であればCPU boundなのでGPUで高速化が容易だったというのは比較的当然だったのだが、今回はI/O boundな問題をGPUで高速化できたという点が非常に興味深い。