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.

Nearest Neighbor search has been well solved in low-dimensional space, but is challenging in high-dimensional space due to the curse of dimensionality. As a trade-off between efficiency and result accuracy, a variety of c-approximate nearest neighbor (c-ANN) algorithms have been proposed to return a c-approximate NN with confident at least δ. We observe that existing c-ANN search algorithms have some limitations on I/O efficiency when their indexes are resided on the external memory, which is critical for handling large scale high-dimensional data. In this paper, we introduce an incremental search based c-ANN search algorithm, named I-LSH. Unlike the previous LSH methods, which expand the bucket width in an exponential way, I-LSH adopts a more natural search strategy to incrementally access the hash values of the objects. We provide rigorous theoretical analysis to underpin our incremental search strategy. Our comprehensive experiment results show that, compared with state-of-the-art I/O efficient c-ANN techniques, our algorithm can achieve much better I/O efficiency under the same theoretical guarantee.