Accelerating BWA-MEM Read Mapping on GPUs.
Accelerating BWA-MEM Read Mapping on GPUs.
复制标题
DOI：
10.1145/3577193.3593703
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
下一代测序（NGS）的进步显著降低了生成DNA序列数据的成本，并提高了数据生成的速度。然而，这种高通量数据生产增加了对高效数据分析程序的需求。分析测序数据时计算要求最高的步骤之一是将NGS产生的短读段映射到参考DNA序列（例如人类基因组）。映射程序BWA-MEM及其更新版本BWA-MEM 2，针对CPU进行了优化，是此任务最受欢迎的选择。在这项研究中，我们讨论了BWA-MEM在GPU上的实现。这是一项具有挑战性的任务，因为BWA-MEM中的许多算法和数据结构不能在GPU架构上有效执行。本文确定了在BWA-MEM程序的所有主要阶段开发高效GPU代码的主要挑战，包括播种、种子链接、Smith-Waterman对齐、内存管理和I/O处理。我们对BWA-MEM和BWA-MEM 2在64线程CPU上运行进行比较实验。结果表明，我们的实现在使用NVIDIA A40时比BWA-MEM 2实现了高达3.2倍的加速比，比BWA-MEM实现了高达5.8倍的加速比。使用NVIDIA A6000和NVIDIA A100，我们分别实现了比BWA-MEM 2高3.4倍/3.8倍和比BWA-MEM高6.1倍/6.8倍的壁时加速比。在阶段比较中，A40/A6000/A100 GPU分别在BWA-MEM的三个主要阶段实现了高达3.7/3.8/4x，2/2.3/2.5x和3.1/5/7.9x的加速：播种和种子链，Smith-Waterman和SAM输出。据我们所知，这是第一个尝试在GPU上实现整个BWA-MEM程序的研究。
Advancements in Next-Generation Sequencing (NGS) have significantly reduced the cost of generating DNA sequence data and increased the speed of data production. However, such high-throughput data production has increased the need for efficient data analysis programs. One of the most computationally demanding steps in analyzing sequencing data is mapping short reads produced by NGS to a reference DNA sequence, such as a human genome. The mapping program BWA-MEM and its newer version BWA-MEM2, optimized for CPUs, are some of the most popular choices for this task. In this study, we discuss the implementation of BWA-MEM on GPUs. This is a challenging task because many algorithms and data structures in BWA-MEM do not execute efficiently on the GPU architecture. This paper identifies major challenges in developing efficient GPU code on all major stages of the BWA-MEM program, including seeding, seed chaining, Smith-Waterman alignment, memory management, and I/O handling. We conduct comparison experiments against BWA-MEM and BWA-MEM2 running on a 64-thread CPU. The results show that our implementation achieved up to 3.2x speedup over BWA-MEM2 and up to 5.8x over BWA-MEM when using an NVIDIA A40. Using an NVIDIA A6000 and an NVIDIA A100, we achieved a wall-time speedup of up to 3.4x/3.8x over BWA-MEM2 and up to 6.1x/6.8x over BWA-MEM, respectively. In stage-wise comparison, the A40/A6000/A100 GPUs respectively achieved up to 3.7/3.8/4x, 2/2.3/2.5x, and 3.1/5/7.9x speedup on the three major stages of BWA-MEM: seeding and seed chaining, Smith-Waterman, and making SAM output. To the best of our knowledge, this is the first study that attempts to implement the entire BWA-MEM program on GPUs.