SaLoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs
Yonsei University
arXiv:2301.09310 [cs.DB], (23 Jan 2023)
@misc{https://doi.org/10.48550/arxiv.2301.09310,
doi={10.48550/ARXIV.2301.09310},
url={https://arxiv.org/abs/2301.09310},
author={Park, Seongyeon and Kim, Hajin and Ahmad, Tanveer and Ahmed, Nauman and Al-Ars, Zaid and Hofstee, H. Peter and Kim, Youngsok and Lee, Jinho},
keywords={Databases (cs.DB), Distributed, Parallel, and Cluster Computing (cs.DC), FOS: Computer and information sciences, FOS: Computer and information sciences},
title={SaLoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs},
publisher={arXiv},
year={2023},
copyright={Creative Commons Attribution 4.0 International}
}
Sequence alignment forms an important backbone in many sequencing applications. A commonly used strategy for sequence alignment is an approximate string matching with a two-dimensional dynamic programming approach. Although some prior work has been conducted on GPU acceleration of a sequence alignment, we identify several shortcomings that limit exploiting the full computational capability of modern GPUs. This paper presents SaLoBa, a GPU-accelerated sequence alignment library focused on seed extension. Based on the analysis of previous work with real-world sequencing data, we propose techniques to exploit the data locality and improve workload balancing. The experimental results reveal that SaLoBa significantly improves the seed extension kernel compared to state-of-the-art GPU-based methods.
January 29, 2023 by hgpu
