文献

J-GLOBAL ID：201802264215043932   整理番号：18A0708112

GPU上でのBellman-Fordアルゴリズムの効率的実装【JST・京大機械翻訳】

Efficient implementation of the Bellman-Ford algorithm on GPU

著者 (2件)： Nazarifard Marjan (Salman Institute of Higher Education, Mashhad, Iran) ,  Bahrepour Davoud (Mashhad Branch, Islamic Azad University, Mashhad, Iran)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： KBEI  ページ： 0773-0778  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 単一ソース最短経路(SSSP)問題は,グラフ解析における一般的アルゴリズムである。Bellman-Fordは,ソースノードへの最短経路を解くための基本的アルゴリズムであり,グラフにおける負の重みづけサイクルの検出を可能にする。さらに,それは,並列アルゴリズムのクラス,メモリアクセス,および作業分布が不規則でデータ依存性であることを示した。近年,グラフィックスプロセッサは,スーパーコンピュータにおける加速器と同様に多くのアルゴリズムを実装するために使用されている。いくつかのSSSPアルゴリズムを,図形処理ユニット(GPU)に基づいて提案した。それらの各々は,特定のタイプのグラフを横断することができた。本論文では,CUDAを用いてGPU上のBellman-Fordアルゴリズムを加速し,それにより,以前のアルゴリズムと比較して,最短時間内に高密度でまばらなグラフ(規則的で不規則な)を追跡することができた。シミュレーション結果によると,提案した実装は,従来の並列実装アルゴリズムの大部分と比較して,1.87×の平均スピードアップを提供した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【JST・京大機械翻訳】

シソーラス用語： シミュレーション ,  加速器 ,  高速化 ,  並列アルゴリズム ,  グラフ ,  重みづけ ,  図式解法 ,  スーパコンピュータ ,  *アルゴリズム
準シソーラス用語： 並列実装 ,  CUDA ,  GPU【プロセッサ】 ,  データ依存性 ,  メモリアクセス ,  最短経路 , 【Automatic Indexing@JST】

分類 (2件)： 計算理論  (JB02000A) ,  ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (3件)： GPU ,  アルゴリズム ,  実装