| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-08-02 17:00 An Optimal Parallel Prefix-sums Algorithm on the Memory Machine Models for GPUs ○Koji Nakano（Hiroshima Univ.）  CPSY2012-15 |
|
| 抄録 | （和） | 本論文では，GPU向けの理論計算モデルDMMとUMM上の最適な並列接頭部和アルゴリズムを示す． これらのモデルは，３つのパラメタ，スレッド数$p$，メモリ幅$w$，メモリアクセスレイテンシ$l$を持つ． まず，$n$個の数の合計が$O({n\over w}+{nl\over p}+l\log n)$時間で求められることを示す． そして，合計を求める計算が少なくとも$\Omega({n\over w}+{nl\over p}+l\log n)$時間 必要であることを示す． 最後に，接頭部和が最適な$O({n\over w}+{nl\over p}+l\log n)$ 時間で求められることを示す． |
| （英） | The main contribution of this paper is to show optimal algorithms computing the sum and the prefix-sums on two memory machine models, the Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM). The DMM and the UMM are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. These models have three parameters, the number $p$ of threads, the width $w$ of the memory, and the memory access latency $l$. We first show that the sum of $n$ numbers can be computed in $O({n\over w}+{nl\over p}+l\log n)$ time units on the DMM and the UMM. We then go on to show that $\Omega({n\over w}+{nl\over p}+l\log n)$ time units are necessary to compute the sum. Finally, we show an optimal parallel algorithm that computes the prefix-sums of $n$ numbers in $O({n\over w}+{nl\over p}+l\log n)$ time units on the DMM and the UMM. |
|
| キーワード | （和） | メモリマシンモデル / 接頭部和 / 並列アルゴリズム / GPU / CUDA / / / |
| （英） | Memory machine models / Prefix-sums computation / Parallel algorithms / GPU / CUDA / / / | |
| 文献情報 | 信学技報, vol. 112, no. 173, CPSY2012-15, pp. 37-42, 2012年8月. | |
| 資料番号 | CPSY2012-15 | |
| 発行日 | 2012-07-26 (CPSY) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CPSY2012-15 |
|
| 研究会情報 | |
| 研究会 | DC CPSY |
| 開催期間 | 2012-08-02 - 2012-08-03 |
| 開催地（和） | とりぎん文化会館 |
| 開催地（英） | Torigin Bunka Kaikan |
| テーマ（和） | 2012年並列／分散／協調処理に関する『鳥取』サマー・ワークショップ（SWoPP鳥取2012） |
| テーマ（英） | Summer United Workshops on Parallel, Distributed and Cooperative Processing "Tottori" (SWoPP 2012) |
| 講演論文情報の詳細 | |
| 申込み研究会 | CPSY |
| 会議コード | 2012-08-DC-CPSY |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | An Optimal Parallel Prefix-sums Algorithm on the Memory Machine Models for GPUs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | メモリマシンモデル / Memory machine models |
| キーワード(2)（和/英） | 接頭部和 / Prefix-sums computation |
| キーワード(3)（和/英） | 並列アルゴリズム / Parallel algorithms |
| キーワード(4)（和/英） | GPU / GPU |
| キーワード(5)（和/英） | CUDA / CUDA |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中野 浩嗣 / Koji Nakano / ナカノ ヒロツグ |
| 第1著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima Univ. (略称： Hiroshima Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-08-02 17:00:00 |
| 発表時間 | 30分 |
| 申込先研究会 | CPSY |
| 資料番号 | CPSY2012-15 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.173 |
| ページ範囲 | pp.37-42 |
| ページ数 | 6 |
| 発行日 | 2012-07-26 (CPSY) |
[研究会発表申込システムのトップページに戻る]