DSIM: Distributed Sequence Matching on Near-DRAM Accelerator for Genome Assembly

Aman Sinha*, Huei Chun Yang, Pei Yi Liu, Yen Shi Kuo, Yuhao Fang, Tien Shuo Chang, Ke Han Li, Bo Cheng Lai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish
Pages (from-to)486-499
Number of pages14
JournalIEEE Journal on Emerging and Selected Topics in Circuits and Systems
Issue number2
StatePublished - 1 Jun 2022


  • distributed systems
  • Ferragina-Manzini Index (FM-Index)
  • genome alignment
  • genome assembly
  • Near-data processing
  • Processing-In-Memory (PIM)


Dive into the research topics of 'DSIM: Distributed Sequence Matching on Near-DRAM Accelerator for Genome Assembly'. Together they form a unique fingerprint.

Cite this