Paper Info
Title
Accelerating Smith-Waterman Algorithm For Biological Database Search On Cuda-Compatible Gpus
Abstract
This paper presents a fast method capable of accelerating the Smith-Waterman algorithm for biological database search on a cluster of graphics processing units (GPUs). Our method is implemented using compute unified device architecture (CUDA), which is available on the nVIDIA GPO. As compared with previous methods, our method has four major contributions. (1) The method efficiently uses on-chip shared memory to reduce the data amount being transferred between off-chip video memory and processing elements in the GPO. (2) It also reduces the number of data fetches by applying a data reuse technique to query and database sequences. (3) A pipelined method is also implemented to overlap GPU execution with database access. (4) Finally, a master/worker paradigm is employed to accelerate hundreds of database searches on a cluster system. In experiments, the peak performance on a GeForce GTX 280 card reaches 8.32 giga cell updates per second (GCUPS). We also find that our method reduces the amount of data fetches to 1/140, achieving approximately three times higher performance than a previous CODA-based method. Our 32-node cluster version is approximately 28 times faster than a single GPO version. Furthermore, the effective performance reaches 75.6 giga instructions per second (GIPS) using 32 GeForce 8800 GTx cards.
Year
DOI
Venue
2010
10.1587/transinf.E93.D.1479
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
Keywords
Field
DocType
Smith-Waterman algorithm, sequence alignment, acceleration, GPU, CUDA
Graphics,Giga-,Shared memory,CUDA,Computer science,Parallel computing,Biological database,Smith–Waterman algorithm,Shared resource,Instructions per second
Journal
Volume
Issue
ISSN
E93D
6
1745-1361
Citations 
PageRank 
References 
12
0.82
17
Authors
3
Name
Order
Citations
PageRank
Yuma Munekawa1321.66
Fumihiko Ino231738.63
Kenichi Hagihara352856.94