ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis

Tsung Yu Liu; Yen An Lu; James Yu; Chin Fu Nien; Hsiang Yun Cheng

doi:10.1145/3658617.3697571

ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis

Tsung Yu Liu
, Yen An Lu
, James Yu
, Chin Fu Nien^*
, Hsiang Yun Cheng^*

^*Corresponding author for this work

Department of Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Read mapping, which involves computationally intensive approximate string matching (ASM) on large datasets, is the primary performance bottleneck in genome sequence analysis. To accelerate read mapping, a processing-in-memory (PIM) architecture that conducts highly parallel computations within the memory to reduce energy-inefficient data movements can be a promising solution. In this paper, we present ReTAP, a processing-in-ReRAM Bitap accelerator for genomic analysis. Instead of using the intricate dynamic programming algorithm, our design incorporates the Bitap algorithm, which uses only simple bitwise operations to perform ASM. Additionally, we explore the opportunity to reduce redundant computations by dynamically adjusting the error tolerance of Bitap and co-design the hardware to enhance computation parallelism. Our evaluation demonstrates that ReTAP outperforms GenASM, the state-of-the-art Bitap accelerator, with a 5.74× throughput and 1.79× energy efficiency.

Original language	English
Title of host publication	ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	79-85
Number of pages	7
ISBN (Electronic)	9798400706356
DOIs	https://doi.org/10.1145/3658617.3697571
State	Published - 4 Mar 2025
Event	30th Asia and South Pacific Design Automation Conference, ASP-DAC 2025 - Tokyo, Japan Duration: 20 Jan 2025 → 23 Jan 2025

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
ISSN (Print)	2153-6961
ISSN (Electronic)	2153-697X

Conference

Conference	30th Asia and South Pacific Design Automation Conference, ASP-DAC 2025
Country/Territory	Japan
City	Tokyo
Period	20/01/25 → 23/01/25

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

approximate string matching (ASM)
genome sequencing
processing-in-memory (PIM)
read mapping
resistive random access memory (ReRAM)

Access to Document

10.1145/3658617.3697571

Cite this

Liu, T. Y., Lu, Y. A., Yu, J., Nien, C. F., & Cheng, H. Y. (2025). ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis. In ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings (pp. 79-85). (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/3658617.3697571

Liu, Tsung Yu ; Lu, Yen An ; Yu, James et al. / ReTAP : Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis. ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2025. pp. 79-85 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

@inproceedings{223aa16d8d2848bcbb27c494d7db83cc,

title = "ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis",

abstract = "Read mapping, which involves computationally intensive approximate string matching (ASM) on large datasets, is the primary performance bottleneck in genome sequence analysis. To accelerate read mapping, a processing-in-memory (PIM) architecture that conducts highly parallel computations within the memory to reduce energy-inefficient data movements can be a promising solution. In this paper, we present ReTAP, a processing-in-ReRAM Bitap accelerator for genomic analysis. Instead of using the intricate dynamic programming algorithm, our design incorporates the Bitap algorithm, which uses only simple bitwise operations to perform ASM. Additionally, we explore the opportunity to reduce redundant computations by dynamically adjusting the error tolerance of Bitap and co-design the hardware to enhance computation parallelism. Our evaluation demonstrates that ReTAP outperforms GenASM, the state-of-the-art Bitap accelerator, with a 5.74× throughput and 1.79× energy efficiency.",

keywords = "approximate string matching (ASM), genome sequencing, processing-in-memory (PIM), read mapping, resistive random access memory (ReRAM)",

author = "Liu, \{Tsung Yu\} and Lu, \{Yen An\} and James Yu and Nien, \{Chin Fu\} and Cheng, \{Hsiang Yun\}",

note = "Publisher Copyright: {\textcopyright} 2025 Copyright is held by the owner/author(s). Publication rights licensed to ACM.; 30th Asia and South Pacific Design Automation Conference, ASP-DAC 2025 ; Conference date: 20-01-2025 Through 23-01-2025",

year = "2025",

month = mar,

day = "4",

doi = "10.1145/3658617.3697571",

language = "English",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "79--85",

booktitle = "ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings",

address = "美國",

}

Liu, TY, Lu, YA, Yu, J, Nien, CF & Cheng, HY 2025, ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis. in ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, Institute of Electrical and Electronics Engineers Inc., pp. 79-85, 30th Asia and South Pacific Design Automation Conference, ASP-DAC 2025, Tokyo, Japan, 20/01/25. https://doi.org/10.1145/3658617.3697571

ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis. / Liu, Tsung Yu; Lu, Yen An; Yu, James et al.
ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2025. p. 79-85 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - ReTAP

T2 - 30th Asia and South Pacific Design Automation Conference, ASP-DAC 2025

AU - Liu, Tsung Yu

AU - Lu, Yen An

AU - Yu, James

AU - Nien, Chin Fu

AU - Cheng, Hsiang Yun

PY - 2025/3/4

Y1 - 2025/3/4

N2 - Read mapping, which involves computationally intensive approximate string matching (ASM) on large datasets, is the primary performance bottleneck in genome sequence analysis. To accelerate read mapping, a processing-in-memory (PIM) architecture that conducts highly parallel computations within the memory to reduce energy-inefficient data movements can be a promising solution. In this paper, we present ReTAP, a processing-in-ReRAM Bitap accelerator for genomic analysis. Instead of using the intricate dynamic programming algorithm, our design incorporates the Bitap algorithm, which uses only simple bitwise operations to perform ASM. Additionally, we explore the opportunity to reduce redundant computations by dynamically adjusting the error tolerance of Bitap and co-design the hardware to enhance computation parallelism. Our evaluation demonstrates that ReTAP outperforms GenASM, the state-of-the-art Bitap accelerator, with a 5.74× throughput and 1.79× energy efficiency.

AB - Read mapping, which involves computationally intensive approximate string matching (ASM) on large datasets, is the primary performance bottleneck in genome sequence analysis. To accelerate read mapping, a processing-in-memory (PIM) architecture that conducts highly parallel computations within the memory to reduce energy-inefficient data movements can be a promising solution. In this paper, we present ReTAP, a processing-in-ReRAM Bitap accelerator for genomic analysis. Instead of using the intricate dynamic programming algorithm, our design incorporates the Bitap algorithm, which uses only simple bitwise operations to perform ASM. Additionally, we explore the opportunity to reduce redundant computations by dynamically adjusting the error tolerance of Bitap and co-design the hardware to enhance computation parallelism. Our evaluation demonstrates that ReTAP outperforms GenASM, the state-of-the-art Bitap accelerator, with a 5.74× throughput and 1.79× energy efficiency.

KW - approximate string matching (ASM)

KW - genome sequencing

KW - processing-in-memory (PIM)

KW - read mapping

KW - resistive random access memory (ReRAM)

UR - https://www.scopus.com/pages/publications/105000303306

U2 - 10.1145/3658617.3697571

DO - 10.1145/3658617.3697571

M3 - Conference contribution

AN - SCOPUS:105000303306

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 79

EP - 85

BT - ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 20 January 2025 through 23 January 2025

ER -

Liu TY, Lu YA, Yu J, Nien CF, Cheng HY. ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis. In ASP-DAC 2025 - 30th Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc. 2025. p. 79-85. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). doi: 10.1145/3658617.3697571

ReTAP: Processing-in-ReRAM Bitap Approximate String Matching Accelerator for Genomic Analysis

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this