講演抄録/キーワード |
講演名 |
2009-12-03 10:20
Smith-WatermanアルゴリズムにおけるGPUを用いた実装方法の一提案 ○土肥慶亮(長崎大)・Ling Cheng(エディンバラ大)・濱田 剛・柴田裕一郎・小栗 清(長崎大)・Khaled Benkrid(エディンバラ大) CPSY2009-43 |
抄録 |
(和) |
本稿では,Smith-Waterman (SW) アルゴリズムをGPU上で並列計算させるための設計,実装を行う.実装では,二つのシーケンスのアライメントマトリックスを小領域に分割し,それらをwarp単位でスレッドに割り当て計算を行う.評価の結果,9.09 GCUPS (Giga Cell Update per Second) から12.71 GCUPSの性能を達成し,4つのGPUコアを用いた場合では,29.46GCUPSから43.05GCUPSの性能を達成した.現在発表されている最も高速なGPU上での実装と比較して,最大46%の高速化に成功した. |
(英) |
This paper describes a implementation of the Smith-Waterman (SW) algorithm on GPUs. Central to this is a divide and conquer approach which divides the computation of a whole pairwise sequence alignment matrix into multiple sub-matrices (or parallelograms) each running efficiently on the available hardware resources of the GPU. Moreover, we use thread warps and padding techniques in order to decrease the cost of thread synchronization. As a result, our implementation of the SW algorithm achieves a throughput ranging between 9.09 GCUPS (Giga Cell Update per Second) and 12.71 GCUPS on a single-GPU version, and a throughput between 29.46 GCUPS and 43.05 GCUPS on a quad-GPU platform. Compared with the best GPU implementation of the SW algorithm reported to date, our implementation achieves up to 46% improvement in speed. |
キーワード |
(和) |
Smith Waterman アルゴリズム / GPGPU / CUDA / / / / / |
(英) |
Smith Waterman algorithm / GPGPU / CUDA / / / / / |
文献情報 |
信学技報, vol. 109, no. 319, CPSY2009-43, pp. 1-6, 2009年12月. |
資料番号 |
CPSY2009-43 |
発行日 |
2009-11-26 (CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CPSY2009-43 |