GPUスレッド生成手法切り替えによるSSSP探索の高速化
スポンサーリンク
概要
- 論文の詳細を見る
グラフの 1 ノードから他の全てのノードへの最短距離と経路を求める SSSP(Single-Source Shortest Path) 探索は,その処理の並列性の高さから GPU を用いて計算が高速化できることが知られている.SSSP 探索の計算は,グラフの始点ノードから全ノードへの距離情報が収束するまで計算を繰り返すことにより実現するが,情報が更新されるノード数は反復処理の各回で大きく異なる.従来手法では更新ノード数が少ない回でもグラフの全ノード分の GPU スレッドを生成するが,特に大規模なグラフでは更新処理を行わない無駄なスレッドが多数発生し,スレッド生成のオーバヘッドが増大する課題があった.本稿では,更新ノード数が少ない回は更新が行われるノードを計算する GPU スレッドだけを生成し,更新ノード数が多い回は更新ノードをカウントするオーバヘッドを避けるためにカウントを行わずにグラフの全ノード分のスレッドを生成する手法を提案する.これにより,143 万ノードの関東地図に対する SSSP 計算において従来手法より処理性能を 18% 向上した.
- 2013-11-19
著者
関連論文
- 5.広域災害に対するストレージによるデータ保護(非常災害に向けた高度情報通信ネットワークの構成と制御)
- ディザスタリカバリアーキテクチャ概説 (事業継続・災害対策特集) -- (NECのBCサービス・ソリューション)
- 中継バッファ方式の災害復旧時間短縮手法(ストレージ応用技術, SWOPP武雄2005 (2005年並列/分散/協調処理に関する「武雄」サマー・ワークショップ))
- 中継バッファ装置を用いた災害対策方式(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))
- データインテンシブコンピューティングの省電力化に向けたGPUノードの活用(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- D-4-8 過去に遡った検索を実現する情報検索システムの提案(D-4.データ工学,一般講演)
- クラウド時代を支えるグリーンなデータセンタのストレージ技術動向 (特集 クラウドを支えるデータストレージ技術)
- D-5-11 時空間に対する連想記憶を刺激するトピック提示手法(D-5. 言語理解とコミュニケーション,一般セッション)
- 高度なテレマティクスサービスを実現するデータ活用プラットフォーム
- 高度なテレマティクスサービスを実現するデータ活用プラットフォーム
- 分散データストアシステムに対するEnergyCapping制御
- GPUスレッド生成手法切り替えによるSSSP探索の高速化