Lune

HPCA2023Top-tier venue

NvWa: Enhancing Sequence Alignment Accelerator Throughput via Hardware Scheduling

Yewen Li, Xueqi Li, Ruihao Gao, Wanqi Liu, Guangming Tan

Abstract

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.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Faster and Cheaper: Pushing the Sequence Alignment Throughput with Commercial CPUsZhonghai Zhang, Yewen Li, Ke Meng, Chunming Zhang et al.PPoPP 2026 · 1 citation
  2. CASA: An Energy-Efficient and High-Speed CAM-based SMEM Seeding Accelerator for Genome AlignmentYi Huang, Lingkun Kong, Dibei Chen, Zhiyu Chen et al.MICRO 2023 · 5 citations
  3. AGAThA: Fast and Efficient GPU Acceleration of Guided Sequence Alignment for Long Read MappingSeongyeon Park, Junguk Hong, Jaeyong Song, Hajin Kim et al.PPoPP 2024 · 7 citations
  4. SMX: Heterogeneous Architecture for Universal Sequence Alignment AccelerationMax Doblas, Po Jui Shih, Oscar Lostes-Cazorla, Miquel Moretó et al.MICRO 2025 · 7 citations
  5. SeedEx: A Genome Sequencing Accelerator for Optimal Alignments in Subminimal SpaceDaichi Fujiki, Shunhao Wu, Nathan Ozog, Kush Goliya et al.MICRO 2020 · 52 citations
Dusk over the sea between two cliffs drawn in fine vertical lines