CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))

  • 奥山 倫弘
    大阪大学基礎工学部情報科学科
  • 伊野 文彦
    大阪大学大学院情報科学研究科コンピュータサイエンス専攻
  • 萩原 兼一
    大阪大学大学院情報科学研究科コンピュータサイエンス専攻

書誌事項

タイトル別名
  • Accelerating All-Pairs Shortest Path Problem Using CUDA

この論文をさがす

説明

本論文では全点対最短経路(APSP:All-Pairs Shortest Path)問題をGPU(Graphics Processing Unit)を用いて高速化した結果を述べる.提案手法は,GPUで動作するプログラムをGPU向けの開発環境CUDA(Compute Unified Device Architecture)を用いて記述する.アルゴリズムには単一始点最短経路を繰り返し求める手法(SSSP反復法)を用いる.問題全体での逐次処理を減らしてより高い速度向上を得るために,1っのSSSP問題を1つのタスクとし,それらのタスクを並列処理する.さらに,共有メモリを用いてタスク間でデータを共有し,グローバルメモリの参照を削減する.結果,既存手法よりも3.5〜18倍高速であった.また,SSSP反復法の性能がグラフの特性に依存して変動することを示す.

収録刊行物

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

  • CRID
    1574231877019766400
  • NII論文ID
    110006828689
  • NII書誌ID
    AN10463942
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ