# GenStore: A High-Performance and Energy-Efficient
In-Storage Computing System for Genome Sequence Analysis

Nika Mansouri Ghiasi1 Jisung Park1 Harun Mustafa1 Jeremie Kim1 Ataberk Olgun1
,  Arvid Gollwitzer1 Damla Senol Cali2 Can Firtina1 Haiyu Mao1 Nour Almadhoun
Alserr1 and  Rachata Ausavarungnirun3 Nandita Vijaykumar4 Mohammed Alser1 Onur
Mutlu1 1ETH Zürich 2Bionano Genomics 3KMUTNB 4University of Toronto

(2022)

###### Abstract.

Read mapping is a fundamental step in many genomics applications. It is used
to identify potential matches and differences between fragments (called
_reads_) of a sequenced genome and an already known genome (called a
_reference genome_). Read mapping is costly because it needs to perform
_approximate string matching (ASM)_ on large amounts of data. To address the
computational challenges in genome analysis, many prior works propose various
approaches such as accurate _filters_ that select the reads within a dataset
of genomic reads (called a _read set_) that _must_ undergo expensive
computation, efficient heuristics, and hardware acceleration. While effective
at reducing the amount of expensive computation, all such approaches still
require the costly movement of a large amount of data from storage to the rest
of the system, which can significantly lower the end-to-end performance of
read mapping in conventional and emerging genomics systems.

We propose _GenStore_ , the first in-storage processing system designed for
genome sequence analysis that greatly reduces both data movement and
computational overheads of genome sequence analysis by exploiting low-cost and
accurate _in-storage filters_. GenStore leverages hardware/software co-design
to address the challenges of in-storage processing, supporting reads with 1)
different properties such as read lengths and error rates, which highly depend
on the sequencing technology, and 2) different degrees of genetic variation
compared to the reference genome, which highly depends on the genomes that are
being compared. Through rigorous analysis of read mapping processes of reads
with different properties and degrees of genetic variation, we meticulously
design low-cost hardware accelerators and data/computation flows inside a NAND
flash-based solid-state drive (SSD). Our evaluation using a wide range of real
genomic datasets shows that GenStore, when implemented in three modern NAND
flash-based SSDs, significantly improves the read mapping performance of
state-of-the-art software (hardware) baselines by 2.07-6.05$\times$
(1.52-3.32$\times$) for read sets with high similarity to the reference genome
and 1.45-33.63$\times$ (2.70-19.2$\times$) for read sets with low similarity
to the reference genome.

Read Mapping, Filtering, Genomics, Storage, Near-Data Processing

††copyright: acmlicensed††price: 15.00††doi:
10.1145/3503222.3507702††journalyear: 2022††submissionid:
asplos22main-p39-p††isbn: 978-1-4503-9205-1/22/02††conference: Proceedings of
the 27th ACM International Conference on Architectural Support for Programming
Languages and Operating Systems; February 28 – March 4, 2022; Lausanne,
Switzerland††booktitle: Proceedings of the 27th ACM International Conference
on Architectural Support for Programming Languages and Operating Systems
(ASPLOS ’22), February 28 – March 4, 2022, Lausanne, Switzerland††ccs:
Computer systems organization Special purpose systems††ccs: Hardware External
storage

##  1\. Introduction

Genome sequence analysis, which analyzes the DNA sequences of organisms, is
important for many applications in personalized medicine (clark2019diagnosis,
; farnaes2018rapid, ; sweeney2021rapid, ; alkan2009personalized, ;
flores2013p4, ; ginsburg2009genomic, ; chin2011cancer, ; Ashley2016, ),
outbreak tracing (bloom2021massively, ; yelagandula2021multiplexed, ;
le2013selected, ; nikolayevskyy2016whole, ; qiu2015whole, ;
gilchrist2015whole, ), and evolutionary studies (hoban2016finding, ;
romiguier2014comparative, ; ellegren2016determinants, ; prohaska2019human, ;
ellegren2014genome, ; Prado-Martinez2013, ; Prohaska2019, ). The information
of an organism’s DNA is converted to digital data via a process called
_sequencing_. A sequencing machine extracts the sequences of DNA molecules
from the organism’s sample in the form of strings consisting of four _base
pairs (bps)_ , denoted by A, C, G, and T. No current sequencing technology has
the capability to read a human DNA molecule in its entirety. Instead, state-
of-the-art sequencing machines generate randomly sampled, inexact sub-strings
of the original genome, called _reads_. The information about the
corresponding location of each read in the complete genome is lost during
sequencing in most technologies. State-of-the-art sequencing machines produce
one of two kinds of reads. 1) Short read sequencing technologies, such as
Illumina (reuter2015high, ; van2014ten, ), produce reads that are highly
accurate (99-99.9%) (glenn2011field, ; goodwin2016coming, ; quail2012tale, ),
but short (e.g., up to a few hundred DNA _base pairs_ (glenn2011field, ;
kchouk2017generations, ; pfeiffer2018systematic, )). 2) Long read sequencing
technologies, such as Pacific Biosciences (PacBio)
(amarasinghe2020opportunities, ) and Oxford Nanopore Technologies (ONT)
(cali2017nanopore, ), produce reads that are less accurate (85-90%)
(ardui2018single, ; kchouk2017generations, ; weirather2017comprehensive, ;
van2018third, ), but long (e.g., lengths ranging from thousands to millions of
base pairs (wang2021nanopore, )).

Many genomics applications that involve the comparison of the genomic reads to
a reference genome require a fundamental initial process, called _read
mapping_. Read mapping identifies potential matching locations of reads
against a reference genome (alser2020accelerating, ; alser2020technology, )
and is a _very_ computationally-costly process (xin2013accelerating, ;
xin2015shifted, ; turakhia2018darwin, ; cali2020genasm, ;
alser2020sneakysnake, ; alser2017gatekeeper, ; nag2019gencache, ;
kim2019airlift, ; kim2018grim, ; firtina2020apollo, ) due to two key
challenges. First, it uses _computationally-expensive algorithms_ involving
approximate string matching (ASM) (cali2020genasm, ; vsovsic2017edlib, ;
alser2017gatekeeper, ; alser2017magnet, ; alser2019shouji, ;
alser2020sneakysnake, ; kim2018grim, ; kim2019airlift, ; needleman1970general,
; smith1981identification, ; gotoh1982improved, ). A read is _aligned_ to a
reference genome if the read is sufficiently similar to one or more
subsequences in that reference genome. Reads generated by a sequencing machine
might have differences compared to the reference genome due to either errors
in the sequencing process or genetic variations (xin2013accelerating, ;
levy2016advancements, ; hu2021next, ; 10002015global, ). ASM is widely used in
existing read mappers to accurately account for such potential differences
when determining the similarity between each read and the reference genome.
Second, read mapping performs _large amounts of expensive ASM computation_
because the genomic read datasets contain many reads (e.g., millions of
reads), and each read requires ASM computation on multiple subsequences in the
reference genome (see Section 2.1 for more details).

Since read mapping is a key performance bottleneck in genome sequence analysis
applications, there has been significant effort into improving read mapping
performance via both algorithmic and system optimizations. Many prior works
propose efficient heuristics for ASM (zhang2000greedy, ; slater2005automated,
; li2018minimap2, ; myers1999fast, ; marco2021fast, ), hardware accelerators
(alser2020accelerating, ; huangfu2018radar, ; cali2020genasm, ;
turakhia2018darwin, ; fujiki2018genax, ; fujiki2020seedex, ; banerjee2018asap,
; khatamifard2021genvom, ; gupta2019rapid, ; li2021pim, ; angizi2019aligns, ;
zokaee2018aligner, ; madhavan2014race, ; cheng2018bitmapper2, ;
houtgast2018hardware, ; houtgast2017efficient, ; goyal2017ultra, ;
chen2016spark, ; chen2014accelerating, ; chen2021high, ; zeni2020logan, ;
ahmed2019gasal2, ; nishimura2017accelerating, ; de2016cudalign, ;
liu2015gswabe, ; liu2013cudasw++, ; wilton2015arioc, ; fei2018fpgasw, ;
waidyasooriya2015hardware, ; chen2015novel, ; rucci2018swifold, ;
haghi2021fpga, ; li2021pipebsw, ; ham2020genesis, ; ham2021accelerating, ;
wu2019fpga, ), and various _filters_ that try to efficiently and accurately
prune reads that do not require expensive computation (alser2020technology, ;
kim2018grim, ; alser2020accelerating, ; cali2020genasm, ; singh2021fpga, ;
nag2019gencache, ; kim20111, ; alser2017gatekeeper, ; alser2017magnet, ;
alser2019shouji, ; alser2020sneakysnake, ; bingol2021gatekeeper, ;
hameed2021alpha, ; guo2019hardware, ; xin2015shifted, ; xin2013accelerating,
). For example, filters can be used to quickly prune reads that have exact
matches in the reference genome. Pruned reads do not go through the expensive
ASM process, which improves read mapping performance and efficiency
(alser2020accelerating, ; singh2021fpga, ; kim2018grim, ; alser2020technology,
; alser2017gatekeeper, ; alser2017magnet, ; alser2019shouji, ;
alser2020sneakysnake, ; cali2020genasm, ; bingol2021gatekeeper, ;
nag2019gencache, ).

While prior works improve read mapping performance, to our knowledge, _none_
of them consider the I/O cost that most systems must pay to read the large
amount of data from the storage system to main memory and computation units.
Read mapping incurs unnecessary data movement from the storage system for
large amounts of _low-reuse_ data. For example, while existing filters prune
many reads to avoid expensive computation, they still need to first read the
_entire_ read set from the storage system, even though a large fraction of the
reads would be filtered out and _not_ be reused in the later stages of the
read mapping process. The unnecessary data movement from the storage system
can bottleneck read mapping performance in both conventional (software-based)
and emerging (hardware-accelerated) genomics systems, while having a larger
impact on emerging systems that greatly reduce the computation bottlenecks of
ASM (e.g., (alser2020accelerating, ; huangfu2018radar, ; cali2020genasm, ;
fujiki2018genax, ; fujiki2020seedex, ; banerjee2018asap, ; turakhia2018darwin,
; nag2019gencache, )).

_In-storage filtering_ can be a fundamental solution for reducing the cost of
the unnecessary data movement in read mapping. Our motivational study using an
ideal in-storage filter for read mapping (Section 3) demonstrates that in-
storage processing can greatly accelerate the end-to-end read mapping process.
This is because in-storage filtering not only avoids unnecessary data movement
from storage, but also _eliminates_ the computational burden of the filtering
process from the rest of the system.

Our goal in this work is to improve the performance of genome sequence
analysis by effectively reducing unnecessary data movement from the storage
system. To this end, we propose _GenStore_ , the first in-storage processing
system designed for genome sequence analysis. The key idea of GenStore is to
exploit low-cost _in-storage accelerators_ to accurately _filter out_ the
reads that do not require the expensive ASM computation in read mapping,
thereby significantly reducing unnecessary data movement from the storage
system to main memory and processors.

We identify two key challenges in designing an efficient in-storage system for
read mapping. First, read mapping workloads exhibit fundamentally different
behavior due to 1) the varying read properties such as read length and error
rates, which highly depend on the sequencing technology, and 2) the genetic
variation of reads compared to the reference genome, which highly depends on
the genomes that are being compared. Second, existing filtering methods incur
a large number of random accesses to large datasets, which is challenging for
a modern NAND flash-based solid-state drive (SSD)111 In this work, we focus on
SSDs based on NAND flash memory, the prevalent memory technology in modern
storage systems. We expect that GenStore would also provide performance and
energy benefits with storage devices that are built using emerging non-
volatile memory technologies. to cope with due to its poor random-access
performance and limited size of internal DRAM.

We address these challenges with hardware/software co-design in three key
directions. First, based on our detailed analysis of read mapping, we design
two different accelerators that can accelerate a wide range of read mapping
applications for reads with different properties (lengths and error rates) and
genetic variations. Each accelerator filters a large fraction of genomic read
datasets using simple operations. Second, we develop storage technology-aware
algorithmic optimizations to replace expensive random accesses with more
efficient sequential accesses to storage devices (e.g., NAND flash-based
SSDs). Third, we carefully design an efficient technique for data placement
inside the storage device that takes full advantage of the high internal SSD
bandwidth to concurrently access large amounts of genomic data.

We design GenStore to support two in-storage filtering mechanisms in a single
SSD: 1) GenStore-EM and 2) GenStore-NM.

GenStore-EM filters _e xactly-matching_ reads, i.e., reads that exactly match
subsequences of a reference genome. Due to the low error rates of short reads,
a large fraction of short reads map _exactly_ to the reference genome
(10002015global, ; uk10k2015uk10k, ; nag2019gencache, ). For example, on
average 80% of human short reads map exactly to the human reference genome
(10002015global, ; uk10k2015uk10k, ; nag2019gencache, ). However, finding
exactly-matching reads in the SSD is challenging, as it incurs a number of
random accesses per read to a large index structure that stores unique
subsequences of length $k$ (called _k-mers_) and their positions in the
reference genome. Since each read consists of many k-mers, filtering each read
requires several random accesses to the index. To avoid such random accesses,
we introduce a new _sorted, read-sized_ k-mer index structure, which enables
_sequentially_ scanning of the read set and the new index, with only one index
lookup per read during filtering.

GenStore-NM filters most of the _n on-matching_ reads, i.e., reads that would
not align to any subsequence in the reference genome. In read mapping, a
significant fraction of reads might not align to the reference genome due to
1) the high sequencing error rate (in long reads) and/or 2) high genetic
variation (in both short and long reads). For example, both short and long
read sets sequenced from rapidly-evolving viral samples (such as SARS-CoV-2)
can have high genetic variations compared to the reference genome, leading to,
on average, 36% (up to 99.9%) of reads not aligning to the reference
(bhoyar2021high, ). To avoid expensive ASM operations for such non-matching
reads, state-of-the-art read mappers commonly employ a step called _chaining_
, which calculates a similarity score for each read (called _chaining score_)
to the reference and filters out reads with a low score. GenStore-NM uses this
basic idea of chaining to build an in-storage filter.

Calculating a chaining score for a read inside the SSD is challenging since it
requires performing an expensive dynamic programming algorithm on the read’s
k-mers that exactly match the reference. This is particularly challenging for
long reads since they have a large number of k-mers per read. To avoid such
expensive computation, we _selectively_ perform chaining only on reads with a
small number of exactly-matching k-mers and send other reads to the host
system for full read mapping (including chaining). Selective chaining is
effective because 1) a read with many exactly-matching k-mers most likely
aligns to the reference genome and thus does not require in-storage filtering,
and 2) selective chaining can filter many non-aligning reads, without
requiring costly hardware resources in the SSD.

To evaluate GenStore, we use a combination of synthesized Verilog models of
our in-storage accelerators and state-of-the-art simulation tools that are
widely used for DRAM and SSD research, Ramulator (kim2016ramulator, ) and
MQSim (tavakkol2018mqsim, ). To assess the performance impact of the storage
system, we evaluate three GenStore-enabled systems with different SSD
configurations (low-end, medium-end, and high-end). We integrate GenStore into
a state-of-the-art software read mapper (Minimap2 (li2018minimap2, )) and two
state-of-the-art hardware read mappers (GenCache (nag2019gencache, ) for short
reads and Darwin (turakhia2018darwin, ) for long reads). Our results show that
GenStore-EM and GenStore-NM improve the performance of Minimap2 by
2.07-6.05$\times$ and 1.45-33.63$\times$, respectively, with _no_ accuracy
loss. GenStore-EM improves the performance of GenCache by 1.52-3.32$\times$,
and GenStore-NM improves the performance Darwin by 2.70-19.2$\times$, with
_no_ accuracy loss.

This work makes the following key contributions:

  * $\circ$

We introduce GenStore, the first in-storage processing system designed for
genome sequence analysis. GenStore fundamentally addresses the high I/O cost
of reading low-reuse genomic data from storage systems.

  * $\circ$

We address the challenges of in-storage filtering for genome sequence analysis
by analyzing the read mapping process and performing hardware/software co-
design to develop in-storage filtering mechanisms and accelerators for genomic
reads with various lengths, error rates, and genetic variations.

  * $\circ$

We introduce two in-storage accelerators, 1) GenStore-EM for filtering
exactly-matching reads and 2) GenStore-NM for filtering most reads that would
not align to any subsequence in the reference genome. GenStore filters out a
large fraction of reads with lightweight hardware accelerators and _no_ loss
of accuracy, thereby improving the end-to-end performance and energy
efficiency of genome sequence analysis.

##  2\. Background

We provide brief background on read mapping and NAND flash-based SSDs,
necessary to understand the rest of the paper.

###  2.1. Read Mapping

End-to-End Workflow of Genome Sequence analysis. There are three key initial
steps in a standard genome sequencing and analysis workflow
(alser2020technology, ; alser2020accelerating, ). The first step is the
collection, preparation, and sequencing of a DNA sample in the laboratory.
Modern sequencing machines are unable to read an organism’s genome as a single
complete sequence; instead they generate shorter subsequences sampled randomly
from the genome sequence (syed2009next, ; shendure2008next, ). The second step
is _basecalling_ , which converts the representation of the subsequences
generated by the sequencing machine (e.g., images or electric current,
depending on the sequencing technology (cali2017nanopore, ;
levy2016advancements, )) into _reads_ , which are sequences of _nucleotides_
(i.e., A, C, G, and T in the DNA alphabet). In order to reproduce the complete
genome sequence from the shorter read sequences, the third step, called _read
mapping,_ identifies potential matching locations of each read with respect to
a known reference genome (e.g., a representative genome sequence for a
particular species) (li2018minimap2, ; alser2020technology, ; cali2020genasm,
; alkan2009personalized, ). Genomic read sets can be obtained by, for example,
1) sequencing a DNA sample and storing the generated read set into the SSD of
a sequencing machine (gamaarachchi2022fast, ; minion21, ) or 2) downloading
read sets from publicly available repositories (leinonen2010sequence, ) and
storing them into an SSD.

In this work, we focus on optimizing the performance of read mapping because
sequencing and basecalling are performed only once per read set, whereas read
mapping can be performed _many times_ for the same read set. This is common in
many genomic applications for two reasons. First, some applications require
analyzing the genetic differences between a read set belonging to an
individual and _many_ reference genomes of other individuals. Examples of such
applications include measuring the genetic diversity in a population
(kostlbacher2021pangenomics, ; van2020emergence, ) and determining the donor
of a sample by quantifying the reads that have a match in each reference
genome (lapierre2020metalign, ; meyer2021critical, ). Second, some other
applications require repeating the read mapping step many times to improve the
outcome of read mapping. Examples of such applications are 1) mapping with
new, more updated reference genomes (kim2019airlift, ), or 2) using different
mapping parameter values (such as the maximum number of allowed differences
between a read and a subseqeuence in the reference genome so that they are
considered similar) (khayat2021hidden, ).

Improving read mapping performance is critical since it is a fundamental step
used in almost all genomic analyses that use sequencing data
(alser2020accelerating, ; cali2020genasm, ; turakhia2018darwin, ; kim2018grim,
). The contribution of read mapping to the entire analysis pipeline varies
depending on the application. For example, read mapping takes up to 1) 45% of
the execution time when discovering sequence variants in cancer genomics
studies (luo2014balsa, ), and 2) 60% of the execution time when profiling the
species composition of a multi-species (i.e., _metagenomic_) read set
(lapierre2020metalign, ).

Read Mapping Process. Since the sequencing process does not provide location
information for both short and long reads in most technologies, _read mapping_
is a fundamental initial process for many genomics applications. The read
mapping process identifies subsequences in the reference genome to which the
input reads match. For each _matching location_ , i.e., the location of each
matching subsequence in the reference genome, a read mapper computes an
_alignment score_ , indicating the degree of similarity between the read and
the region of the reference to which the read aligns. Matching base pairs
between the read and the reference increase the alignment score, whereas
_edits_ (i.e., base pair mismatches, insertions, or deletions relative to the
reference) decrease this score.

Since each read is much shorter than the reference genome (e.g., the human
reference genome contains $\sim$3.2 billion base pairs), a read mapper
typically uses an index of the reference genome to reduce the search space for
each read. The index is a dictionary, i.e., a key-value store, where the keys
are unique $k$-length subsequences (called _$k$ -mers_) extracted from the
reference genome, and the values are the exactly-matching locations of these
$k$-mers in the reference genome (xin2013accelerating, ; xin2016optimal, ).
The value of $k$ is fixed during indexing and used for all subsequent
steps.222$k$ is typically between 11 and 31 (altschul1990basic, ;
li2018minimap2, ; wood2019improved, ), depending on the application. To
greatly reduce the storage overhead of the index and speed up queries against
it, without significantly changing the final outcome of read mapping, some
read mappers index only a subset of reference genome $k$-mers called
_minimizers_ (schleimer2003winnowing, ; roberts2004reducing, ;
marccais2017improving, ). A minimizer is a representative $k$-mer of a set of
$k$-mers according to a scoring mechanism. For example, some read mappers
(li2016minimap, ; li2018minimap2, ) calculate hash values for all $k$-mers in
a window of $w$ consecutive $k$-mers from an input sequence, and mark the
$k$-mer with the smallest hash value as the minimizer $k$-mer.

Read mapping is a three-step process. In the first step (_seeding_), the read
mapper queries the index structure to determine potential locations in the
reference genome where the read could map. To do so, the read mapper looks up
every minimizer k-mer fetched from a read in the reference index. If the
minimizer k-mer hits in the reference index, the read mapper marks the
locations of such a k-mer in the reference genome as the read’s _potential
matching locations_ , also called _seeds_. In the second step (_seed
filtering_ and/or _chaining_), the read mapper prunes those potential matching
locations in the reference to which the read would not align. If all of the
potential matching locations of the read get filtered, the read mapper
discards the read from further analysis. The read mapper uses a dynamic
programming (DP) algorithm to 1) merge overlapping seeds into longer regions,
called _chains_ (li2018minimap2, ), and 2) calculate their corresponding
_chaining scores,_ which refers to the approximation of the entire read’s
alignment score in these regions. If the read mapper finds one or more chains
with a sufficiently high chaining score (indicating a high degree of
similarity to the reference genome), then the read mapper performs the third
step. If the read has no chain with a sufficiently high score, the read mapper
prunes the read and skips the third step. In the third step (_sequence
alignment_), the read mapper determines the exact differences between a read
and the reference genome at the potential matching locations. Sequence
alignment is done with a computationally-expensive DP algorithm
(alser2020accelerating, ; alser2017gatekeeper, ; alser2017magnet, ;
alser2019shouji, ; alser2020technology, ; cali2020genasm, ; kim2018grim, ;
needleman1970general, ; smith1981identification, ; alser2020sneakysnake, ) to
perform approximate string matching (ASM). Finally, the read mapper returns
the locations in the reference genome with the best alignment scores for each
read.

Pre-Alignment Read Filtering. To mitigate the high performance overhead of
alignment, read filtering approaches are widely used. Read filters can be
incorporated at any stage of the process before alignment. There are two main
filter types. The first filter type (xin2013accelerating, ; xin2015shifted, ;
alser2017gatekeeper, ; alser2017magnet, ; kim2018grim, ; alser2019shouji, ;
bingol2021gatekeeper, ) aims to efficiently filter potential matching
locations in the reference genome that lead to a large number of edits (larger
than a user-defined threshold) between the read and the reference genome at
those locations. Doing so avoids a costly alignment step for potential
locations at which the read would not match the subsequences of the reference
genome. The second filter type (nag2019gencache, ) aims to detect if a read
matches a subsequence of the reference genome with _no_ edits (i.e., exact-
match) or _very few_ (e.g., 1-5) edits. Reads that satisfy this requirement
are guaranteed to align to at least one location in the reference genome
without requiring the costly read alignment process. This filter type is
particularly effective for read sets with a large number of exactly-matching
reads (e.g., 80% in human short read sets (10002015global, ; uk10k2015uk10k, ;
nag2019gencache, )). While both filter types reduce computation overhead, they
still require a large number of random memory accesses for each read, similar
to the baseline read mapper. In a typical read set of several gigabytes, read
filters incur several random accesses per read 1) to the reference index for
seeding, and potentially, 2) to the reference genome to compare the read with
the subsequence of reference genome at each potential matching location.

###  2.2. SSD Organization

Figure 1 depicts the internal organization of a modern NAND flash-based solid-
state drive (SSD) that consists of three main components: 1 NAND flash
packages, 2 an SSD controller, and 3 DRAM.NAND Flash Memory. A NAND package
comprises multiple _dies_ (also called _chips_) that share the package’s I/O
pins. One or more packages share command/data busses (called _channels_) to
connect to the SSD controller. Dies sharing the same channel can operate
independently of each other, but only one die can communicate with the SSD
controller (e.g., for data transfer) at a time via the shared channel. A die
has multiple (e.g., 2 or 4) _planes_. Each plane contains thousands of
_blocks_. A block includes hundreds to thousands of _pages_ , each of which is
4–16 KiB in size. NAND flash memory performs read/write operations at page
granularity but erase operations at block granularity. Planes in the same die
share the peripheral circuitry used to access pages; as such, they can
concurrently operate only when accessing pages (or blocks) at the same offset,
which are called _multi-plane_ operations.

Figure 1. Organizational overview of a modern SSD.

SSD Controller. An SSD controller has two main components: 1) multiple cores
to run SSD firmware, commonly called the _flash translation layer (FTL)_ , and
2) per-channel hardware flash controllers for request handling and error-
correcting codes (ECC) for underlying NAND flash chips. The FTL is responsible
for communication with the host system, internal I/O scheduling, and various
SSD management tasks required for hiding the unique characteristics of NAND
flash memory from the host system. For example, a page of NAND flash memory
needs to first be erased before it is programmed,333This is called the _erase-
before-write_ property. so the FTL always performs _out-of-place_ updates by
writing the new data of a _logical_ page to a new _physical_ page that was
erased previously. To this end, the FTL maintains logical-to-physical (L2P)
address mappings for reads and performs garbage collection to reclaim new
physical pages for writes.

Internal DRAM. A modern SSD employs large low-power DRAM (e.g., 4GB LPDDR4
DRAM for a 4TB SSD (samsung860pro, )) to store metadata for SSD management
tasks. Most of the DRAM capacity is used to store the L2P mappings for address
translation. It is common practice to maintain the L2P mappings at 4KiB
granularity to provide high random access I/O performance (park-nvmsa-2018, ;
kim-dac-2017, ), so in a 32-bit architecture, the memory overhead for the L2P
mappings is approximately 0.1% of the SSD capacity (4 bytes per 4KiB data).

SSD I/O Bandwidth. To mitigate the large performance gap between main memory
and the storage system, SSD manufacturers increase the external bandwidth of
SSDs by employing advanced I/O interfaces between the host system and SSDs.
For example, while older SATA3 SSDs provide around 500MB/s sequential-read
bandwidth (inteldcs4500, ; samsung860pro, ), state-of-the-art PCIe-Gen4 SSDs
can provide significantly higher sequential-read bandwidth, up to 8 GB/s
(e.g., 7 GB/s in Samsung PM1735 (samsungPM1735, )).

A modern SSD’s _internal_ bandwidth (i.e., I/O bandwidth between NAND flash
chips and SSD controller) is usually higher than its external bandwidth (i.e.,
I/O bandwidth between the host and the SSD). For example, a recent enterprise
SSD controller (anandcontroller, ) supports 6,550MB/s external bandwidth and
19.2GB/s internal bandwidth (16 channels, each with a bandwidth of 1.2 GB/s).
Over-provisioning the internal bandwidth is reasonable since 1) a modern SSD
needs to perform various internal management tasks (e.g., garbage collection
(tavakkol2018flin, ; kim2020evanesco, ; cai2017error, ; park-dac-2019, ; park-
dac-2016, ) and wear-leveling (chang2007efficient, ; cai2017error, )), and 2)
a higher channel count reduces contention between requests by interleaving
data between the channels.

##  3\. Motivational Studies

We perform experimental studies to understand the potential of efficient in-
storage accelerators for improving the performance of genome sequence analysis
applications.

###  3.1. Methodology

Read Mappers. We evaluate five read mapping systems, each of which adopts
different optimization techniques to accelerate read mapping: 1) Base uses
Minimap2 (li2018minimap2, ), a state-of-the-art software tool for read
mapping. 2) SW-filter extends Minimap2 to _filter out exactly-matching reads_
(i.e., reads that exactly match subsequences in one or more locations in the
reference genome) using simple single-instruction-multiple-data (SIMD)
operations, without requiring costly ASM operations. 3) Ideal-ISF uses an
ideal In-Storage Filter (_ISF_) that can _concurrently_ filter out exact-
matching reads inside the SSD while the host CPU performs read mapping for
non-filtered reads. 4) ACC uses a state-of-the-art hardware accelerator for
short read mapping, GenCache (nag2019gencache, ). 5) Ideal-ISF+ACC uses an
ideal in-storage filter (ISF) that can _concurrently_ filter out exactly-
matching reads inside the SSD while a hardware accelerator (ACC) performs read
mapping for non-filtered reads.

System Configuration. To assess the impact of the storage subsystem on end-to-
end application performance, we evaluate each of the five systems with four
different configurations: 1) a low-end SSD (SSD-L) (inteldcs4500, ) with a
SATA3 interface (SATA, ), 2) a mid-end SSD (SSD-M) (samsung980pro, ) using a
PCIe Gen3 M.2 interface (PCIE, ), 3) a high-end SSD (SSD-H) (samsungPM1735, )
with a PCIe Gen4 interface (PCIE4, ), and 4) a system where _all_ of the
processed data is pre-loaded to DRAM with no performance cost for pre-loading
(DRAM), as the _idealized_ case where storage I/O overheads are completely
eliminated (we do not evaluate DRAM for Ideal-ISF and Ideal-ISF+ACC since
using in-storage processing is contradictory to pre-loading all the data to
main memory). We assume 8 channels for SSD-L and 16 channels for SSD-M and
SSD-H, where the maximum bandwidth per channel is 1.2 GB/s. The maximum
internal bandwidth is calculated by 1.2 GB/s $\times$ channel count. The
external bandwidth of SSD-L, SSD-M, and SSD-H for sequential reads is 500
MB/s, 3.5 GB/s, and 7 GB/s, respectively. Hence, the internal bandwidth of
SSD-L, SSD-M, and SSD-H for sequential reads is 19.2$\times$, 5.48$\times$,
and 2.74$\times$ that of its external bandwidth, respectively.

We evaluate Base and SW-filter by running Minimap2 on a high-end server (AMD
EPYC 7742 CPU (amdepyc, ) with 1TB DDR4 DRAM). We simulate the performance of
the other three systems using our simulation environment that faithfully
models system components including DRAM and storage devices (see Section 5).
We map all reads of a short read dataset against the human reference genome,
where 80% of the reads have one or more exactly-matching subsequences in the
reference genome (10002015global, ; uk10k2015uk10k, ).

Key Features of an Ideal In-Storage Filter. We assume two key features for
Ideal-ISF and Ideal-ISF+ACC. First, I/O overheads due to limited external SSD
bandwidth are _completely_ eliminated for filtered reads. Second, the system
provides high in-storage filtering performance such that the filtering process
can concurrently run in the SSD, and the latency of this filtering process is
_fully hidden_ by the read mapping of unfiltered reads in the host CPU (Ideal-
ISF) or hardware accelerator (Ideal-ISF+ACC). We assume that the accelerator
or the CPU streams through the input reads in batches and analyzes a batch
_concurrently_ with reading the next batch. Thus, the execution time of Ideal-
ISF (+ACC) can be modeled as follows:

(1) $T_{\text{{Ideal-
ISF}}}=T_{\text{I/O-Ref}}+\max\left\\{T_{\text{I/O-Unfiltered}},T_{\text{RM-
Unfiltered}}\right\\},$

where $T_{\text{I/O-Ref}}$, $T_{\text{I/O-Unfiltered}}$, and $T_{\text{RM-
Unfiltered}}$ are the latency of reading the reference genome from the SSD
into main memory, the latency of reading the unfiltered genomic reads from the
SSD, and the latency of read mapping of the unfiltered reads, respectively.
For a given input size, $T_{\text{RM-Unfiltered}}$ varies depending on the
computation unit used for read mapping (i.e., the host CPU or accelerator),
while the I/O-latency values only depend on the SSD configuration.

###  3.2. Results & Analysis

Figure 2 shows the execution time of read mapping in the five evaluated
systems, each with four different storage subsystem configurations. We make
four key observations.

Observation 1. The ideal in-storage filter provides significant performance
improvements over other systems. Ideal-ISF significantly outperforms Base and
SW-filter (by 3.12$\times$ and 2.21$\times$, respectively), and Ideal-ISF+ACC
provides a large speedup (2.78$\times$) over ACC, when they all use SSD-H.
These large improvements are due to two key benefits provided by the ideal in-
storage filter: 1) mitigation of data movement from the storage devices and 2)
removal of the burden of filtering out 80% of the input read set from the rest
of the system, including processors and main memory. To distinguish the
effects of these two benefits, we analyze an ideal _outside-storage_ filter
(Ideal-OSF) that provides only the second benefit; this filter concurrently
runs with the read mapper and fully overlaps the filtering process with the
read mapping process of unfiltered reads. The execution time of Ideal-OSF
(+ACC) can be formulated as follows:

(2) $T_{\text{{Ideal-OSF}}}=T_{\text{I/O-Ref}}+\max\left\\{T_{\text{I/O-All-
Reads}},T_{\text{RM-Unfiltered}}\right\\},$

where $T_{\text{I/O-All-Reads}}$ is the latency for reading all genomic reads
from the SSD into main memory. Using SSD-H, Ideal-OSF leads to an execution
time of 1.15 seconds, which is 60% slower than the Ideal-ISF+ACC. This is
because $T_{\text{I/O-All-Reads}}$ is significantly larger than both
$T_{\text{RM-Unfiltered}}$ and $T_{\text{I/O-Unfiltered}}$ (in Equation (1)).

Figure 2. Execution time of read mapping with four different storage
configurations.

The remaining observations dive deeper into the effects of the I/O bottleneck
on each read mapping system.

Observation 2. In Base and SW-filter, using high-end SSDs significantly
improves read mapping performance over low-end SSDs, effectively reducing the
storage performance bottleneck that exists in low-end SSDs. For example, using
SSD-H instead of SSD-L reduces the execution time of Base and SW-filter by 24%
and 38%, respectively, showing comparable performance to DRAM, where all the
data is pre-loaded to main memory (i.e., _no_ I/O accesses). This is because,
by using SSD-M and SSD-H, the performance bottleneck of the application shifts
to parts of the system other than I/O (e.g., CPU or main memory). This
observation shows that I/O has a significant impact on application performance
but this impact can be alleviated at the cost of expensive storage devices and
interfaces. Note that, while SSD-M and SSD-H provide an order-of-magnitude
higher bandwidth for sequential reads compared to SSD-L, it is challenging to
scale a storage system’s capacity using the high-end SSDs due to their
significantly-higher prices and the relatively smaller number of the PCIe
slots in a server.444The cost of the total storage system depends on both the
price of each SSD and the available interconnection slots in the systems.
High-bandwidth interconnects such as PCIe take up very large space in the
system. As a result, there are fewer PCIe slots than SATA slots in a system.
For example, building a 16-TB storage system with a single PCIe SSD (Micron
9300 PRO (micros9300pro, )) costs more than 3,000 USD, while the cost is less
than 1,600 USD if we use four 4-TB SATA SSDs (WD BLUE (wdblue, )).

Observation 3. Even though SW-filter outperforms Base, its filtering process
is slow. Potentially, SW-filter could provide significant performance benefits
over Base due to two reasons; 1) as explained, 80% of reads in the dataset
exactly match the reference genome, so only 20% of the reads need to undergo
the costly ASM computaion; 2) exact-match filtering requires only simple
computation, i.e., SIMD XOR operations used by SW-filter. However, even with
DRAM, SW-filter’s speedup over Base is only 41%. The limited speedup is mainly
due to large number of random memory accesses concurrently issued from all
threads to the reference index (explained in Section 2.1). This observation
highlights the potential of in-storage filtering. Even though both SW-filter
and Ideal-ISF filter out the same fraction of reads, the filtering process
outside the SSD must compete with the read mapping process for the resources
in the system (e.g., the limited main memory bandwidth). In contrast,
filtering of reads inside the SSD (where the reads originally reside) can
remove the burden of filtering from the rest of the system.

Observation 4. With a hardware accelerator (ACC), using the state-of-the-art
SSD (SSD-H) does _not_ fully alleviate the storage bottleneck, showing 23%
longer execution time compared to when all the data is pre-loaded to main
memory (DRAM). While using SSD-M and SSD-H in Base and SW-filter shifts the
bottleneck away from I/O, ACC turns I/O into a bottleneck again. This is
because ACC greatly reduces the computational bottleneck, which increases the
relative effect of the storage subsystem on the end-to-end execution time. The
ACC and Ideal-ISF+ACC results clearly show that data movement between the
storage devices and the hardware accelerator, which has not been properly
considered in prior read mapping accelerators (nag2019gencache, ;
cali2020genasm, ; fujiki2018genax, ; turakhia2018darwin, ; madhavan2014race, ;
cheng2018bitmapper2, ; houtgast2018hardware, ; houtgast2017efficient, ;
goyal2017ultra, ; chen2016spark, ; chen2014accelerating, ; chen2021high, ;
huangfu2018radar, ; khatamifard2021genvom, ), can significantly bottleneck the
potential benefits of the accelerator.

Comparison to Other Near-Data Processing Systems. Even though read mapping
applications could also benefit from other near-data processing (NDP)
approaches such as processing-in-main memory (PIM) (kim2018grim, ;
laguna2020seed, ; khatamifard2021genvom, ; kaplan2018rassa, ) or processing-
in-caches (nag2019gencache, ), in-storage processing can _fundamentally_
address the data movement problem by filtering large, low-reuse data _where
the data initially resides_. As an extreme example, even if an _ideal_
accelerator achieved a _zero_ execution time for read mapping by addressing
all of the computation and main memory overheads, there would still exist the
need to bring the data from storage to the accelerator. In our motivational
study, even SSD-H takes at least 1.55 seconds to read the entire dataset,
which is 2.15$\times$ slower than the execution time that Ideal-ISF+ACC
provides (0.72 seconds). Thus, even though solutions such as processing-in-
memory can improve read mapping execution times, they still need to pay the
cost of data movement from the storage system to the main memory
(singh2021fpga, ; turakhia2018darwin, ; cali2020genasm, ; kim2018grim, ;
huangfu2018radar, ; khatamifard2021genvom, ; gupta2019rapid, ; li2021pim, ;
angizi2019aligns, ; zokaee2018aligner, ). Therefore, an in-storage filter can
be further integrated with any read mapping accelerator, including PIM
accelerators, to alleviate their data movement overhead.

###  3.3. Our Goal

Based on our observations, we conclude that an efficient in-storage filter can
be a key enabler for read mappers to achieve high performance in both
conventional software-based (e.g., Base and SW-filter) and new hardware-
accelerated (e.g., ACC) genomics systems. In particular, in-storage filtering
enables the system to take full advantage of the high computation capability
of hardware accelerators by fundamentally addressing the data movement
bottleneck. Our goal is to design an in-storage filter for genome sequence
analysis in a cost-effective manner.

We have three key objectives in designing our new system. First, the system
should provide high in-storage filtering performance to overlap the filtering
with the read mapping of unfiltered data (as Ideal-ISF does in our motivation
study). Second, it should support reads with 1) different properties (e.g.,
lengths and error rates) and 2) different degrees of genetic variation in the
compared genomes. Third, it should _not_ require significant additional
hardware overhead, e.g., complicated logic circuits or large SRAM/DRAM memory.

##  4\. GenStore

We propose _GenStore_ , the first in-storage processing system tailored for
genome sequence analysis. GenStore greatly reduces both data movement and
computational overheads of genome sequence analysis by exploiting low-cost and
accurate in-storage filters. GenStore supports reads with different properties
(lengths and error rates) and different degrees of genetic variation in the
compared genomes. We primarily design GenStore as an in-storage accelerator,
which is an _extension_ of the existing SSD controller and flash translation
layer (FTL). GenStore is designed to be integrated into the system such that,
when the accelerator is not in use, the entire storage device is available to
all other applications, just like in a general-purpose system today.

###  4.1. Overview

The key idea of GenStore is to exploit low-cost _in-storage_ accelerators to
accurately _filter out_ the reads that do not require the expensive alignment
step in read mapping and thus significantly reduce unnecessary data movement
from the storage system to main memory and processors. Figure 3 shows the
overall architecture of GenStore and how it interacts with the host system.
GenStore employs two types of hardware accelerators: 1 a single _SSD-level_
accelerator and 2  _channel-level_ accelerators, each of which is dedicated to
a channel. The GenStore-FTL ( 3) communicates with the host system and manages
the metadata and data flow over the SSD hardware components (i.e., NAND flash
chips, internal DRAM, and in-storage accelerators).

Figure 3. Overview of GenStore.

Once the host system indicates that the SSD should start analysis as required
by a read mapping application ( 1 in Figure 3), GenStore prepares for
operation as an accelerator ( 2). It flushes the conventional FTL metadata
necessary to operate as a regular SSD (e.g., L2P mappings (kim2020evanesco,
)), while loading the GenStore metadata necessary for each use case (Section
4.4 provides more details on GenStore FTL). After finishing the preparation,
GenStore starts the filtering process. It keeps concurrently reading the data
to process from _all_ NAND flash chips ( 3) via multi-plane operations (i.e.,
it exploits the SSD’s full internal bandwidth, which is much higher than the
I/O bandwidth between the SSD and host system (koo2017summarizer, ;
mailthody2019deepstore, )), while filtering out reads ( 4) that do not have to
undergo further analysis (e.g., ASM computation). Doing so is possible due to
multiple channel-level accelerators that provide computational throughput
matching the SSD’s internal bandwidth even for the most complicated
computation required for filtering. The host system performs further
computation as soon as GenStore sends unfiltered reads ( 5), which removes
GenStore’s filtering process almost completely from the critical path of the
application.

As explained in Section 2.2, most of the internal DRAM is occupied by the
regular L2P mapping. Therefore, flushing the regular L2P mapping data into
NAND flash memory enables GenStore to exploit most of the GB-scale DRAM (e.g.,
4GB DRAM in a 4TB SSD (samsung860pro, )) for its operations, which
significantly reduces the overhead of additional internal DRAM that might
otherwise be required to store the GenStore metadata necessary for the
filtering process. We carefully design the GenStore filtering algorithms to
only _sequentially_ access the underlying NAND flash chips, so GenStore
requires only a small amount of metadata to access the stored data. Therefore,
GenStore can use most of the internal DRAM space for such metadata. We
envision that all GenStore metadata are built _offline_ by the host or some
other system (e.g., by the sequencing machine when the read set or reference
genome are initially stored to the SSD). Constructing GenStore metadata is a
_one-time_ preprocessing step that can be performed independently of the read
mapping process, while the result of the preprocessing step can be used
multiple times for different genomics applications.

There exist two main challenges in designing GenStore as an efficient in-
storage filter for read mapping. First, the behavior and data-access patterns
in read mapping significantly vary depending on the read properties (length
and error rate) and genetic variation between the compared genomes. Second,
hardware resources (e.g., CPU and DRAM) are quite limited even in modern high-
end SSDs. We address these challenges via thorough hardware/software co-design
tailored for filtering 1) exactly-matching reads, i.e., reads that exactly
match subsequences of the reference genome (Section 4.2), and 2) most of the
non-matching reads, i.e., reads that would not align to any subsequence of the
reference genome (Section 4.3).

###  4.2. GenStore-EM for Exactly-Matching Reads

####  4.2.1. Approach Overview

GenStore-EM accelerates read mapping by using an efficient in-storage filter
for reads that have at least one exact match in the reference genome. Due to
the low error rates of short reads, combined with low genetic variation
between the compared genomes, a large fraction of short reads map _exactly_ to
the reference genome (10002015global, ; uk10k2015uk10k, ; nag2019gencache, ).
For example, on average 80% of human short reads map _exactly_ to the human
reference genome (10002015global, ; uk10k2015uk10k, ; nag2019gencache, ).
Since exact-match detection is computationally cheaper than ASM, concurrently
filtering exact-matching reads inside the SSD can significantly improve the
runtime of read mapping (as we demonstrate in Section 3). Note that, GenStore-
EM is not applicable to long reads due to their greater length. For example,
for a 10K base pair-long human read, even with zero sequencing error rate, the
probability of the read exactly matching a subsequence in the reference genome
is very low (e.g., $<3.6\times 10^{-6}$) due to natural genetic variation.555A
typical human genome contains genetic variations at $\sim$4.1 to 5 million
(10002015global, ) out of a total of $\sim$3.2 billion base pairs
(schneider2017evaluation, ). Thus, each 10K-bps read contains, on average,
$\sim$12.5 to 15.3 base pairs that are different from the reference genome.

Key Challenges. The key challenge in designing GenStore-EM is the large number
of random accesses to large data structures inside the SSD. As explained in
Section 2, identifying exact matches for read mapping requires a number of
random accesses _for each k-mer in a read_ to two large data structures: 1) a
large k-mer index, to find potential matching locations of each k-mer in the
reference genome, and 2) the reference genome, to find candidate matching
sequences at the candidate matching locations in the reference genome.
Handling random accesses to large data structures is challenging for NAND
flash-based SSDs for two reasons. First, NAND flash memory exhibits poor
performance for random access reads. Second, we cannot use in-SSD DRAM to
store the large data structures that are randomly accessed, since even in
high-end SSDs, the size of internal DRAM is relatively small (e.g., 4 GB
(samsung860pro, )) compared to the size of the data structures that GenStore-
EM needs to handle (e.g., 7 GB for the human reference genome and its index
(li2018minimap2, )).

Key Idea. The key idea in GenStore-EM is to _sequentialize_ most data accesses
via a carefully designed metadata structure and data layout. To do so, we
design a new _sorted,_ _read-sized_ k-mer index structure. This index enables
_sequential_ scanning of the read set and the new index, with only one index
lookup per read while performing filtering.

Figure 4 shows the key idea of GenStore-EM with a simplified example in which
each short read consists of three base pairs (bps).666In a realistic scenario,
the read length is much larger (e.g., 150 bps). Suppose that we have two data
structures: 1) a sorted read table (_SRTable_), each entry of which stores a
read and its unique ID, and 2) a sorted k-mer index (_SKIndex_), which
contains _all unique read-sized_ k-mers of the reference genome, along with
each k-mer’s corresponding locations in the reference genome. Each data
structure is _sorted_ by read/k-mer in alphabetical order. With these two data
structures, it is possible to identify each read’s exactly-matching locations
in the reference genome by _streaming_ both reads and k-mers through a simple
comparator. We use two pointers, $r$ and $k$, which point to the current
entries we are examining in SRTable and SKIndex, respectively. We
_sequentially increment_ the two pointers in three different ways based on the
comparison result of the current read and k-mer. First, when the current read
and k-mer are identical ( 1 in Figure 4), we record the read as an exactly-
matching read and increment $r$ and $k$. Second, if the read is alphabetically
larger than the k-mer ( 2), we conclude that the k-mer does not match any read
in SRTable and increment $k$ (so that we can examine if the next k-mer matches
the read). Third, if the k-mer is alphabetically larger than the read ( 3), we
conclude that the read does not match any k-mer in SKIndex. We record the read
as _not_ an exact match and increment $r$ (so that we can examine the next
read).

Figure 4. Overview of the key idea of GenStore-EM.

GenStore-EM’s two data structures and filtering algorithm enable an exact-
match filter highly suitable for in-storage processing. First, since these two
data structures are only sequentially accessed, the filtering process can be
done in a _streaming_ manner, leveraging the high sequential read bandwidth of
NAND flash memory. Second, we can easily perform exact-match detection of a
read and a read-sized k-mer with simple comparator logic and fully pipeline
the filtering process with sequential access to the data structures.

A _read-sized_ k-mer index increases the total amount of accessed data for
read mapping. The reason is that a read-length value of k (e.g., k=150)
significantly increases the number of unique k-mers, compared to the k values
commonly used in conventional read mappers (e.g., k=15). For example, the size
of an index structure for all unique k-mers in the human reference genome is
21 GB when k=15, while the size increases to 126 GB when k=150. However, our
proposal (i.e., a large yet sequentially-accessed SKIndex) is feasible and
desirable for in-storage processing due to the large capacity and high
internal bandwidth of modern NAND flash-based SSDs.

####  4.2.2. Design of GenStore-EM

Figure 5 illustrates the overall operational flow of GenStore-EM, which
consists of two steps: Step 1. data fetching and Step 2. exact-match
filtering. GenStore-EM uses the two data structures explained in Section
4.2.1: 1) a sorted read table (SRTable) for storing the read set and 2) a
sorted k-mer index (SKIndex) for storing read-sized k-mers from the reference
genome. Step 1 reads the two data structures from NAND flash chips to the
SSD’s internal DRAM in a batched manner ( 1 in Figure 5). Step 2 performs
exact-match filtering within each read batch, using simple comparator logic in
the SSD-level accelerator ( 2). Steps 1 and 2 are performed in a pipelined
manner. During filtering, GenStore-EM sends the unfiltered reads to the host
system for full read mapping. This enables the concurrent filtering of reads
in the SSD and read mapping of the unfiltered reads in the host system.

Figure 5. Overview of GenStore-EM.

Data Structures. We carefully design SRTable and SKIndex to minimize
performance and storage overheads of GenStore-EM, by extending the two data
structures described in Figure 4 in two aspects. First, both SRTable and
SKIndex contain a _strong_ hash value (e.g., SHA-1 (dang2015secure, ) or MD5
(rivest1992rfc1321, )) of each read and read-sized k-mer, respectively, which
is used as both the sorting criterion of the data structures and a
_fingerprint_ of each read and k-mer that is used by the comparator logic.
Second, unlike the data structures described in Figure 4, SKIndex no longer
contains the k-mers of the reference genome but only the fingerprints of the
k-mers. Using strong hash values enables GenStore-EM to determine exact
matches between a read and a k-mer by comparing only their fingerprints, which
provides two benefits. First, it reduces the storage overhead of SKIndex by
obviating the need to store the raw read-sized k-mers.777We design SRTable to
store the raw reads so that we can transfer _unfiltered_ reads to the host for
full read mapping after we detect them as non-exactly-matching reads. For the
human reference genome, the size of the optimized SKIndex (which stores
fingerprints instead of read-sized k-mers) is 32 GB when the read size is 150
bps, which is 3.9$\times$ smaller than the size of the unoptimized SKIndex.
Second, using fingerprints significantly reduces the performance overhead of
exact-match detection by avoiding comparisons of reads and k-mers that are
hundreds of bytes in size.

Note that such exact-match detection does _not_ affect the accuracy of read
mapping due to the extremely low collision rate of strong hash functions. Even
in an extremely rare case of a hash collision, the impact of the collision on
GenStore’s accuracy will be negligible (arxivGS, ), since the DNA information
loss due to the falsely filtered read will highly likely be compensated by
other reads generated from the neighboring locations in the DNA, which almost
_fully_ overlap with the falsely filtered read but have totally different hash
values. This is because it is common practice to sequence each DNA fragment
several times (i.e., with high coverage) to improve the accuracy of downstream
genetic analyses (sims2014sequencing, ; quail2012tale, ; levy2016advancements,
; hu2021next, ).

We envision that all GenStore data structures are built _offline_ by the host
or some other system (e.g., by the sequencing machine when the read set or
reference genome are initially written to the SSD). This preprocessing
overhead can be hidden by two essential initial steps of the genome sequence
analysis pipeline: 1) sequencing and 2) basecalling. For example, in the
current highest-throughput Illumina NovaSeq 6000 sequencer (illumina, ),
sequencing and basecalling work in a pipelined manner and generate genomic
read data at a limited throughput of 18.9 MB/s (illumina, ). We analyze the
throughput of GenStore’s preprocessing step (i.e., generating hash values and
sorting reads) and observe that even a personal laptop (lenovot740p, ) can
provide 174 MB/s of preprocessing throughput. Therefore, GenStore’s
preprocessing can be done in a pipelined manner with sequencing/basecalling,
without decreasing the overall throughput of these steps. This low
preprocessing overhead can be further amortized since the preprocessed data
can be reused multiple times in different read mapping experiments.

Step 1. Data Fetching. GenStore-EM reads SRTable and SKIndex in batches, while
exploiting the _full_ internal bandwidth of the SSD. In Figure 5, we refer to
each batch of SRTable as an _SRTable Batch_ and each batch of SKIndex as an
_SKIndex batch_. The batch size is equal to the size of data that can be read
in parallel by a multi-plane read operation for each chip (i.e., _Number of
Planes in the SSD_ $\times$  _Page Size_), which enables 100% utilization of
the NAND flash chips while reading a batch. As shown in Figure 5 (bottom),
GenStore-EM stores the SRTable and SKIndex to NAND flash chips in an
_interleaved_ manner so that each of the data structures can be _sequentially_
, _evenly_ distributed across all the NAND flash chips.

GenStore-EM exploits the SSD’s full internal bandwidth using double buffering.
As shown in Figure 5, GenStore-EM employs two sets of batch buffers in the
internal DRAM: _SRTable Buffer_ (for SRTable) and _SKIndex Buffer_ (for
SKIndex), each of which can store two batches of the respective data
structure. After Step 1 finishes fetching $Batch\\#i$, it proceeds to fetching
$Batch\\#i+1$, while Step 2 starts working on $Batch\\#i$. If the two steps
work with the same throughput, we only need to buffer two batches for each
data structure. For example, to enable double-buffering in an 8-channel SSD
(with four 2-plane dies per channel and 16-KiB pages), the batch buffers
require 8MB DRAM space in total.

Step 2. Exact-Match Filtering. Step 2 scans through each batch of SRTable and
SKIndex stored in SRTable Buffer and SKIndex Buffer, respectively, comparing
the fingerprints (strong hash values) with a simple hardware comparator. When
$FP(r_{i})>FP(k_{j})$ (where $FP(x)$ is the fingerprint of $x$, and $r_{i}$
and $k_{j}$ are the $i$-th read and $j$-th k-mer in the current batch,
respectively), Step 2 scans SKIndex while increasing $j$ until it finds
$k_{j}$ such that $FP(r_{i})\leq{}FP(k_{j})$. If $FP(r_{i})<FP({{k}}_{j})$, it
is guaranteed that no exact match exists for read $r_{i}$, so GenStore-EM
sends $r_{i}$ to the host for the read mapping process. When
$FP(r_{i})=FP({{k}}_{j})$, i.e., the two fingerprints are identical, and
GenStore-EM marks the read as an exactly matching read.

Due to the simple computation in Step 2, the execution time of GenStore-EM is
bottlenecked by Step 1 (Data Fetching). As explained, Step 1 only streams the
data structures in batches from the underlying NAND flash chips to the
internal DRAM, leveraging the SSD’s full internal bandwidth. Therefore, the
performance of GenStore-ER can be easily scaled up by increasing the SSD’s
internal parallelism (e.g., by deploying more channels or using low-latency
NAND flash memory (cheong-isscc-2018, ; park-nvmsa-2018, ; park-asplos-2021,
)).

###  4.3. GenStore-NM for Non-Matching Reads

####  4.3.1. Approach Overview

GenStore-NM filters most of the _n on-matching_ reads, i.e., reads that would
not align to any subsequence in the reference genome. This is motivated by the
fact that in read mapping, a large fraction of reads might _not_ align to the
reference genome due to 1) the high sequencing error rate (in long reads)
and/or 2) high genetic variation between the compared genomes (in both short
and long reads). To illustrate this, we analyze four read mapping use cases,
one with read sets with high sequencing error rates, and three with high
genetic variation in the compared genomes. Use cases with high genetic
variation include 1) samples from rapidly-evolving species (such as SARS-CoV-2
(bhoyar2021high, )) that have high genetic variation compared to the reference
genome, 2) samples with no known reference genomes, and 3) mapping a read set
against the human reference genome to filter out _human contamination_ , i.e.,
reads that have been sequenced from human-origin contaminant DNA in a non-
human sample.888Contamination of non-human samples with human DNA is commonly
observed (breitwieser2019human, ; human2012structure, ) and corrected for
(danko2021global, ; knight2018best, ; human2012structure, ). For each use case
(except for the _Contamination_ use case), we analyze two different
combinations of the input read set and the reference. Table 1 summarizes the
result of this analysis by showing input read sets, the properties of each
read set (e.g., read length and dataset size), reference genomes, and the
percentage of reads in each read set that align to subsequences in the
reference genome. We observe that a large fraction of reads (31.7%–99.6%)
within a read set does _not align to any subsequence_ in the reference genome.
Quickly filtering this large fraction of non-aligning reads in the SSD can
reduce the large data movement from the storage and expensive ASM computation
for reads that would not align.

Table 1. Fraction of aligning reads in various read mapping use cases with
short and long reads.

Use case | Input read set (Short/Long) | Size | Reference | Align
---|---|---|---|---
[GB] | [%]
Sequencing errors | ERR3988483 (L) (sayers2021database, ) | 54 | hg38 (schneider2017evaluation, ) | 47.4
HG002_ONT_20200204 (L) (zook2016extensive, ) | 371 | 69.3
Rapidly evolving | SRR5413248 (L) (sayers2021database, ) | 1.69 | NZ_NJEX02 (clark2016genbank, ) | 60.0
samples | SRR12423642 (S) (sayers2021database, ) | 0.466 | NC_045512.2 (wu2020new, ) | 23.1
No reference | SRR6767727 (L) (sayers2021database, ) | 12.4 | NZ_NJEX02 (clark2016genbank, ) | 0.35
SRR9953689 (L) (sayers2021database, ) | 15.9 | 37.0
Contamination | SRR9953689 (L) (sayers2021database, ) | 15.9 | hg38 (schneider2017evaluation, ) | 1.0

To avoid expensive ASM computation for reads that would not be aligned, state-
of-the-art read mappers commonly employ a step called _chaining_ (described in
Section 2.1), which calculates each read’s similarity score (called _chaining
score_) to the reference genome and filters out reads with a low score.
GenStore-NM uses this basic idea of chaining to build an in-storage filter.

Key Challenges. Calculating a chaining score in the SSD is challenging because
finding the best chaining score requires performing an expensive dynamic
programming (DP) algorithm on every potential matching location (i.e., seed)
within a read (explained in Section 2.1). Normally this operation has
$\mathcal{O}(N^{2})$ time and space complexity, where $N$ is the number of
seeds. Even though a chaining score can be approximated accurately in
$\mathcal{O}(hN)$ time and space by considering only $h<50$ seeds at a time
(li2018minimap2, ), we observe that some long reads can have up to thousands
of seeds due to their length. Therefore, designing a chaining accelerator to
perform an expensive DP algorithm on these large reads ($N>1000$) can incur
significant performance or area overheads.

Key Ideas. To avoid such expensive chaining, GenStore-NM selectively performs
a fast version of chaining _only_ on reads with a small number of seeds and
sends other reads to the host system for full read mapping (including complete
chaining). This idea is based on our key observation that 1) a read with a
large number of seeds most likely aligns to the reference genome and does not
require in-storage filtering, and 2) selective chaining can filter many non-
aligning long reads, without requiring costly hardware resources in the SSD.
Figure 6 shows the alignment probability of a read in a long read dataset
(SRR5413248 (sichtig2019fda, ) in Table 1) to subsequences in the reference
genome (NZ_NJEX02 (clark2016genbank, )), as a function of the number of seeds
per read ($N$). The average read length in this dataset is 10K base pairs and
the number of seeds goes up to several thousands for some reads. We observe
that reads with a sufficiently large number of seeds are very likely to align
to subsequences in the reference genome (e.g., at least 85% of reads with
$N\geq 64$ seeds align). Such reads can be directly sent to the CPU for full
read mapping (bypassing the in-storage chaining-based filter).

Figure 6. Alignment probability as a function of the number of seeds per read
in a long read mapping use case.

We extend this analysis to read datasets from various organisms commonly used
in genomics studies: E. coli (clark2016genbank, ), yeast (engel2014reference,
), thale cress (berardini2015arabidopsis, ), fruit fly (larkin2020, ), mouse
(church2009lineage, ), and human (schneider2017evaluation, ). We observe that
when a read has $N=64$, $128$, or $256$ seeds, it aligns with average
probabilities of $88.87\%$, $91.32\%$, and $93.84\%$, respectively. Based on
these observations, we design GenStore-NM to _selectively_ perform chaining
only on reads with fewer than $N$ seeds, while sending reads with at least $N$
seeds to the host system.999GenStore-NM’s design can be tuned based on
different values of $N$. This selective chaining significantly reduces the
chaining execution time and additional hardware area cost, while filtering
most reads that would not align to the reference genome.

####  4.3.2. Design of GenStore-NM

Figure 7 shows the overview of GenStore-NM that filters out most of the non-
matching reads in three steps. In Step 1, GenStore-NM reads the input read set
from the flash chips, generates minimizer k-mers for each read (as explained
in Section 2.1), and looks up each minimizer in a _K-mer Index_ (KmerIndex) to
find the potential matching locations, i.e., seeds ( 1 in Figure 7). In Step
2, GenStore-NM counts the number of seeds in each read to decide if the read
needs to go through chaining ( 2). To further improve overall performance,
Step 2 also filters out reads with _too few_ seeds (i.e., $<M$), which would
not align to the reference and thus would be filtered anyway by the baseline
read mapper (li2018minimap2, ). In Step 3, GenStore-NM filters reads based on
their chaining scores using a fast and efficient chaining accelerator ( 3). If
a read has at least one chain with a score above a specified threshold, it is
sent to the CPU for mapping. Otherwise, the read is filtered. All three steps
run in a pipelined manner.

Figure 7. Overview of GenStore-NM.

Data Structures. We carefully design the KmerIndex to reduce the SSD’s
internal DRAM capacity required for storing it. KmerIndex, similar to the
index used by the baseline read mapping tool (i.e., Minimap2 (li2018minimap2,
)), is a hierarchical hash table. To reduce the memory capacity required for
storing the KmerIndex, we make three modifications: 1) not store the reference
genome since it is not needed by our approach, 2) not store seeds with _many_
matching locations (e.g., more than 495 locations in the baseline read mapper
(li2018minimap2, ))101010Each matching k-mer can map to one or more locations
in the reference genome. since read mappers usually ignore such seeds in the
chaining process (li2018minimap2, ), and 3) increase the number of hash table
buckets so that each bucket holds one minimizer. Increasing the number of
buckets increases the false positive rate in the filter, which leads to
finding extra seeds and performing extra chaining operations (without loss of
accuracy). We make this trade-off to reduce the KmerIndex’s size and the
required memory space. These optimizations reduce the size of the index for
the human reference genome (li2018minimap2, ) from 5.8 GB to 2.9 GB, which
enables GenStore-NM to easily store the KmerIndex in the limited DRAM space
inside the SSD.

Step 1: Seed Finding. This step finds the potential matching locations of a
read (i.e., seeds) in the KmerIndex. GenStore-NM first reads the input read
set from all flash chips ( 1 in Figure 7). GenStore-NM exploits the _full_
internal bandwidth of the SSD by reading the read set in parallel via a multi-
plane read operation for each chip (same as GenStore-EM, Section 4.2.2). In a
shifting buffer (called the _K-mer Window_) in the channel-level accelerator,
GenStore-NM stores the $w$ most recently read k-mers of each read. For each
sliding window of $w$ k-mers,111111The default value for $w$ in Minimap2
(li2018minimap2, ) is 10, but GenStore’s design can be tuned for different
values. GenStore-NM finds the minimizer of the window (described in Section
2.1) using a 64-bit Integer Mix hash function (hash64) (wang2007integer, ) in
the SSD-level accelerator ( 2). GenStore -NM queries each minimizer in the
KmerIndex until it reads $N$ seeds (e.g., $N$ = 64) or it reaches the end of
the read ( 3). Each index query takes up to two memory accesses (to visit the
two levels of the hash table). GenStore-NM stores the seeds in the _Location
Buffer_ in the channel-level accelerator ( 4), and moves to Step 2.

Step 2: Seed Count-Based Filtering. This step compares the number of seeds in
the Location Buffer with a lower bound $M$ and an upper bound $N$. If a read
has fewer than $M$ matching seeds, it is filtered since it will not meet the
minimum chaining score requirement of the baseline read mapper
(li2018minimap2, ).121212We use $M$=3, as in (li2018minimap2, ), but GenStore-
NM’s design trivially supports different values of $M$. If the read has more
than $N$ seeds, it means that the read will very likely align to the reference
(e.g., reads with at least 64 seeds in Figure 6) and thus require the full
read mapping process. GenStore-NM sends such reads to the host system for the
full read mapping process. This way, the read mapping process of the
unfiltered reads can run concurrently with GenStore’s filtering operations.
For any other read, GenStore-NM performs chaining in the SSD in Step 3.

Step 3: Chaining-Based Filtering. This step performs chaining (see Section
2.1), a step commonly used in state-of-the-art read mappers (li2018minimap2, ;
dobin2012, ; li2016minimap, ) to filter out reads with low chaining scores and
send reads with high chaining scores to the CPU to undergo the full read
mapping process. The key difference in GenStore-NM’s chaining process compared
to existing read mappers is that GenStore-NM _selectively_ performs chaining
only on reads with lower seed counts than a threshold $N$. Such selective
chaining is based on our two key observations; 1) a long read with many seeds
most likely aligns to the reference genome and thus does not require in-
storage filtering, and 2) selective chaining can filter many non-aligning long
reads, without requiring costly hardware resources in the SSD (as shown in
Section 4.3.1).

We design GenStore-NM’s chaining unit based on the chaining algorithm used in
Minimap2 (li2018minimap2, ), a state-of-the-art baseline read mapper. A chain
is computed from a sequence of seeds $S_{1},\ldots,S_{N}$131313Sorted based on
their locations in the reference genome. of lengths $w_{1},\ldots,w_{N}$,
respectively. For a given seed $S_{i}$, $x_{i}$ ($y_{i}$) denotes the ending
position of the seed’s matching location in the reference genome (the read).
The chaining score acts as an approximation of an alignment score, increasing
linearly with the number of matching base pairs between the read and the
reference, and decreasing with the size of gaps between the seeds. The
chaining score is defined as follows (based on (li2018minimap2, )):

(3) $f(i)=\max\left\\{\mathop{\max}_{i>j\geq
1}\left\\{f(j)+\alpha(j,i)-\beta(j,i)\right\\},w_{i}\right\\},$

where $f(i)$ is the best chaining score which can be computed with the seeds
$S_{1},\ldots,S_{i}$. Given a chain whose last seed is $S_{j}$, $\alpha(j,i)$
(also called the _match score_) is the number of new base pairs added to the
chain after adding $S_{i}$. $\beta(j,i)$ (also called the _gap penalty_)
subtracts from the chain score based on the distance between $S_{i}$ and
$S_{j}$ in the reference genome.141414See Minimap2 (li2018minimap2, ) for more
details regarding $\alpha(j,i)$ and $\beta(j,i)$.

GenStore-NM’s Chaining-Based Filter (in Figure 7) consists of 1) a  _Chaining
Buffer_ to store $x_{i}$, $y_{i}$, $w_{i}$, and $f(i)$ values and 2) a
_Chaining Processing Element (PE)_ based on Equation (3). Figure 8 shows the
design of the Chaining PE in the channel-level accelerator. We reduce the
latency and size of this unit by approximating multiplication with shift
operations. We ensure that our hardware optimizations always over-estimate the
chaining score so that we do not filter out any potential read mappings.
GenStore-NM does not affect the accuracy of the read mapper because the filter
performs the same computations as the baseline chaining filter for reads with
seeds $<N$ inside SSD. The chaining PE needs to be executed $N\times M$ times
per read where $N$ is the number of seeds per read and $M$ is the DP-
iterations of each seed. Due to the limited number of seeds that go through
the chaining step, we limit the number of chaining units that are needed to
match the full internal bandwidth of SSD.

Figure 8. Chaining processing element (PE) in GenStore-NM.

Similar to GenStore-EM, the steps of GenStore-NM are pipelined. The
performance of GenStore-NM can be easily scaled up by increasing the SSD’s
internal parallelism (e.g., by deploying more channels or using low-latency
NAND flash memory) (cheong-isscc-2018, ; park-nvmsa-2018, ; park-asplos-2021,
).

###  4.4. GenStore Flash Translation Layer (FTL)

GenStore requires simple changes to the existing FTL code.

GenStore FTL Metadata. GenStore metadata includes the mapping information of
the data structures necessary for read mapping acceleration, which enables
access to the data structures without the L2P mapping table of the regular
FTL. In accelerator mode, where GenStore operates as an accelerator, GenStore
also keeps in internal DRAM other metadata structures of the regular FTL
(e.g., the page status table and block read counts (park-asplos-2021, ;
cai2017error, )) which need to be updated during the filtering process. We
carefully design GenStore to only _sequentially_ access the underlying NAND
flash chips while operating as an accelerator, so it requires only a small
amount of metadata to access the stored data.

Data Placement. GenStore needs to properly place its data structures to enable
the full utilization of the internal SSD bandwidth in accelerator mode. When
each data structure is initially written to the SSD, GenStore sequentially and
evenly distributes it across NAND flash chips. We design GenStore to store
every data structure using multiple sets of NAND flash blocks such that each
block set consists of NAND flash blocks with the same block offset across the
planes in a die. For example, a die’s block set $k$ includes all NAND flash
blocks whose offset is $k$ in the die. Such data placement enables GenStore
not only to always perform _multi-plane_ read operations during the filtering
process, but also to significantly reduce the size of GenStore metadata. For
example, suppose that a GenStore-enabled SSD consists of 128 2-plane NAND
flash dies, and the block size is 12 MB (i.e., the size of each block set
would be 24 MB). In such a case, GenStore can specify the physical location of
a 30-GB data structure by maintaining only the list of 1,250 (30 GB/24 MB)
physical block addresses. This way, GenStore significantly reduces the size of
the necessary mapping information from 300 MB (with conventional 4-KiB page
mapping) to only 5 KB (1,250$\times$4 bytes), and the saved internal DRAM
space can be used for loading data structures in the accelerator mode.

SSD Management Tasks. In accelerator mode, GenStore stops working as a regular
SSD. It only reads data structures to perform filtering, and does not write
any new data. Therefore, GenStore does not require any write-related SSD-
management tasks such as garbage collection (tavakkol2018flin, ;
kim2020evanesco, ; cai2017error, ; park-dac-2016, ; park-dac-2019, ) and wear-
leveling (chang2007efficient, ; cai2017error, ; cai-insidessd-2018, ).

The other tasks necessary for ensuring data reliability, such as refreshing
data to avoid uncorrectable errors due to data retention and read disturb
(cai-hpca-2017, ; luo2018improving, ; luo-hpca-2018, ; cai2015read, ;
cai2013error, ; cai2012flash, ; cai2017error, ; ha2015integrated, ; cai-
insidessd-2018, ; luo2015warm, ), can be done before or after the filtering
process, for two reasons. First, GenStore significantly limits the amount of
data whose retention age would exceed the manufacturer-specified threshold for
reliable operation (e.g., 1 year (micron3dnandflyer, )) during the filtering
process, since GenStore’s filtering process takes a short time.151515E.g.,
less than 7 minutes for a 1TiB dataset even with a low-end SSD (SSD-L)
(samsung860pro, ). GenStore simply refreshes such data (cai2013error, ;
luo2018improving, ; cai2017error, ; cai2012flash, ) before starting the
filtering process. Second, GenStore-FTL can easily avoid read disturbance
errors for data with high read counts (cai2015read, ; ha2015integrated, )
since GenStore sequentially reads NAND flash blocks only _once_ during
filtering. After the filtering process, to prevent read disturb errors in
future filtering processes or regular accesses, GenStore refreshes pages that
store a data structure if the structure’s read count exceeds a certain
threshold.

##  5\. Evaluation Methodology

Evaluated Systems. We show the benefits of GenStore when it is integrated with
the state-of-the-art software and hardware read mappers. To this end, we
evaluate the following systems:

  * $\circ$

Base: Minimap2 (li2018minimap2, ) is a state-of-the-art software read mapper
baseline for both short and long reads. GenCache (nag2019gencache, ) and
Darwin (turakhia2018darwin, ) are state-of-the-art hardware read mappers for
short and long reads, respectively.

  * $\circ$

GS-Ext: Base integrated with an implementation of the GenStore filter without
in-storage support (Ext stands for _external_ to storage). GS-Ext concurrently
filters reads while using Base to perform read mapping for unfiltered reads.
The goal of evaluating GS-Ext is to decouple the effects of GenStore’s two
major benefits: 1) alleviating I/O bottlenecks via efficient in-storage
processing and 2) reducing the workload of the read mapper by filtering reads
with simple operations. GS-Ext obtains the second benefit but not the first.
For software read mappers, we evaluate a pure software implementation of
GenStore that concurrently runs with Base.161616We do not evaluate a separate
GS-Ext configuration for long read software mapper since Base (Minimap2
(li2018minimap2, )) already incorporates the chaining filter used in GenStore-
NM. GenStore-NM implements part of this chaining filter at low cost (enabled
by the key observations in Section 4.3) to fit within the constraints of in-
storage processing. For hardware read mappers, we evaluate a hardware
implementation of GenStore _outside_ the SSD.

  * $\circ$

GS: Base integrated with the hardware GenStore filtering accelerators,
GenStore-EM and GenStore-NM, as described in Sections 4.2 and 4.3. GS
concurrently filters reads _inside_ the SSD while using Base to perform read
mapping for unfiltered reads.

The source code of GenStore and scripts and datasets can be freely downloaded
from https://github.com/CMU-SAFARI/GenStore.

Area and Power. We implement GenStore’s logic components in Verilog HDL. We
synthesize our designs using the Synopsys Design Compiler (synopsysdc, ) with
a 65nm process technology node to estimate latency, area and power
consumption. We use the SSD power values of the Samsung 3D NAND flash-based
SSD (samsung860pro, ), and DRAM power values based on DDR4 model (ddr4sheet, ;
ghose2019demystifying, ).

Performance Modeling. We evaluate hardware configurations using two state-of-
the-art simulators to analyze the performance of GenStore. We model DRAM
timing with the DDR4 interface (ghose2019demystifying, ; ghose2018your, ) in
Ramulator (kim2016ramulator, ; ramulatorsource, ), a widely-used, cycle-
accurate DRAM simulator. We model SSD performance using MQSim
(tavakkol2018mqsim, ), a widely-used simulator for modern SSDs. We model the
end-to-end throughput of GenStore based on the throughput of each GenStore
pipeline stage: accessing NAND flash chips, accessing internal DRAM,
accelerator computation, and transferring unfiltered data to the host. We
estimate the performance of GenCache and Darwin accelerators based on the data
reported in the original works (nag2019gencache, ; turakhia2018darwin, ).

Real System Results. We use real systems to evaluate all software
configurations. For a given reference genome, separate reference indexes are
generated for each sequencing technology using the software read mapper’s
default settings for each technology (li2018minimap2, ). All other read
mapping parameters are kept at their default values. We perform all
experiments on an AMD${}^{\text{\textregistered}}$
EPYC${}^{\text{\textregistered}}$ 7742 CPU with 1TB DDR4 DRAM (available in
user space). We measure power in these systems using
AMD${}^{\text{\textregistered}}$ µProf (microprof, ). We carefully evaluate
GenStore’s benefits over the baseline in a conservative manner by using
optimized configurations for all baselines. Our baselines fetch data from the
SSD by sequentially reading the data in batches (li2018minimap2, ), while
providing sufficiently large DRAM capacity to contain all data that gets
reused _during_ read mapping. We use the number of threads that leads to each
software configuration’s best performance (i.e., execution time): 128 threads
for Base and 16 threads for GS-Ext in our experimental setup.171717Performance
of GS-Ext saturates after 16 threads since it becomes bottlenecked by the
external SSD bandwidth.

SSD Configurations. We analyze the benefits of GenStore on three SSD
configurations: 1) a low-end SSD (SSD-L) (inteldcs4500, ) with a SATA3
interface (SATA, ), 2) a mid-end SSD (SSD-M) (samsung980pro, ) using a PCIe
Gen3 M.2 interface (PCIE, ), and 3) a high-end SSD (SSD-H) (samsungPM1735, )
with a PCIe Gen4 interface (PCIE4, ).

Datasets. For short read experiments, we use the hg38 human reference genome
(schneider2017evaluation, ). In Section 3, we use real short reads(SRR2052419
(zook2016extensive, ), 19.6 GB). In Section 6, to flexibly and controllably
analyze the effect of read sets with different features, we simulate read sets
with various sizes (up to 440 GB) and different fractions of exactly-matching
reads (75% and 85%) using the Mason 2 genomic read simulator
(holtgrewe2010mason, ). We generate reads with different exact-match rates by
introducing sequence mutations (uniformly randomly drawn from the gold-
standard mutation list for the human sample NA12878 (zook2016extensive, )) to
the reference genome. For the long read experiments, we use the reference
genome and read set from Table 1 in Section 4.3.1. To flexibly analyze the
effect of data size, we generate larger read sets by concatenating the
original read sets several times.

##  6\. Evaluation

###  6.1. Area and Power Analysis

We propose GenStore as an in-storage processing system that supports both
accurate short reads and error-prone long reads with different levels of
genetic variation between compared genomes. Table 2 shows the area and power
consumption of each logic unit used in GenStore. In the first column, the
table shows the different logic units used in GenStore along with the width of
each entry. The second column shows the number of instances of each unit in an
8-channel SSD. We find the number of instances based on the frequency of and
the required throughput from each unit such that GenStore can process data
concurrently read from all planes in all SSD channels. GenStore’s hardware
units work at different clock frequencies, with the lowest frequency being 300
MHz (for each channel-level Chaining PE). While the hardware units can be
designed to operate at higher frequency, their throughput is sufficient when
operating at lower frequencies since the end-to-end execution time of GenStore
is bottlenecked by NAND flash reads. The third and fourth columns show the
area and power of one instance of each unit.

Table 2. Area and power breakdown of GenStore’s logic

Logic unit | # of instances | Area [mm2] | Power [mW]
---|---|---|---
Comparator (64-bit) | 1 per SSD | 0.0007 | 0.14
$K$-mer Window ($10\times 19\text{-bit}$) | 2 per channel | 0.0018 | 0.27
Hash Accelerator (64-bit) | 2 per SSD | 0.008 | 1.8
Location Buffer ($64\times 64\text{-bit}$) | 1 per channel | 0.00725 | 0.37375
Chaining Buffer ($50\times(16\text{-bit}+64\text{-bit})$) | 1 per channel | 0.008 | 0.95
Chaining PE | 1 per channel | 0.004 | 0.98
Control | 1 per SSD | 0.0002 | 0.11
Total for an 8-channel SSD | - | 0.20 | 26.6

The total hardware area needed for GenStore is very small (0.20 mm2 at 65 nm
and 0.02 mm2 at 14 nm, only 0.006% of a 14nm Intel Processor (wikichipcascade,
)).181818Since lower technology nodes are not available publicly, we scale the
area consumption down to lower process technology nodes using the methodology
in (stillmaker2017Scaling, ). The area overhead of GenStore hardware (0.06 mm2
at 32 nm) is less than 9.5% of the three 28nm ARM Cortex R4 processors
(cortexr4, ) in a SATA SSD controller (samsung860pro, ).

The area and power of most logic units (except for the comparator, the hash64
accelerator, and the control unit) increase linearly with the channel count.
Each instance of the comparator and hash64 accelerator supports multiple
channels (up to 12 and 4 channels, respectively). Therefore, these units scale
by $\lceil\frac{\\#channels}{12}\rceil$ or
$\lceil\frac{\\#channels}{4}\rceil$, respectively. The area and power of
GenStore’s control unit remains the same across different channel counts.

###  6.2. GenStore-EM Analysis

We analyze the benefits of GenStore-EM for a 22-GB short read set where 80% of
reads exactly match some subsequence in the reference genome (see Section 5
for input generation methodology), on a system with three different SSD
configurations: SSD-L, SSD-M, and SSD-H.

Integration with a Software Read Mapper. Figure 9(a) shows the execution time
of four read mapper configurations: 1) Base (Minimap2 (li2018minimap2, )), 2)
SIMD, an extension of Base with a SIMD implementation of a baseline exactly-
matching read filter using 128-bit SIMD instructions, 3) GS-Ext, and 4) GS. We
divide the execution time between Alignment (chaining and alignment’s
contribution to end-to-end execution time) and Other (file access, seeding,
and exact match filtering’s contribution to end-to-end execution time).

(a) Software read mapper.

(b) Hardware read mapper.

Figure 9. GenStore-EM performance under different SSDs.

We make four observations from Figure 9(a). First, for all SSD types, GS
significantly outperforms Base and SIMD by $2.07$-$2.45\times$ and
$1.66$-$2.09\times$, respectively, by alleviating the cost of moving data from
the SSD to the host CPU and removing the burden of finding exactly-matching
reads from the rest of the system (DRAM and the processor). Second, GS-Ext
provides significant performance improvements over both Base and SIMD in SSD-M
and SSD-H. However, GS-Ext provides limited benefits over SIMD in SSD-L since
its performance is bottlenecked by the low external I/O bandwidth. Third, even
though SIMD also filters out the same number of reads and reduces the
alignment time similarly to GS and GS-Ext, its average performance benefit
over Base ($1.19\times$) is quite limited compared to those of GS
($2.23\times$) and GS-Ext ($1.83\times$). This is because 1) both GS and GS-
Ext reduce the number of memory accesses per read and convert the random
memory accesses to more efficient streaming accesses, and 2) GS addresses the
I/O bottlenecks due to limited external SSD bandwidth. Based on our
observations, we draw two conclusions. First, GenStore-EM leads to large
performance improvements in short read genomic analysis by efficiently
filtering large amounts of data in storage. Second, even without in-storage
processing support, the key idea of GenStore-EM can significantly improve the
performance of the state-of-the-art software read mapper especially when using
high-bandwidth SSDs (e.g., SSD-M and SSD-H).

Integration with a Hardware Read Mapper. Figure 9(b) shows the execution time
of three hardware read mapper configurations: 1) Base (GenCache
(nag2019gencache, )), 2) GS-Ext, and 3) GS.191919We do not show the execution
breakdown of mapping in Figure 9(b) since we cannot obtain the execution time
breakdown for the hardware read mapper from (nag2019gencache, ). Integrating
GenStore with existing accelerators requires no architectural changes to
GenStore and the accelerators because GenStore operates directly on the
original data that is stored in the SSD, before any accelerator-specific
operation starts. The only factor that GenStore needs to consider is to
generate its outputs (i.e., the information of unfiltered reads) in the format
that the accelerator needs as its inputs. The host system is responsible for
orchestrating the execution and data flows between GenStore and the
accelerator.

We make two observations based on Figure 9(b). First, GS significantly
outperforms Base by $3.32\times$, $2.55\times$, and $1.52\times$ on systems
with SSD-L, SSD-M, and SSD-H, respectively. Second, GS-Ext performs
significantly slower than Base ($2.28$-$1.91\times$) on all systems since
GenStore-EM requires accessing the large SSIndex data structure (Section 4.2),
while GS-Ext suffers from limited SSD external bandwidth. We conclude that the
in-storage processing approach in GenStore effectively addresses the I/O
bottleneck, which becomes even more significant with hardware accelerators
that address the computation bottleneck.

Effect of Read Set Features on Performance. We study the benefits of GenStore-
EM depending on the characteristics of input read sets. To this end, we
evaluate GenStore-EM while changing two key characteristics: 1) the input read
set size and 2) exactly-matching read rate. These two factors affect the data
movement savings ($DM\\_Saving$) of GenStore as governed by Equation (4):

(4)
$DM\\_Saving=\frac{{Size_{Ref}+Size_{{{ReadSet}}}}}{Size_{Ref}+{Size_{{{ReadSet}}}\times(1-Ratio_{Filter})}},$

where $Size_{Ref}$ is the size of the reference genome and its index (e.g., 7
GB for humans (li2018minimap2, )), $Size_{{{ReadSet}}}$ is the size of the
read set, and $Ratio_{Filter}$ in GenStore-EM is the exactly-matching read
rate of the read set.

Figure 10(a) shows the execution time of Base and GS for the baseline software
read mapper (Minimap2 (li2018minimap2, )) for input read sets with different
sizes (1x, 10x, and 20x larger than the size of our default 22-GB short read
set) and different exactly-matching read rates (75% and 85%) on a system with
SSD-H. We make two observations. First, GS’s performance benefit grows as
input size increases (from $2.62\times$ to $4.75\times$) due to larger data
movement savings. Since $Size_{Ref}$ is constant, $DM\\_Saving$ and the
performance benefits of GenStore-EM increase with larger $Size_{{{ReadSet}}}$
(see Equation (4)). Second, GS’s performance benefit increases with higher
exactly-matching read rates (from $3.46\times$ to $6.05\times$ for the largest
read set) because with a larger exactly-matching read rate (i.e.,
$Ratio_{Filter}$ in Equation (4)), data movement saving ($DM\\_Saving$)
increases, and the time spent on mapping the unfiltered reads decreases.
Mapping the unfiltered reads is the key contributor to the end-to-end
execution time of GS since it has larger execution time compared to
concurrently running GenStore-EM operations in the SSD. We conclude that the
benefits of GenStore-EM, when integrated with the software read mapper,
increases with larger read sets and with larger exactly-matching read rates.

Figure 10(b) shows the execution time of Base and GS for a baseline hardware
read mapper (GenCache (nag2019gencache, )). We make two observations. First,
GS’s performance benefit increases with larger input sizes (from $1.52\times$
to $3.13\times$) due to its larger data movement reduction. Second, GS’s
performance benefit does _not_ increase with higher exactly-matching read
rates. This is because, with the hardware read mapper, the end-to-end
performance of GS is dominated by the execution time of GenStore-EM’s filter
operations inside the SSD, which only depends on the input read set size and
not on the exact-match rate. We conclude that the benefits of GenStore-EM,
when integrated with the hardware read mapper, increases with larger input
read set sizes.

(a) Software read mapper.

(b) Hardware read mapper.

Figure 10. GenStore-EM performance versus input size and exact match rate.

###  6.3. GenStore-NM Analysis

We analyze the benefits of GenStore-NM for a 12.4-GB read set (the first _No
reference_ use case in Table 1) with 99.65% of reads _not_ aligning on a
system with three different SSD configurations: SSD-L, SSD-M, and SSD-H.

Integration with a Software Read Mapper. Figure 11(a) shows the execution time
of two read mapper configurations: 1) Base (Minimap2 (li2018minimap2, )),
which already incorporates the chaining filter, and 2) GS.202020Unlike Figure
9(a), we do not divide the execution times of Alignment and Other in Figure
11(a) since the execution time of GS is dominated by the filter operations of
GenStore-NM. This is because, in this case, a large fraction (e.g., 99.65% in
our evaluated dataset) of reads get filtered in the SSD and the execution time
of mapping the unfiltered reads is very small. We observe that GS outperforms
Base by $22.4\times$, $29.0\times$, and $27.9\times$ on systems with SSD-L,
SSD-M, and SSD-H, respectively.212121In this case, GS provides larger benefits
for systems with SSD-M and SSD-H since these SSDs have larger internal
bandwidth compared to SSD-L. The reason is that GS alleviates the cost of data
movement from SSD to the processor and removes the burden of mapping a large
fraction of reads from the rest of the system (DRAM and the processor).

(a) Software read mapper.

(b) Hardware read mapper.

Figure 11. GenStore-NM performance under different SSDs.

Integration with a Hardware Read Mapper. Figure 11(b) shows the execution time
of three hardware read mapper configurations: 1) Base (Darwin
(turakhia2018darwin, )), 2) GS-Ext, and 3) GS. We make two observations based
on Figure 11(b). First, GS significantly outperforms Base by $19.2\times$,
$6.86\times$, and $6.85\times$ on systems with SSD-L, SSD-M, and SSD-H,
respectively. The reason is that GS alleviates the cost of data movement from
SSD to the accelerator and removes the burden of read mapping for the filtered
reads from the rest of the system (DRAM and the accelerator). Second, GS-Ext
does not provide significant performance benefits compared to Base in systems
with SSD-L and SSD-M since the execution time of GS-Ext is dominated by the
I/O overhead of bringing reads from SSD to the accelerator. GS-Ext performs
$2.50\times$ faster than Base in systems with SSD-H since the I/O bottlenecks
are partially alleviated with SSD-H. However, the benefits of GS-Ext are
limited compared to GS since GS significantly alleviates the I/O overhead of
bringing reads from SSD to the accelerator with all three SSD configurations.

Effect of Read Set Features on Performance. We study how the benefits of
GenStore-NM vary depending on the characteristics of input read sets. To this
end, we evaluate GenStore-NM while changing two key characteristics: 1) the
input read set size and 2) alignment rates (the fraction of reads in the read
set that align to the reference genome). We use input sets with different
sizes (1$\times$, 10$\times$, and 20$\times$ larger than the size of our
default 12.5GB read set) with different alignment rates ($0.3\%$ and $37\%$,
corresponding to the first and second _No reference_ use cases in Table 1), on
a system with SSD-H. Figure 12 shows the execution time of Base and GS for the
baseline software read mapper (li2018minimap2, ) (Figure 12(a)) and the
baseline hardware read mapper (turakhia2018darwin, ) (Figure 12(b)).

(a) Software read mapper.

(b) Hardware read mapper.

Figure 12. GenStore-NM performance versus input size and read alignment rate.

We make two main observations from Figure 12. First, for both hardware and
software read mappers, GS’s performance benefits vary little as the input size
changes. The reason is that $Size_{Ref}$ is very small (14.6 MB) for this
experiment. Therefore, data movement saving ($DM\\_Saving$ in Equation (4))
mainly correlates with alignment rate (i.e., $1-Ratio_{Filter}$). Second, for
both software and hardware read mappers, GS’s performance benefit increases as
the ratio of non-aligning reads increases (i.e., as alignment rate reduces),
because with higher values of $Ratio_{Filter}$, both 1) $DM\\_Saving$
increases and 2) the time spent on mapping unfiltered reads decreases. We
conclude the GenStore-NM provides high performance benefits to both software
and hardware read mappers with different input sizes and its benefits increase
with lower alignment rates.

###  6.4. Energy Analysis

To demonstrate the energy benefits of different GenStore modes, we obtain the
energy of the host processor, the host-side DRAM, the DRAM inside the SSD, the
communication between the SSD and the host, active and idle energy of the SSD,
and the energy of the logic units used in GenStore (Section 6.1). We calculate
the energy of each component based on its idle and dynamic power consumption
and its execution time. We observe that by filtering out large amounts of
data, GenStore reduces the end-to-end energy consumption of read mapping in
all of our evaluations compared to Base (Minimap2 (li2018minimap2, )). We
measure the energy consumption for experiments on all SSD configurations. By
filtering exact matches in a short read set with 80% exactly-matching read
rate (see Section 5), GenStore-EM reduces the energy consumption by on average
(up to) $3.92\times$ ($3.97\times$) across all storage configurations. By
filtering non-matching reads in a long long read set with a read alignment
rate of 0.35% (the first _No reference_ use case in Table 1), GenStore-NM
reduces the energy consumption by on average (up to) $27.17\times$
($29.25\times$) across all storage configurations.

##  7\. Related Work

To our knowledge, GenStore is the _first_ in-storage system designed for
accelerating genome sequence analysis. GenStore works with both short and long
reads, and different degrees of genetic variation between the compared
genomes.

Accelerating Read Mapping. There exists a large body of work on accelerating
read mapping, which tend to follow two general directions: 1) non-filtering
and 2) filtering approaches (alser2020accelerating, ). Neither of these two
approaches are designed for processing in storage. Non-filtering approaches
accelerate one or more non-filtering steps of read mapping (e.g., seeding and
approximate string matching) using hardware accelerators. Examples of these
accelerators include processing-in-memory architectures (huangfu2018radar, ;
khatamifard2021genvom, ; cali2020genasm, ; gupta2019rapid, ; li2021pim, ;
angizi2019aligns, ; zokaee2018aligner, ), ASICs (turakhia2018darwin, ;
fujiki2018genax, ; madhavan2014race, ), GPUs (cheng2018bitmapper2, ;
houtgast2018hardware, ; houtgast2017efficient, ; zeni2020logan, ;
ahmed2019gasal2, ; nishimura2017accelerating, ; de2016cudalign, ;
liu2015gswabe, ; liu2013cudasw++, ; liu2009cudasw++, ; liu2010cudasw++, ;
wilton2015arioc, ), and FPGAs (goyal2017ultra, ; chen2016spark, ;
chen2014accelerating, ; chen2021high, ; fujiki2020seedex, ; banerjee2018asap,
; fei2018fpgasw, ; waidyasooriya2015hardware, ; chen2015novel, ;
rucci2018swifold, ; haghi2021fpga, ; li2021pipebsw, ; ham2020genesis, ;
ham2021accelerating, ; wu2019fpga, ). Filtering approaches accelerate the pre-
alignment filtering step of read mapping. These works provide highly-parallel
read filtering heuristics that quickly eliminate dissimilar sequences before
invoking computationally-expensive alignment algorithms. Examples of these
accelerators include processing-near-memory architectures (nag2019gencache, ;
kim20111, ; singh2021fpga, ; hameed2021alpha, ), FPGAs (alser2017gatekeeper, ;
alser2017magnet, ; alser2019shouji, ; alser2020sneakysnake, ; guo2019hardware,
), GPUs (alser2020sneakysnake, ; bingol2021gatekeeper, ; guo2019hardware, ),
or traditional CPU-based acceleration (xin2015shifted, ; xin2013accelerating,
; alser2020sneakysnake, ).

In contrast to GenStore, prior works on read mapping acceleration suffer from
two key issues. First, they all _still_ need to access the genomic data that
is initially stored in the storage device, which incurs time and energy costs
due to data movement overhead from the storage device to the main memory and
later to the CPU cores or accelerators. Second, most prior works support
processing _only_ one type of sequencing reads (turakhia2018darwin, ;
fujiki2018genax, ; alser2017gatekeeper, ; bingol2021gatekeeper, ;
khatamifard2021genvom, ; liu2015gswabe, ; angizi2019aligns, ;
zokaee2018aligner, ; cheng2018bitmapper2, ; houtgast2017efficient, ;
houtgast2018hardware, ; alser2019shouji, ; alser2017magnet, ; ham2020genesis,
; wilton2015arioc, ; li2021pipebsw, ; banerjee2018asap, ;
waidyasooriya2015hardware, ; chen2021high, ; liu2013cudasw++, ;
guo2019hardware, ; xin2015shifted, ; xin2013accelerating, ), which limits
their applicability. Compared to existing filtering approaches, our work 1) is
the first to identify the I/O inefficiencies that are not addressed by
existing techniques and 2) introduces new filtering techniques that enable
efficient in-storage processing for both short and long reads.

In-Storage Processing Systems. Prior works explore in-storage processing in
the form of application-specific accelerators (mailthody2019deepstore, ;
pei2019registor, ; jun2018grafboost, ; do2013query, ; seshadri2014willow, ;
kim2016storage, ; riedel2001active, ; riedel1998active, ), general-purpose
processing inside storage devices (gu2016biscuit, ; kang2013enabling, ;
wang2019project, ; acharya1998active, ; keeton1998case, ; riedel1998active, ;
riedel2001active, ), SSDs closely integrated with FPGAs (jun2015bluedbm, ;
jun2016bluedbm, ; torabzadehkashi2019catalina, ; lee2020smartssd, ;
ajdari2019cidr, ; koo2017summarizer, ), or SSDs closely integrated with GPUs
(cho2013xsd, ). Several works propose techniques for general pattern matching
in storage (jeong2019react, ; jun2016storage, ) _without_ a specific focus on
read mapping _nor_ support for different sequencing read types and data
structures. None of these works perform in-storage filtering for read mapping
to accelerate genome sequence analysis.

##  8\. Discussion

As sequencing technologies develop in the future, we expect that GenStore will
still play an important role in genomic sequence analysis. We witness three
major trends in sequencing technologies. First, the length and the accuracy of
reads are expected to increase (levy2016advancements, ; hu2021next, ;
alser2020accelerating, ; morrison2020nanopore, ; nanopore2020, ). Second,
short reads will continue to be widely used due to their _very_ high accuracy
and low cost (quail2008large, ; pacbio2021, ; quail2012tale, ). Third, DNA
sequencing machines are increasingly adopting data processing capabilities to
perform _both_ sequencing and genomic analysis within the same machine
(wang2021nanopore, ; dunn2021, ; loka2019reliable, ; zhang2021real, ;
ardui2018single, ; kovaka2020targeted, ).

Even with increases in long read accuracy (_trend 1_), GenStore-NM would
continue to filter large numbers of reads that do _not_ align to a reference
genome due to genetic differences between the compared genomes
(danko2021global, ; afshinnekoo2015geospatial, ; hsu2016urban, ;
sherman2019assembly, ; li2021building, ; miga2021need, ). Given that accurate
short reads are essential for many processes in genome analysis (_trend 2_),
e.g., for polishing (zhang2020comprehensive, ; firtina2020apollo, ;
miga2020telomere, ) and validating (logsdon2021structure, ) long read
sequences, GenStore-EM can continue to accelerate short read mapping by
filtering out exactly-matching reads. With the push to provide DNA sequencing
and preliminary genetic analysis on more portable integrated devices with
limited compute resources and available DRAM capacity (wang2021nanopore, ;
alser2020accelerating, ; dunn2021, ; peresini2021nanopore, ) (_trend 3_),
there will be a growing demand for data movement-minimizing systems like
GenStore to quickly filter out a large fraction of reads at low cost and high
efficiency (singh2021fpga, ; dunn2021, ; bhoyar2021high, ; ahmed2021pan, ;
kovaka2020targeted, ; pomerantz2018real, ).

With higher availability of portable genome sequencers, genomic analyses will
be performed more routinely (sunagawa2015structure, ; uk10k2015uk10k, ;
danko2021global, ; alser2020accelerating, ; bloom2021massively, ;
morrison2020nanopore, ; pomerantz2018real, ; clark2019diagnosis, ;
farnaes2018rapid, ; sweeney2021rapid, ; alkan2009personalized, ; flores2013p4,
; ginsburg2009genomic, ; chin2011cancer, ; Ashley2016, ) and will need to
provide much faster results (alser2020accelerating, ; singh2021fpga, ). In-
storage processing is crucial for meeting the huge demands for faster analyses
that scale well to large numbers of genomic samples. Examples of these
analyses include gene detection (lax2014longitudinal, ), alignment of reads
from rapidly mutating organisms such as SARS-CoV-2 (bhoyar2021high, ;
bloom2021massively, ), and studies of as-of-yet undiscovered microbes
(danko2021global, ; afshinnekoo2015geospatial, ; hsu2016urban, ;
sunagawa2015structure, ). In these analyses, GenStore-NM can effectively
filter out $>$99.7% (lax2014longitudinal, ; hsu2016urban, ), $\sim$36.1%
(bhoyar2021high, ), and $\sim$47.3% (danko2021global, ;
afshinnekoo2015geospatial, ; hsu2016urban, ) of the reads, respectively,
thereby greatly improving the end-to-end throughput and energy efficiency of
genome sequence analysis. We hope that our proposed techniques provide a
foundation for future efforts to accelerate genome analysis.

##  9\. Conclusion

We propose GenStore, a new in-storage processing system for genome sequence
analysis. GenStore can be integrated with both hardware and software read
mappers to improve the end-to-end performance of both short and long read
mapping. We address the challenges of in-storage processing for genomic read
filtering via new hardware/software co-designed techniques and develop new in-
storage filtering accelerators for both short and long reads. Our evaluations
show that GenStore provides large performance and energy improvements when
integrated into the state-of-the-art software and hardware read mappers. We
hope that GenStore inspires other in-storage processing and storage system
design ideas for genome sequence analysis. A promising avenue for future work
is to enable the integration of GenStore-like accelerators into sequencing
devices for extreme scalability and efficiency.

## Acknowledgments

We thank the anonymous reviewers of MICRO 2021 and ASPLOS 2022 for feedback.
We thank the SAFARI group members for feedback and the stimulating
intellectual environment. We acknowledge the generous gifts and support
provided by our industrial partners: Google, Huawei, Intel, Microsoft, VMware,
and the Semiconductor Research Corporation. This research was partially
supported by the ETH Future Computing Laboratory. Jisung Park was in part
supported by the National Research Foundation (NRF) of Korea
(NRF-2020R1A6A3A03040573).

## References

  * (1) Michelle M Clark, Amber Hildreth, Sergey Batalov, Yan Ding, Shimul Chowdhury, et al.  Diagnosis of Genetic Diseases in Seriously Ill Children by Rapid Whole-genome Sequencing and Automated Phenotyping and Interpretation.  Science Translational Medicine, 2019.
  * (2) Lauge Farnaes, Amber Hildreth, Nathaly M Sweeney, Michelle M Clark, Shimul Chowdhury, et al.  Rapid Whole-genome Sequencing Decreases Infant Morbidity and Cost of Hospitalization.  NPJ Genomic Medicine, 2018.
  * (3) Nathaly M Sweeney, Shareef A Nahas, Shimul Chowdhury, Sergey Batalov, Michelle Clark, et al.  Rapid Whole Genome Sequencing Impacts Care and Resource Utilization in Infants with Congenital Heart Disease.  NPJ Genomic Medicine, 2021.
  * (4) Can Alkan, Jeffrey M Kidd, Tomas Marques-Bonet, Gozde Aksay, Francesca Antonacci, et al.  Personalized Copy Number and Segmental Duplication Maps Using Next-Generation Sequencing.  Nature Genetics, 2009.
  * (5) Mauricio Flores, Gustavo Glusman, Kristin Brogaard, Nathan D Price, and Leroy Hood.  P4 Medicine: How Systems Medicine Will Transform the Healthcare Sector and Society.  Personalized Medicine, 2013.
  * (6) Geoffrey S Ginsburg and Huntington F Willard.  Genomic and Personalized Medicine: Foundations and Applications.  Translational Research, 2009.
  * (7) Lynda Chin, Jannik N Andersen, and P Andrew Futreal.  Cancer Genomics: From Discovery Science to Personalized Medicine.  Nature Medicine, 2011.
  * (8) Euan A Ashley.  Towards Precision Medicine.  Nature Reviews Genetics, 2016.
  * (9) Joshua S Bloom, Laila Sathe, Chetan Munugala, Eric M Jones, Molly Gasperini, et al.  Massively Scaled-up Testing for SARS-CoV-2 RNA via Next-generation Sequencing of Pooled and Barcoded Nasal and Saliva Samples.  Nature Biomedical Engineering, 2021.
  * (10) Ramesh Yelagandula, Aleksandr Bykov, Alexander Vogt, Robert Heinen, Ezgi Özkan, et al.  Multiplexed Detection of SARS-CoV-2 and Other Respiratory Infections in High Throughput by SARSeq.  Nature Communications, 2021.
  * (11) Vien Thi Minh Le and Binh An Diep.  Selected Insights from Application of Whole Genome Sequencing for Outbreak Investigations.  Current Opinion in Critical Care, 2013.
  * (12) Vlad Nikolayevskyy, Katharina Kranzer, Stefan Niemann, and Francis Drobniewski.  Whole Genome Sequencing of Mycobacterium Tuberculosis for Detection of Recent Transmission and Tracing Outbreaks: A Systematic Review.  Tuberculosis, 2016.
  * (13) Shaofu Qiu, Peng Li, Hongbo Liu, Yong Wang, Nan Liu, et al.  Whole-genome Sequencing for Tracing the Transmission Link between Two ARD Outbreaks Caused by A Novel HAdV Serotype 7 Variant, China.  Scientific Reports, 2015.
  * (14) Carol A Gilchrist, Stephen D Turner, Margaret F Riley, William A Petri, and Erik L Hewlett.  Whole-genome Sequencing in Outbreak Analysis.  Clinical Microbiology Reviews, 2015.
  * (15) Sean Hoban, Joanna L Kelley, Katie E Lotterhos, Michael F Antolin, Gideon Bradburd, et al.  Finding the Genomic Basis of Local Adaptation: Pitfalls, Practical Solutions, and Future Directions.  The American Naturalist, 2016.
  * (16) J Romiguier, Philippe Gayral, Marion Ballenghien, Arnaud Bernard, Vincent Cahais, et al.  Comparative Population Genomics in Animals Uncovers the Determinants of Genetic Diversity.  Nature, 2014.
  * (17) Hans Ellegren and Nicolas Galtier.  Determinants of Genetic Diversity.  Nature Reviews Genetics, 2016.
  * (18) Ana Prohaska, Fernando Racimo, Andrew J Schork, Martin Sikora, Aaron J Stern, et al.  Human Disease Variation in the Light of Population Genomics.  Cell, 2019.
  * (19) Hans Ellegren.  Genome Sequencing and Population Genomics in Non-Model Organisms.  Trends in Ecology & Evolution, 2014.
  * (20) Javier Prado-Martinez, Peter H. Sudmant, Jeffrey M. Kidd, Heng Li, Joanna L. Kelley, et al.  Great Ape Genetic Diversity and Population History.  Nature, 2013.
  * (21) Ana Prohaska, Fernando Racimo, Andrew J Schork, Martin Sikora, Aaron J Stern, et al.  Human Disease Variation in the Light of Population Genomics.  Cell, 2019.
  * (22) Jason A Reuter, Damek V Spacek, and Michael P Snyder.  High-Throughput Sequencing Technologies.  Molecular Cell, 2015.
  * (23) Erwin L van Dijk, Hélène Auger, Yan Jaszczyszyn, and Claude Thermes.  Ten Years of Next-Generation Sequencing Technology.  Trends in Genetics, 2014.
  * (24) Travis C Glenn.  Field Guide to Next-Generation DNA Sequencers.  Molecular Ecology Resources, 2011.
  * (25) Sara Goodwin, John D McPherson, and W Richard McCombie.  Coming of Age: Ten Years of Next-generation Sequencing Technologies.  Nature Reviews Genetics, 2016.
  * (26) Michael A Quail, Miriam Smith, Paul Coupland, Thomas D Otto, Simon R Harris, et al.  A Tale of Three Next Generation Sequencing Platforms: Comparison of Ion Torrent, Pacific Biosciences and Illumina MiSeq Sequencers.  BMC Genomics, 2012.
  * (27) Mehdi Kchouk, Jean-Francois Gibrat, and Mourad Elloumi.  Generations of Sequencing Technologies: from First to Next Generation.  Biology and Medicine, 2017.
  * (28) Franziska Pfeiffer, Carsten Gröber, Michael Blank, Kristian Händler, Marc Beyer, et al.  Systematic Evaluation of Error Rates and Causes in Short Samples in Next-generation Sequencing.  Scientific Reports, 2018.
  * (29) Shanika L Amarasinghe, Shian Su, Xueyi Dong, Luke Zappia, Matthew E Ritchie, and Quentin Gouil.  Opportunities and Challenges in Long-read Sequencing Data Analysis.  Genome Biology, 2020.
  * (30) Damla Senol Cali, Jeremie S Kim, Saugata Ghose, Can Alkan, and Onur Mutlu.  Nanopore Sequencing Technology and Tools for Genome Assembly: Computational Analysis of the Current State, Bottlenecks and Future Directions.  Briefings in Bioinformatics, 2018.
  * (31) Simon Ardui, Adam Ameur, Joris R Vermeesch, and Matthew S Hestand.  Single Molecule Real-Time (SMRT) Sequencing Comes of Age: Applications and Utilities for Medical Diagnostics.  Nucleic Acids Research, 2018.
  * (32) Jason L Weirather, Mariateresa de Cesare, Yunhao Wang, Paolo Piazza, Vittorio Sebastiano, et al.  Comprehensive Comparison of Pacific Biosciences and Oxford Nanopore Technologies and Their Applications to Transcriptome Analysis.  F1000Research, 2017.
  * (33) Erwin L van Dijk, Yan Jaszczyszyn, Delphine Naquin, and Claude Thermes.  The Third Revolution in Sequencing Technology.  Trends in Genetics, 2018.
  * (34) Yunhao Wang, Yue Zhao, Audrey Bollas, Yuru Wang, and Kin Fai Au.  Nanopore Sequencing Technology, Bioinformatics and Applications.  Nature Biotechnology, 2021.
  * (35) Mohammed Alser, Zülal Bingöl, Damla Senol Cali, Jeremie Kim, Saugata Ghose, et al.  Accelerating Genome Analysis: A Primer on An Ongoing Journey.  IEEE Micro, 2020.
  * (36) Mohammed Alser, Jeremy Rotman, Kodi Taraszka, Huwenbo Shi, Pelin Icer Baykal, et al.  Technology Dictates Algorithms: Recent Developments in Read Alignment.  Genome Biology, 2021.
  * (37) Hongyi Xin, Donghyuk Lee, Farhad Hormozdiari, Samihan Yedkar, Onur Mutlu, and Can Alkan.  Accelerating Read Mapping with FastHASH.  BMC Genomics, 2013.
  * (38) Hongyi Xin, John Greth, John Emmons, Gennady Pekhimenko, Carl Kingsford, et al.  Shifted Hamming Distance: A Fast and Accurate SIMD-friendly Filter to Accelerate Alignment Verification in Read Mapping.  Bioinformatics, 2015.
  * (39) Yatish Turakhia, Gill Bejerano, and William J Dally.  Darwin: A Genomics Co-processor Provides up to 15,000 x Acceleration on Long Read Assembly.  In ASPLOS, 2018.
  * (40) Damla Senol Cali, Gupreet Kalsi, Zulal Bingöl, Lavanya Subramanian, Can Firtina, et al.  GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis.  In MICRO, 2020.
  * (41) Mohammed Alser, Taha Shahroodi, Juan Gómez-Luna, Can Alkan, and Onur Mutlu.  SneakySnake: A Fast and Accurate Universal Genome Pre-alignment Filter for CPUs, GPUs and FPGAs.  Bioinformatics, 2020.
  * (42) Mohammed Alser, Hasan Hassan, Hongyi Xin, Oğuz Ergin, Onur Mutlu, and Can Alkan.  GateKeeper: A New Hardware Architecture for Accelerating Pre-alignment in DNA Short Read Mapping.  Bioinformatics, 2017.
  * (43) Anirban Nag, CN Ramachandra, Rajeev Balasubramonian, Ryan Stutsman, Edouard Giacomin, et al.  GenCache: Leveraging In-cache Operators for Efficient Sequence Alignment.  In MICRO, 2019.
  * (44) Jeremie S Kim, Can Firtina, Meryem Banu Cavlak, Damla Senol Cali, Mohammed Alser, et al.  AirLift: A Fast and Comprehensive Technique for Remapping Alignments between Reference Genomes.  arXiv, 2019.
  * (45) Jeremie S Kim, Damla Senol Cali, Hongyi Xin, Donghyuk Lee, Saugata Ghose, et al.  GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-memory Technologies.  BMC Genomics, 2018.
  * (46) Can Firtina, Jeremie S Kim, Mohammed Alser, Damla Senol Cali, A Ercument Cicek, et al.  Apollo: A Sequencing-technology-independent, Scalable and Accurate Assembly Polishing Algorithm.  Bioinformatics, 2020.
  * (47) Martin Šošić and Mile Šikić.  Edlib: A C/C++ Library for Fast, Exact Sequence Alignment Using Edit Distance.  Bioinformatics, 2017.
  * (48) Mohammed Alser, Onur Mutlu, and Can Alkan.  MAGNET: Understanding and Improving the Accuracy of Genome Pre-alignment Filtering.  arXiv, 2017.
  * (49) Mohammed Alser, Hasan Hassan, Akash Kumar, Onur Mutlu, and Can Alkan.  Shouji: A Fast and Efficient Pre-alignment Filter for Sequence Alignment.  Bioinformatics, 2019.
  * (50) Saul B Needleman and Christian D Wunsch.  A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins.  Journal of Molecular Biology, 1970.
  * (51) Temple F Smith, Michael S Waterman, et al.  Identification of Common Molecular Subsequences.  Journal of Molecular Biology, 1981.
  * (52) Osamu Gotoh.  An Improved Algorithm for Matching Biological Sequences.  Journal of Molecular Biology, 1982.
  * (53) Shawn E Levy and Richard M Myers.  Advancements in Next-generation Sequencing.  Annual Review of Genomics and Human Genetics, 2016.
  * (54) Taishan Hu, Nilesh Chitnis, Dimitri Monos, and Anh Dinh.  Next-Generation Sequencing Technologies: An Overview.  Human Immunology, 2021.
  * (55) 1000 Genomes Project Consortium et al.  A Global Reference for Human Genetic Variation.  Nature, 2015.
  * (56) Zheng Zhang, Scott Schwartz, Lukas Wagner, and Webb Miller.  A Greedy Algorithm for Aligning DNA Sequences.  Journal of Computational Biology, 2000.
  * (57) Guy St C Slater and Ewan Birney.  Automated Generation of Heuristics for Biological Sequence Comparison.  BMC Bioinformatics, 2005.
  * (58) Heng Li.  Minimap2: Pairwise Alignment for Nucleotide Sequences.  Bioinformatics, 2018.
  * (59) Gene Myers.  A Fast Bit-vector Algorithm for Approximate String Matching Based on Dynamic Programming.  JACM, 1999.
  * (60) Santiago Marco-Sola, Juan Carlos Moure, Miquel Moreto, and Antonio Espinosa.  Fast Gap-affine Pairwise Alignment Using the Wavefront Algorithm.  Bioinformatics, 2021.
  * (61) Wenqin Huangfu, Shuangchen Li, Xing Hu, and Yuan Xie.  RADAR: A 3D-ReRAM based DNA Alignment Accelerator Architecture.  In DAC, 2018.
  * (62) Daichi Fujiki, Arun Subramaniyan, Tianjun Zhang, Yu Zeng, Reetuparna Das, et al.  Genax: A Genome Sequencing Accelerator.  In ISCA, 2018.
  * (63) Daichi Fujiki, Shunhao Wu, Nathan Ozog, Kush Goliya, David Blaauw, et al.  SeedEx: A Genome Sequencing Accelerator for Optimal Alignments in Subminimal Space.  In MICRO, 2020.
  * (64) Subho Sankar Banerjee, Mohamed El-Hadedy, Jong Bin Lim, Zbigniew T Kalbarczyk, Deming Chen, et al.  ASAP: Accelerated Short-read Alignment on Programmable Hardware.  IEEE Transactions on Computers, 2019.
  * (65) S Karen Khatamifard, Zamshed Chowdhury, Nakul Pande, Meisam Razaviyayn, Chris H Kim, and Ulya R Karpuzcu.  GeNVoM: Read Mapping Near Non-Volatile Memory.  TCBB, 2021.
  * (66) Saransh Gupta, Mohsen Imani, Behnam Khaleghi, Venkatesh Kumar, and Tajana Rosing.  RAPID: A ReRAM Processing In-memory Architecture for DNA Sequence Alignment.  In ISLPED, 2019.
  * (67) Xue-Qi Li, Guang-Ming Tan, and Ning-Hui Sun.  PIM-Align: A Processing-in-Memory Architecture for FM-Index Search Algorithm.  Journal of Computer Science and Technology, 2021.
  * (68) Shaahin Angizi, Jiao Sun, Wei Zhang, and Deliang Fan.  Aligns: A Processing-in-memory Accelerator for DNA Short Read Alignment Leveraging SOT-MRAM.  In DAC, 2019.
  * (69) Farzaneh Zokaee, Hamid R Zarandi, and Lei Jiang.  Aligner: A Process-in-memory Architecture for Short Read Alignment in ReRAMs.  IEEE Computer Architecture Letters, 2018.
  * (70) Advait Madhavan, Timothy Sherwood, and Dmitri Strukov.  Race Logic: A Hardware Acceleration for Dynamic Programming Algorithms.  ACM SIGARCH Computer Architecture News, 2014.
  * (71) Haoyu Cheng, Yong Zhang, and Yun Xu.  Bitmapper2: A GPU-accelerated All-mapper Based on The Sparse Q-gram Index.  TCBB, 2018.
  * (72) Ernst Joachim Houtgast, Vlad-Mihai Sima, Koen Bertels, and Zaid Al-Ars.  Hardware Acceleration of BWA-MEM Genomic Short Read Mapping for Longer Read Lengths.  Computational Biology and Chemistry, 2018.
  * (73) Ernst Joachim Houtgast, VladMihai Sima, Koen Bertels, and Zaid AlArs.  An Efficient GPU-accelerated Implementation of Genomic Short Read Mapping with BWA-MEM.  ACM SIGARCH Computer Architecture News, 2017.
  * (74) Amit Goyal, Hyuk Jung Kwon, Kichan Lee, Reena Garg, Seon Young Yun, et al.  Ultra-fast Next Generation Human Genome Sequencing Data Processing Using DRAGENTM Bio-IT Processor for Precision Medicine.  Open Journal of Genetics, 2017.
  * (75) Yu-Ting Chen, Jason Cong, Zhenman Fang, Jie Lei, and Peng Wei.  When Spark Meets FPGAs: A Case Study for Next-Generation DNA Sequencing Acceleration.  In USENIX HotCloud, 2016.
  * (76) Peng Chen, Chao Wang, Xi Li, and Xuehai Zhou.  Accelerating the Next Generation Long Read Mapping with the FPGA-based System.  TCBB, 2014.
  * (77) Yen-Lung Chen, Bo-Yi Chang, Chia-Hsiang Yang, and Tzi-Dar Chiueh.  A High-Throughput FPGA Accelerator for Short-Read Mapping of the Whole Human Genome.  IEEE TPDS, 2021.
  * (78) Alberto Zeni, Giulia Guidi, Marquita Ellis, Nan Ding, Marco D Santambrogio, et al.  Logan: High-performance GPU-based X-drop Long-read Alignment.  In IPDPS, 2020.
  * (79) Nauman Ahmed, Jonathan Lévy, Shanshan Ren, Hamid Mushtaq, Koen Bertels, and Zaid Al-Ars.  GASAL2: A GPU Accelerated Sequence Alignment Library for High-Throughput NGS Data.  BMC Bioinformatics, 2019.
  * (80) Takahiro Nishimura, Jacir L Bordim, Yasuaki Ito, and Koji Nakano.  Accelerating the Smith-waterman Algorithm Using Bitwise Parallel Bulk Computation Technique on GPU.  In IPDPSW), 2017.
  * (81) Edans Flavius de Oliveira Sandes, Guillermo Miranda, Xavier Martorell, Eduard Ayguade, George Teodoro, and Alba Cristina Magalhaes Melo.  CUDAlign 4.0: Incremental Speculative Traceback for Exact Chromosome-wide Alignment in GPU Clusters.  IEEE TPDS, 2016.
  * (82) Yongchao Liu and Bertil Schmidt.  GSWABE: Faster GPU-accelerated Sequence Alignment with Optimal Alignment Retrieval for Short DNA Sequences.  Concurrency and Computation: Practice and Experience, 2015.
  * (83) Yongchao Liu, Adrianto Wirawan, and Bertil Schmidt.  CUDASW++ 3.0: Accelerating Smith-Waterman Protein Database Search by Coupling CPU and GPU SIMD Instructions.  BMC Bioinformatics, 2013.
  * (84) Richard Wilton, Tamas Budavari, Ben Langmead, Sarah J Wheelan, Steven L Salzberg, and Alexander S Szalay.  Arioc: High-throughput Read Alignment with GPU-accelerated Exploration of The Seed-and-extend Search Space.  PeerJ, 2015.
  * (85) Xia Fei, Zou Dan, Lu Lina, Man Xin, and Zhang Chunlei.  FPGASW: Accelerating Large-scale Smith–Waterman Sequence Alignment Application with Backtracking on FPGA Linear Systolic Array.  Interdisciplinary Sciences: Computational Life Sciences, 2018.
  * (86) Hasitha Muthumala Waidyasooriya and Masanori Hariyama.  Hardware-acceleration of Short-read Alignment Based on the Burrows-wheeler Transform.  TPDS, 2015.
  * (87) Yu-Ting Chen, Jason Cong, Jie Lei, and Peng Wei.  A Novel High-throughput Acceleration Engine for Read Alignment.  In FCCM, 2015.
  * (88) Enzo Rucci, Carlos Garcia, Guillermo Botella, Armando De Giusti, Marcelo Naiouf, and Manuel Prieto-Matias.  SWIFOLD: Smith-Waterman Implementation on FPGA with OpenCL for Long DNA Sequences.  BMC Systems Biology, 2018.
  * (89) Abbas Haghi, Santiago Marco-Sola, Lluc Alvarez, Dionysios Diamantopoulos, Christoph Hagleitner, and Miquel Moreto.  An FPGA Accelerator of the Wavefront Algorithm for Genomics Pairwise Alignment.  In FPL, 2021.
  * (90) Luyi Li, Jun Lin, and Zhongfeng Wang.  PipeBSW: A Two-Stage Pipeline Structure for Banded Smith-Waterman Algorithm on FPGA.  In ISVLSI, 2021.
  * (91) Ham, Tae Jun and Bruns-Smith, David and Sweeney, Brendan and Lee, Yejin and Seo, Seong Hoon and Song, U Gyeong and Oh, Young H and Asanovic, Krste and Lee, Jae W and Wills, Lisa Wu.  Genesis: A Hardware Acceleration Framework for Genomic Data Analysis.  In ISCA, 2020.
  * (92) Tae Jun Ham, Yejin Lee, Seong Hoon Seo, U Gyeong Song, Jae W Lee, et al.  Accelerating Genomic Data Analytics With Composable Hardware Acceleration Framework.  IEEE Micro, 2021.