title: CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions.
abstract: BACKGROUND
  The maximal sensitivity for local alignments makes the Smith-Waterman algorithm a popular choice for protein sequence database search based on pairwise alignment. However, the algorithm is compute-intensive due to a quadratic time complexity. Corresponding runtimes are further compounded by the rapid growth of sequence databases.
  
  
  RESULTS
  We present CUDASW++ 3.0, a fast Smith-Waterman protein database search algorithm, which couples CPU and GPU SIMD instructions and carries out concurrent CPU and GPU computations. For the CPU computation, this algorithm employs SSE-based vector execution units as accelerators. For the GPU computation, we have investigated for the first time a GPU SIMD parallelization, which employs CUDA PTX SIMD video instructions to gain more data parallelism beyond the SIMT execution model. Moreover, sequence alignment workloads are automatically distributed over CPUs and GPUs based on their respective compute capabilities. Evaluation on the Swiss-Prot database shows that CUDASW++ 3.0 gains a performance improvement over CUDASW++ 2.0 up to 2.9 and 3.2, with a maximum performance of 119.0 and 185.6 GCUPS, on a single-GPU GeForce GTX 680 and a dual-GPU GeForce GTX 690 graphics card, respectively. In addition, our algorithm has demonstrated significant speedups over other top-performing tools: SWIPE and BLAST+.
  
  
  CONCLUSIONS
  CUDASW++ 3.0 is written in CUDA C++ and PTX assembly languages, targeting GPUs based on the Kepler architecture. This algorithm obtains significant speedups over its predecessor: CUDASW++ 2.0, by benefiting from the use of CPU and GPU SIMD instructions as well as the concurrent execution on CPUs and GPUs. The source code and the simulated data are available at http://cudasw.sourceforge.net.
authors.affiliation: Institut für Informatik, Johannes Gutenberg Universität Mainz, Mainz, Germany. liuy@uni-mainz.de
authors.forename: Yongchao
authors.initials: Y
authors.lastname: Liu
authors.forename: Adrianto
authors.initials: A
authors.lastname: Wirawan
authors.forename: Bertil
authors.initials: B
authors.lastname: Schmidt
mesh_terms: D000465:Algorithms; D030562:Databases, Protein; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software
references.citation: Bioinformatics. 2012 Jul 15;28(14):1830-7
references.pmid: 22576173
references.citation: BMC Bioinformatics. 2008 Mar 26;9 Suppl 2:S10
references.pmid: 18387198
references.citation: BMC Bioinformatics. 2011 Jun 01;12:221
references.pmid: 21631914
references.citation: Bioinformatics. 2005 Aug 15;21(16):3431-2
references.pmid: 15919726
references.citation: Bioinformatics. 2000 Aug;16(8):699-706
references.pmid: 11099256
references.citation: Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
references.pmid: 7984417
references.citation: Bioinformatics. 2009 Jul 15;25(14):1754-60
references.pmid: 19451168
references.citation: BMC Res Notes. 2010 Apr 06;3:93
references.pmid: 20370891
references.citation: BMC Res Notes. 2009 May 06;2:73
references.pmid: 19416548
references.citation: BMC Bioinformatics. 2008 Sep 17;9:377
references.pmid: 18798993
references.citation: Proc Natl Acad Sci U S A. 1988 Apr;85(8):2444-8
references.pmid: 3162770
references.citation: BMC Bioinformatics. 2011 May 20;12:181
references.pmid: 21599912
references.citation: BMC Bioinformatics. 2012 Aug 09;13:196
references.pmid: 22876807
references.citation: Bioinformatics. 2012 Mar 15;28(6):878-9
references.pmid: 22285832
references.citation: Comput Appl Biosci. 1997 Apr;13(2):145-50
references.pmid: 9146961
references.citation: BMC Bioinformatics. 2010 Dec 21;11 Suppl 12:S3
references.pmid: 21210982
references.citation: J Mol Biol. 1982 Dec 15;162(3):705-8
references.pmid: 7166760
references.citation: Nucleic Acids Res. 1997 Sep 1;25(17):3389-402
references.pmid: 9254694
references.citation: J Mol Biol. 1981 Mar 25;147(1):195-7
references.pmid: 7265238
references.citation: Bioinformatics. 2007 Jan 15;23(2):156-61
references.pmid: 17110365
references.citation: BMC Res Notes. 2008 Oct 29;1:107
references.pmid: 18959793
references.citation: BMC Bioinformatics. 2007 Jun 07;8:185
references.pmid: 17555593
references.citation: BMC Bioinformatics. 2009 Dec 15;10:421
references.pmid: 20003500
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712