CASA: An Energy-Efficient and High-Speed CAM-based SMEM Seeding Accelerator for Genome Alignment
Open Access
- 28 October 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1423-1436
Abstract
Genome analysis is a critical tool in medical and bioscience research, clinical diagnostics and treatment, and disease control and prevention. Seed and extension-based alignment is the main approach in the genome analysis pipeline, and BWA-MEM2, a widely acknowledged tool for genome alignment, performs seeding by searching for super maximal exact match (SMEM). The computation of SMEM searching requires high memory bandwidth and energy consumption, which becomes the main performance bottleneck in BWA-MEM2. State-of-the-Art designs like ERT and GenAx have achieved impressive speed-ups of SMEM-based genome alignment. However, they are constrained by frequent DRAM fetches or computationally intensive intersection calculations for all possible k-mers at every read position. We present a CAM-based SMEM seeding accelerator for genome alignment (CASA), which circumvents the major throughput and power bottlenecks brought by data fetches and frequent position intersections through the co-design of a novel CAM-based computing architecture and a new SMEM search algorithm. CASA mainly consists of a pre-seeding filter table and a SMEM computing unit. The former expands the k-mer size to 19 using limited on-chip memory, which enables the efficient filtration of non-SMEM pivots. The latter applies a new algorithm to filter out disposable SMEMs that are already contained in other SMEMs. We evaluated a 28nm CASA implementation using the human and mouse genome references. CASA achieves 1.2 × and 5.47 × throughput improvement over ERT and GenAx while only requiring less than 30GB/s DRAM bandwidth and keeping the same alignment results as BWA-MEM2. Moreover, CASA provides 2.57 × and 6.69 × higher energy efficiency than ERT and GenAx.Keywords
Funding Information
- National Natural Science Foundation of China (62204139)
- Beijing Superstring Academy of Memory Technology (61834002)
This publication has 48 references indexed in Scilit:
- SOAP3-dp: Fast, Accurate and Sensitive GPU-Based Short Read AlignerPLOS ONE, 2013
- Fast gapped-read alignment with Bowtie 2Nature Methods, 2012
- Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and SurveyIEEE Journal of Solid-State Circuits, 2006
- A Greedy Algorithm for Aligning DNA SequencesJournal of Computational Biology, 2000
- A fast bit-vector algorithm for approximate string matching based on dynamic programmingJournal of the ACM, 1999
- Comparison of methods for searching protein sequence databasesProtein Science, 1995
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981
- A fast string searching algorithmCommunications of the ACM, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975