文献

J-GLOBAL ID：200902261955097270   整理番号：08A0499484

CUDAを用いたGPUによる全点対最短経路問題の実装比較

著者 (3件)： 奥山倫弘 (大阪大 基礎工) ,  伊野文彦 (大阪大 基礎工) ,  萩原兼一 (大阪大 基礎工)
資料名： 情報処理学会シンポジウム論文集  (情報処理学会ワークショップ論文集)
巻： 2008  号： 2  ページ： 58  発行年： 2008年01月17日 
JST資料番号： Y0978B  ISSN： 1344-0640  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフに含まれる2頂点u,vのすべての組に対して最短経路を求める全点対最短経路(APSP)問題について,1)単一始点最短経路(SSSP)を繰り返し求めるSSSP反復法,2)隣接行列形式でグラフを表すフロイド・ワーシャル法を用いたGPU(Graphics Processing Unit)実装が提案されている。本論文では,2)をCUDA(Compute Unified Device Architecture)のメモリ特性に合わせて改良し,i)隣接行列Aの行列要素を事前に共有メモリに転送してブロック内の複数スレッドで共有する手法,ii)coalesced readにできない行列要素の参照回数を最小にするためにAの1行を1ブロックで処理し,各ブロックごとに行列要素の値を共有メモリで共有する手法を実装した。GeForce 8800 GTXを用いてランダムグラフのAPSPを求める実験を行い,ii)ではA[i,k]=Lの場合にi行列の更新を省略することで最も短い実行時間を得られた。一方,グラフの頂点数|V|が多くなると1)が最短となるものの,最短経路を正しく求められない頂点が|V|=1Kのとき全体の14.2%も存在することを示した。

シソーラス用語： システムインタフェイス ,  *専用プロセッサ ,  *最短路問題 ,  グラフ ,  行列 ,  共有メモリ ,  マルチスレッド ,  *数値計算 ,  性能評価
準シソーラス用語： CUDA ,  *GPU【専用プロセッサ】 ,  隣接行列

分類 (3件)： 専用演算制御装置  (JC04030Y) ,  ネットワーク法  (KA03040X) ,  数値計算  (JE02000J)

タイトルに関連する用語 (5件)： CUDA ,  GPU ,  点 ,  最短経路問題 ,  実装