CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions
<p>Abstract</p> <p>Background</p> <p>Due to its high sensitivity, the Smith-Waterman algorithm is widely used for biological database searches. Unfortunately, the quadratic time complexity of this algorithm makes it highly time-consuming. The exponential growth of biolo...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2010-04-01
|
| Series: | BMC Research Notes |
| Online Access: | http://www.biomedcentral.com/1756-0500/3/93 |
| _version_ | 1818759120557178880 |
|---|---|
| author | Schmidt Bertil Liu Yongchao Maskell Douglas L |
| author_facet | Schmidt Bertil Liu Yongchao Maskell Douglas L |
| author_sort | Schmidt Bertil |
| collection | DOAJ |
| description | <p>Abstract</p> <p>Background</p> <p>Due to its high sensitivity, the Smith-Waterman algorithm is widely used for biological database searches. Unfortunately, the quadratic time complexity of this algorithm makes it highly time-consuming. The exponential growth of biological databases further deteriorates the situation. To accelerate this algorithm, many efforts have been made to develop techniques in high performance architectures, especially the recently emerging many-core architectures and their associated programming models.</p> <p>Findings</p> <p>This paper describes the latest release of the CUDASW++ software, CUDASW++ 2.0, which makes new contributions to Smith-Waterman protein database searches using compute unified device architecture (CUDA). A parallel Smith-Waterman algorithm is proposed to further optimize the performance of CUDASW++ 1.0 based on the single instruction, multiple thread (SIMT) abstraction. For the first time, we have investigated a partitioned vectorized Smith-Waterman algorithm using CUDA based on the virtualized single instruction, multiple data (SIMD) abstraction. The optimized SIMT and the partitioned vectorized algorithms were benchmarked, and remarkably, have similar performance characteristics. CUDASW++ 2.0 achieves performance improvement over CUDASW++ 1.0 as much as 1.74 (1.72) times using the optimized SIMT algorithm and up to 1.77 (1.66) times using the partitioned vectorized algorithm, with a performance of up to 17 (30) billion cells update per second (GCUPS) on a single-GPU GeForce GTX 280 (dual-GPU GeForce GTX 295) graphics card.</p> <p>Conclusions</p> <p>CUDASW++ 2.0 is publicly available open-source software, written in CUDA and C++ programming languages. It obtains significant performance improvement over CUDASW++ 1.0 using either the optimized SIMT algorithm or the partitioned vectorized algorithm for Smith-Waterman protein database searches by fully exploiting the compute capability of commonly used CUDA-enabled low-cost GPUs.</p> |
| first_indexed | 2024-12-18T06:37:40Z |
| format | Article |
| id | doaj.art-447d31d34ea4464b8fa89c22052e4d7b |
| institution | Directory Open Access Journal |
| issn | 1756-0500 |
| language | English |
| last_indexed | 2024-12-18T06:37:40Z |
| publishDate | 2010-04-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Research Notes |
| spelling | doaj.art-447d31d34ea4464b8fa89c22052e4d7b2022-12-21T21:17:44ZengBMCBMC Research Notes1756-05002010-04-01319310.1186/1756-0500-3-93CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractionsSchmidt BertilLiu YongchaoMaskell Douglas L<p>Abstract</p> <p>Background</p> <p>Due to its high sensitivity, the Smith-Waterman algorithm is widely used for biological database searches. Unfortunately, the quadratic time complexity of this algorithm makes it highly time-consuming. The exponential growth of biological databases further deteriorates the situation. To accelerate this algorithm, many efforts have been made to develop techniques in high performance architectures, especially the recently emerging many-core architectures and their associated programming models.</p> <p>Findings</p> <p>This paper describes the latest release of the CUDASW++ software, CUDASW++ 2.0, which makes new contributions to Smith-Waterman protein database searches using compute unified device architecture (CUDA). A parallel Smith-Waterman algorithm is proposed to further optimize the performance of CUDASW++ 1.0 based on the single instruction, multiple thread (SIMT) abstraction. For the first time, we have investigated a partitioned vectorized Smith-Waterman algorithm using CUDA based on the virtualized single instruction, multiple data (SIMD) abstraction. The optimized SIMT and the partitioned vectorized algorithms were benchmarked, and remarkably, have similar performance characteristics. CUDASW++ 2.0 achieves performance improvement over CUDASW++ 1.0 as much as 1.74 (1.72) times using the optimized SIMT algorithm and up to 1.77 (1.66) times using the partitioned vectorized algorithm, with a performance of up to 17 (30) billion cells update per second (GCUPS) on a single-GPU GeForce GTX 280 (dual-GPU GeForce GTX 295) graphics card.</p> <p>Conclusions</p> <p>CUDASW++ 2.0 is publicly available open-source software, written in CUDA and C++ programming languages. It obtains significant performance improvement over CUDASW++ 1.0 using either the optimized SIMT algorithm or the partitioned vectorized algorithm for Smith-Waterman protein database searches by fully exploiting the compute capability of commonly used CUDA-enabled low-cost GPUs.</p>http://www.biomedcentral.com/1756-0500/3/93 |
| spellingShingle | Schmidt Bertil Liu Yongchao Maskell Douglas L CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions BMC Research Notes |
| title | CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions |
| title_full | CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions |
| title_fullStr | CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions |
| title_full_unstemmed | CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions |
| title_short | CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions |
| title_sort | cudasw 2 0 enhanced smith waterman protein database search on cuda enabled gpus based on simt and virtualized simd abstractions |
| url | http://www.biomedcentral.com/1756-0500/3/93 |
| work_keys_str_mv | AT schmidtbertil cudasw20enhancedsmithwatermanproteindatabasesearchoncudaenabledgpusbasedonsimtandvirtualizedsimdabstractions AT liuyongchao cudasw20enhancedsmithwatermanproteindatabasesearchoncudaenabledgpusbasedonsimtandvirtualizedsimdabstractions AT maskelldouglasl cudasw20enhancedsmithwatermanproteindatabasesearchoncudaenabledgpusbasedonsimtandvirtualizedsimdabstractions |