CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
スポンサーリンク
概要
- 論文の詳細を見る
本論文では全点対最短経路(APSP:All-Pairs Shortest Path)問題をGPU(Graphics Processing Unit)を用いて高速化した結果を述べる.提案手法は,GPUで動作するプログラムをGPU向けの開発環境CUDA(Compute Unified Device Architecture)を用いて記述する.アルゴリズムには単一始点最短経路を繰り返し求める手法(SSSP反復法)を用いる.問題全体での逐次処理を減らしてより高い速度向上を得るために,1っのSSSP問題を1つのタスクとし,それらのタスクを並列処理する.さらに,共有メモリを用いてタスク間でデータを共有し,グローバルメモリの参照を削減する.結果,既存手法よりも3.5〜18倍高速であった.また,SSSP反復法の性能がグラフの特性に依存して変動することを示す.
- 2008-03-05
著者
-
伊野 文彦
大阪大学大学院情報科学研究科コンピュータサイエンス専攻
-
萩原 兼一
大阪大学大学院情報科学研究科コンピュータサイエンス専攻
-
萩原 兼一
大阪大学大学院情報科学研究科
-
奥山 倫弘
大阪大学大学院情報科学研究科コンピュータサイエンス専攻
-
奥山 倫弘
大阪大学基礎工学部情報科学科
-
伊野 文彦
大阪大学大学院情報科学研究科
関連論文
- CUDAによる高速なコーンビーム再構成の実装と性能評価(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- D-11-80 GPUによるTotal Variation Minimization法の高速化(D-11.画像工学,一般セッション)
- GPUグリッドにおいて描画および科学計算を並行処理するための制御手法(カーネル)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- GPUによるOSEM再構成の高速化及び精度評価(医用システム,システム開発論文)
- 大規模データセットを可視化するための効率の良い並列ボリュームレンダリング(並列処理応用)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- GPUによるOSEM再構成の高速化および精度評価(基盤技術1)
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- 時系列ボリュームレンダリングの描画速度を調節するための非可逆圧縮手法
- GPUを用いたコーンビーム再構成の性能評価と精度検証(画像再構成)
- 複数のCUDA互換GPUによるストリーム処理のためのミドルウェア
- CUDAカーネルの性能を解析するための実行履歴生成ツール
- CUDAプログラムにおいてストリーム処理を支援するミドルウェア
- GPUクラスタによる高速なアミノ酸配列データベース検索
- CUDAによるパラメータ・スイープアプリケーションの高速化
- CUDAを用いた高速なモルフォロジー演算
- CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 統合開発環境CUDAを用いたGPUでの配列アライメントの高速化手法(メモリアクセス,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- CUDAによる高速なコーンビーム再構成の実装と性能評価(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 統合開発環境CUDAを用いたGPUでの配列アライメントの高速化手法(メモリアクセス,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- GPU上での高速なブロック化フロイド・ワーシャル法
- 複数の並列計算環境に対応したMapReduceのPythonによる実装
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 術中二次元/三次元剛体位置合せのための並列化手法(ディペンダブルコンピューティング)
- GPUを用いてコーンビームCTのボリューム再構成を高速化する手法(一般セッション,センシング技術とその応用)
- GPU内部におけるプロセッサ間の命令移動による高速化ツール
- GPUアプリケーションを高速化するための命令割当て方式(GPU応用)
- デスクトップ・ボリュームレンダリングのための解像度制御によるビデオメモリ使用量削減(ハードウエアによるCG処理およびCG一般)
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- デスクトップグリッド環境でのマルチジョブスケジューリングにおけるジョブの追い越しを防ぐジョブ優先度制御
- A_002 企業イントラグリッドでのジョブ割当てアルゴリズムの比較評価(A分野:モデル・アルゴリズム・プログラミング)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップDBWS2005)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップ2005)
- グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(シンポジウム)
- PCクラスタを用いた並列非剛体位置合わせ手法の性能評価(可視化・レジストレーション)
- タスク複製率とプロセッサ***率に着目したBSPスケジュール生成手法の提案
- グリッド環境において計算結果を効率よく再利用するための通信量削減(HPC-2 : 通信方式)
- D-16-7 GPUを用いた逐次近似法によるコーンビーム再構成の高速化(D-16.医用画像,一般セッション)
- GPUを用いたアウトオブコアなコーンビーム再構成の高速化
- スケール不変な格子を生成する適応格子細分化法アプリケーションのための計算量予測手法(アルゴリズム理論)
- グリッドアプリケーションの実行時間を短縮するための計算結果再利用機構の評価
- 適応格子細分化法を用いる画像処理のための実行時間予測手法(ポスターセッション)
- 汎用グラフィクスハードウェアを用いた2次元/3次元剛体位置合わせの高速化(コンピュータグラフィックス)
- 汎用グラフィクスハードウェアを用いた2方向投影による2次元/3次元剛体位置合わせ(再構成他, 医用画像一般)
- 汎用グラフィクスハードウェアを用いた2次元/3次元剛体位置合わせの高速化(HPCシステム)
- フラクタル解析による適合格子細分化法の計算量予測
- 短時間処理向け資源管理を実現するためのGlobus Toolkitの性能評価(グリッド(2), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- PCクラスタを用いた2次元/3次元剛体位置合わせの高速処理(レジストレーション・イメージマッチング)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- MI-Cluster : 術中医用画像処理を実現するPCクラスタシステム
- 夢はバラ色 予測医学基盤オープンプラットフォームの構築に向けて
- 手術ロボットのための医用画像処理技術 : 最近の進展と将来の方向 : 日本学術振興会未来開拓学術推進事業「術中における多次元画像の獲得と利用」の成果を中心として
- GPUによる高速なコーンビーム再構成:円軌道装置のためのRGBAデータへの詰め込み
- GPUを用いてコーンビームCTのボリューム再構成を高速化する手法(一般セッション,センシング技術とその応用)
- 複数の並列計算環境に対応した MapReduce の Python による実装
- B-007 実時間グリッド計算のための資源割当システムの設計(B.ソフトウェア)
- 分散メモリ型並列計算機を用いた非剛体レジストレーションの並列化
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- 並列型画像処理ライブラリの高効率化(JAMITセッション)
- 3次元並列型画像処理ライブラリ開発における基礎的検討(再構成他, 医用画像一般)
- GPGPUアプリケーションの開発を支援するための性能モデル(GPU応用)
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- プログラマブルGPUにおけるLU分解の設計と実装(GPU応用)
- D-11-90 大規模なマルチスケールボリュームレンダリングのための先読み手法の検討(D-11.画像工学D(画像処理・計測),一般講演)
- GPUによる高速な全変動最小化
- GPUを装備する計算機を計算資源とするグリッドにおける資源選択手法の検討
- メッセージ通信プログラムにおける性能解析のための大規模な実行履歴の生成(システム性能評価)
- (83)通常講義の中でのPBL演習の試み(第21セッション 創成教育(I))
- ボリュームレンダリングにおける効率的なテクスチャ参照
- 累積不透明度の伝搬による並列ボリュームレンダリングの計算量削減(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-6並列分散ソフトウェア)
- 投影面分割に基づく階層的な画像合成手法を用いた並列ボリュームレンダリング
- 投影面分割に基づく階層的な画像合成手法を用いた並列ボリュームレンダリング(高速ネットワークとマルチメディアアプリケーション)
- 分散メモリ型並列計算機による高解像度ボリュームレンダリング(バイオメトリクスシステムおよび一般)
- GPUによる高速な全変動最小化(計算機システム)
- GPUグリッドによる高速な塩基配列アライメント(HPC-5 : アプリケーションI)
- GPUを用いたモルフォロジー演算のベクトル化(セッション5 :CG処理の高速化,テーマ:CGと記録及びCG一般)
- グリッド環境において遊休GPUを活用するための資源選択手法(Session 3:Cluster/Grid)
- D-16-8 GPUを用いたモルフォロジー演算の高速化手法(D-16.医用画像,一般講演)
- 部分的なタスク実行によるマスタスレーブ型並列プログラムの高速な性能予測(アプリケーションとその並列化)
- 並列プログラムの性能改善支援機能を持つ性能解析システム : Gordini(並列処理)
- MPI-PreDebugger : 通信依存解析に基づくメッセージ通信並列プログラム向けデバッグ支援ツール
- LogGPS : メッセージ通信プロトコルの切替えを考慮した高水準通信ライブラリ向けの並列計算モデル
- CUDAプログラムにおけるメモリ参照効率を解析するための実行履歴生成手法
- 遺伝子配列に対するペアワイズアライメントのGPUによる高速化
- 重複排除ストレージにおけるSHA-1計算のSSEによるスループット向上手法
- 正規化相互情報量に基づく非剛体位置合わせのCUDAによる高速化 (医用画像)
- GPUにおいてパラメータスイープを高速化するための並列方式
- 正規化相互情報量に基づく非剛体位置合わせのCUDAによる高速化(位置合わせ・神経回路,ポスターティーザー1,統計モデルとその応用,医用画像一般)
- 協調マルチタスキングを用いて短い遊休時間を活用するGPUグリッドシステムの提案
- GPUを用いた分枝限定法におけるメモリ参照効率を高めるための配列パッキング手法