WEKO3
アイテム
CUDAによる全点対最短経路問題の高速化
https://ipsj.ixsq.nii.ac.jp/records/22877
https://ipsj.ixsq.nii.ac.jp/records/2287748e8e562-803e-4f2a-a34a-ac10a7cb0f3b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-ARC08177025.pdf (619.5 kB)
|
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2008-03-06 | |||||||
| タイトル | ||||||||
| タイトル | CUDAによる全点対最短経路問題の高速化 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Accelerating All-Pairs Shortest Path Problem Using CUDA | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報科学科 | ||||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報科学科 | ||||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報科学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka University | ||||||||
| 著者名 |
奥山, 倫弘
× 奥山, 倫弘
|
|||||||
| 著者名(英) |
Tomohiro, Okuyama
× Tomohiro, Okuyama
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では全点対最短経路（APSP：All-Pairs Shortest Path）問題をGPU（Graphics Processing Unit）を用いて高速化した結果を述べる．提案手法は，GPUで動作するプログラムをGPU向けの開発環境CUDA（Compute Unified Device Architecture）を用いて記述する．アルゴリズムには単一始点最短経路を繰り返し求める手法（SSSP反復法）を用いる．問題全体での逐次処理を減らしてより高い速度向上を得るために，1つのSSSP問 題を1つのタスクとし，それらのタスクを並列処理する．さらに，共有メモリを用いてタスク間でデータを共有し，グローバルメモリの参照を削減する．結果，既存手法よりも3.5～18倍高速であった．また，SSSP反復法の性能がグラフの特性に依存して変動することを示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper presents acceleration results of the all-pairs shortest path (APSP) problem on a graphics processing unit (GPU). The proposed method is implemented using compute unified device architecture (CUDA), which offers the development environment for GPUs. The method is based on an iterative algorithm that repeatedly computes single-source shortest paths (SSSPs). In order to obtain a higher speedup, we decrease the sequential part of the algorithm by processing SSSP problems in parallel. Furthermore, we reduce the access to global memory by using shared memory, which allows tasks to share data between them. As a result, our method is 3.5-18 times faster than an existing method. We also show that the iterative method varies the performance depending on the characteristic of the graph. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10096105 | |||||||
| 書誌情報 |
情報処理学会研究報告計算機アーキテクチャ（ARC） 巻 2008, 号 19(2008-ARC-177), p. 145-150, 発行日 2008-03-06 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
