DSIM: Distributed Sequence Matching on Near-DRAM Accelerator for Genome Assembly
- 4 May 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Emerging and Selected Topics in Circuits and Systems
- Vol. 12 (2) , 486-499
Abstract
Matching nucleic acid sequences has long become the performance bottleneck in genome assembly which aims to connect enormous partial genome reads without prior knowledge of the reference sequence. The intensive and random data accesses of querying sequences using the widely adopted FM-Index data structure have caused in-efficient usage and long runtime of the memory system. Existing software FM-Index tools are limited on algorithmic inefficiency and poor processing parallelism. Solutions on GPU, FPGA and ASIC focus mainly on computational acceleration while still bottlenecked at the memory-bound nature of querying FM-Index. This paper proposes DSIM, a scalable FM-Index querying on near-DRAM accelerators. DSIM supports highly parallel multi-step query processing by distributing partial FM-Index table to different DRAM chips. Each genome sequence is partitioned into shorter queries and dispatched to the corresponding DRAM chip for string lookup. The optimized data layout and execution control on DRAM enables high row-data reuse and minimizes CPU-DRAM data transfers. The light-weight mapping scheme on the host CPU facilitates effective query distribution to DRAM chips and further supports scalability to multiple DIMMs (Dual-Inline Memory Modules). An in-DRAM arbiter is implemented to control the intra-chip data processing without affecting the external memory controller and DDR protocol. Experiments on 128-chip DRAM system showed that DSIM achieves up to 231 $\times$ and 8.9 $\times$ overall speedup compared to the software FM-Index tool and the state-of-the-art near-DRAM solution respectively.Keywords
Funding Information
- Ministry of Science and Technology, Taiwan (MOST 108-2628-E-009-007-MY3, MOST 109-2622-E-009-029)
- IEEE Publication Technology Group, Piscataway, NJ, USA
This publication has 37 references indexed in Scilit:
- n-step FM-Index for Faster Pattern MatchingProcedia Computer Science, 2013
- The GEM mapper: fast, accurate and versatile alignment by filtrationNature Methods, 2012
- High-performance short sequence alignment with GPU accelerationDistributed and Parallel Databases, 2012
- A survey of error-correction methods for next-generation sequencingBriefings in Bioinformatics, 2012
- The gem5 simulatorACM SIGARCH Computer Architecture News, 2011
- Aligning Short Sequencing Reads with BowtieCurrent Protocols in Bioinformatics, 2010
- Efficient construction of an assembly string graph using the FM-indexBioinformatics, 2010
- SOAP2: an improved ultrafast tool for short read alignmentBioinformatics, 2009
- Fast and accurate short read alignment with Burrows–Wheeler transformBioinformatics, 2009
- Comparative genome assemblyBriefings in Bioinformatics, 2004