Optimizing Traceback in the Smith-Waterman Algorithm for GPUs
DescriptionThe traceback phase of the Smith-Waterman (SW) algorithm requires significant memory and introduces an irregular memory access pattern which makes it challenging to implement for GPU architectures. In this work, we introduce a novel strategy for implementing the traceback kernel for the SW algorithm on GPUs by restructuring the global memory access patterns and introducing a memory-efficient data structure for storing large dynamic programming matrices in GPU’s limited memory. To demonstrate this kernel’s performance we integrated this into the existing ADEPT library and Metahipmer2, a de novo metagenomic short read assembler. Our implementation is 3.6x faster than traceback in GASAL2, and 51x faster than traceback in Striped Smith-Waterman, the current state of the art SW libraries on GPU and CPU respectively. It sped up the final alignment step in Metahipmer2 by an average of 44% and improved the overall execution time of Metahipmer2 by an average of 13%.