NvWa: Enhancing Sequence Alignment Accelerator Throughput via Hardware Scheduling

Sequence alignment is the most time-consuming step in the genome analysis pipeline. Since sequence alignment generally follows the seed-and-extension paradigm, prior proposed hardware accelerators either opt to accelerate the seeding phase or the seed-extension phase. However, the diversity of each sequence in the alignment workflow leads to the pipeline stall or bubbles, which finally results in a decreased throughput for the end-to-end sequence alignment.In this paper, we propose NvWa, which is a hardware scheduling accelerator for sequence alignment. To solve the diversity problem, we propose three novel scheduling mechanisms and corresponding architecture, which target the seeding phase, the seed-extension phase, and the interaction between the two phases, respectively. For the seeding phase, we propose a Seeding Scheduler to schedule all idle seeding units in only one cycle. For the seed-extension phase, the Extension Scheduler can achieve both lower latency and higher parallelism when facing seed-extension tasks with different scales. Between the two phases, an efficient Coordinator caches and dispatches seeding hits to optimal and sub-optimal seed-extension units. Furthermore, to avoid algorithmic obsolescence for the new sequence technologies, we propose a loosely coupled design, which decouples the data path and the control scheduling path. Experimental results show that NvWa can achieve 493×, 200×, 12.11×, 2.30× speedup and 14.21×, 5.60×, 4.34×, 5.85× energy reduction when compared with a 16-thread CPU baseline, an NVIDIA A100 GPU, and two state-of-the-art accelerators, respectively.