The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Student: LeAnn Lindsey (University of Utah, Lawrence Berkeley National Laboratory (LBNL))
Supervisor: Muaaz Awan (Lawrence Berkeley National Laboratory (LBNL))
Abstract: The 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%.
ACM-SRC Semi-Finalist: yes
Poster: PDF
Poster Summary: PDF
Back to Poster Archive Listing