# MetaStore: High-Performance Metagenomic Analysis
via In-Storage Computing

Nika Mansouri Ghiasi$1$ Mohammad Sadrosadati$1$ Harun Mustafa$1$ Arvid
Gollwitzer$1$ Can Firtina$1$ Julien Eudine$1$ Haiyu Ma$1$ Joël Lindegger$1$
Meryem Banu Cavlak$1$ Mohammed Alser$1$ Jisung Park$2$ Onur Mutlu$1$
$1$ETH Zürich $2$POSTECH

###### Abstract

Metagenomics, the study of the genome sequences of diverse organisms in a
common environment, has led to significant advancements in many fields. Since
the species present in a metagenomic sample are not known in advance,
metagenomic analysis commonly involves the key tasks of determining the
species present in a sample and their relative abundances. These tasks require
searching large metagenomic databases containing information on different
species’ genomes. Metagenomic analysis suffers from significant data movement
overhead due to moving large amounts of low-reuse data from the storage system
to the rest of the system. In-storage processing can be a fundamental solution
for reducing data movement overhead. However, designing an in-storage
processing system for metagenomics is challenging because none of the existing
approaches can be directly implemented in storage effectively due to the
hardware limitations of modern SSDs.

We propose MetaStore, the _first_ in-storage processing system designed to
significantly reduce the data movement overhead of end-to-end metagenomic
analysis. MetaStore is enabled by our lightweight and cooperative design that
effectively leverages and orchestrates processing inside and outside the
storage system. Through our detailed analysis of the end-to-end metagenomic
analysis pipeline and careful hardware/software co-design, we address in-
storage processing challenges for metagenomics via specialized and efficient
1) task partitioning, 2) data/computation flow coordination, 3) storage
technology-aware algorithmic optimizations, 4) light-weight in-storage
accelerators, and 5) data mapping. Our evaluation shows that MetaStore
outperforms the state-of-the-art performance- and accuracy-optimized software
metagenomic tools by 2.7–37.2$\times$ and 6.9–100.2$\times$, respectively,
while matching the accuracy of the accuracy-optimized tool. MetaStore achieves
1.5–5.1$\times$ speedup compared to the state-of-the-art metagenomic hardware-
accelerated tool, while achieving significantly higher accuracy.

##  I Introduction

Metagenomics is an increasingly important domain in bioinformatics, which
analyzes the genome sequences of various organisms of _different species_
present in a common environment (e.g., human gut, soil, or oceans) [1, 2, 3].
Unlike traditional genomics [4, 5, 6, 7, 8, 9] that studies genome sequences
from an individual (or a small group of individuals) of the _same species_
using a _known_ reference genome, metagenomics deals with genome sequences
whose species are _not known_ in advance in many cases, thereby requiring
comparisons of the target sequences against large databases of many reference
genomes. Metagenomics has led to groundbreaking advancements in many fields,
such as precision medicine [10, 11], urgent clinical settings [12],
understanding microbial diversity of an environment [13, 14], discovering
early warnings of communicable diseases [15, 16, 17], and outbreak tracing
[18]. The pivotal role of metagenomics, together with the rapid improvements
in genome sequencing technologies (e.g., reduced costs and improved throughput
[19]), has resulted in a fast-growing adoption of metagenomics over the past
few years [11, 20, 21].

The metagenomic workflow consists of three key steps: (i) sequencing, (ii)
basecalling, and (iii) metagenomic analysis. First, sequencing extracts the
genomic information of all organisms in a sample into digital data. Since the
current sequencing technologies _cannot_ process the DNA molecule as a whole,
a sequencing machine generates randomly sampled, inexact fragments of genomic
information, called _reads_. Second, basecalling converts the raw sequencer
data of reads into a sequence of characters that represent nucleotides, A, C,
G, and T. Third, metagenomic analysis determines the species _present/absent_
in the sample and their _relative abundances_.

To enable fast and efficient metagenomics for many critical applications, it
is essential to improve the performance and energy efficiency of metagenomic
analysis due to three reasons. First, metagenomic analysis is typically
performed much more frequently compared to the other two steps  (i.e.,
sequencing and basecalling) in the metagenomic workflow. While the two steps
are one-time tasks for a sample in many cases, sequenced and basecalled reads
in a sample can often be analyzed in _multiple studies_ or at _different
times_ in the same study [22]. Second, as shown in our motivational analysis
in §III on a high-end server node, even for one round of analysis, the
analysis step bottlenecks the end-to-end performance and energy consumption of
the workflow. Third, the performance and energy-efficiency gaps between the
analysis step and the other steps are expected to widen even more due to the
rapid advancements in sequencing technologies, such as significant increases
in throughput and energy efficiency of sequencing at rates [23, 24, 25, 26,
27, 28] higher than Moore’s Law [19], the development of sequencing
technologies that enable analysis during sequencing [29, 30, 31, 32, 33, 34],
and portable and energy-efficient high-throughput sequencers [35, 36]. Due to
these reasons, it is not feasible to efficiently keep up with these
advancements by merely scaling up traditional systems to improve the analysis.

The analysis step suffers from significant data movement overhead due to
accessing large amounts of low-reuse data. Since we do not know the species
present in a metagenomic sample, metagenomic tasks require searching large
databases (up to several terabytes [37, 38, 39, 40], with emerging databases
exceeding a hundred terabytes [39, 40]) that contain information on different
organisms’ reference genomes. Based on the recent trends, the database sizes
are expected to increase even further in the future, and at a fast pace, due
to recent advances in the automated and scalable construction of genomic data
from more organisms [41, 42].111For example, based on recently published
trends, the ENA assembled/annotated sequence database currently _doubles_
every 19.9 months [26], and the BLAST nt database doubled from 2021 to 2022
[43]. Our motivational analysis (§III) of the state-of-the-art metagenomic
analysis tools shows that data movement overhead from the storage system
significantly impacts their end-to-end performance, even when the main memory
is larger than the accessed data. Due to its low reuse, the data needs to move
all the way from the storage system to the main memory and processing units
for its first use, and most likely not be used again within the analysis. This
low data reuse, alongside low computation intensity and limited I/O bandwidth
leads to large storage I/O overhead.

While there have been great efforts in accelerating metagenomic analysis, to
our knowledge, no prior work fundamentally addresses its storage I/O
overheads. Some works [44, 45, 46, 47] aim to alleviate this overhead by
applying sampling techniques to reduce the database size, but they incur
accuracy loss, which is problematic for many use cases [48, 49, 50, 46].
Various other works [51, 52, 53, 54, 55, 56, 57, 58, 59, 60] accelerate other
bottlenecks in metagenomic analysis, such as computation and main memory
bottlenecks. These works do not alleviate I/O overhead, whose impact on end-
to-end performance (as shown in §III) becomes even larger when other
bottlenecks get alleviated.

_In-storage processing (ISP)_ , i.e., processing data directly inside the
storage device where target data resides, can be a fundamental and cost-
efficient approach for mitigating the data-movement bottleneck in metagenomic
analysis, given its three key benefits. First, ISP can significantly reduce
unnecessary data movement from storage systems by processing large amounts of
low-reuse data inside the storage while sending only the results to the host.
Second, ISP can leverage the high SSD-internal bandwidth to access target data
without being restricted by the SSD-external bandwidth limits. Third, it
reduces the overall burden of the application from the rest of the system
(e.g., processing units and main memory), freeing up the host system to
perform other useful work meanwhile.

Despite the benefits of ISP, none of the existing approaches for metagenomic
analysis can be directly implemented as an ISP system effectively due to the
limited hardware resources available in storage devices. Some tools incur a
large number of random accesses to search the database [54, 45], which hinders
leveraging ISP’s large potential by preventing the full utilization of the
SSD’s222In this work, we focus on NAND flash-based SSDs, the predominant
technology used in the modern storage systems. We expect that our insights and
our designs would also provide benefits with storage systems built with other
emerging technologies. internal bandwidth. This is due to costly conflicts in
internal SSD resources (e.g., channels and NAND flash chips [61, 62, 63])
caused by random accesses. Some tools predominantly incur more suitable
streaming accesses [64, 46], but they do so at the cost of more computation
and main memory capacity requirements. This becomes challenging for ISP due to
limited hardware resources available inside SSDs. Therefore, directly adopting
these approaches in ISP incurs performance, energy, and storage device
lifetime overheads.

Our goal is to improve metagenomics performance by reducing data movement
overhead, right from the storage system, in a cost-effective manner and by
addressing the challenges of ISP. To this end, we propose MetaStore, the
_first_ ISP system designed for metagenomics. The key idea of MetaStore is to
enable _cooperative_ ISP for metagenomics, where we do not merely focus on the
storage system and, instead, capitalize on the strengths of processing both
inside and outside the storage system via an end-to-end and synergistic
design.

We design MetaStore as an efficient pipeline between the SSD and the host
system to (i)  _leverage_ and (ii)  _orchestrate_ the capabilities of both. To
this end, we propose new hardware/software co-designed approaches in five
aspects. First, based on our detailed analysis of the key metagenomic tasks,
we partition and map the task parts to the host and the ISP system, such that
each part maps to its most suitable architecture. Second, we coordinate the
data/computation flow between the host and the SSD, such that MetaStore (i)
completely overlaps the data transfer time between them with computation time
to reduce the communication overhead between the task partitions, (ii) can
leverage both the SSD’s internal and external bandwidth efficiently, (iii)
does not require large DRAM inside the SSD or a large number of writes to the
flash chips. Third, we devise storage technology-aware algorithm optimizations
to enable efficient access patterns to the SSD. Fourth, we design lightweight
in-storage accelerators to perform MetaStore’s ISP tasks, while minimizing the
required SRAM/DRAM buffer spaces inside the SSD. Fifth, we design an efficient
data mapping scheme and Flash Translation Layer (FTL), specialized based on
the characteristics of the metagenomic tasks to leverage the SSD’s full
internal bandwidth.

We evaluate MetaStore with two different SSD configurations (performance-
optimized [65] and cost-optimized [66]) to show the impact of the storage
system. We compare MetaStore against three state-of-the-art metagenomic
analysis tools: (i) Kraken2 [45], which is optimized for performance, (ii)
Metalign [64], which is optimized for accuracy, and (iii) a state-of-the-art
processing-in-memory accelerator, Sieve [54], integrated into Kraken2 to
accelerate its k-mer matching. By analyzing _end-to-end_ performance, we show
that MetaStore provides 2.66–37.24$\times$ speedup compared to Kraken2, and
1.46–5.06$\times$ speedup compared to Sieve, while providing significantly
higher accuracy. MetaStore provides 6.93–100.20$\times$ speedup compared to
Metalign, while providing the same accuracy. MetaStore provides large average
energy reduction of 5.36$\times$ and 1.88$\times$ compared to Kraken2 and
Sieve, respectively, and 15.16$\times$ compared to accuracy-optimized
Metalign. MetaStore’s benefits come at a low area cost of 1.7% of the three
cores [67] in a SSD controller [68].

This work makes the following major contributions:

  * •

We propose MetaStore, the _first_ ISP system for metagenomics. Via our end-to-
end and cooperative approach, MetaStore fundamentally reduces I/O costs of
metagenomic analysis.

  * •

We present new hardware/software co-designed approaches to enable an efficient
pipeline between the host and the SSD to address the challenges of ISP for
metagenomics.

  * •

MetaStore improves the performance and energy efficiency compared to the
state-of-the-art metagenomics tools, while maintaining high accuracy. It does
so without relying on costly hardware resources throughout the sytsem, making
metagenomics more accessible for its wider adoption.

##  II Background

###  II-A Metagenomics Analysis

Metagenomic analysis tools commonly perform two key tasks of identifying (i)
species _present/absent_ in a sample, and (ii) their _relative abundances_.

####  II-A1 Presence/absence Identification

To find species present in the sample, many tools extract _k-mers_ (i.e.,
subsequences of length $k$) from the input query reads and search for the
k-mers in a _reference database_. Each database contains k-mers extracted from
reference genomes of a wide range of species. The database associates each
indexed k-mer with a _taxonomic identifier (i.e., tax ID)_ 333A tax ID is an
integer attributed to a cluster of related species. of the reference genome(s)
the k-mer comes from. The GB- or TB-scale databases typically support random
(e.g., [45, 44, 48]) or streaming (e.g., [64, 46, 69]) access patterns.

Tools with Random Access Queries (R-Qry). Many tools commonly perform random
accesses to search their database. A state-of-the-art tool in this category is
Kraken2 [45], which maintains a hash table associating each indexed k-mer to a
tax ID. To identify which species are present in a set of queries, Kraken2
extracts k-mers from the read queries and searches the database to retrieve
the k-mers’ associated tax IDs. For each read, Kraken2 collects the tax IDs of
that read’s k-mers and, based on the occurrence frequencies of these tax IDs,
uses a classification algorithm to assign a single tax ID to each read.
Finally, Kraken2 identifies the species with these tax IDs as present in the
sample.

Tools with Streaming Access Queries (S-Qry). Some tools (e.g., [64, 46, 69])
predominantly feature streaming accesses to their databases. A state-of-the-
art tool in this category is Metalign [64]. Presence/absence identification in
Metalign is done via 1) preparing the input read set queries, and 2) finding
species present in them. To process the read set queries, the tool extracts
k-mers from the reads and sorts them. Finding the species present in the
sample involves two steps. First, it finds the intersecting k-mers between the
query k-mers and a pre-sorted reference database. In this step, the tool uses
large k-mers (e.g., $k=60$) for both the queries and the database to maintain
a low species false positive rate. This is because large k-mers are more
unique, and matching a long k-mer ensures that the queries have at least one
long and specific match to the database. Second, the tool finds the tax IDs of
the intersecting k-mers. To do so, it searches for the intersecting k-mers or
their prefixes in a smaller _sketch database_ of variable-sized k-mers. Each
_sketch_ is a small representative subset of k-mers associated with a given
tax ID. Searching for prefixes in this step increases the true positive rate
by expanding the number of matching tax IDs.

####  II-A2 Abundance Estimation

After finding the species present in the sample, some applications require a
more sensitive step to find the species’ relative abundances [70, 71].
Different tools implement their own approaches for estimating abundances,
ranging from relatively light-weight statistical models [70, 72] to more
accurate but computationally-intensive read mapping [64, 44, 48]. Read mapping
is the process of finding potential matching locations of reads against one or
more reference genomes. Metagenomic tools can map the query reads against
reference genomes of species present in the sample, accurately determining the
number of reads belonging to each species.

###  II-B SSD Organization

Figure 1: Organizational overview of a modern SSD.

Fig. 1 depicts the organization of a modern NAND flash-based SSD, consisting
of three main components.

1

NAND Flash Memory. A NAND package consists of multiple _dies_ or _chips_ ,
sharing the NAND package’s I/O pins. One or multiple packages share a
command/data bus or _channel_ to communicate with the SSD controller. Dies can
operate independently, but each channel can be used by only one die at a time
to communicate with the controller. Each die has multiple (e.g., 2 or 4)
_planes_ , each with thousands of _blocks_. Each block has hundreds to
thousands of 4–16 KiB _pages_. NAND flash memory performs read/write
operations at page granularity but erase operations at block granularity. The
peripheral circuitry to access pages is shared among the planes in each die.
Hence, it is possible for the planes in a die to operate concurrently when
accessing pages (or blocks) at the same offset. This mode is called the
_multiplane_ operation.

2

SSD Controller. An SSD controller consists of two key components. First,
multiple cores run SSD firmware, commonly referred to as the _flash
translation layer (FTL)_. The FTL is responsible for communication with the
host system, internal I/O scheduling, and various SSD management tasks.
Second, per-channel hardware flash controllers manage request handling and
error correction for the NAND flash chips.

3

DRAM. Modern SSDs use low-power DRAM to store metadata for SSD management
tasks. Most of the DRAM capacity inside the SSD (i.e., internal DRAM) is used
to store the logical-to-physical (L2P) mappings, which are typically
maintained at a granularity of 4KiB to enhance random access performance.
Therefore, in a 32-bit architecture, and 4 bytes of metadata stored for every
4KiB of data, L2P memory overhead is about 0.1% of the SSD’s capacity. For
example, a 4-GB LPDDR4 DRAM is used for a 4-TB SSD [68].

##  III Motivational Analysis

###  III-A Criticality of Metagenomic Analysis

The analysis step bottlenecks the end-to-end performance of the metagenomic
workflow and poses a pressing need for acceleration [54, 55, 20, 73, 12, 74]
for three reasons. First, the sequencing and basecalling steps for a sample
read set are one-time tasks in the majority of cases. In contrast, in many
cases, the reads from a single sequenced sample can be analyzed by _multiple
studies_ or _at different times_ in the same study [22]. Second, even for one
round of analysis, the analysis _throughput_ is significantly lower than the
throughput with which modern sequencing machines generate data [75, 76]. A
single sequencing machine can sequence _many samples_ from different sources
(e.g., different patients or environments) in parallel [23, 77], achieving
very high throughput. Our analysis with a state-of-the-art metagenomic
analysis tool [64] shows that analyzing the data sequenced and basecalled by a
high-throughput sequencer in 48 hours takes 38 days on a high-end server node
(details in §V). Such long analysis poses serious challenges for metagenomic
analysis, specifically for the time-critical use cases (e.g., clinical
settings [12] and timely and widespread surveillance of infectious diseases
[18]). Since the growth rate of sequencing throughput is higher than Moore’s
Law [19], this already large gap between sequencing and computation throughput
is widening [23, 25, 26, 28], and merely scaling up traditional systems for
analysis is not efficient. Third, the urgent need for rapid metagenomics has
driven significant advancements in sequencing technologies that enable
_runtime analysis during sequencing_ [29, 30, 31, 32], which increasingly
highlights the criticality of fast analysis.

Similarly, the analysis step is the primary energy bottleneck in the
metagenomic workflow, and optimizing its efficiency is vital as sequencing
technologies rapidly evolve. For example, a high-end sequencer [75] uses 405
KJ to sequence and basecall 100 million reads, with 92.5 Mbp/s throughput and
2,500 W power consumption [75]. In contrast, processing this dataset on a
commodity server (§V) requires 675 KJ, accounting for 63% of total energy. The
need to enhance the analysis’ energy efficiency is further increasing for two
reasons. First, sequencing efficiency has improved markedly. For example, a
new version of Illumina sequencer from 2023 [75] provides 44$\times$ higher
throughput at only 1.5$\times$ larger power consumption compared to an older
version [78] from 2020, resulting in much better sequencing energy efficiency.
Therefore, solely relying on scaling up commodity systems to improve the
analysis throughput worsens the analysis energy bottleneck significantly.
Second, the increased adoption of compact _portable DNA sequencers_ [36] for
on-site metagenomic analysis (e.g., in remote locations [79] or for
personalized bedside care [20]) offers high-throughput sequencing with low
energy costs. This trend further amplifies the need for energy- and cost-
effective analysis that can match the portability and convenience of these
portable yet powerful devices.

###  III-B Data Movement Overheads

We conduct experimental analysis to assess the storage system’s impact on the
performance of metagenomics analysis.

Tools and Datasets. We analyze two state-of-the-art tools for performing the
presence/absence identification: 1) Kraken2 [45], which queries the large
database with random access patterns (R-Qry), 444We experiment with both
techniques of accessing the database devised in the R-Qry baseline [80] and
report the best timing. The first technique uses mmap to access the database,
while the second technique loads the entire database from the SSD to DRAM as
the first step when the analysis starts. In this experiment, the second
approach performs slightly better since, when analyzing our read set, the
application requires accessing most parts of the database during its
execution. and 2) Metalign [64], which mostly exhibits sequential streaming
accesses to the database (S-Qry). We use the best-performing thread count in
each case. We use a query sample with 100 million reads555This is in the upper
quartile of metagenomic read set sizes [25]. (RL_S001__insert_270.fq) from the
CAMI dataset [81], commonly used for profiling metagenomic tools. We generate
a database based on microbial genomes drawn from NCBI’s databases [82, 64]
using default parameters for each tool. For Kraken2 [45], this results in a
293 GB database. For Metalign [64], this results in a 701 GB k-mer database
and a 6.9 GB sketch tree. To show the impact of recent trends in the rapid
increase of database sizes, we also analyze larger k-mer databases (0.6 TB and
1.4 TB for Kraken and Metalign, respectively) that include genomes of more
species.

System Configurations. We use a high-end server with AMD EPYC 7742 CPU [83]
and 1.5-TB DDR4 DRAM. Note that the DRAM size is larger than the size of all
data accessed during the analysis by each tool and on each input dataset. This
way, we can analyze the fundamental I/O data movement overhead of moving large
amounts of low-reuse data from the storage system to the main memory without
being limited by DRAM capacity. We evaluate the impact of I/O overhead with:
1) a cost-optimized SSD (SSD-C) [66] with a SATA3 interface [84], 2) a
performance-optimized SSD (SSD-P) [65] with a PCIe Gen4 interface [85], and 3)
a hypothetical configuration with zero performance overhead due to storage I/O
(No-I/O). SSD-P provides an order-of-magnitude higher sequential-read
bandwidth compared to SSD-C. However, scaling up storage capacity only using
performance-optimized SSDs is challenging due to their much higher prices and
fewer PCIe slots compared to SATA on servers.

Figure 2: Performance of (a) R-Qry and (b) S-Qry under different storage
configurations and database sizes.

Results and Analysis. Fig. 2 shows the performance of R-Qry and S-Qry,
normalized against the No-I/O configuration. We make three key observations.
First, I/O overhead has a large impact on end-to-end performance for all
cases. Compared to SSD-C (SSD-P), No-I/O leads to 9.4$\times$ (1.7$\times$)
and 32.9$\times$ (3.6$\times$) better performance in R-Qry and S-Qry (on
average across both databases), respectively. While both baselines
significantly suffer from large I/O overhead, we observe a relatively larger
impact on S-Qry due to its lower data reuse compared to R-Qry. Second, even
using the state-of-the-art SSD (SSD-P) does not alleviate this overhead,
leaving large performance gaps between SSD-P and No-I/O in both R-Qry and
S-Qry. Third, I/O overhead increases as the databases grow larger. For
example, for R-Qry, the performance difference between SSD-C and No-I/O
increases from 7.1$\times$ to 12.5$\times$ when the database grows from 0.3 TB
to 0.6 TB. Based on these observations, we conclude that I/O accesses lead to
large overheads in metagenomic analysis, with this overhead expected to worsen
in the future.

This I/O overhead, stemming from the need to move large amounts of low-reuse
data is a fundamental problem and hard to avoid. One might think it is
possible to avoid I/O performance overheads by either 1) using sampling to
shrink databases [44, 45, 46, 47] or 2) keeping all data required by
metagenomic analysis perpetually resident in main memory. Neither of these
solutions is suitable. The first approach inevitably reduces accuracy [48, 81]
to levels unacceptable for many use cases [48, 49, 50, 46, 19]. The second
approach is energy inefficient, costly, unscalable, and unsustainable due to
two reasons. First, the sizes of metagenomic databases (which are already
large, i.e., in some recent examples, exceeding a hundred terabytes [39, 40])
have been increasing rapidly. For example, recent trends show the _doubling_
of different important databases over the course of only several months [26,
43]. Second, regardless of individual data sizes, different analyses need
different databases. For example, a medical center may need to use various
different databases for its patients (e.g., for different viral infections
[86, 44], sepsis [12], etc.). Therefore, it is inefficient and unsustainable
to maintain _all_ data required by _all possible_ analyses in DRAM at all
times.666Ultimately, these are the same reasons that the metagenomic community
has been investigating storage efficiency (e.g., the mentioned sampling
techniques [44, 45, 46, 47]) as opposed to merely relying on scaling the
system’s DRAM.

The impact of I/O accesses on end-to-end performance becomes even more
prominent in emerging systems in which other bottlenecks (e.g., computation or
main memory bottlenecks) get alleviated. For example, while metagenomics can
benefit from near-data processing at the main memory level, i.e., processing-
in-memory (PIM) [54, 57, 58, 55, 87], these approaches still incur the
overhead of moving the large, low re-use data from storage. In fact, by
accelerating other overheads, the impact of storage I/O on end-to-end
performance increases. For example, for the 0.3-TB and 0.6TB Kraken2
databases, and considering a state-of-the-art PIM accelerator [54] of Kraken2,
No-I/O’s end-to-end performance is on average 26.1$\times$ (3.0$\times$)
better than SSD-C (SSD-P), respectively. We conclude that while PIM can
provide significant benefits for metagenomics analysis, it does not alleviate
the overhead of moving large, low-reuse data from the storage device.

###  III-C Our Goal

Processing data directly in the storage system, where the data originally
resides, via ISP can be a fundamental and cost-efficient approach for reducing
the overheads of moving large volumes of low-reuse data across the system. ISP
provides three key benefits. First, it reduces unnecessary data movement from
the storage system. Second, it reduces the overall performance and energy
burden of the application from the rest of the system, freeing them up to do
other useful work meanwhile. Third, as shown by many prior works (e.g., [88,
89, 90, 91]), ISP can benefit from the SSD’s larger internal bandwidth. For
example, with 8 (16) channels for SSD-C (SSD-P) and the maximum per-channel
bandwidth of 1.2 GB/s, the maximum internal bandwidth is calculated to be 9.6
GB/s (19.2 GB/s). The external sequential-read bandwidth of SSD-C (SSD-P) is
560 MB/s (7 GB/s). Therefore, the internal bandwidth is 17.4$\times$
(2.7$\times$) larger than the external in SSD-C (SSD-P).

Despite its benefits, designing an ISP system for metagenomics is challenging
because none of the existing approaches can be directly implemented as an ISP
system effectively due to the constrained hardware resources in the SSD.
Techniques such as R-Qry hinder leveraging ISP’s large potential by preventing
the full utilization of the SSD’s internal bandwidth due to costly conflicts
in internal SSD resources [61, 62, 63] caused by random accesses. Techniques
such as S-Qry predominantly incur more suitable streaming accesses, but they
do so at the cost of more computation and main memory capacity requirements,
posing challenges for ISP. Therefore, directly adopting these approaches in
the storage system incurs performance, energy, and storage device lifetime
overheads. Our goal is to improve the performance of the end-to-end
metagenomic analysis workflow by reducing data movement overhead, right from
the storage system, in a cost-effective manner and by addressing the
challenges of ISP.

##  IV MetaStore

We propose MetaStore, the first ISP system for metagenomics. MetaStore extends
the existing SSD controller and FTL and integrates into the system so that
when not used for ISP, the SSD can be accessible for all other applications as
it would be in a conventional system. We address the challenges of ISP for
metagenomics via hardware/software co-design to enable _cooperative ISP_ via
an efficient pipeline between the host and the storage system to maximally
leverage and orchestrate their capabilities. Based on our detailed analysis of
metagenomic tasks, we partition the tasks and map each part to the most
suitable system, while ensuring that the partitioning does not lead to
additional overhead due to data transfer time. MetaStore efficiently
coordinates the data/control flow between the host and storage systems. For
each part, we develop algorithmic optimizations, data mapping schemes, and/or
lightweight in-storage accelerators based on the characteristics of the task,
real datasets, and the underlying hardware.

We explain MetaStore’s _Step 1: Preparing the Input Queries_ , _Step2: Finding
Candidate Species_ , and the optional _Step 3: Abundance Estimation_ , and
MetaStore-FTL in §IV-A, IV-B, IV-C, and IV-D, respectively. §IV-E shows the
end-to-end walkthrough. §IV-F shows optimizations for use cases where multiple
samples require the same database simultaneously.

###  IV-A Step 1: Preparing the Input Queries

MetaStore works with lexicographically-sorted data structures to avoid
expensive random accesses to the SSD (similar to S-Qry described in §II-A).
Similar to many other metagenomic tools (including [80, 57, 64, 92]), we
assume the sorted k-mer databases are pre-built before the analysis. However,
sorting k-mers extracted from the input query read set (i.e., sample) cannot
efficiently be done offline because it requires storing a separate large data
structure (i.e., sorted k-mer set) alongside each sample, which could
potentially be even larger than the original sample and lead to a significant
waste of storage capacity. Therefore, to prepare the input queries, MetaStore
1) extracts k-mers from the sample, 2) sorts the k-mers, and if needed, 3)
prunes some k-mers with user-defined criteria.

In MetaStore’s pipeline, we execute this step in the host for three reasons.
First, sorting benefits from the relatively larger DRAM and compute resources
in the host. Second, due to the host’s large DRAM, performing this step in the
host leads to significantly fewer writes to the flash chips and can positively
impact their lifetime. For typical metagenomic read sets, storing k-mers
extracted from reads within a sample takes tens of gigabytes (e.g., on average
60 GB in our experiments with standard CAMI read sets [81], as detailed in
§V). While it is possible to generate and sort these k-mers inside the SSD by
leveraging the small internal DRAM (e.g., 4-GB DRAM for a 4-TB SSD), these
operations would require frequent writes to the flash chips. Third, by
effectively leveraging the host for this step, we can enable pipelining and
overlapping the execution of Steps 1 and Step 2 (which requires searching the
terabyte-scale low-reuse metagenomic database).

To enable the efficient execution of this step in the host, we need to ensure
two points. First, partitioning the application between the host system and
the SSD in different stages should not incur significant overhead due to data
transfer time. Second, while it is reasonable in most cases to expect the host
DRAM to be large enough to contain all extracted k-mers from a sample,
MetaStore should support scenarios where this is not the case and minimize the
performance, lifetime, and endurance overheads of writes due to page swapping.

####  IV-A1 K-mer Extraction

To reduce data transfer overhead between partitions, we propose a new input
processing scheme by improving upon input processing in KMC [93]. We partition
the k-mers into buckets, where each bucket corresponds to a lexicographical
range and stores k-mers falling into that range. This way, we can overlap the
k-mer sorting and transfer of one bucket with ISP on the previous buckets.
Step 2 (§IV-B) can start working on a bucket as soon as that bucket’s k-mers
are sorted and pruned. This is because the database k-mers are also sorted and
can already be accessed within the range corresponding to the bucket. Fig. 3
shows an overview of MetaStore’s k-mer extraction. The host reads the input
reads ( 1 in Fig. 3), extracts their k-mers ( 2), and stores them in the
buckets ( 3).777To avoid bucket size imbalance, we generate preliminary
buckets for a small subset of k-mers at the beginning. If we observe an
imbalance between these buckets, we balance the buckets by merging some to
meet a user-defined bucket count (default 512).

To support scenarios where the extracted k-mers of one sample do not fully fit
in the host DRAM, MetaStore pins some buckets to DRAM (e.g., Buckets $1$ to
$N-1$ in Fig. 3) and uses the SSD to store the others. This way, the k-mers
belonging to the DRAM-pinned buckets do not move back and forth between the
host and the SSD ( 4). To further reduce the overhead of writes/reads for the
SSD-pinned buckets, MetaStore’s bucketing scheme takes two measures. First, it
uses buffers in the host DRAM for the SSD-pinned buckets so that when full, it
flushes the contents of the buffers to the SSD, utilizing the full sequential-
write bandwidth. Second, we map the bucket’s k-mers across SSD channels, dies,
and planes evenly for parallelism and in an interleaved manner. Since
MetaStore does not require writes to the flash chips after this step, it can
flush all of the FTL metadata for write-related management to free up internal
DRAM for the next steps (details in §IV-D).

Figure 3: K-mer extraction.

####  IV-A2 Sorting

After generating all k-mer buckets, MetaStore proceeds to sort the k-mers
within the individual buckets. As soon as the sorting of a specific bucket
(i.e., bucket $i$) is completed, MetaStore transfers this bucket to the DRAM
inside the SSD in batches (to go through the second stage, as described in
§IV-B). Meanwhile, during the transfer of bucket $i$, MetaStore advances to
the sorting of bucket $i+1$. MetaStore can also orthogonally use a sorting
accelerator to perform sorting.

####  IV-A3 Excluding K-mers

MetaStore, like various tools [94, 95], can exclude k-mers based on user-
defined frequencies. Users can exclude 1) overly common k-mers, which are not
discriminative, and 2) k-mers that appear only once, which may represent
sequencing errors or low-abundance organisms that are hard to distinguish from
random occurrences.888Other k-mer selection/sampling criteria can also be
orthogonally and flexibly integrated in this step. Excluding these k-mers can
improve accuracy and reliability. Exclusion occurs after sorting, where k-mers
are inherently counted, and before transferring buckets to Step 2. While the
size of the extracted query k-mers (§IV-A1) can be large (on average 60 GB in
our experiments), the size of the k-mer set selected to go to the next stage
is much smaller (on average 6.5 GB) and is also significantly smaller than the
database that can be up to several terabytes [41, 42].

###  IV-B Step 2: Finding Candidate Species

In this stage, MetaStore finds the species present in the sample by 1)
intersecting the query k-mers and the database, and 2) finding the tax IDs of
the intersecting k-mers. We perform this stage inside the SSD since it
requires streaming the large database with low reuse and involves only
lightweight computation. This enables MetaStore to leverage the large SSD-
internal bandwidth and alleviate the overall burden of moving/analyzing large,
low-reuse data from the rest of the system.

Considering the SSD hardware limitations, MetaStore should leverage the full
internal bandwidth while ensuring it does not require expensive hardware
resources inside the SSD (e.g., large DRAM bandwidth and costly logic units).
Performing this step effectively inside the SSD requires efficient
coordination between the SSD and the host, mapping, hardware design, and
storage technology-aware algorithmic optimizations.

####  IV-B1 Intersection Finding

In this step, MetaStore finds the intersecting k-mers, i.e., k-mers present in
both the query k-mer buckets arriving from the host and the large k-mer
database stored in the flash chips.

Relying on the internal DRAM for 1) buffering the query k-mers arriving from
the host and the database k-mers arriving from the SSD channels at full
bandwidth and 2) streaming through both to find their intersection can
pressure the bandwidth of the internal DRAM. For example, reading at the full
internal bandwidth in a high-end SSD can already exceed the LPDDR4 DRAM
bandwidth used in current SSDs [96, 97, 65] and even the 16-GB/s DDR4
bandwidth [96, 98]. To address this challenge, we adopt an approach similar to
[96] and perform computation directly on flash data streams without needing to
write them to the internal DRAM. Despite its key benefits, this approach
requires large buffers (64KB for input and 64 KB for output, _per SSD
channel_).

To enable computation directly on the flash data streams at a low cost, we
leverage two key features of MetaStore to find the minimum required buffer
size. First, the computation in this step is very lightweight and does not
require a large buffer for data awaiting computation. Second, data is
uniformly distributed across channels, and each comparator needs to only
operate on the data received from one channel. Based on these, we directly
read data from the flash controller and include _two_ k-mer registers per
channel. While one register stores a k-mer as the input to the comparator, the
other stores the bytes in the next k-mer as they arrive from the flash
controller. For the cases where MetaStore cannot read the next database k-mer
(i.e., when the comparator needs to compare database k-mer $i$ with several
k-mers from the query bucket), MetaStore will not fetch the next k-mer from
the flash controller. This way, by only using two registers, MetaStore can
directly compute on the flash data stream at a low cost, and without
bottlenecking the limited internal DRAM bandwidth.

Fig. 4 shows the operations. First, MetaStore reads the query k-mers from the
host in batches to the internal DRAM ( 1 in Fig. 4). Second, it concurrently
reads both the sorted query k-mers from the internal DRAM and the sorted
database k-mers from all flash chips. It performs a comparison operation to
find their intersection ( 2). To do so, MetaStore uses per-channel comparators
located on the SSD controller to operate on each channel’s data stream. Third,
MetaStore writes the intersecting k-mers to the internal DRAM for further
analysis ( 3).

Figure 4: Intersection finding.

Fetching Query K-mers. To leverage the external bandwidth efficiently,
MetaStore moves buckets from the host to the internal DRAM in batches, with a
size equal to the size of the data that can be sent from the host to the SSD.
We consider two batches of k-mers stored in the internal DRAM. While
transferring batch $B\\#i$, MetaStore performs intersection finding on
$B\\#i-1$. For an SSD with 8 channels, 4 dies/channel, 2 planes/die, and
16-KiB pages, MetaStore only requires space for two 1-MiB batches in the
internal DRAM.

Intersection Finding. MetaStore reads the query k-mers from the internal DRAM
and the database k-mers from the flash controller. This step runs in a
pipeline with the previous. We store the database evenly across different
channels to leverage the full internal bandwidth when sequentially reading
data using multi-plane operations. MetaStore finds the intersecting k-mers
using a simple comparator logic. If a database k-mer equals a query k-mer, we
record it as an intersection in the internal DRAM. If a query k-mer is larger
(smaller), MetaStore reads the next database (query) k-mer. MetaStore’s
Control Unit, located on the SSD controller, receives the comparison results
and issues the control signals accordingly.999The figures exclude the Control
Unit and its connections for readability.

Storing the Intersecting K-mers. MetaStore stores the intersecting k-mers in
the internal DRAM.101010The intersection does not have a strict size
requirement and can fill in the remaining free space of the internal DRAM
opportunistically. Typically, due to its small size, the intersection k-mer
set can fit within the internal DRAM. However, in a corner case where the
intersecting k-mers cannot fully fit in the internal DRAM, MetaStore can start
the tax ID retrieval (§IV-B2) for the already-found intersecting k-mers. After
that, it can return to this step and over-write the old intersecting k-mers in
DRAM. The internal DRAM’s bandwidth needs to support 1) fetching the query
k-mers from the host, 2) reading them out for comparison, 3) storing the
intersection, and 4) FTL metadata. Since the query k-mer set and FTL metadata
(FTL details in §IV-D) are significantly smaller than the database, they can
be accessed at a much smaller bandwidth than reading the database. For
example, for our datasets (§V), while fully leveraging the internal bandwidth
of SSD-P, MetaStore requires only 2.4 GB/s of DRAM bandwidth.

Leveraging our optimizations, MetaStore’s ISP requires only simple computation
and small buffers. This enables MetaStore’s ISP to also run on the embedded
cores on the SSD controller. We evaluate both MetaStore configurations (with
the lightweight accelerator or embedded cores) in §VI. Choosing between these
two MetaStore configurations is a design decision with different trade-offs,
with the accelerator configuration achieving better performance and
significantly higher power efficiency.

####  IV-B2 Retrieving Tax IDs

This step retrieves the species tax IDs of the intersecting k-mers. To do so,
we compare the intersecting k-mers against the pre-built k-mer sketches
representing each species’ reference genomes. Similar to [64], we use CMash
[99] to generate sketches. MetaStore can orthogonally use other sketches.
MetaStore flexibly supports variable-sized k-mers. As shown by prior works
[99, 44], while longer k-mers offer greater discrimination, they may result in
incomplete detection of hits between queries and sketches. In such cases,
users may also try smaller k-mers (i.e., k-mers prefixes) to identify
additional matches.

Figure 5: Sketch data structures.

Finding tax IDs for variable-sized k-mers is challenging since it requires
many pointer-chasing operations on a large data structure that may not fit in
the internal DRAM. To find the tax IDs of k-mers, some approaches [100, 99,
64] devise data structures to encode the k-mer information in a space-
efficient manner. For example, CMash [99] encodes k-mers of variable sizes in
a ternary search tree. Fig. 5 shows 5-, 4-, and 3-mers alongside their tax IDs
in a separate tables, as used by some prior approaches [101, 102], and b in a
ternary search tree. This tree structure is devised to 1) save space and 2)
retrieve the tax IDs for all k-mers with $k\leq k_{max}$ that are prefixes of
a query $k_{max}$-mer. For example, as shown in Fig. 5, when traversing the
tree to look up the 5-mer AATCC, we can look up the 4-mer AATC during the same
traversal. Despite its benefits, this approach requires up to $k_{max}$
pointer-chasing operations for _each lookup_. Performing these operations
inside the SSD is challenging since the tree can be larger than the internal
DRAM, and pointer chasing on flash arrays is expensive due to their
significantly larger latency compared to DRAM.

While MetaStore can execute this part in the host, we identify a new
optimization opportunity leveraging unique features of ISP (i.e., large
internal bandwidth and storage capacity), which avoids pointer-chasing at the
cost of larger data structures. Fig. 5 c shows an overview of our approach,
_K-mer Sketch Streaming (KSS)_. For k-mers with size $k_{max}$, MetaStore
stores the k-mer sketches and their tax IDs similar to a. MetaStore sorts this
table alphabetically. For smaller values of $k$, MetaStore uses the prefixes
of the $k_{max}$-mers to retrieve smaller k-mers. For each smaller k-mer, it
only stores the tax IDs that are _not_ attributed to their corresponding
larger k-mer.111111A smaller k-mer can be found in more species since it is
less unique than its corresponding $k_{max}$-mers. Storing the k-mer itself is
not needed because it can be retrieved as the prefix of the larger k-mers.
This encoding allows for tax ID retrieval by sequentially streaming through
the intersecting k-mers (which are already sorted) and these KSS tables. While
the KSS data structure is larger than b, it is suitable for ISP due to the
high internal bandwidth and large capacity. KSS can also be helpful for
outside-SSD execution with SSDs with high external bandwidth (§VI-A). KSS
leads to 7.5$\times$ smaller data structures compared to the 107-GB a, and
2.1$\times$ larger compared to b (dataset details in §V).

Fig. 6 shows an overview of MetaStore’s Tax ID retrieval. As an example, we
demonstrate retrieving 5-mers and 4-mers. First, MetaStore reads the
intersecting k-mers (i.e., 5-mers) from the internal DRAM and concurrently
reads the 5-mer sketches and their IDs from an SSD channel. It performs a
comparison operation on the 5-mer streams to find matches ( 1). Second, to
find 4-mer matches, MetaStore compares the _prefixes_ of the intersecting
4-mers with the prefixes of the 4-mer sketches ( 2). MetaStore devises a
lightweight _Index Generator_. It compares the 4-mer prefixes of each pair of
consecutive 5-mer sketches, and when the prefixes are not equal (i.e., a new
4-mer appears), it points to the next element in the 4-mer table. We map the
data related to 5-mers and 4-mers in different channels to allow for
concurrent accesses to leverage the full internal bandwidth. Third, MetaStore
sends the retrieved tax IDs to the host ( 3) as the IDs of the candidate
species present in the sample.

Figure 6: Tax ID retrieval.

###  IV-C Step 3: Abundance Estimation

For metagenomic applications that require abundance estimation, MetaStore
integrates further analysis on the candidate species identified as present at
the end of Step 2. MetaStore can flexibly integrate with different approaches
used in various tools, such as (i) lightweight statistics [70, 72] or (ii)
more accurate and costly read mapping [64, 44, 48], where the input read set
is mapped to the reference genomes of candidate present species. In this step,
MetaStore facilitates integration with different approaches. The lightweight
statistical approaches work directly on the output of Step 2. To facilitate
the more complex read mapping, MetaStore prepares the data needed by the
software or hardware mapper used in the system. The mapper needs the query
reads and an index of the reference genomes of the candidate species, commonly
used during read mapping [6]. Constructing individual species indexes can be a
one-time offline task. However, generating a unified index for the collection
of the present species cannot be done offline, as these specific species are
undetermined beforehand.

We facilitate the read mapping process by generating a unified reference index
of the species detected in Step 2, inside the SSD directly while reading the
individual indexes of these species. Fig. 7 demonstrates this with an example
of two pre-built and pre-sorted indexes of species A and B. Each index entry
shows a k-mer and its location in that species’ reference genome. MetaStore
reads each index sequentially and merges them. When finding a common k-mer
between the two indexes, (e.g., CCA in Fig. 7), it stores both locations for
that k-mer in the unified index. In this example, assuming the size of the
reference genome A is 1000, we store the location of CCA in B as 1020 in the
unified index.

Figure 7: Merging the reference indexes.

###  IV-D MetaStore-FTL

MetaStore-FTL needs simple changes to the baseline FTL, to handle
communication/data flow between the host and the SSD. At the beginning,
MetaStore-FTL maintains all metadata of the regular FTL in the internal DRAM.
For the only step that requires writes (§IV-A1, at the beginning of Step 1 in
the host), MetaStore-FTL still uses the write-related metadata (e.g., L2P,
bad-block information). After this step, MetaStore does not require writes, so
it flushes the regular L2P and loads MetaStore’s L2P, while still keeping the
other metadata of a regular FTL.

Fig. 8 shows how MetaStore-FTL manages the target data stored in NAND flash
memory, i.e., databases121212K-mer and sketch databases are the only data
structures accessed from NAND flash memory during MetaStore’s ISP operations.
The read set k-mers get transferred from the host system to the SSD during
ISP., with a reduced amount of metadata. When initially storing a database ( 1
in Fig. 8), MetaStore-FTL 2 _evenly and sequentially_ distributes the data
across all SSD channels while ensuring that every _active_ block [103] (which
is currently used for writing) in different channels has the same page
offset.131313This can be done by either allocating dedicated blocks for the
database. Doing so allows MetaStore-FTL to only keep a small mapping data
structure ( 3) that consists of (i) the mapping between start logical page
address (LPA) and physical page address (PPA), (ii) the database size, and
(iii) the sequence of physical block addresses (PBAs) used to store the
database, instead of the entire LPA-to-PPA mappings. This is because MetaStore
always accesses the database _sequentially_. As shown in Fig. 8, MetaStore-FTL
can sequentially read the stored database from the starting LPA while
performing page reads in a round-robin manner across channels; it just
increments the PPA within a physical block and resets the PPA when reading the
next block. Compared to the regular L2P, whose space overhead is 0.1% of
stored data (4 bytes per 4 KiB), MetaStore’s L2P is very small. For example,
MetaStore only requires $\sim$1.3 MB to store a 4-TB database, assuming a
physical block size of 12 MB: 4 bytes for each of the 349,525 (4 TB/12 MB)
used blocks (and a few bytes for the start L2P mapping and database size).
Note that the only metadata other than L2P mappings that must be kept during
ISP is the per-block access count for read-disturbance management [104], so
the size of total metadata for MetaStore is up to 2.6 MB for a 4-TB SSD.
Flushing regular L2P into flash memory and using this smaller L2P enables us
to exploit most of the internal DRAM during ISP (to store query batches
$B\\#i$ and $B\\#i-1$ and Intersection, as shown in Figs. 4 and 6).

Figure 8: Data layout and mapping data structure in MetaStore.

MetaStore’s in-storage accelerators are located on the SSD controller and
access data _after_ ECC (which is designed to match the channels bandwidth).
MetaStore performs other tasks necessary for ensuring reliability (e.g.,
refreshing data to prevent uncorrectable errors[105, 106, 107, 104, 108, 109,
110, 111, 112, 113]) _before or after_ the ISP phase. This is because 1) the
duration of each MetaStore process is significantly smaller than the
manufacturer-specified threshold for reliable retention age (e.g., one year
[114]), and 2) since MetaStore only reads data sequentially with low re-use,
it can avoid read disturbance errors [104] during ISP.

###  IV-E End-to-End Walkthrough

Fig. 9 shows an end-to-end walkthrough of MetaStore’s steps. Upon receiving a
notification from the host to initiate metagenomic analysis 1, MetaStore
readies itself for collaborative ISP ( 2). To do so, MetaStore loads the
MetaStore-FTL metadata needed for its operations. After the preparation,
MetaStore starts the three-step execution. In Step 1, the host processes the
input read queries ( 3) and transfers them in batches to the SSD ( 4). In Step
2, the ISP units find the species present in the sample ( 5). Steps 1 and 2
run in a pipelined manner for consecutive query batches. In Step 3, MetaStore
facilitates the integration with different abundance estimation approaches by
preparing ( 6) and transferring ( 7) the data needed for any further analysis.
With its hardware/software co-design, MetaStore avoids channel conflicts and
frequent management tasks (by not requiring writes) during ISP, and leverages
the full internal bandwidth.

Figure 9: Overview of MetaStore.

###  IV-F Multi-Sample Analysis

For some use cases, a metagenomic study can have multiple read sets (i.e.,
samples) available at the same time that need to access the same database. If
the host’s DRAM is larger than the k-mer sizes extracted from a sample, we use
the available DRAM opportunistically to buffer k-mers extracted from _several_
samples. This way, MetaStore streams through the database only once. Fig. 10
shows the timeline of analyzing a single (S) or multiple (M) samples in the
baseline (Base), in our proposed optimized approach in software (Opt), and in
MetaStore (MS). MetaStore can flexibly integrate with a sorting accelerator to
further improve end-to-end performance.

Figure 10: Timeline of multi-sample analysis.

##  V Evaluation Methodology

SSDs. Our system is equipped with SSD-C [66] and SSD-P [65] as described in
§III-B.

Performance. We design a simulator that models all MetaStore’s components,
including host operations, accessing flash chips, the internal DRAM, the in-
storage accelerator, and interfaces between the host and the SSD. We feed the
latency and throughput of each of MetaStore components to this simulator. For
the components in the hardware-based steps (e.g., ISP units in Steps 2 and 3):
We implement MetaStore’s logic components in Verilog. We synthesize them using
the Synopsys Design Compiler [115] with a 65 nm library[116] to estimate their
frequency. We use two state-of-the-art simulators, Ramulator [117, 118] for
DRAM to model SSD’s internal DRAM accurately, and MQSim [119] for SSD’s
internal operations. For the components in the software-based steps (e.g.,
host operations in Step 1): We measure performance on a real system, an
AMD${}^{\text{\textregistered}}$ EPYC${}^{\text{\textregistered}}$ 7742 CPU
with 128 physical cores, 1-TB DRAM (in all experiments unless stated
otherwise), and the mentioned SSDs. We will open-source our simulator and
scripts. For the software baselines, we measure performance on the mentioned
real system, using the number of threads that lead to each tool’s best
performance.

Area and Power. For logic components, we use the results from our Design
Compiler synthesis. We implement MetaStore’s logic components in Verilog. For
SSD power, we use the values of a Samsung 3D NAND flash-based SSD [68]. For
DRAM power, we base the values on a DDR4 model [98, 120]. For the CPU cores,
we use AMD${}^{\text{\textregistered}}$ µProf [121].

Baseline Metagenomic Tools. We use a state-of-the-art performance-optimized
(P-Opt) tool, Kraken2 + Bracken [45], and a state-of-the-art accuracy-
optimized (A-Opt) tool, Metalign [64]. Particularly, for the presence/absence
task, we use Kraken2 without Bracken, and Metalign without mapping (i.e., only
KMC [93] \+ CMash [99]). For abundance estimation, we use Kraken2 + Bracken,
and full Metalign. For both Metalign and MetaStore, we use GenCache [122] for
mapping. We use the optimal mapping throughput as reported by the original
paper [122]. MetaStore can flexibly integrate with other mappers. We also
compare MetaStore against a state-of-the-art PIM k-mer matching accelerator,
Sieve [54], for accelerating Kraken2’s pipeline. We use the optimal k-mer
matching performance as reported by the original paper [54].

Datasets. We use three query read sets from the commonly-used CAMI benchmark
[123], with low/medium/high genetic diversity. Each read set has 100 million
reads. We generate a database based on microbial genomes drawn from NCBI’s
databases [82, 64] using default parameters for each tool. For Kraken2 [45],
this results in a 293 GB database. For Metalign [64], this results in a 701 GB
k-mer database and a 6.9 GB sketch tree. MetaStore uses the same 701 GB k-mer
database and a 14 GB sketch database for our KSS.

##  VI Evaluation

###  VI-A Presence/Absence Identification Analysis

We use 1-TB DRAM in this analysis (smaller than all datasets used here). Fig.
11 shows the performance of five tools: 1) P-Opt, 2) A-Opt, 3) A-Opt+KSS:
A-Opt that leverages the software implementation of our KSS approach (§IV-B2),
instead of Metalign’s CMash [64], 4) MS-NOL: a MetaStore implementation
without overlapping the host and SSD operations as enabled by MetaStore’s
bucketing (§IV-A), 5) Ext-MS: a MetaStore implementation without ISP, where
the same accelerators used in MetaStore are outside the SSD, 6) MS-CC: a
MetaStore configuration in which the cores on the SSD controller141414We
assume three/four ARM Cortex-R4 cores [67] for SSD-C/SSD-P. perform
MetaStore’s ISP tasks, and 7) MS: a MetaStore configuration in which the
accelerators on the SSD controller perform the ISP tasks. Speedup is
calculated over P-Opt. A-Opt achieves significantly larger accuracy compared
to P-Opt [81, 64]. In particular, A-Opt leads to 4.84$\times$ higher F1 scores
and 13% lower L1 norm scores on average across our inputs. MS matches the
accuracy of A-Opt since it analyzes the same k-mer and sketch databases.

Figure 11: Speedup for different SSDs and input sets.

We make six key observations. First, MetaStore achieves significant speedup:
on the system with SSD-C (SSD-P), MS is 5.34–6.38$\times$ (2.66–6.52$\times$)
faster compared to P-Opt, and 12.41–18.22$\times$ (6.93–20.39$\times$) faster
compared to A-Opt. Second, A-Opt+KSS improves A-Opt’s performance by
1.41$\times$ (4.19$\times$) on average, while it still performs 10.51$\times$
(2.89$\times$) slower than MS on SSD-C (SSD-P). This shows that while our KSS
approach, even outside the SSD, provides large benefits (specifically on
SSD-P), MetaStore provides more significant additional benefits by alleviating
the I/O overhead. Third, with SSD-C (SSD-P), MS leads to 23.45% (34.94%)
greater average speedup compared to MS-NOL, which shows the benefits of
MetaStore’s bucketing to enable overlapping of the steps. Fourth MS leads to
10.19$\times$ (2.17$\times$) average speedup compared to Ext-MS on SSD-C
(SSD-P) due to our specialized ISP. Fifth, while MS-CC provides large
speedups, MS leads to 9% (43%) greater average speedup compared to MS-CC on
SSD-C (SSD-P). While both MetaStore configurations provide large speedups,
this observation shows the benefits of accelerators for MetaStore’s ISP tasks
as the internal bandwidth grows. Sixth, MetaStore’s speedup increases for
inputs with higher genetic diversity since they lead to more sketch tree
lookups in the baseline, while in MetaStore’s KSS approach, all tax IDs are
retrieved with a single pass through the tables.

To further demonstrate the benefits of MetaStore’s optimizations, Fig. 12
shows the time breakdowns with CAMI-L as a representative. First, A-Opt+KSS
benefits from faster tax ID retrieval compared to A-Opt, since KSS avoids many
tree lookups (here 60) for each intersecting k-mer. Therefore, for a
sufficiently large number of intersecting k-mers, KSS’ one-time sequential
scan through all sketches is more efficient than 60 pointer-chases for _each
k-mer_. Second, MS-NOL benefits from faster intersection finding and tax ID
retrieval. Third, MS benefits from overlapping part of the input query
processing with intersection finding.

Figure 12: Time breakdown with different SSDs for CAMI-L.

Impact of Database Size. Fig. 13 shows the impact of database size, using
CAMI-M as a representative input. The largest database size in each tool
(marked by 3$\times$) equals the size mentioned in §V. We observe that
MetaStore’s performance benefits increase as the database size increases (up
to 5.64$\times$/3.67$\times$ speedup compared to P-Opt on SSD-C/SSD-P).

Figure 13: Speedup with different database sizes.

Impact of the Number of SSDs. MetaStore benefits from more SSDs in two ways.
First, we can map different databases to different SSDs and run various
analyses concurrently, each benefiting from MetaStore, as already shown.
Second, since the databases and the queries are sorted in MetaStore, we can
disjointly partition the database between different SSDs. Fig. 14 shows
MetaStore’s benefits in this case. We show that MetaStore maintains its large
speedups with many SSDs because as the external bandwidth increases for the
baselines, internal bandwidth also increases for MetaStore. Particularly,
speedup over P-Opt increases until some point (two SSDs) because MetaStore
takes better advantage of the bandwidth scaling due to its more efficient
streaming accesses. Although there is a slight decrease in speedup when moving
from two to eight SSDs, the speedup is still high (6.9$\times$/5.2$\times$
over eight SSD-Cs/SSD-Ps). This decrease is because in MetaStore, due to the
large internal bandwidth with 8 SSDs, the pipeline’s throughput becomes
dependent on the sorting throughput in the host. Therefore, in large systems
with many SSDs, MetaStore can flexibly integrate with a sorting accelerator to
further improve end-to-end performance. Based on these observations, we
conclude that MetaStore effectively leverages the increased internal bandwidth
as the number of SSDs increases.

Figure 14: Speedup with different number of SSDs.

Impact of Main Memory Capacity. Fig. 15 shows the impact of main memory
capacity with CAMI-M as a representative input.151515In all cases, except for
the 32GB configuration, all k-mer buckets extracted from the read set (§IV-A1)
fit in DRAM. To gain a fair understanding of I/O overheads when DRAM is
smaller than the database, we ensure to reduce this overhead as much as
possible in software. To this end, we adopt an optimization [46] to load and
process P-Opt’s database into chunks that fit in DRAM. In this case, random
accesses to the database in each chunk do not need to repeatedly access the
SSD, but there are still two overheads. First, we must still pay the I/O cost
of bringing all the chunks from the SSD to DRAM. Second, for every chunk, all
of the input sequences must be queried repeatedly.161616Note that this
optimization is not required for A-Opt due to its streaming accesses to the
database.

We make three observations. First, MetaStore’s speedup increases compared to
P-Opt with smaller DRAM (e.g., up to 38.53$\times$ on SSD-P). This is because
P-Opt’s performance gets hindered by the memory capacity, while MetaStore does
not rely on large DRAM for buffering the database. Second, A-Opt and A-Opt+KSS
do not get affected by the small DRAM (except for the 32-GB configuration) due
to their streaming database accesses with _no_ reuse. But regardless of the
DRAM size, they suffer from I/O overhead. Third, with the 32-GB DRAM (which is
smaller than the extracted k-mers from the read set in Step 1, §IV-A1), MS’s
speedup increases due to the optimizations in MetaStore’s bucketing (§IV-A1).
We conclude that MetaStore enables fast and accurate analysis, _without
relying_ on large DRAM or high-bandwidth interconnects between the host and
the SSD. This can 1) allow multiple jobs to run concurrently on a system and
more effectively share the available DRAM capacity and SSD external bandwidth,
or 2) facilitate the use of cost-effective, portable (e.g., edge) devices for
metagenomic tasks.

Figure 15: Speedup with different main memory capacities. Figure 16: Speedup
of MetaStore on a cost-optimized system over baselines on a performance-
optimized system.

Impact on System Cost Efficiency. MetaStore increases system cost-efficiency
because (i) it analyzes large amounts of data inside the storage system and
removes a large part of the analysis burden from other parts of the system,
and (ii) does not rely on either high-bandwidth interfaces between the SSD the
host or large DRAM capacity. To demonstrate this point, Fig. 16 shows
MetaStore’s performance on a cost-optimized system with SSD-C and 64-GB DRAM
(MS_C) compared to P-Opt and A-Opt on a performance-optimized system with
SSD-P and 1-TB DRAM (P-Opt_P and A-Opt_P). We observe that MS_C provides
2.37$\times$ and 7.20$\times$ average speedup compared to P-Opt and A-Opt,
respectively. Note that MS_C provides the same accuracy as A-Opt_P and
significantly higher accuracy compared to P-Opt_P. We conclude that MetaStore
can outperform the baseline tools even when running on a more cost-optimized
system and achieving high accuracy. This is critical in both increasing the
overall cost-efficiency of the system and in enabling portable metagenomic
analysis, which is gaining increasing importance after the advancement of
compact portable DNA sequencers [35, 36, 124] for on-site metagenomic analysis
[79, 20].

Comparison to a PIM Accelerator. Fig. 17 evaluates MetaStore compared to a
PIM-accelerated baseline. We model Kraken2’s _end-to-end_ execution time
(i.e., including the I/O accesses to load data to the PIM accelerator, k-mer
matching, sample classification, and other computation [45]), performing the
k-mer matching part on a state-of-the-art PIM system, Sieve [54].171717We do
not use PIM for k-mer matching in Metalign because it is bottlenecked only by
the I/O bandwidth, not main memory, due to its streaming accesses. We observe
that MetaStore achieves 4.84-5.06$\times$ (1.46-2.73$\times$) speedup on SSD-C
(SSD-P) while achieving significantly higher accuracy. A larger database for
Kraken2 to encode richer information can increase the accuracy but will
increase I/O overhead even further. We conclude that MetaStore can provide
large speedups at high accuracy via analysis of large databases inside the
SSD.

Figure 17: Speedup over a PIM-accelerated baseline [54].

###  VI-B Abundance Estimation Analysis

We analyze P-Opt, A-Opt, MS-NIdx (a MetaStore implementation that does not
leverage MetaStore’s third step for generating a unified reference index shown
in §IV-A, and instead uses Minimap2 [6]), and MS. In Fig. 18, we make two key
observations. First, MetaStore leads to significant speedup compared to P-Opt
and A-Opt, achieving 5.09–5.47$\times$ (2.46–3.72$\times$) speedup on SSD-C
(SSD-P) compared to P-Opt, and 11.96–15.25$\times$ (6.50–20.79$\times$)
speedup on SSD-C (SSD-P) compared to P-Opt. Second, MetaStore’s full
implementation achieves 65% higher average speedup compared to MS-NIdx.

Figure 18: Speedup for abundance estimation.

###  VI-C Multi-Sample Analysis

Figure 19: Speedup for multi-sample analysis.

Fig. 19 shows speedups for multi-sample use cases (§IV-F) with 256-GB host
DRAM, in which we can buffer k-mers of 1–16 samples (assuming each sample’s
size is similar to CAMI-M). We show the performance of our multi-sample
pipelined optimization (§IV-F) in software (MS-Pipe) and in the full MetaStore
design (MS). In all configurations that require sorting (all except P-Opt), we
use a state-of-the-art sorting accelerator [125].181818 We use the sorting
throughput reported by the original paper [125] and model the buckets’
communication time with the accelerator. We make two key observations. First,
MS achieves large speedups of up to 37.2$\times$/100.2$\times$ compared to
P-Opt/A-Opt. Second, MS-Pipe leads to up to 20.51$\times$ (52.0$\times$)
speedup compared to A-Opt on SSD-C (SSD-P), and the speedup grows with the
number of samples.

###  VI-D Area and Power

Table I shows the area and power consumption of MetaStore’s logic units at 300
MHz. While they could be designed to operate at a higher frequency, their
throughput is already sufficient since MetaStore is bottlenecked by NAND flash
reads. MetaStore’s hardware area and power requirements are minimal: only 0.04
mm2 and 7.658 mW at 65 nm. The area overhead of MetaStore hardware is 0.011
mm2 at 32 nm, 191919We scale the area to lower technology node using the
methodology in [126] since these technology nodes are not available publicly.
which is 1.7% of the three 28-nm ARM Cortex R4 cores [67] in a SATA SSD
controller [68]. These logic units are 26.85$\times$ more power-efficient than
these cores during MetaStore’s ISP.

Table I: Area and power consumption of MetaStore’s logic.

Logic unit | # of instances | Area [mm2] | Power [mW]
---|---|---|---
Comparator (120-bit) | 1 per channel | 0.001361 | 0.284
60-mer Registers (2$\times$ 120-bit) | 1 per channel | 0.002821 | 0.645
Index Generator (64-bit) | 1 per channel | 0.000272 | 0.025
Control Unit | 1 per SSD | 0.000188 | 0.026
Total for an 8-channel SSD | - | 0.04 | 7.658

###  VI-E Energy

For each tool, we calculate each part’s energy based on its active/idle power
and execution time. We observe that MetaStore provides significant energy
benefits by alleviating the I/O overhead and  reducing the burdens of the
analysis from the rest of the system. Across the SSDs and the datasets, we
observe that MetaStore leads to 5.36$\times$ (9.82$\times$), 15.16$\times$
(25.68$\times$), and 1.88$\times$ (3.49$\times$) average (maximum) energy
reduction compared to P-Opt, A-Opt, and the PIM-accelerated P-Opt when finding
species present in the sample.

##  VII Related Work

To our knowledge, MetaStore is the _first_ ISP system for end-to-end
metagenomic analysis. We already extensively compare MetaStore against Kraken2
[45], Metalign [64], and Sieve [54]. Here, we briefly discuss other related
works.

Software Optimization of Metagenomics. There are various pure software tools
for metagenomics. Several tools (e.g., [80, 64]) use comprehensive databases
for high accuracy. However, these tools usually incur significant
computational and I/O costs due to their database size. Some tools (e.g., [45,
46, 47]) apply sampling techniques to significantly reduce database size, but
at the cost of accuracy loss. All of these techniques feature trade-offs
between accuracy and performance due to the significant I/O costs of moving
large metagenomic databases.

Hardware Acceleration of Metagenomics. There are several works using GPU [60,
52, 53, 56], FPGA [127], and PIM [54, 57, 58, 51, 55, 87] to accelerate
metagenomics by alleviating its computation or main memory data movement
overheads. These works do not alleviate I/O overhead, whose impact on end-to-
end performance becomes even larger when other bottlenecks get alleviated.

In-Storage Processing. Several works propose ISP designs as accelerators for
different applications [128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138,
139, 88, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150] (e.g., in
machine learning [150, 151, 147], pattern processing and read mapping [149,
91], and graph analytics [141]), general-purpose [152, 153, 154, 155, 156,
146, 145, 157, 158, 159, 160, 161, 162, 163], bulk-bitwise operations using
flash memory [164, 165], in close integration with FPGAs [166, 167, 168, 169,
170, 90], or GPUs [171]. None of these works perform metagenomic analysis nor
address the challenges of ISP for metagenomics.

MetaStore is the first work that targets the end-to-end process of metagenomic
analysis, and by addressing the unique challenges of leveraging ISP for
metagenomics, MetaStore fundamentally alleviates its data movement overhead
from the storage system. MetaStore does so through its lightweight,
synergistic, and cooperative design with processing inside and outside the
storage system.

##  VIII Conclusion

We introduce MetaStore, the first ISP system for metagenomics to reduce the
I/O cost of metagenomics. To enable efficient ISP for metagenomics, we propose
new 1) task partitioning, 2) storage technology-aware algorithms, 3) data
mapping, and 4) data/computation flow coordination. Our evaluations on large
metagenomic databases show that MetaStore improves the performance and energy
efficiency of metagenomics, with high accuracy and at a low cost.

## References

  * [1] S. D. Ehrlich, _MetaHIT: The European Union Project on Metagenomics of the Human Intestinal Tract_. New York, NY: Springer New York, 2011, pp. 307–316.
  * [2] S. Sunagawa, L. P. Coelho, S. Chaffron, J. R. Kultima, K. Labadie, G. Salazar, B. Djahanschiri, G. Zeller, D. R. Mende, A. Alberti, F. M. Cornejo-Castillo, P. I. Costea, C. Cruaud, F. d’Ovidio, S. Engelen, I. Ferrera, J. M. Gasol, L. Guidi, F. Hildebrand, F. Kokoszka, C. Lepoivre, G. Lima-Mendez, J. Poulain, B. T. Poulos, M. Royo-Llonch, H. Sarmento, S. Vieira-Silva, C. Dimier, M. Picheral, S. Searson, S. Kandels-Lewis, T. O. coordinators, C. Bowler, C. de Vargas, G. Gorsky, N. Grimsley, P. Hingamp, D. Iudicone, O. Jaillon, F. Not, H. Ogata, S. Pesant, S. Speich, L. Stemmann, M. B. Sullivan, J. Weissenbach, P. Wincker, E. Karsenti, J. Raes, S. G. Acinas, P. Bork, E. Boss, C. Bowler, M. Follows, L. Karp-Boss, U. Krzic, E. G. Reynaud, C. Sardet, M. Sieracki, and D. Velayoudon, “Structure and Function of the Global Ocean Microbiome,” _Science_ , 2015.
  * [3] N. Fierer, “Embracing the unknown: disentangling the complexities of the soil microbiome,” _Nature Reviews Microbiology_ , vol. 15, no. 10, pp. 579–590, Oct 2017.
  * [4] D. S. Cali, G. S. Kalsi, Z. Bingöl, C. Firtina, L. Subramanian, J. S. Kim, R. Ausavarungnirun, M. Alser, J. Gomez-Luna, A. Boroumand, A. Norion, A. Scibisz, S. Subramoneyon, C. Alkan, S. Ghose, and O. Mutlu, “GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis,” in _MICRO_ , 2020.
  * [5] Y. Huang, L. Kong, D. Chen, Z. Chen, X. Kong, Z. Jianfeng, K. Mamouras, S. Wei, K. Yang, and L. Liu, “Casa: An energy-efficient and high-speed cam-based smem seeding accelerator for genome alignment,” _MICRO_ , 2023.
  * [6] H. Li, “Minimap2: Pairwise Alignment for Nucleotide Sequences,” _Bioinformatics_ , 2018.
  * [7] 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.
  * [8] Y. Turakhia, G. Bejerano, and W. J. Dally, “Darwin: A Genomics Co-processor Provides up to 15,000 x Acceleration on Long Read Assembly,” in _ASPLOS_ , 2018.
  * [9] S. Gupta, M. Imani, B. Khaleghi, V. Kumar, and T. Rosing, “RAPID: A ReRAM Processing In-memory Architecture for DNA Sequence Alignment,” in _ISLPED_ , 2019.
  * [10] T. M. Kuntz and J. A. Gilbert, “Introducing the microbiome into precision medicine,” _Trends in Pharmacological Sciences_ , vol. 38, no. 1, pp. 81–91, 2017, special Issue: Precision Medicine.
  * [11] M. Dixon, M. Stefil, M. McDonald, T. E. Bjerklund-Johansen, K. Naber, F. Wagenlehner, and V. Mouraviev, “Metagenomics in diagnosis and improved targeted treatment of uti,” _World Journal of Urology_ , vol. 38, no. 1, pp. 35–43, Jan 2020.
  * [12] A. M. Taxt, E. Avershina, S. A. Frye, U. Naseer, and R. Ahmad, “Rapid identification of pathogens, antibiotic resistance genes and plasmids in blood cultures by nanopore sequencing,” _Scientific Reports_ , vol. 10, no. 1, p. 7622, 05 2020. [Online]. Available: https://doi.org/10.1038/s41598-020-64616-x
  * [13] E. Afshinnekoo, C. Meydan, S. Chowdhury, D. Jaroudi, C. Boyer, N. Bernstein, J. Maritz, D. Reeves, J. Gandara, S. Chhangawala, S. Ahsanuddin, A. Simmons, T. Nessel, B. Sundaresh, E. Pereira, E. Jorgensen, S.-O. Kolokotronis, N. Kirchberger, I. Garcia, D. Gandara, S. Dhanraj, T. Nawrin, Y. Saletore, N. Alexander, P. Vijay, E. Hénaff, P. Zumbo, M. Walsh, G. O’Mullan, S. Tighe, J. Dudley, A. Dunaif, S. Ennis, E. O’Halloran, T. Magalhaes, B. Boone, A. Jones, T. Muth, K. Paolantonio, E. Alter, E. Schadt, J. Garbarino, R. Prill, J. Carlton, S. Levy, and C. Mason, “Geospatial Resolution of Human and Bacterial Diversity with City-scale Metagenomics,” _Cell Systems_ , 2015.
  * [14] T. Hsu, R. Joice, J. Vallarino, G. Abu-Ali, E. M. Hartmann, A. Shafquat, C. DuLong, C. Baranowski, D. Gevers, J. L. Green, X. C. Morgan, J. D. Spengler, and C. Huttenhower, “Urban Transit System Microbial Communities Differ by Surface Type and Interaction with Humans and the Environment,” _Msystems_ , 2016.
  * [15] G. John, N. S. Sahajpal, A. K. Mondal, S. Ananth, C. Williams, A. Chaubey, A. M. Rojiani, and R. Kolhe, “Next-generation sequencing (ngs) in covid-19: A tool for sars-cov-2 diagnosis, monitoring new strains and phylodynamic modeling in molecular epidemiology,” _Current Issues in Molecular Biology_ , vol. 43, no. 2, pp. 845–867, 2021.
  * [16] D. Nagy-Szakal, M. Couto-Rodriguez, H. L. Wells, J. E. Barrows, M. Debieu, K. Butcher, S. Chen, A. Berki, C. Hager, R. J. Boorstein, M. K. Taylor, C. B. Jonsson, C. E. Mason, and N. B. O’Hara, “Targeted hybridization capture of sars-cov-2 and metagenomics enables genetic variant discovery and nasal microbiome insights,” _Microbiology Spectrum_ , vol. 9, no. 2, pp. e00 197–21, 2021.
  * [17] D. F. Nieuwenhuijse and M. P. G. Koopmans, “Metagenomic sequencing for surveillance of food- and waterborne viral diseases,” _Frontiers in Microbiology_ , vol. 8, 2017.
  * [18] J. Hadfield, C. Megill, S. M. Bell, J. Huddleston, B. Potter, C. Callender, P. Sagulenko, T. Bedford, and R. A. Neher, “Nextstrain: Real-time Tracking of Pathogen Evolution,” _Bioinformatics_ , 2018.
  * [19] B. Berger and Y. W. Yu, “Navigating bottlenecks and trade-offs in genomic data analysis,” _Nature Reviews Genetics_ , vol. 24, no. 4, pp. 235–250, 2023\.
  * [20] A. Dulanto Chiang and J. P. Dekker, “From the Pipeline to the Bedside: Advances and Challenges in Clinical Metagenomics,” _The Journal of Infectious Diseases_ , vol. 221, no. Supplement_3, pp. S331–S340, 09 2019. [Online]. Available: https://doi.org/10.1093/infdis/jiz151
  * [21] C. Y. Chiu and S. A. Miller, “Clinical metagenomics,” _Nature Reviews Genetics_ , vol. 20, no. 6, pp. 341–355, Jun 2019.
  * [22] N. A. Bokulich, M. Ziemski, M. S. Robeson, and B. D. Kaehler, “Measuring the microbiome: Best practices for developing and benchmarking microbiomics methods,” _Computational and Structural Biotechnology Journal_ , vol. 18, pp. 4048–4062, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S200103702030516X
  * [23] T. Hu, N. Chitnis, D. Monos, and A. Dinh, “Next-Generation Sequencing Technologies: An Overview,” _Human Immunology_ , 2021.
  * [24] M. Alser, Z. Bingöl, D. S. Cali, J. Kim, S. Ghose, C. Alkan, and O. Mutlu, “Accelerating genome analysis: A primer on an ongoing journey,” _IEEE Micro_ , vol. 40, no. 5, pp. 65–75, 2020.
  * [25] K. Katz, O. Shutov, R. Lapoint, M. Kimelman, J. Brister, and C. O’Sullivan, “The Sequence Read Archive: a decade more of explosive growth,” _Nucleic Acids Research_ , vol. 50, no. D1, pp. D387–D390, 11 2021. [Online]. Available: https://doi.org/10.1093/nar/gkab1053
  * [26] E. B. Institute, “European Nucleotide Archive Statistics,” https://www.ebi.ac.uk/ena/browser/about/statistics, 2023.
  * [27] M. Alser, J. Lindegger, C. Firtina, N. Almadhoun, H. Mao, G. Singh, J. Gomez-Luna, and O. Mutlu, “From molecules to genomic variations: Accelerating genome analysis via intelligent algorithms and architectures,” _Computational and Structural Biotechnology Journal_ , 2022.
  * [28] R. Leinonen, H. Sugawara, M. Shumway, and I. N. S. D. Collaboration, “The Sequence Read Archive,” _Nucleic Acids Research_ , 2010.
  * [29] H. Zhang, H. Li, C. Jain, H. Cheng, K. F. Au, H. Li, and S. Aluru, “Real-time Mapping of Nanopore Raw Signals,” _Bioinformatics_ , 2021.
  * [30] C. Firtina, N. Mansouri Ghiasi, J. Lindegger, G. Singh, M. B. Cavlak, H. Mao, and O. Mutlu, “RawHash: enabling fast and accurate real-time analysis of raw nanopore signals for large genomes,” _Bioinformatics_ , vol. 39, no. Supplement_1, pp. i297–i307, 06 2023. [Online]. Available: https://doi.org/10.1093/bioinformatics/btad272
  * [31] S. Kovaka, Y. Fan, B. Ni, W. Timp, and M. C. Schatz, “Targeted Nanopore Sequencing by Real-time Mapping of Raw Electrical Signal with UNCALLED,” _Nature Biotechnology_ , 2020.
  * [32] O. Mutlu and C. Firtina, “Accelerating Genome Analysis via Algorithm-Architecture Co-Design,” in _DAC_ , 2023.
  * [33] C. Firtina, M. Soysal, J. Lindegger, and O. Mutlu, “Rawhash2: Accurate and fast mapping of raw nanopore signals using a hash-based seeding mechanism,” _arXiv preprint arXiv:2309.05771_ , 2023.
  * [34] J. Lindegger, C. Firtina, N. M. Ghiasi, M. Sadrosadati, M. Alser, and O. Mutlu, “Rawalign: Accurate, fast, and scalable raw nanopore signal mapping via combining seeding and alignment,” _arXiv preprint arXiv:2310.05037_ , 2023\.
  * [35] O. N. Technologies, “MinION Mk1B IT Requirements,” https://community.nanoporetech.com/requirements_documents/minion-it-reqs.pdf, 2021\.
  * [36] M. Jain, H. E. Olsen, B. Paten, and M. Akeson, “The oxford nanopore minion: delivery of nanopore sequencing to the genomics community,” _Genome Biology_ , vol. 17, no. 1, p. 239, 11 2016. [Online]. Available: https://doi.org/10.1186/s13059-016-1103-0
  * [37] E. W. Sayers, E. E. Bolton, J. Brister, K. Canese, J. Chan, D. Comeau, C. Farrell, M. Feldgarden, A. M. Fine, K. Funk, E. Hatcher, S. Kannan, C. Kelly, S. Kim, W. Klimke, M. Landrum, S. Lathrop, Z. Lu, T. Madden, A. Malheiro, A. Marchler-Bauer, T. Murphy, L. Phan, S. Pujar, S. Rangwala, V. Schneider, T. Tse, J. Wang, J. Ye, B. Trawick, K. Pruitt, and S. Sherry, “Database resources of the National Center for Biotechnology Information in 2023,” _Nucleic Acids Research_ , vol. 51, no. D1, pp. D29–D38, 11 2022\.
  * [38] M. Karasikov, H. Mustafa, D. Danciu, M. Zimmermann, C. Barber, G. Ratsch, and A. Kahles, “Metagraph: Indexing and Analysing Nucleotide Archives at Petabase-scale,” _bioRxiv_ , 2020.
  * [39] S. A. Shiryev and R. Agarwala, “Indexing and searching petabyte-scale nucleotide resources,” _bioRxiv_ , pp. 2023–07, 2023.
  * [40] N. C. for Biotechnology Information, “Introducing pebblescout: Index and search petabyte-scale sequence resources faster than ever,” https://ncbiinsights.ncbi.nlm.nih.gov/2023/09/14/introducing-pebblescout/, 2023\.
  * [41] M. Rautiainen, S. Nurk, B. P. Walenz, G. A. Logsdon, D. Porubsky, A. Rhie, E. E. Eichler, A. M. Phillippy, and S. Koren, “Telomere-to-telomere assembly of diploid chromosomes with verkko,” _Nature Biotechnology_ , Feb 2023.
  * [42] E. D. Jarvis, G. Formenti, A. Rhie, A. Guarracino, C. Yang, J. Wood, A. Tracey, F. Thibaud-Nissen, M. R. Vollger, D. Porubsky, H. Cheng, M. Asri, G. A. Logsdon, P. Carnevali, M. J. P. Chaisson, C.-S. Chin, S. Cody, J. Collins, P. Ebert, M. Escalona, O. Fedrigo, R. S. Fulton, L. L. Fulton, S. Garg, J. L. Gerton, J. Ghurye, A. Granat, R. E. Green, W. Harvey, P. Hasenfeld, A. Hastie, M. Haukness, E. B. Jaeger, M. Jain, M. Kirsche, M. Kolmogorov, J. O. Korbel, S. Koren, J. Korlach, J. Lee, D. Li, T. Lindsay, J. Lucas, F. Luo, T. Marschall, M. W. Mitchell, J. McDaniel, F. Nie, H. E. Olsen, N. D. Olson, T. Pesout, T. Potapova, D. Puiu, A. Regier, J. Ruan, S. L. Salzberg, A. D. Sanders, M. C. Schatz, A. Schmitt, V. A. Schneider, S. Selvaraj, K. Shafin, A. Shumate, N. O. Stitziel, C. Stober, J. Torrance, J. Wagner, J. Wang, A. Wenger, C. Xiao, A. V. Zimin, G. Zhang, T. Wang, H. Li, E. Garrison, D. Haussler, I. Hall, J. M. Zook, E. E. Eichler, A. M. Phillippy, B. Paten, K. Howe, K. H. Miga, and H. P. R. Consortium, “Semi-automated assembly of high-quality diploid human reference genomes,” _Nature_ , vol. 611, no. 7936, pp. 519–531, Nov 2022.
  * [43] N. C. for Biotechnology Information, “Re-evaluating the blast nucleotide database (nt),” https://ncbiinsights.ncbi.nlm.nih.gov/2022/11/17/re-evaluating-blast-nucleotide-nt/, 2022\.
  * [44] D. Kim, L. Song, F. P. Breitwieser, and S. L. Salzberg, “Centrifuge: Rapid and Sensitive Classification of Metagenomic Sequences,” _Genome Research_ , 2016.
  * [45] D. E. Wood, J. Lu, and B. Langmead, “Improved Metagenomic Analysis with Kraken 2,” _Genome Biology_ , 2019.
  * [46] C. Pockrandt, A. V. Zimin, and S. L. Salzberg, “Metagenomic classification with krakenuniq on low-memory computers,” _Journal of Open Source Software_ , vol. 7, no. 80, p. 4908, 2022.
  * [47] A. Müller, C. Hundt, A. Hildebrandt, T. Hankeln, and B. Schmidt, “Metacache: context-aware classification of metagenomic reads using minhashing,” _Bioinformatics_ , vol. 33, no. 23, pp. 3740–3748, 2017.
  * [48] A. Milanese, D. R. Mende, L. Paoli, G. Salazar, H.-J. Ruscheweyh, M. Cuenca, P. Hingamp, R. Alves, P. I. Costea, L. P. Coelho, T. S. B. Schmidt, A. Almeida, A. L. Mitchell, R. D. Finn, J. Huerta-Cepas, P. Bork, G. Zeller, and S. Sunagawa, “Microbial abundance, activity and population genomic profiling with motus2,” _Nature Communications_ , vol. 10, no. 1, p. 1014, Mar 2019.
  * [49] S. L. Salzberg, F. P. Breitwieser, A. Kumar, H. Hao, P. Burger, F. J. Rodriguez, M. Lim, A. Quiñones-Hinojosa, G. L. Gallia, J. A. Tornheim, M. T. Melia, C. L. Sears, and C. A. Pardo, “Next-generation sequencing in neuropathologic diagnosis of infections of the nervous system,” _Neurology - Neuroimmunology Neuroinflammation_ , vol. 3, no. 4, 2016. [Online]. Available: https://nn.neurology.org/content/3/4/e251
  * [50] A. Gihawi, Y. Ge, J. Lu, D. Puiu, A. Xu, C. S. Cooper, D. S. Brewer, M. Pertea, and S. L. Salzberg, “Major data analysis errors invalidate cancer microbiome findings,” _bioRxiv_ , 2023. [Online]. Available: https://www.biorxiv.org/content/early/2023/07/31/2023.07.28.550993
  * [51] Z. Jahshan, I. Merlin, E. Garzón, and L. Yavits, “Dash-cam: Dynamic approximate search content addressable memory for genome classification,” _MICRO_ , 2023.
  * [52] R. Kobus, A. Müller, D. Jünger, C. Hundt, and B. Schmidt, “Metacache-gpu: ultra-fast metagenomic classification,” in _50th International Conference on Parallel Processing_ , 2021, pp. 1–11.
  * [53] X. Wang, T. Wang, Z. Xie, Y. Zhang, S. Xia, R. Sun, X. He, R. Xiang, Q. Zheng, Z. Liu, J. Wang, H. Wu, X. Jin, W. Chen, D. Li, and Z. He, “Gpmeta: a gpu-accelerated method for ultrarapid pathogen identification from metagenomic sequences,” _Briefings in Bioinformatics_ , vol. 24, no. 2, p. bbad092, 2023.
  * [54] L. Wu, R. Sharifi, M. Lenjani, K. Skadron, and A. Venkat, “Sieve: Scalable in-situ dram-based accelerator designs for massively parallel k-mer matching,” in _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 2021, pp. 251–264.
  * [55] R. Hanhan, E. Garzón, Z. Jahshan, A. Teman, M. Lanuzza, and L. Yavits, “Edam: edit distance tolerant approximate matching content addressable memory,” in _Proceedings of the 49th Annual International Symposium on Computer Architecture_ , 2022, pp. 495–507.
  * [56] R. Kobus, C. Hundt, A. Müller, and B. Schmidt, “Accelerating Metagenomic Read Classification on CUDA-enabled GPUs,” _BMC Bioinformatics_ , 2017.
  * [57] T. Shahroodi, M. Zahedi, A. Singh, S. Wong, and S. Hamdioui, “Krakenonmem: a memristor-augmented hw/sw framework for taxonomic profiling,” in _Proceedings of the 36th ACM International Conference on Supercomputing_ , 2022, pp. 1–14.
  * [58] T. Shahroodi, M. Zahedi, C. Firtina, M. Alser, S. Wong, O. Mutlu, and S. Hamdioui, “Demeter: A fast and energy-efficient food profiler using hyperdimensional computing in memory,” _IEEE Access_ , vol. 10, pp. 82 493–82 510, 2022.
  * [59] G. Armstrong, C. Martino, J. Morris, B. Khaleghi, J. Kang, J. DeReus, Q. Zhu, D. Roush, D. McDonald, A. Gonazlez _et al._ , “Swapping metagenomics preprocessing pipeline components offers speed and sensitivity increases,” _Msystems_ , vol. 7, no. 2, pp. e01 378–21, 2022.
  * [60] P. Jia, L. Xuan, L. Liu, and C. Wei, “Metabing: Using gpus to accelerate metagenomic sequence classification,” _PloS one_ , vol. 6, no. 11, p. e25353, 2011.
  * [61] R. Nadig, M. Sadrosadati, H. Mao, N. M. Ghiasi, A. Tavakkol, J. Park, H. Sarbazi-Azad, J. G. Luna, and O. Mutlu, “Venice: Improving Solid-State Drive Parallelism at Low Cost via Conflict-Free Accesses,” in _ISCA_ , 2023\.
  * [62] A. Tavakkol, M. Sadrosadati, S. Ghose, J. Kim, Y. Luo, Y. Wang, N. M. Ghiasi, L. Orosa, J. Gómez-Luna, and O. Mutlu, “FLIN: Enabling Fairness and Enhancing Performance in Modern NVMe Solid State Drives,” in _ISCA_ , 2018\.
  * [63] J. Kim, S. Kang, Y. Park, and J. Kim, “Networked SSD: Flash Memory Interconnection Network for High-Bandwidth SSD,” in _MICRO_. IEEE, 2022.
  * [64] N. LaPierre, M. Alser, E. Eskin, D. Koslicki, and S. Mangul, “Metalign: Efficient Alignment-based Metagenomic Profiling Via Containment Min Hash,” _Genome Biology_ , 2020.
  * [65] Samsung, “Samsung SSD PM1735,” https://www.samsung.com/semiconductor/ssd/enterprise-ssd/MZPLJ3T2HBJR-00007/, 2020\.
  * [66] Samsung, “Samsung SSD 870 EVO,” https://www.samsung.com/semiconductor/minisite/ssd/product/consumer/870evo/, 2021\.
  * [67] A. Holdings, “Cortex-R4,” https://developer.arm.com/ip-products/processors/cortex-r/cortex-r4, 2011\.
  * [68] Samsung, “Samsung SSD 860 PRO,” https://www.samsung.com/semiconductor/minisite/ssd/product/consumer/860pro/, 2018\.
  * [69] T. Lemane, P. Medvedev, R. Chikhi, and P. Peterlongo, “kmtricks: efficient and flexible construction of Bloom filters for large sequencing data collections,” _Bioinformatics Advances_ , vol. 2, no. 1, 04 2022.
  * [70] J. Lu, F. P. Breitwieser, P. Thielen, and S. L. Salzberg, “Bracken: Estimating Species Abundance in Metagenomics Data,” _PeerJ Computer Science_ , 2017.
  * [71] Z. Sun, S. Huang, M. Zhang, Q. Zhu, N. Haiminen, A. P. Carrieri, Y. Vázquez-Baeza, L. Parida, H.-C. Kim, R. Knight, and Y.-Y. Liu, “Challenges in benchmarking metagenomic profilers,” _Nature Methods_ , vol. 18, no. 6, pp. 618–626, Jun 2021.
  * [72] E. A. Dimopoulos, A. Carmagnini, I. M. Velsko, C. Warinner, G. Larson, L. A. F. Frantz, and E. K. Irving-Pease, “Haystac: A bayesian framework for robust and rapid species identification in high-throughput sequencing data,” _PLOS Computational Biology_ , vol. 18, no. 9, pp. 1–30, 09 2022.
  * [73] R. C. Edgar, J. Taylor, V. Lin, T. Altman, P. Barbera, D. Meleshko, D. Lohr, G. Novakovsky, B. Buchfink, B. Al-Shayeb, J. F. Banfield, M. de la Peña, A. Korobeynikov, R. Chikhi, and A. Babaian, “Petabase-scale sequence alignment catalyses viral discovery,” _Nature_ , vol. 602, no. 7895, pp. 142–147, 02 2022. [Online]. Available: https://doi.org/10.1038/s41586-021-04332-2
  * [74] M. Sereika, R. H. Kirkegaard, S. M. Karst, T. Y. Michaelsen, E. A. Sørensen, R. D. Wollenberg, and M. Albertsen, “Oxford nanopore r10.4 long-read sequencing enables the generation of near-finished bacterial genomes from pure cultures and metagenomes without short-read or reference polishing,” _Nature Methods_ , vol. 19, no. 7, pp. 823–826, 07 2022. [Online]. Available: https://doi.org/10.1038/s41592-022-01539-7
  * [75] Illumina, “NovaSeq X Series Specifications,” https://emea.illumina.com/systems/sequencing-platforms/novaseq-x-plus/specifications.html, 2023\.
  * [76] O. N. Technologies, “PromethION,” https://nanoporetech.com/products/promethion, 2023.
  * [77] S. Shokralla, T. M. Porter, J. F. Gibson, R. Dobosz, D. H. Janzen, W. Hallwachs, G. B. Golding, and M. Hajibabaei, “Massively parallel multiplex dna sequencing for specimen identification using an illumina miseq platform,” _Scientific Reports_ , vol. 5, no. 1, p. 9687, 04 2015. [Online]. Available: https://doi.org/10.1038/srep09687
  * [78] Illumina, “NovaSeq 6000 System Specifications,” https://emea.illumina.com/systems/sequencing-platforms/novaseq/specifications.html, 2020\.
  * [79] A. Pomerantz, N. Peñafiel, A. Arteaga, L. Bustamante, F. Pichardo, L. A. Coloma, C. L. Barrio-Amorós, D. Salazar-Valenzuela, and S. Prost, “Real-time DNA Barcoding in a Rainforest Using Nanopore Sequencing: Opportunities for Rapid Biodiversity Assessments and Local Capacity Building,” _GigaScience_ , 2018.
  * [80] D. E. Wood and S. L. Salzberg, “Kraken: ultrafast metagenomic sequence classification using exact alignments,” _Genome biology_ , vol. 15, no. 3, pp. 1–12, 2014.
  * [81] F. Meyer, A. Fritz, Z.-L. Deng, D. Koslicki, T. R. Lesker, A. Gurevich, G. Robertson, M. Alser, D. Antipov, F. Beghini, D. Bertrand, J. J. Brito, C. T. Brown, J. Buchmann, A. Buluç, B. Chen, R. Chikhi, P. T. L. C. Clausen, A. Cristian, P. W. Dabrowski, A. E. Darling, R. Egan, E. Eskin, E. Georganas, E. Goltsman, M. A. Gray, L. H. Hansen, S. Hofmeyr, P. Huang, L. Irber, H. Jia, T. S. Jørgensen, S. D. Kieser, T. Klemetsen, A. Kola, M. Kolmogorov, A. Korobeynikov, J. Kwan, N. LaPierre, C. Lemaitre, C. Li, A. Limasset, F. Malcher-Miranda, S. Mangul, V. R. Marcelino, C. Marchet, P. Marijon, D. Meleshko, D. R. Mende, A. Milanese, N. Nagarajan, J. Nissen, S. Nurk, L. Oliker, L. Paoli, P. Peterlongo, V. C. Piro, J. S. Porter, S. Rasmussen, E. R. Rees, K. Reinert, B. Renard, E. M. Robertsen, G. L. Rosen, H.-J. Ruscheweyh, V. Sarwal, N. Segata, E. Seiler, L. Shi, F. Sun, S. Sunagawa, S. J. Sørensen, A. Thomas, C. Tong, M. Trajkovski, J. Tremblay, G. Uritskiy, R. Vicedomini, Z. Wang, Z. Wang, Z. Wang, A. Warren, N. P. Willassen, K. Yelick, R. You, G. Zeller, Z. Zhao, S. Zhu, J. Zhu, R. Garrido-Oter, P. Gastmeier, S. Hacquard, S. Häußler, A. Khaledi, F. Maechler, F. Mesny, S. Radutoiu, P. Schulze-Lefert, N. Smit, T. Strowig, A. Bremges, A. Sczyrba, and A. C. McHardy, “Critical assessment of metagenome interpretation: the second round of challenges,” _Nature Methods_ , vol. 19, no. 4, pp. 429–440, Apr 2022.
  * [82] E. W. Sayers, R. Agarwala, E. E. Bolton, J. Brister, K. Canese, K. Clark, R. Connor, N. Fiorini, K. Funk, T. Hefferon, J. Holmes, S. Kim, A. Kimchi, P. A. Kitts, S. Lathrop, Z. Lu, T. L. Madden, A. Marchler-Bauer, L. Phan, V. A. Schneider, C. L. Schoch, K. D. Pruitt, and J. Ostell, “Database resources of the National Center for Biotechnology Information,” _Nucleic Acids Research_ , vol. 47, no. D1, pp. D23–D28, 11 2018.
  * [83] AMD, “AMD${}^{\text{\textregistered}}$ EPYC${}^{\text{\textregistered}}$ 7742 CPU,” https://www.amd.com/en/products/cpu/amd-epyc-7742.
  * [84] Serial ATA International Organization, “SATA revision 3.0 specifications,” https://www.sata-io.org.
  * [85] PCI-SIG, “PCI Express Base Specification Revision 4.0, Version 1.0,” https://pcisig.com/specifications.
  * [86] D. Kim, L. Song, F. P. Breitwieser, and S. L. Salzberg, “Centrifuge,” http://www.ccb.jhu.edu/software/centrifuge/, 2020.
  * [87] Z. Zou, H. Chen, P. Poduval, Y. Kim, M. Imani, E. Sadredini, R. Cammarota, and M. Imani, “Biohd: an efficient genome sequence search platform using hyperdimensional memorization,” in _Proceedings of the 49th Annual International Symposium on Computer Architecture_ , 2022, pp. 656–669.
  * [88] V. S. Mailthody, Z. Qureshi, W. Liang, Z. Feng, S. G. De Gonzalo, Y. Li, H. Franke, J. Xiong, J. Huang, and W.-m. Hwu, “Deepstore: In-storage Acceleration for Intelligent Queries,” in _MICRO_ , 2019.
  * [89] S. Kang, J. An, J. Kim, and S.-W. Jun, “Mithrilog: Near-storage accelerator for high-performance log analytics,” in _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2021, pp. 434–448.
  * [90] G. Koo, K. K. Matam, I. Te, H. K. G. Narra, J. Li, H.-W. Tseng, S. Swanson, and M. Annavaram, “Summarizer: Trading Communication with Computing Near Storage,” in _MICRO_ , 2017.
  * [91] N. Mansouri Ghiasi, J. Park, H. Mustafa, J. Kim, A. Olgun, A. Gollwitzer, D. Senol Cali, C. Firtina, H. Mao, N. Almadhoun Alserr, R. Ausavarungnirun, N. Vijaykumar, M. Alser, and O. Mutlu, “Genstore: A high-performance in-storage processing system for genome sequence analysis,” in _Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 635–654.
  * [92] D. T. Truong, E. A. Franzosa, T. L. Tickle, M. Scholz, G. Weingart, E. Pasolli, A. Tett, C. Huttenhower, and N. Segata, “MetaPhlAn2 for Enhanced Metagenomic Taxonomic Profiling,” _Nature Methods_ , 2015.
  * [93] M. Kokot, M. Długosz, and S. Deorowicz, “KMC 3: counting and manipulating k-mer statistics,” _Bioinformatics_ , vol. 33, no. 17, pp. 2759–2761, 05 2017.
  * [94] G. Benoit, P. Peterlongo, M. Mariadassou, E. Drezen, S. Schbath, D. Lavenier, and C. Lemaitre, “Multiple comparative metagenomics using multiset k-mer counting,” _PeerJ Computer Science_ , vol. 2, p. e94, 2016.
  * [95] R. Bovee and N. Greenfield, “Finch: a tool adding dynamic abundance filtering to genomic minhashing,” _The Journal of Open Source Software_ , vol. 3, no. 22, p. 505, 2018.
  * [96] C. Zou and A. A. Chien, “Assasin: Architecture support for stream computing to accelerate computational storage,” in _2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2022, pp. 354–368.
  * [97] Samsung, “Samsung SSD 980 PRO,” https://www.samsung.com/semiconductor/minisite/ssd/product/consumer/980pro/, 2020\.
  * [98] M. T. Inc., “4Gb: x4, x8, x16 DDR4 SDRAM Data Sheet,” 2016.
  * [99] S. Liu and D. Koslicki, “CMash: fast, multi-resolution estimation of k-mer-based Jaccard and containment indices,” _Bioinformatics_ , vol. 38, no. Supplement_1, pp. i28–i35, 06 2022.
  * [100] C. Marchet, C. Boucher, S. J. Puglisi, P. Medvedev, M. Salson, and R. Chikhi, “Data structures based on k-mers for querying large collections of sequencing data sets,” _Genome Research_ , vol. 31, no. 1, pp. 1–12, 2021\.
  * [101] D. Koslicki and D. Falush, “Metapalette: a k-mer painting approach for metagenomic taxonomic profiling and quantification of novel strain variation,” _mSystems_ , vol. 1, no. 3, pp. e00 020–16, 2016.
  * [102] S. Weging, A. Gogol-Döring, and I. Grosse, “Taxonomic analysis of metagenomic data with kASA,” _Nucleic Acids Research_ , vol. 49, no. 12, pp. e68–e68, 03 2021.
  * [103] A. Kawaguchi, S. Nishioka, and H. Motoda, “A flash-memory based file system.” in _USENIX ATC_ , 1995.
  * [104] Y. Cai, Y. Luo, S. Ghose, and O. Mutlu, “Read Disturb Errors in MLC NAND Flash Memory: Characterization, Mitigation, and Recovery,” in _IEEE/IFIP DSN_ , 2015.
  * [105] Y. Cai, S. Ghose, Y. Luo, K. Mai, O. Mutlu, and E. F. Haratsch, “Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques,” in _HPCA_ , 2017.
  * [106] Y. Luo, S. Ghose, Y. Cai, E. F. Haratsch, and O. Mutlu, “Improving 3D NAND Flash Memory Lifetime by Tolerating Early Retention Loss and Process Variation,” _ACM POMACS_ , 2018.
  * [107] Y. Luo, S. Ghose, Y. Cai, E. F. Haratsch, and O. Mutlu, “HeatWatch: Improving 3D NAND Flash Memory Device Reliability by Exploiting Self-recovery and Temperature Awareness,” in _HPCA_ , 2018.
  * [108] Y. Cai, G. Yalcin, O. Mutlu, E. F. Haratsch, A. Crista, O. S. Unsal, and K. Mai, “Error Analysis and Management for MLC NAND Flash Memory.” _Intel Technology_ , 2013.
  * [109] Y. Cai, G. Yalcin, O. Mutlu, E. F. Haratsch, A. Cristal, O. S. Unsal, and K. Mai, “Flash Correct-and-refresh: Retention-aware Error Management for Increased Flash Memory lifetime,” in _ICCD_ , 2012.
  * [110] Y. Cai, S. Ghose, E. F. Haratsch, Y. Luo, and O. Mutlu, “Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-state Drives,” in _Proc. IEEE_ , 2017.
  * [111] K. Ha, J. Jeong, and J. Kim, “An Integrated Approach for Managing Read Disturbs in High-density NAND Flash Memory,” _IEEE TCAD_ , 2015.
  * [112] Y. Cai, S. Ghose, E. F. Haratsch, Y. Luo, and O. Mutlu, “Reliability Issues in Flash-memory-based Solid-state Drives: Experimental Analysis, Mitigation, Recovery,” in _Inside Solid State Drives_. Springer, 2018.
  * [113] Y. Luo, Y. Cai, S. Ghose, J. Choi, and O. Mutlu, “WARM: Improving NAND Flash Memory Lifetime with Write-Hotness Aware Retention Management,” in _MSST_ , 2015.
  * [114] Micron, “Product Flyer: Micron 3D NAND Flash Memory,” https://www.micron.com/-/media/client/global/documents/products/product-flyer/3d_nand_flyer.pdf?la=en, 2016\.
  * [115] Synopsys, Inc., “Design Compiler,” https://www.synopsys.com/implementation-and-signoff/rtl-synthesis-test/design-compiler-graphical.html.
  * [116] United Microelectronics Corporation, “UMK65LSCLLMVBBL_A - UMC 65 nm Low-K 1.2V/1.0V Low Leakage LVT Tapless Standard Cell Library, version A02,” 2008\.
  * [117] Y. Kim, W. Yang, and O. Mutlu, “Ramulator: A Fast and Extensible DRAM Simulator,” _CAL_ , 2015.
  * [118] Y. Kim, W. Yang, and O. Mutlu, “Ramulator Source Code,” https://github.com/CMU-SAFARI/ramulator.
  * [119] A. Tavakkol, J. Gómez-Luna, M. Sadrosadati, S. Ghose, and O. Mutlu, “MQSim: A Framework for Enabling Realistic Studies of Modern Multi-queue SSD Devices,” in _FAST_ , 2018.
  * [120] S. Ghose, T. Li, N. Hajinazar, D. S. Cali, and O. Mutlu, “Demystifying Complex Workload-DRAM Interactions: An Experimental Study,” _ACM POMACS_ , 2019.
  * [121] Advanced Micro Devices, “AMD® $\mu$Prof,” https://developer.amd.com/amd-uprof/, 2021.
  * [122] A. Nag, C. Ramachandra, R. Balasubramonian, R. Stutsman, E. Giacomin, H. Kambalasubramanyam, and P.-E. Gaillardon, “GenCache: Leveraging In-cache Operators for Efficient Sequence Alignment,” in _MICRO_ , 2019.
  * [123] A. Sczyrba, P. Hofmann, P. Belmann, D. Koslicki, S. Janssen, J. Dröge, I. Gregor, S. Majda, J. Fiedler, E. Dahms, A. Bremges, A. Fritz, R. Garrido-Oter, T. S. Jørgensen, N. Shapiro, P. D. Blood, A. Gurevich, Y. Bai, D. Turaev, M. Z. DeMaere, R. Chikhi, N. Nagarajan, C. Quince, F. Meyer, M. Balvočiūtė, L. H. Hansen, S. J. Sørensen, B. K. H. Chia, B. Denis, J. L. Froula, Z. Wang, R. Egan, D. Don Kang, J. J. Cook, C. Deltel, M. Beckstette, C. Lemaitre, P. Peterlongo, G. Rizk, D. Lavenier, Y.-W. Wu, S. W. Singer, C. Jain, M. Strous, H. Klingenberg, P. Meinicke, M. D. Barton, T. Lingner, H.-H. Lin, Y.-C. Liao, G. G. Z. Silva, D. A. Cuevas, R. A. Edwards, S. Saha, V. C. Piro, B. Y. Renard, M. Pop, H.-P. Klenk, M. Göker, N. C. Kyrpides, T. Woyke, J. A. Vorholt, P. Schulze-Lefert, E. M. Rubin, A. E. Darling, T. Rattei, and A. C. McHardy, “Critical Assessment of Metagenome Interpretation—A Benchmark of Metagenomics Software,” _Nature Methods_ , 2017.
  * [124] D. Senol Cali, J. S. Kim, S. Ghose, C. Alkan, and O. Mutlu, “Nanopore Sequencing Technology and Tools for Genome Assembly: Computational Analysis of the Current State, Bottlenecks and Future Directions,” _Briefings in Bioinformatics_ , 2018.
  * [125] W. Qiao, L. Guo, Z. Fang, M.-C. F. Chang, and J. Cong, “Topsort: A high-performance two-phase sorting accelerator optimized on hbm-based fpgas,” in _2022 IEEE 30th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2022, pp. 1–1.
  * [126] A. Stillmaker and B. Baas, “Scaling Equations for the Accurate Prediction of CMOS Device Performance from 180 Nm to 7 Nm,” _Integration_ , 2017.
  * [127] A. Saavedra, H. Lehnert, C. Hernández, G. Carvajal, and M. Figueroa, “Mining discriminative k-mers in dna sequences using sketches and hardware acceleration,” _IEEE Access_ , vol. 8, pp. 114 715–114 732, 2020.
  * [128] S. Liang, Y. Wang, Y. Lu, Z. Yang, H. Li, and X. Li, “Cognitive ssd: A deep learning engine for in-storage data retrieval.” in _USENIX Annual Technical Conference_ , 2019, pp. 395–410.
  * [129] M. Kim and S. Lee, “Reducing tail latency of dnn-based recommender systems using in-storage processing,” in _Proceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems_ , 2020, pp. 90–97.
  * [130] M. Lim, J. Jung, and D. Shin, “Lsm-tree compaction acceleration using in-storage processing,” in _2021 IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia)_. IEEE, 2021, pp. 1–3.
  * [131] C. Li, Y. Wang, C. Liu, S. Liang, H. Li, and X. Li, “Glist: Towards in-storage graph learning.” in _USENIX Annual Technical Conference_ , 2021, pp. 225–238.
  * [132] J. Wang, D. Park, Y.-S. Kee, Y. Papakonstantinou, and S. Swanson, “Ssd in-storage computing for list intersection,” in _Proceedings of the 12th International Workshop on Data Management on New Hardware_ , 2016, pp. 1–7.
  * [133] S.-T. Lee and J.-H. Lee, “Neuromorphic computing using nand flash memory architecture with pulse width modulation scheme,” _Frontiers in Neuroscience_ , vol. 14, p. 571292, 2020.
  * [134] M. Kang, H. Kim, H. Shin, J. Sim, K. Kim, and L.-S. Kim, “S-flash: A nand flash-based deep neural network accelerator exploiting bit-level sparsity,” _IEEE Transactions on Computers_ , vol. 71, no. 6, pp. 1291–1304, 2021.
  * [135] R. Han, Y. Xiang, P. Huang, Y. Shan, X. Liu, and J. Kang, “Flash memory array for efficient implementation of deep neural networks,” _Advanced Intelligent Systems_ , vol. 3, no. 5, p. 2000161, 2021.
  * [136] S. Wang, “Memcore: Computing-in-flash design for deep neural network acceleration,” in _2022 6th IEEE Electron Devices Technology & Manufacturing Conference (EDTM)_. IEEE, 2022, pp. 402–402.
  * [137] P. Wang, F. Xu, B. Wang, B. Gao, H. Wu, H. Qian, and S. Yu, “Three-dimensional nand flash for vector–matrix multiplication,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 27, no. 4, pp. 988–991, 2018\.
  * [138] R. Han, P. Huang, Y. Xiang, C. Liu, Z. Dong, Z. Su, Y. Liu, L. Liu, X. Liu, and J. Kang, “A novel convolution computing paradigm based on nor flash array with high computing speed and energy efficiency,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 66, no. 5, pp. 1692–1703, 2019\.
  * [139] W. H. Choi, P.-F. Chiu, W. Ma, G. Hemink, T. T. Hoang, M. Lueker-Boden, and Z. Bandic, “An in-flash binary neural network accelerator with slc nand flash array,” in _2020 IEEE International Symposium on Circuits and Systems (ISCAS)_. IEEE, 2020, pp. 1–5.
  * [140] S. Pei, J. Yang, and Q. Yang, “REGISTOR: A Platform for Unstructured Data Processing inside SSD Storage,” _ACM TOS_ , 2019.
  * [141] S.-W. Jun, A. Wright, S. Zhang, S. Xu, and Arvind, “GraFBoost: Using Accelerated Flash Storage for External Graph Analytics,” in _ISCA_ , 2018\.
  * [142] J. Do, Y.-S. Kee, J. M. Patel, C. Park, K. Park, and D. J. DeWitt, “Query Processing on Smart SSDs: Opportunities and Challenges,” in _ACM SIGMOD_ , 2013.
  * [143] S. Seshadri, M. Gahagan, S. Bhaskaran, T. Bunker, A. De, Y. Jin, Y. Liu, and S. Swanson, “Willow: A User-Programmable SSD,” in _USENIX OSDI_ , 2014\.
  * [144] S. Kim, H. Oh, C. Park, S. Cho, S.-W. Lee, and B. Moon, “In-storage Processing of Database Scans and Joins,” _Information Sciences_ , 2016.
  * [145] E. Riedel, C. Faloutsos, G. A. Gibson, and D. Nagle, “Active Disks for Large-Scale Data Processing,” _Computer_ , 2001.
  * [146] E. Riedel, G. Gibson, and C. Faloutsos, “Active Storage for Large-Scale Data Mining and Multimedia Applications,” _VLDB_ , 1998.
  * [147] Y. Lee, J. Chung, and M. Rhu, “Smartsage: training large-scale graph neural networks using in-storage processing architectures,” in _Proceedings of the 49th Annual International Symposium on Computer Architecture_ , 2022, pp. 932–945.
  * [148] W. S. Jeong, C. Lee, K. Kim, M. K. Yoon, W. Jeon, M. Jung, and W. W. Ro, “REACT: Scalable and High-performance Regular Expression Pattern Matching Accelerator for In-storage Processing,” _IEEE TPDS_ , 2019.
  * [149] S.-W. Jun, H. T. Nguyen, V. Gadepally, and Arvind, “In-storage Embedded Accelerator for Sparse Pattern Processing,” in _HPEC_ , 2016.
  * [150] S. Li, F. Tu, L. Liu, J. Lin, Z. Wang, Y. Kang, Y. Ding, and Y. Xie, “Ecssd: Hardware/data layout co-designed in-storage-computing architecture for extreme classification,” in _Proceedings of the 50th Annual International Symposium on Computer Architecture_ , 2023, pp. 1–14.
  * [151] S. Liang, Y. Wang, C. Liu, H. Li, and X. Li, “Ins-dla: An in-ssd deep learning accelerator for near-data processing,” in _2019 29th International Conference on Field Programmable Logic and Applications (FPL)_. IEEE, 2019, pp. 173–179.
  * [152] B. Gu, A. S. Yoon, D.-H. Bae, I. Jo, J. Lee, J. Yoon, J.-U. Kang, M. Kwon, C. Yoon, S. Cho, J. Jeong, and D. Chang, “Biscuit: A Framework for Near-data Processing of Big Data Workloads,” _ISCA_ , 2016.
  * [153] Y. Kang, Y.-s. Kee, E. L. Miller, and C. Park, “Enabling Cost-effective Data Processing with Smart SSD,” in _MSST_ , 2013.
  * [154] X. Wang, Y. Yuan, Y. Zhou, C. C. Coats, and J. Huang, “Project Almanac: A Time-traveling Solid-state Drive,” in _EuroSys_ , 2019.
  * [155] A. Acharya, M. Uysal, and J. Saltz, “Active Disks: Programming Model, Algorithms and Evaluation,” _ASPLOS_ , 1998.
  * [156] K. Keeton, D. A. Patterson, and J. M. Hellerstein, “A Case for Intelligent Disks (IDISKs),” _SIGMOD Record_ , 1998.
  * [157] F. Merrikh-Bayat, X. Guo, M. Klachko, M. Prezioso, K. K. Likharev, and D. B. Strukov, “High-performance mixed-signal neurocomputing with nanoscale floating-gate memory cell arrays,” _IEEE transactions on neural networks and learning systems_ , vol. 29, no. 10, pp. 4782–4790, 2017.
  * [158] D. Tiwari, S. Boboila, S. Vazhkudai, Y. Kim, X. Ma, P. Desnoyers, and Y. Solihin, “Active flash: Towards energy-efficient, in-situ data analytics on extreme-scale machines,” in _Presented as part of the 11th $\\{$USENIX$\\}$ Conference on File and Storage Technologies ($\\{$FAST$\\}$ 13)_, 2013, pp. 119–132.
  * [159] D. Tiwari, S. S. Vazhkudai, Y. Kim, X. Ma, S. Boboila, and P. J. Desnoyers, “Reducing data movement costs using energy-efficient, active computation on $\\{$SSD$\\}$,” in _Presented as part of the 2012 Workshop on Power-Aware Computing and Systems_ , 2012.
  * [160] S. Boboila, Y. Kim, S. S. Vazhkudai, P. Desnoyers, and G. M. Shipman, “Active flash: Out-of-core data analytics on flash storage,” in _2012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST)_. IEEE, 2012, pp. 1–12.
  * [161] D.-H. Bae, J.-H. Kim, S.-W. Kim, H. Oh, and C. Park, “Intelligent ssd: a turbo for big data mining,” in _Proceedings of the 22nd ACM international conference on Information & Knowledge Management_, 2013, pp. 1573–1576.
  * [162] M. Torabzadehkashi, S. Rezaei, V. Alves, and N. Bagherzadeh, “Compstor: An in-storage computation platform for scalable distributed processing,” in _2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_. IEEE, 2018, pp. 1260–1267.
  * [163] L. Kang, Y. Xue, W. Jia, X. Wang, J. Kim, C. Youn, M. J. Kang, H. J. Lim, B. Jacob, and J. Huang, “Iceclave: A trusted execution environment for in-storage computing,” in _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2021, pp. 199–211.
  * [164] C. Gao, X. Xin, Y. Lu, Y. Zhang, J. Yang, and J. Shu, “Parabit: processing parallel bitwise operations in nand flash memory based ssds,” in _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2021, pp. 59–70.
  * [165] J. Park, R. Azizi, G. F. Oliveira, M. Sadrosadati, R. Nadig, D. Novo, J. Gómez-Luna, M. Kim, and O. Mutlu, “Flash-cosmos: In-flash bulk bitwise operations using inherent computation capability of nand flash memory,” in _2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2022, pp. 937–955.
  * [166] S.-W. Jun, M. Liu, S. Lee, J. Hicks, J. Ankcorn, M. King, S. Xu, and Arvind, “Bluedbm: An Appliance for Big Data Analytics,” in _ISCA_ , 2015.
  * [167] S.-W. Jun, M. Liu, S. Lee, J. Hicks, J. Ankcorn, M. King, and S. Xu, “Bluedbm: Distributed Flash Storage for Big Data Analytics,” _ACM TOCS_ , 2016.
  * [168] M. Torabzadehkashi, S. Rezaei, A. Heydarigorji, H. Bobarshad, V. Alves, and N. Bagherzadeh, “Catalina: In-storage Processing Acceleration for Scalable Big Data Analytics,” in _Euromicro PDP_ , 2019.
  * [169] J. H. Lee, H. Zhang, V. Lagrange, P. Krishnamoorthy, X. Zhao, and Y. S. Ki, “SmartSSD: FPGA Accelerated Near-Storage Data Analytics on SSD,” _IEEE Computer Architecture Letters_ , 2020.
  * [170] M. Ajdari, P. Park, J. Kim, D. Kwon, and J. Kim, “CIDR: A Cost-effective In-line Data Reduction System for Terabit-per-second Scale SSD Arrays,” in _HPCA_ , 2019.
  * [171] B. Y. Cho, W. S. Jeong, D. Oh, and W. W. Ro, “Xsd: Accelerating Mapreduce by Harnessing the GPU inside an SSD,” in _Near-Data Processing_ , 2013.