講演抄録/キーワード |
講演名 |
2014-07-29 13:30
非同期階層メモリマシーンにおけるSummed Area Tableの並列アルゴリズムとそのGPU実装 ○笠置明彦・中野浩嗣・伊藤靖朗(広島大) CPSY2014-23 |
抄録 |
(和) |
CUDAを使用可能なGPUの理論的な非同期並列演算モデルを提案し、Summed Area Table(SAT)の高速な実装を行う。SATは各行各列に対して累積和を求める行列計算処理として知られている。SATの簡単なアルゴリズムは(2R2W SATアルゴリズム)は行方向の累積和を求め、次に行方向の累積和を求めるため、一つの要素に対して2回の読み出しと2回の書き込みを行うアルゴリズムである。本稿では一つの要素に対して1回の読み出しと1回の書き込みを行い、GPUのグローバルメモリへのアクセスに適した効果的なアルゴリズム(1R1W SAT アルゴリズム)を提案する。また、1R1Wアルゴリズムのパフォーマンスを向上させたアルゴリズム((1+r)R1W SAT アルゴリズム)を示す。本研究では各アルゴリズムをGeForce GTX 780 Tiに実装し、大きな行列に対する実行時間を計測した。その結果、提案アルゴリズムは単一コアのCPUを用いた逐次処理と比べて100倍以上の高速化を達成した。 |
(英) |
The main contribution of this paper is to introduce
the asynchronous Hierarchical Memory Machine (asynchronous HMM),
which supports asynchronous execution of CUDA blocks,
and show a global-memory-access-optimal parallel algorithm
for computing the SAT on the asynchronous HMM.
We also show a combined algorithm ($(1+r)$R1W SAT algorithm) of 2R1W and 1R1W SAT algorithms
that may have better performance.
We have implemented several algorithms on GeForce GTX 780 Ti.
The experimental results show that our $(1+r)$R1W SAT algorithm runs faster than any other
SAT algorithms for large input matrices.
Also, it runs more than 100 times faster than the best SAT algorithm using a single CPU. |
キーワード |
(和) |
メモリマシンモデル / prefix-sums / summed area table / GPU / CUDA / / / |
(英) |
memory machine models / prefix-sums / summed area table / GPU / CUDA / / / |
文献情報 |
信学技報, vol. 114, no. 155, CPSY2014-23, pp. 79-84, 2014年7月. |
資料番号 |
CPSY2014-23 |
発行日 |
2014-07-21 (CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CPSY2014-23 |
研究会情報 |
研究会 |
CPSY DC |
開催期間 |
2014-07-28 - 2014-07-30 |
開催地(和) |
朱鷺メッセ 新潟コンベンションセンター |
開催地(英) |
Toki Messe, Niigata |
テーマ(和) |
並列/分散/協調とディペンダブルコンピューティングおよび一般 |
テーマ(英) |
Parallel, Distributed and Cooperative Processing |
講演論文情報の詳細 |
申込み研究会 |
CPSY |
会議コード |
2014-07-CPSY-DC |
本文の言語 |
日本語 |
タイトル(和) |
非同期階層メモリマシーンにおけるSummed Area Tableの並列アルゴリズムとそのGPU実装 |
サブタイトル(和) |
|
タイトル(英) |
Parallel Algorithms for the Summed Area Table on the Asynchronous Hierarchical Memory Machine, with GPU implementations |
サブタイトル(英) |
|
キーワード(1)(和/英) |
メモリマシンモデル / memory machine models |
キーワード(2)(和/英) |
prefix-sums / prefix-sums |
キーワード(3)(和/英) |
summed area table / summed area table |
キーワード(4)(和/英) |
GPU / GPU |
キーワード(5)(和/英) |
CUDA / CUDA |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
笠置 明彦 / Akihiko Kasagi / カサギ アキヒコ |
第1著者 所属(和/英) |
広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.) |
第2著者 氏名(和/英/ヨミ) |
中野 浩嗣 / Koji Nakano / ナカノ コウジ |
第2著者 所属(和/英) |
広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.) |
第3著者 氏名(和/英/ヨミ) |
伊藤 靖朗 / Yasuaki Ito / イトウ ヤスアキ |
第3著者 所属(和/英) |
広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2014-07-29 13:30:00 |
発表時間 |
25分 |
申込先研究会 |
CPSY |
資料番号 |
CPSY2014-23 |
巻番号(vol) |
vol.114 |
号番号(no) |
no.155 |
ページ範囲 |
pp.79-84 |
ページ数 |
6 |
発行日 |
2014-07-21 (CPSY) |