  Genomics is the critical key to enabling precision medicine, ensuring global
food security and enforcing wildlife conservation. The massive genomic data
produced by various genome sequencing technologies presents a significant
challenge for genome analysis. Because of errors from sequencing machines and
genetic variations, approximate pattern matching (APM) is a must for practical
genome analysis. Recent work proposes FPGA, ASIC and even
process-in-memory-based accelerators to boost the APM throughput by
accelerating dynamic-programming-based algorithms (e.g., Smith-Waterman).
However, existing accelerators lack the efficient hardware acceleration for the
exact pattern matching (EPM) that is an even more critical and essential
function widely used in almost every step of genome analysis including
assembly, alignment, annotation and compression.
  State-of-the-art genome analysis adopts the FM-Index that augments the
space-efficient BWT with additional data structures permitting fast EPM
operations. But the FM-Index is notorious for poor spatial locality and massive
random memory accesses. In this paper, we propose a ReRAM-based
process-in-memory architecture, FindeR, to enhance the FM-Index EPM search
throughput in genomic sequences. We build a reliable and energy-efficient
Hamming distance unit to accelerate the computing kernel of FM-Index search
using commodity ReRAM chips without introducing extra CMOS logic. We further
architect a full-fledged FM-Index search pipeline and improve its search
throughput by lightweight scheduling on the NVDIMM. We also create a system
library for programmers to invoke FindeR to perform EPMs in genome analysis.
Compared to state-of-the-art accelerators, FindeR improves the FM-Index search
throughput by $83\%\sim 30K\times$ and throughput per Watt by $3.5\times\sim
42.5K\times$.
