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

情報処理学会 Web Site 被引用文献1件

書誌事項

タイトル別名
  • GPU ジョウ デ ノ コウソク ナ ブロックカ フロイド ・ ワーシャルホウ
  • Fast Blocked Floyd-Warshall Algorithm on the GPU

この論文をさがす

抄録

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

This paper proposes an acceleration method for the iterative blocked Floyd-Warshall (BFW) algorithm, aiming at solving the all-pairs shortest path problem rapidly on the graphics processing unit (GPU). The proposed method contains two variations, both designed to reduce data access to off-chip memory. The first one also reduces the number of instructions by using registers rather than shared memory. The remaining one increases the block size because it is inversely proportional to the amount of off-chip memory access. For graphs with 256-1,024 vertices, both variations demonstrate 4% faster performance than a previous method that employs a recursive BFW algorithm. For larger graphs, on the other hand, our iterative method is 1-10% slower than the recursive method. The proposed method achieves approximately 70% of peak computational performance.

収録刊行物

被引用文献 (1)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ