GPU上での高速なブロック化フロイド・ワーシャル法

スポンサーリンク

概要

論文の詳細を見る
本稿では,GPU (Graphics Processing Unit) を用いて全点対最短経路問題を高速に解くために,反復型ブロック化フロイド・ワーシャル法の高速化手法を提案する.提案手法は 2 種類あり,いずれもオフチップメモリの参照量を削減することで高速化を図る.1 つ目の手法は,共有メモリの代わりにレジスタを優先的に用い,命令数を削減する.もう 1 つの手法は,オフチップメモリの参照量がブロックの大きさに反比例することに着目し,より大きなブロックを用いる.既存の再帰型ブロック化手法と比較した結果,頂点数が 256〜1,024 個の場合,両手法ともに 4% 以上高速であった.頂点数が多い場合,性能は 1〜10% ほど下回った.GPU のピーク演算性能に対して 70% の効率を達成した.
2010-06-21

著者

関連論文

もっと見る

スポンサーリンク