# X-TIME: An in-memory engine for accelerating machine learning on tabular
data with CAMs

Giacomo Pedretti12, John Moon1, Pedro Bruel1, Sergey Serebryakov1, Ron M.
Roth1, Luca Buonanno1,
Tobias Ziegler1, Cong Xu1, Martin Foltin1, Paolo Faraboschi1, Jim Ignowski1,
and Catherine E. Graves1  1Artificial Intelligence Research Lab (AIRL),
Hewlett Packard Labs, Milpitas (CA)
<EMAIL_ADDRESS>
###### Abstract

Structured, or tabular, data is the most common format in data science. While
deep learning models have proven formidable in learning from unstructured data
such as images or speech, they are less accurate than simpler approaches when
learning from tabular data. In contrast, modern tree-based Machine Learning
(ML) models shine in extracting relevant information from structured data. An
essential requirement in data science is to reduce model inference latency in
cases where, for example, models are used in a closed loop with simulation to
accelerate scientific discovery. However, the hardware acceleration community
has mostly focused on deep neural networks and largely ignored other forms of
machine learning. Previous work has described the use of an analog content
addressable memory (CAM) component for efficiently mapping random forests. In
this work, we focus on an overall analog-digital architecture implementing a
novel increased precision analog CAM and a programmable network on chip
allowing the inference of state-of-the-art tree-based ML models, such as
XGBoost and CatBoost. Results evaluated in a single chip at 16nm technology
show 119$\times$ lower latency at 9740$\times$ higher throughput compared with
a state-of-the-art GPU, with a 19W peak power consumption.

##  I Introduction

Extracting relevant information from structured (i.e., tabular) data is of
utmost importance in practical data science. Tabular data consist of a matrix
of samples organized in rows, each of which has the same set of features in
its columns, and is commonly used for medical, financial, scientific, and
networking applications, enabling efficient search operations on large-scale
datasets. While deep learning has shown impressive improvements in accuracy
for unstructured data, such as image recognition or machine translation, tree-
based machine learning (ML) models still outperform neural networks in
classification and regression tasks on tabular data [13, 60, 21]. This
difference in model accuracy is due to robustness to uninformative features of
tree-based models, bias towards a smooth solution of neural networks models,
and in general the need for rotation invariant models where the data is
rotation invariant itself, as in the case of tabular data [21]. With high
model accuracy and ease of use, tree-based ML models are greatly preferred by
the data science community [7], with $>74\%$ of data scientists preferring to
use these models while $<40\%$ choose neural networks in a recent survey.
However, tree-based models have garnered little attention in the architecture
and custom accelerator research fields, particularly compared to deep
learning. While small models are easily executed, performance issues for
larger tree-based ML models arise due to limited inference latency both on CPU
and GPUs [67, 26] originating from irregular memory accesses and thread
synchronization issues. Recent work attempted to address this limitation by
improving GPU memory organization with compiler optimizations [5, 4] and
model-tailored strategies for inference [67], with limited success. As large
tree-based models are finding performance limits in existing hardware, larger
models ($>$1M nodes) are demonstrating increasingly compelling uses in
practical environments where high throughput and moderate latency are desired
[3, 1]. For example, the winner of a recent IEEE-CIS Fraud detection
competition used a tree-based ML model with 20M nodes [1]. Moreover, reducing
inference latency is critical in scientific applications where for use in
real-time processing, model latency must be $\sim$100 ns [61]. Similar low
latency requirements for model inference arise in a real-time in-the-loop
decision, data filtering systems, or streaming data scenarios, which are
common across financial, medical and cybersecurity domains [17, 1] where
tabular data and tree-based ML also dominate. Thus, these models are reaching
sizes and complexity levels for meaningful real-world tasks, as they are
hitting limits on inference latency and throughput in current systems.
Recently, several custom accelerators for tree-based ML inference have been
developed based either on FPGA [61, 17] or custom ASICs [64, 26]. A common
architecture in most of the accelerators mentioned above implements look-up
tables (LUTs) storing the attributes of a decision tree (DT) which is accessed
multiple times during inference, with reads based on decision paths taken
during the tree traversal. Along with low latency inference, an efficient
hardware representation of trees is necessary to implement the required very
large models.

One promising new architectural approach for improving tree-based model
inference is in-memory, or in situ[58, 16], computing, where data are stored
and processed in the same location. This approach eliminates access, transfer,
and processing of data in a separate compute unit [31, 71], limiting memory
accesses and reducing latency. In this work, we propose to leverage analog
arrays of resistive memory devices, also called RRAM or memristors, in an in-
memory architecture to accelerate tree-based models. Previous research has
shown that these devices can efficiently perform multiplication and other
matrix algebraic functions in crossbar architectures [27, 58, 62, 14, 16].
However, crossbar architectures are limited to matrix operations, which are
not useful for inference on tree-based models. Another class of in-memory
computing primitives is Content Addressable Memories (CAMs) [48, 19], high-
speed and highly-parallel circuits that search for a given input in a table of
stored words and return the matched search input’s location. Conventional CAMs
use SRAM, resulting in a large bit-cell unit (12-16 transistors) to perform
fast lookups of input data. A variety of computing tasks have been
demonstrated with lower power resistive-memory-based CAMs, such as associative
computing [22, 23, 69] and finite state automata [18, 29]. More recently,
analog CAMs have been proposed [39] which leverage the analog states in
memristor devices. An analog CAM cell performs in situ comparisons of stored
(analog) ranges with (analog) inputs, by computing if the input is within the
range. Effectively, analog CAM arrays perform a massively parallel comparison
between an input vector of analog values and stored words of analog ranges.
Given that DTs are a set of conditional branches, analog CAMs naturally map
DTs and perform highly parallel inference of decision forests [51]. Previous
work showed the potential of this approach but was limited to component level
estimation, to 4-bit precision, and random forest models [51].

This work presents X-TIME, an in-memory engine for accelerating tree-based ML
models with analog CAMs. The major contributions of this paper compared to
previous work [51] are (1) a novel analog CAM cell design and operation to
perform decision tree inference at doubled (i.e. 8-bit) memristor precision
(i.e. 4-bit), (2) an in-core leaves accumulation architecture to seamlessly
perform inference of a large number of trees in parallel and (3) a
programmable network on chip to operate any tree-based ML model regardless of
the ensemble reduction operation.

The paper is organized as follows: first, we present a general architecture
overview, followed by a detailed description of the main components. We then
present performance results with trained state-of-the-art models on a
benchmark of tabular datasets, comparing our architecture to GPU inference
with state-of-the-art libraries and recently proposed accelerators. Our
simulated evaluation shows up to 119$\times$ increased throughput at
9740$\times$ decreased latency in a single 19W chip. Intuitively, the drastic
performance improvement originates from the highly parallel CAM hardware,
which performs both parallel memory lookup and threshold comparison in-memory
simultaneously for all trees.

##  II Background

Figure 1: Schematic illustration of (a) a decision tree and (b) a decision
tree ensemble.

###  II-A Tree-based Machine Learning

A DT is a regression and classification machine learning model consisting of a
set of nodes arranged in a tree-like structure. Each node can have multiple
children nodes, but the most common case is a binary tree, where each node has
only two children. The first node is usually called the root. Each node $j$
consists of a conditional branch where in the a single input feature element
$f_{i}$ is compared with a trainable threshold $T_{j}$. The exception to this
is the last node, or leaf, which stores the model’s prediction for a given
input, and which can be a class (classification) or a scalar value
(regression). A balanced tree can be defined by its depth $D$, which is equal
to the maximum number of nodes in a root-to-leaf traversal. Fig. 1(a) shows an
example of a DT with $L=4$ leaves and $D=2$.
Multiple DTs can be trained together as an ensemble for increased accuracy in
classification and regression tasks. Fig. 1(b) shows a conceptual
representation of a DT ensemble, where multiple trees are executed in parallel
and their output combined with a reduction operation yields the model’s final
result. An example of a DT ensemble model is Random Forests (RF) [10], in
which DTs are trained independently and in parallel on different random
subsets of the dataset, and majority voting between leaf values yields the
ensemble’s prediction. Another kind of DT ensemble can be built by Gradient
Boosting (GB) algorithms, in which DTs are trained in series such that the
$i^{th}$ DT is trained to fit the partial residuals left by the $(i-1)^{th}$
DT. During inference, all DTs of a GB group can be run in parallel and the
reduction operation sums the predicted leaf values of each DT. Interest in GB
has grown recently due to new training algorithms such as eXtreme Gradient
Boosting (XGBoost) [15], Light Gradient Boosting Machine (lightgbm) [37], and
Categorical Boosting (CatBoost) [53]. These algorithms have improved ensemble
training with high accuracy.

DTs and their ensembles are widely used in data science and are usually
preferred over deep learning and other more complex models [7] due to several
distinguishing features. First, DT models are easy to train and optimize,
handle missing data very well, and do not require substantial prior domain
knowledge to achieve good results. Second, these models are significantly more
explainable and interpretable when compared to neural networks, as
backtracking operations to determine why an input was placed in a given class
[45] are straightforward and low complexity. Finally, a dominant reason many
use DT models is a practical one, as GB models outperform state-of-the-art
deep learning models in structured, or tabular, data problems [13, 60, 21], if
trained with very large ensembles, usually with $>1$ M nodes [3, 1].

###  II-B Tree-based ML model inference on GPU

While training DT models is relatively fast when compared to, for example, a
large deep neural network, the computations involved in inference are very
irregular and not particularly suitable for CPUs and GPUs, becoming
inefficient for very large models, with $>1$ M nodes [3, 1]. While CPUs can
run irregular control path fairly well, their parallelism is limited. GPUs
have a very large parallelism, but suffer from the irregularity of memory
access patterns, as will be explained in detail below. Recent NVIDIA libraries
implementations have shown order of magnitude improvements compared to CPU and
previous GPU implementations [5]. However, three different factors still limit
GPU throughput and latency [67], in particular for tree ensembles. First, a
high number of uncoalesced memory accesses, due to the low ratio between
requested and fetched data, causes low memory efficiency. Trees are usually
stored in memory with nodes from different trees interleaved in breadth-first
order, resulting in coalesced memory accesses close to the root, where
children nodes are more likely to be part of the same memory transaction of
the parent node, but uncoalesced memory accesses further from the root. Thus,
with increasing tree depth the proportion of coalesced memory accesses
decreases and memory system efficiency also decreases. Second, synchronization
between threads and the consequent load imbalance due to waiting for the
deepest trees limits latency. A common implementation scheme on GPU assigns
each tree in the ensemble to a different thread by round-robin. At the end of
each thread block, a reduction operation is then performed. However, a given
ensemble may contain short and tall trees, with the latter having
substantially larger latency. Thus, each thread block must wait until the
slowest (tallest) tree has finished processing, increasing overall latency.
Finally, with a larger number of trees $N_{trees}$ in the ensemble, the
increasing number of thread blocks and the global reduction performed between
thread blocks becomes a significant overhead. Multiple techniques have been
proposed to increase the throughput of tree ensemble inference [5, 4, 67],
mainly by re-organizing the memory - for example, for sparse trees and
scheduling of threads - but with limited impact on latency. In this work, we
focus on addressing these limitations with an in-memory computing architecture
using content-addressable memories.

Figure 2: Comparison of (a) a conventional CAM/TCAM and (b) an analog CAM

###  II-C Analog Content Addressable Memory

CAMs are specialized memory devices that search a table of stored words (rows)
or keys in parallel for a given input query. The CAM search output is a one-
hot vector where a high value corresponds to a match between the input data
query and stored row word key [48, 19]. In conventional CAMs, this output
vector is converted into a single address by a priority encoder. Each CAM cell
functions as both storage and bit comparison, and the input query is compared
to each CAM word simultaneously to produce a high throughput, low latency few-
cycle compare operation at the cost of high power and area. In addition to
binary (0 and 1) values, ternary CAMs (TCAMs) have a third wildcard value, X
(or “don’t care”), which can be used to compress the stored CAM table or
perform partial match searches. When an X is stored or searched, that cell
matches irrespective of whether the searched or stored value is 1 or 0. Fig.
2(a) shows a schematic illustration of a conventional CAM/TCAM circuit, where
input queries are applied on the column search lines (SLs) and outputs are
read along the row ”match lines” (MALs). An XNOR operation occurs between the
query values and stored cell values in the corresponding column. The MAL
$j_{th}$ row output is produced by a bit-wise AND operation between cells
along the row and returns a match (high) or mismatch (low). The red boxes in
Fig. 2(a) correspond to mismatches between input and stored value. In
practice, MALs are initially pre-charged high and a mismatch in a cell
activates a pull-down transistor connected to MAL to discharge it, such that a
match is returned only if all pull-down transistors remain off during a search
operation. TCAMs are used ubiquitously in networking applications that require
high-throughput and low-latency operations, for example for packet
classification and forwarding, and access control lists [48, 35]. While
offering high performance, conventional SRAM-TCAMs are power and area hungry
and require 16 transistors. Recently there has been significant interest in
developing TCAMs with memristor devices and resistive non-volatile memories
[22, 23, 44, 20, 40] with compact size and low power operation. As programming
these devices is relatively slow, emerging TCAMs have targeted in-memory
computing applications [31, 28, 19] where stored value updates are infrequent.
Beyond direct digital memory operation, memristor devices have also
demonstrated ranges of stable analog states of $>16$ levels. Leveraging this
analog state capability, recent work proposed and demonstrated an analog CAM
circuit design and operation [39] (conceptual representation in Fig 2(b)). In
an analog CAM, ranges are stored in each cell, an analog input is applied
vertically along columns and a match is returned along rows if the inputs are
all within the stored range of each cell in a row. In the analog CAM circuit,
no analog-to-digital conversion is required, eliminating an expensive circuit
which was a limiting bottleneck of past in-memory computing architectures
based on analog circuits [55]. Multiple analog CAM circuits have since been
realized, based on memristor devices [39, 52] and ferroelectric memory devices
[47, 70]. In such circuits, two analog memory elements represent the lower and
upper bound thresholds. Analog CAMs have been shown to map CAM tables more
efficiently [39], as well as implement novel functions, such as computing
distances for memory-augmented neural networks [47, 36, 40], decision tree
inference [51] and pattern learning [52].

Figure 3: DT example from Fig.1(a) mapped in an analog CAM and RAM pair

###  II-D Mapping tree models to analog CAMs

The X-TIME compiler takes a description of a DT ensemble in a tabular mode
[49], where each row contains the node attributes (feature ID and value) and
the left/right children, traverses the tree structures, extracts all the root-
to-leaf paths and maps each of them to a CAM row, for example, Fig. 3 shows
the mapping of Fig. 1(a). Each column corresponds to a different feature of
the input vector $q$. Each node is mapped in the column corresponding to the
feature used in the node’s comparison, and the comparison’s threshold value is
programmed in the analog CAM’s lower and/or upper bound, according to the
direction, left or right, taken by the comparison’s result for the root-to-
leaf path. A “don’t care” is used if a feature is missing, by programming the
full range (0 to 1 in our example) in the analog CAM cell. The feature vector
(query) is applied on the DL and the output on the MAL is high for the matched
branch, i.e. the traversed root-to-leaf path, in a single CAM operation. This
mapping requires the number of CAM rows to match the number of tree leaves,
and the number of CAM columns to match the number of features $N_{feat}$. MALs
can be connected directly to the WLs of a conventional RAM storing leaf values
to return the model’s prediction. Effectively, the analog CAM traverses root-
to-leaf paths, and the RAM retrieves leaf values. Previous results of this
approach have shown significant speedups for RF inference [51] and reduced
energy consumption compared to both GPU and state-of-art ASICs [34], although
with limited architecture investigation for scaling and no flexibility to
accommodate different datasets or model types. In this work, we present a
complete architecture development and study for handling multiple DT ensemble
algorithms such as RF, XGBoost, and CatBoost, and learning tasks such as
regression, binary classification, and multi-class classification with the
same architecture. In addition, we extend the use of the previously presented
analog CAM [39, 51] circuit to support higher precision data by developing a
flexible connectivity strategy and bit-arithmetic refactoring. We compare the
performance of our architecture on state-of-the-art tabular dataset machine
learning tasks against GPUs, showing a large improvement in latency and
throughput while using a single chip with limited power consumption.

##  III Architecture organization

Figure 4: Architecture hierarchy

Fig. 4 shows the internal architecture of an X-TIME single-chip accelerator.
The accelerator is composed of a group of cores connected by an H-tree
Network-on-Chip (NoC) topology converging to a co-processor (CP). Each core
contains an analog CAM array acting as a processing element (PE-CAM), buffer,
multiple match resolver (MMR), SRAM memory, and accumulator (ACC) (i.e.
feedback adder). Typical CAM architectures also contain similar elements,
except for the ACC, where memory is used as an address encoder [48]. To map
models larger than a single array, each PE-CAM has a number of stacked arrays
(extended row-wise) and queued arrays (extended column-wise) to handle more
and larger words, respectively. Stacked arrays share the same peripherals,
namely the Pre-Charger (P-Ch), the Digital Analog Converter (DAC), the Sense
Amplifier (SA), and the Match-Line Register (ML-REG). The connection of queued
arrays ensures that only previously matched lines are charged by making the
ML-REG of array $i$ feed the P-Ch of the array $i+1$.

###  III-A Inference

X-TIME compiler maps the trained trees to the cores according to Fig. 3 and
ref. [51]. Training is performed using standard libraries such as scikit-
learn[49] or XGBoost[15]. XGBoost outputs a table with $N_{leaves}+N_{nodes}$
(where $N_{leaves}$ is the total number of leaves in the ensemble) rows each
storing the node ID, left and right child ID, node value, node feature, leaf
value (if it is a leaf) and tree ID. Converting this table for CAM usage, we
obtain a table of size $L\times(2N_{feat}+3)$ with each row storing the
lower/upper bound for each feature, the leaf value, class ID/label (in the
case of multi-class classification) and tree ID, representing the model
ensemble for our architecture. The X-TIME compiler assigns trees to cores via
round-robin, directly mapping the first $L\times(2N_{feat})$ columns of a tree
to the lower and upper bound of the analog CAM circuit, and the third-last
column to the SRAM. Class and tree ID are uniquely represented in the core
address. The largest ensemble in our architecture is constrained by the
maximum number of leaves $N_{leaves,max}$ in all trees and the number of
available cores $N_{C}$. If $L<N_{words}/2$, multiple trees can be mapped to a
single core, where $N_{words}=N_{stacked}\times H$ is the number of words
addressable by each core (with $H$ number of rows in an analog CAM array and
$N_{stacked}$ number of arrays stacked).

During inference, a feature vector is sent through the network to a core and
searched in the PE-CAM. Each queued analog CAM block receives a different
portion of the feature vector which is converted into analog voltage values by
a DAC. A shift operation before the conversion is performed for increasing
operation precision (as discussed in section III-B). A logical AND operation
is inherently performed between the queued arrays, similar to MAL segmentation
used in modern TCAMs to maintain high throughput where MALs are divided into
sections of shorter words with an AND between individual MAL results.
Connecting multiple TCAM arrays with common MALs is logically equivalent to a
larger TCAM, with the bit-wise AND operation between TCAM cells on the same
MAL now extended between arrays. In our case, the analog CAM stores a branch
split into multiple analog CAM arrays and reconstructed by means of the
logical AND, such that only if all branch nodes arranged in multiple arrays
are matched will a match be returned on the corresponding MAL.

The final output of the PE-CAM is stored in a buffer and fed into the MMR
which selects only one match signal to proceed logically. The MMR is needed
due to the possibility of mapping multiple trees in a single core. In fact,
given $N_{trees,core}$ mapped to a core, for each inference the PE-CAM would
return $N_{trees,core}$ matches in the form of a sparse Boolean vector with
$N_{trees,core}$ match values (“1”s). The MMR generates $N_{trees,core}$ one-
hot Boolean vectors used for directly accessing the SRAM word lines (WL). The
SRAM stores the corresponding leaf value of each branch, which are retrieved
sequentially and accumulated by the ACC block, which performs a local
reduction operation. After $N_{trees,core}$ accumulations are performed, the
resulting leaf value is sent as output to the router. Leaf values coming from
multiple cores can be summed at the router level as section III-D discusses,
performing a shared reduction operation. Finally, the resulting leaf value is
propagated to the CP which performs a global reduction and computes the model
prediction. The latter is usually a simple operation, such as a majority
voting or a threshold comparison.

###  III-B Analog CAM with improved precision

Figure 5: (a) analog CAM 8-bit macro-cell and (b) analog CAM 4-bit sub-cell
circuit.

Machine learning algorithms usually do not require high-precision floating
point operations for achieving good results [24]. However, as will be detailed
in section IV we found out that typically 8 bits precision, corresponding to
256 bins for each feature, is required for matching floating point (FP)
accuracy inference of tree-based machine learning models.
While analog CAM circuits offer the possibility of mapping arbitrary ranges,
memristor device reliability poses a challenge in supporting more than 16
levels or 4 bits [51]. In the case of crossbar arrays of memristors mapping
algebraic matrices, such as a neural network layer, multiple techniques have
been proposed for overcoming limited device precision, for example by
implementing bit slicing [58] in which with an $M$ levels memristor,
$N=2^{2M}$ bits can be represented by connecting two devices on the same row.
In crossbar arrays, it is also straightforward to arbitrarily adjust the input
precision by applying binary pulses and performing SHIFT and ADD operations at
the output [58].
Unfortunately, such techniques do not apply to analog CAM arrays. The analog
CAM encodes a unary representation and by connecting two analog CAM cells on
the same MAL to represent one macro-cell, it is only possible to double the
number of levels (i.e. $2^{N_{bits}}$) rather than the number of bits. Thus
given memristors with $M=4$ bits, 16 analog CAM cells are needed for
representing $N=8$ bits, leading to an exponential overhead. Here, we propose
a novel solution to increase the precision with the same base analog CAM cell
circuit, which requires 2 analog CAM cells and 2 clock cycles for performing 8
bits search operation with $M=4$ bits memristors.
To demonstrate, let us first take the case where the lower bound threshold
$T_{L}$ is needed to be mapped and operated with $N=8$ bit of precision but we
only have $M=4$ bits of precision in our analog CAM and memristor devices. The
lower bound threshold can be sub-divided into its most significant bit
representation $T_{LMSB}$ and least significant bit representation $T_{LLSB}$,
each one made of $M$ bits, and written as
$T_{L}=2^{M}T_{LMSB}+T_{LLSB}=16T_{LMSB}+T_{LLSB}$. Each analog CAM cell
computes the conditional operation $\textrm{MAL}=q\geq T_{L}$, where $q$ is
the input query applied to the DL. We similarly divide the input $q$ into most
and least significant representations $q_{MSB}$ and $q_{LSB}$, such that
$q=2^{M}q_{MSB}+q_{LSB}=16q_{MSB}+q_{LSB}$ and we can obtain the result of MAL
by computing

$\begin{split}[(q_{MSB}\geq T_{LMSB})\wedge(q_{LSB}\geq T_{LLSB})]\\\
\vee(q_{MSB}\geq T_{LMSB}+1)\end{split}$ (1)

or alternatively, rearranging the terms:

$\begin{split}[(q_{MSB}\geq T_{LMSB}+1)\vee(q_{LSB}\geq T_{LLSB})]\\\
\wedge(q_{MSB}\geq T_{LMSB}).\end{split}$ (2)

Note that Eq. 2 is more CAM-friendly since it is a conjunction of two terms
that can be appended to the same MAL. The same calculation derives the upper
bound $T_{H}$ conditions and with an AND operation between this and equation
(2), the full computation $\textrm{MAL}=T_{L}\leq q<T_{H}$ results in:

$\begin{split}[(q_{MSB}\geq T_{LMSB}+1)\vee(q_{LSB}\geq T_{LLSB})]\\\
\wedge(q_{MSB}\geq T_{LMSB})\\\
\wedge[(q_{MSB}<T_{HMSB})\vee(q_{LSB}<T_{HLSB})]\\\
\wedge(q_{MSB}<T_{HMSB}+1).\end{split}$ (3)

Analog CAMs cells arranged on the same MAL perform a bit-wise AND ($\wedge$)
operation between them, thus a circuit addition is needed for performing the
OR ($\vee$) operation. To do that we realized analog CAM macro-cells as shown
in Fig. 5(a). Each analog CAM macro-cell is made of two sub-cells (Fig. 5(b)),
which are equivalent to the circuit design previously presented [39, 51, 52].
These sub-cells are connected such that the LSB cell has upper MALs (MALloU
and MALhiU) connected to the principal MAL of the row (which is shared among
multiple columns), bottom MALs connected to the upper MALs of the MSB cell,
while the MSB cell has its bottom MALs connected to ground, as shown in the
figure. In this configuration, the macro-cell implements an OR operation with
analog CAM sub-cells. Effectively, the MAL stays charged high for a match if
either the MSB sub-cell or the LSB sub-cell is matched. However, to perform
the operation of equation (3), inputs on the lower and upper thresholds must
be separated, thus each DL is an analog bus of 4 wires. While this could
signal a large overhead, in practice these two lines are already independent
and separated in the original analog CAM circuit to enable programming of the
memristor devices [39].

TABLE I: Input to apply for doubling precision with time shifting Input | Cycle 1 | Cycle 2
---|---|---
$q_{HLSB}$ | $q_{LSB}$ | $GND$
$q_{LLSB}$ | $q_{LSB}$ | $VDD$
$q_{HMSB}$ | $q_{MSB}$ | $q_{MSB}-1$
$q_{LMSB}$ | $q_{MSB}-1$ | $q_{MSB}$

Table I shows the required inputs for each DL analog bus wire to compute
equation (3) in a 2-step search operation. With MAL pre-charged high, the
first cycle evaluates the first bracket of equation (3) for the lower and
upper bound (the OR operation). Without pre-charging MAL again, the second
cycle evaluates the second term of each bound by inputting always care (i.e.
always mismatch) values to the LSB sub-cell. Therefore, an AND operation
between the outputs of cycle 1 and cycle 2 is computed on MAL following cycle
2, similar to a 2-step search approach previously demonstrated for increasing
bit density in TCAMs [44].

To the best of our knowledge, this is an entirely new approach and the
proposed circuit operation is the most compact way of computing equation (3)
with an analog CAM, and thus for doubling the bit precision. While other
circuit designs may implement the same function in one clock cycle, these
would have a significantly larger area. For example, one could separate cells
performing the OR operation by connecting the discharge transistors in series
rather than in parallel. This approach would also allow for selecting the
precision of each feature to be either 4 or 8-bit, depending on the required
precision. However, to perform such an operation in one cycle, three analog
CAM cells with complex routing are needed. Given that analog CAM search
latency is forecast to 100 ps [39], we found that performing two searches
rather than one would not unduly increase the overall latency. Thus, we adopt
this circuit formulation and operation which doubles the bit precision while
doubling the area and analog CAM search latency.

###  III-C Core pipeline

Figure 6: Examples of core tree mapping (top) and pipeline execution (bottom)
of models with $N_{feat}=130$, $D=8$, $N_{trees,core}=1$ (a) and
$N_{feat}=130$, $D=5$, $N_{trees,core}=5$ (b).

In our ML experiments and hyperparameters search (see IV-A for details) we
found out that $N_{leaves}=256$ per tree is typically sufficient to achieve
high accuracy. Given that previous results have shown that analog CAM arrays
with up to 128 rows do not encounter significant technology issues at 16
nm[38], each X-TIME core contains 2 stacked arrays, resulting in $2\times
128=256$ addressable words ($N_{leaves}$). We perform a survey on the size of
typical tabular datasets [60, 21], finding than usually $N_{feat}<100$ and
often feature pre-processing reduces the number of $N_{feat}$ significantly
before applying inputs to the decision tree ensemble. Previous results have
shown that arrays with up to 100 columns have a very small access latency ($<$
1ns) [38]. Nevertheless, we include an outlier dataset with $N_{feat}=130$[65]
to show how to handle larger input vector sizes with input vector
segmentation, as will be described below. Each core contains 2 arrays of 65
columns, resulting in a width of $2\times 65=130$. Overall, each core has a
total addressable analog CAM of macro array size $2\times 128\times 2\times
65=256\times 65$.

The search operation is performed in series by groups of 65 features, while
all the branches mapped to each queued array are computed in parallel.
Multiple trees can be mapped to a single core, by arranging them in different
portions of the analog CAM macro on the vertical axis. To avoid structural
hazards, different considerations are made before applying new inputs to the
core, as will be discussed below. Fig. 6 shows mappings of trees to analog CAM
core assuming a feature vector of length 130. When a feature vector is
searched, a set of components with indices ranging from $0$ to $64$ (INA in
Fig. 6(a)) is sent to the first analog CAM logical array (aCAM1) while a
second set of components with indices from $65$ to $129$ (INB) is sent to the
second array (aCAM2). Comparison sequences on each tree branch are
reconstructed by the AND operations made by aCAM1 and aCAM2 by selectively
pre-charging only aCAM2 rows matched in aCAM1. Each analog CAM array has a
latency of $\lambda_{CAM}=4$ cycles for performing the search operation. One
cycle is used for pre-charging the MAL, two cycles for the search operation
(MSB and LSB), and one cycle for latching the MAL sense amp, which leads to a
total core latency of $\lambda_{C}=12$ cycles, with all other components
(Buffer, MMR, SRAM, ACC) having a single cycle latency.

In the case of up to four trees mapped to the core (e.g. one tree as in Fig.
6(a-top)) when an array finishes the search operation, it starts processing a
new sample, as shown in Fig. 6(a-bottom) and no additional bubbles are
required. The maximum ideal core throughput $\tau_{C}$, considering a clock
frequency of 1GHz [39] and a relatively large number of samples $N_{s}$, can
thus be computed by

$\tau_{C}=\dfrac{N_{s}}{\lambda_{C}+\lambda_{CAM}(N_{s}-1)}\sim
250MSamples/s.$ (4)

If more than 4 trees are mapped in the core (e.g. five trees as in Fig.
6(b-top)), extra pipeline bubbles $N_{B}=N_{trees,core}$ should be inserted.
In fact the MMR needs to performed more than 4 iterations in order to generate
the one-hot vector for accessing the leaves, stored in the SRAM. Fig.
6(b-bottom) shows the core pipeline in this case, which reaches an ideal
throughput of

$\tau_{C}=\dfrac{N_{s}}{\lambda_{C}+N_{B}(N_{s}-1)}\sim 200MSamples/s\\\ $ (5)

To maintain such a high throughput, cores need to be fed with input data fast
enough. On the other hand, the architecture should be able of adapting to
multiple models (such as RF, XGBoost and others, either classification or
regression problems) and exploiting the vast amount of cores for parallel
computations. Thus we designed a programmable NoC able of handling multiple
workloads.

###  III-D Flexible connectivity

We identified four possible examples of inference operation that cover all
ensembles models and tasks previously described, and exploit all the
possibilities of our architecture: (1) regression and binary classification,
(2) multi-class classification, (3) regression and binary classification with
input batching and (4) multi-class classification with input batching.

In the case of regression and binary classification, leaves contain normalized
partial predictions of each tree branch called logits, that are summed over
the ensemble. In each core, the SRAM is programmed with logits that are summed
locally in the core and in each network node inside the router. The final
prediction is then sent to the CP which compares it with a threshold,
typically 0 or 0.5 and sends the final result to the output. In the case of
multiclass classification, logits should be summed class-wise and $N_{class}$
logits should be sent to the CP which performs an argmax computation to select
the predicted class.

Figure 7: Example of network configurations for regression/binary
classification (a), multiclass classification (b) and regression/binary
classification with input batching (c). Schematic representation of X-TIME
programming flow

We propose a flexible/re-configurable NoC design (Fig. 7(a-c)) to aggregate
results based on model type. The inset of Fig. 7(a) shows the downstream
circuit schematic for the custom router. A buffer (size $N_{ports}\times
S_{flit}=4\times 64$) stores incoming leaves and has the output connected to a
de-multiplexer (DEMUX) controlled by a configuration register. The DEMUX sends
each leaf either to the accumulator circuit or directly to the output, with
only logits belonging to the same class accumulated. Three examples of network
configuration are shown in Fig. 7 for supporting (a) regression or binary
classification, (b) multi-class classification, and (c) regression or binary
classification with input batching. In the first case, the X-TIME compiler
maps $N_{trees}=8$ trees with a depth $D=7$ each, with $N_{trees,core}=2$ each
core. The same inputs (blue solid and light blue dashed lines) are applied to
all the cores in parallel and all the logits (solid purple lines) are summed
together, being a regression/binary classification problem. The X-TIME
compiler sets the configuration bit of all routers to ’1’ such that logits are
always accumulated in the router before propagating.

For multi-class classification (Fig. 7(b)), the X-TIME compiler maps
$N_{estimators}=2$ estimators each made of $N_{trees}=4$ (one for each class)
with a depth $D=7$. Each core holds two trees belonging to the same class and
the same inputs (blue solid and light blue dashed lines) are applied to all
cores in parallel. The X-TIME compiler sets router configuration bits to 0, as
it is not possible to perform an accumulation/reduction at the router level
and the reduction must be done globally by the CP. Thus, logits for each class
are transmitted independently (solid purple lines, dashed purple lines, solid
pink lines, and dashed pink lines). Note that this configuration limits
throughput to an upper limit of $1/N_{classes}$ samples for each clock.

Finally, for regression/binary classification with input batching (Fig. 7(c)),
the X-TIME compiler maps an ensemble of $N_{trees}=4$ with depth $d=7$ and to
increase the throughput, replicates trees in multiple cores, such that cores
C1 and C2 map the same trees of cores C3 and C4. Different inputs are applied
to different cores, or groups of cores by appropriately addressing each
feature vector. Core C1 and C2 receive a first input (solid blue line) while
cores C3 and C4 receive a second input (dashed light blue). Logits can be
accumulated at the router level only between trees belonging to the same input
batch, as in the lower level of the architecture in Fig. 7(c). The X-TIME
compiler programs the lower level router configuration bits to ’1’ to enable
local accumulation, and the higher level configuration bits to ’0’ to enable
logits direct propagation. Input batching addresses one of the main issues of
specialized accelerators in keeping resource utilization high [68]. With a
similar procedure, multiple unique models can be mapped to the accelerator, by
assigning a different batch to each model. If a model does not fit an X-TIME
chip, given that we estimate the power of a single chip to be under 20W, we
envision a PCIe card containing multiple X-TIME chips connected to a standard
server, that the CPU can use to offload the decision tree inference
operations, similar to what is done with GPU cards today.

##  IV Evaluation Methodology

###  IV-A Datasets and model training

TABLE II: Datasets and models characterization Dataset | ID | Task | Samples | $\boldsymbol{N_{feat}}$ | $\boldsymbol{N_{classes}}$ | Model | $\boldsymbol{N_{trees}}$ | $\boldsymbol{N_{leaves,max}}$
---|---|---|---|---|---|---|---|---
Churn modelling[33] | 1 | Binary Classification | 10000 | 10 | 2 | CatBoost | 404 | 256
Eye movements[57] | 2 | Multiclass Classification | 10936 | 26 | 3 | XGBoost | 2352 | 256
Forest cover type[11] | 3 | Multiclass Classification | 581012 | 54 | 7 | XGBoost | 1351 | 231
Gas concentration[65] | 4 | Multiclass Classification | 13910 | 129 | 6 | Random Forest | 1356 | 217
Gesture phase segmentation[66] | 5 | Multiclass Classification | 9873 | 32 | 5 | XGBoost | 1895 | 256
Telco customer churn[12] | 6 | Binary Classification | 7032 | 19 | 2 | XGBoost | 159 | 4
Rossmann stores sales[6] | 7 | Regression | 610253 | 29 | N/A | XGBoost | 2017 | 256

For our experiments, we trained state-of-the-art models with four machine
learning algorithms on a set of benchmark datasets from ref. [60] (details in
Table II). The algorithms included random forests (RF) from scikit-learn [49],
and gradient boosted trees from XGBoost [15], LightGBM [37] and CatBoost [53].
Hyperparameter optimization was performed on all datasets using Hyperopt [9]
library integrated with Ray Tune [42], a distributed hyperparameter
optimization platform. Our machine learning benchmark pipeline consists of
three steps. In the first step, we pre-process datasets, splitting raw data
into train, validation and test splits and performing data set cleaning, using
the same splits as authors in ref. [60]. In the second step, we performed
hyperparameter optimization using 100 trials for each combination of
model/dataset pairs. In the third step, we selected the best configuration
(highest accuracy on test splits) with an additional 20 runs (training
sessions with the same hyperparameters but varying initial random seeds) to
confirm model performance and stability with the found hyperparameters. Once
the best hyperparameters were identified, we selected the best model for each
dataset and compile them to a threshold map for programming thresholds into
the analog CAM arrays for detailed simulations and performance benchmarking.
Fig. 7(d) shows a conceptual schematic of the workflow, whose output is a
series of threshold maps (one for each tree) with the lower/upper bound to
program in analog CAMs, the corresponding core/class address and leaf value
for each node.

###  IV-B Cycle-detailed simulator

We developed a functional and cycle-detailed
simulator111https://github.com/HewlettPackard/X-TIME to evaluate latency,
throughput, energy efficiency, area, and accuracy of the in-memory engine for
tree-based model inference. The architecture simulator was developed using the
Structural Simulation Toolkit (SST) [56] and estimates the performance on the
benchmark datasets detailed above. SST, which is a parallel discrete-event
simulator framework, can integrate modular components in a unified interface
and simulate large-scale systems with MPI. It also provides interfaces for
simulation components and components that perform actual functions such as
processors, memory, and networks. For our system, the user-defined components
emulate the cycle-level function of each block described in Fig. 4, and data
flow through the links connecting the components with specified delay. The
cycle-level architecture simulation consisting of an H-tree NoC with 4096
cores and 1365 routers verified the error-free functional operation and the
pipelined architecture without hazards, while also estimating system
performance.

Figure 8: Area (a) and peak power (b) breakdown

Fig. 8 summarizes the power and area for the proposed architecture. We derive
the analog CAM area at 16 nm from previous work [39, 51], which includes the
analog CAM array, DAC, SA, and P-Ch area, and extract the power consumption
using single cell parameters [51] and simulating the model mapping with
memristor conductances from $1\mu S$ to $100\mu S$. The analog CAM model
includes parasitics that limit the CAM pre-charge and discharge time and the
DAC operational frequency [39]. Power and area values for register and logic
are based on TSMC 16nm PDK and previous work [8]. The MMR design is based on
the matching token MMR topology [46] whose output is fed-back to MAL registers
enabling multiple iterations when multiple trees are mapped to the same core.
Notably, area and power is mainly consumed by the analog CAM arrays, with
peripheral components contributing a negligible amount. Also, the overall peak
power consumption of 19 W is comparable to GPU idle power ($\sim$25 W).

###  IV-C Profiling Tree Model Inference on NVIDIA GPUs

As our performance baseline, we profiled the inference step of the tree models
and corresponding datasets shown in Table II on an NVIDIA V100 GPU. A common
and fair criticism of our general approach is that comparing simulated results
with those from hardware is not a true apples-to-apples comparison, as many
non-idealities are expected in real-world physical implementation. However, in
our case, previous results [26] have shown that for tree-based workloads one
would expect up to a maximum 3$\times$ increase in latency from an ideal GPU
simulation to physical measurements, and our results (as detailed in the
following section) show orders of magnitude improvement compared to GPU, thus
the possible error derived from using simulation metrics is small compared to
the improvement we’ve demonstrated here. Further, the practice of comparing
GPU measurements with in-house simulators has been accepted for emerging in-
memory computing architectures[16, 25, 30] given the difficulty in otherwise
making fair comparisons. We measured 5 times each GPU kernel time to process
data batches of increasing size, up to a saturation point, where throughput
improvements were no longer observed. In order to estimate GPU upper bound
performance, we isolated the kernel execution time of each model using
NVIDIA’s nvprof [2] tool, not including in our measurements the time to
perform all memory transfers from the host (CPU) to device (GPU) and back, and
all internal GPU transfers. When possible, we profiled models using CUDA
kernels from the NVIDIA RAPIDS Forest Inference Library (FIL) [54].

##  V Results

###  V-A Model inference performance

Figure 9: (a) Accuracy for different training constraints and (b) relative
accuracy as a function of memristor and DAC defects.

In designing our HW architecture, we investigated the required bit accuracy
and model types that the architecture should support to maintain state-of-the-
art accuracy. To assess these parameters, we compared model accuracy for
different training parameters and model types to guide the X-TIME requirements
(Figure. 9(a)). First, we trained RF, XGBoost, CatBoost, and LightGBM models
without any constraints on the number of trees, or the number of leaves and
allowing floating point precision for thresholds and features
(‘Unconstrained’), to achieve our baseline state-of-the-art accuracy [60]. We
then tested optimized models to fit the hardware with 8-bit precision (‘X-TIME
8bit’: maximum $N_{trees}=4096$, $N_{leaves,max}=256,N_{bit}=8$), which
resulted in limited accuracy loss compared to the unconstrained baseline case.
To assess the need for 8-bit vs. 4-bit analog CAMs, we optimized the model to
fit 4-bit hardware, allowing the number of leaves to double for an iso-area
comparison (‘X-TIME 4bit’: maximum $N_{trees}=4096$,
$N_{leaves,max}=512,N_{bit}=4$). Another option would double the maximum
number of allowed trees, but we generally found that 4096 trees are high
enough for matching unconstrained baseline accuracy. Our results showed a
reduction in performance of $20\%$ in the case of regression on Rossmann store
sales dataset [6] and $18\%$ in the case of multi-class classification on gas
concentration dataset [65]. Finally, we limited the optimizer to RF models
only, which results in significant accuracy degradation for several datasets
(label = ‘Only RF’), given that it is not possible to train directly with
4-bit precision, and the after-training quantization significantly decreased
accuracy, demonstrating the need for supporting a broader range of model types
beyond those demonstrated in previous work [51].

To assess the promise of this analog hardware approach in practical use, we
also studied the impact of variations and defects of the analog hardware on
model inference accuracy. The two most impactful sources of error to
classification/regression results in this analog hardware are the known
memristor conductance variations [50] and DAC input variations to the aCAM. We
considered experimental data from TaOx memristor and 16 nm analog
circuits[51]. Fig. 9(b) shows the mean relative accuracy, defined as the ideal
accuracy of Fig. 9(a) over the defect-compromised accuracy, averaged over 100
runs, as a function of the percentage of defects, where a defect is defined as
a 1-level random flip in the memristor conductance or DAC output voltage. A
number of devices were randomly selected, with half having errors flipped up
and half down. The plot shows the average results across all classification
datasets. We observe that these models and our architecture are fairly
resilient to memristor variations, as individual errors do not have a large
impact due to the ensemble nature of the model itself. With the aforementioned
conductance window and a conservative standard deviation of $1\mu S$ it is
expected to have a flip probability of $\sim 0.2\%$, corresponding to accuracy
drop $<0.5\%$. On the other hand, while DAC variations also impact the
accuracy, DACs are usually designed for operating up to 16 bits [43], thus
realizing a stable/error-free 4-bit design is not particularly challenging.
Models with a smaller number of trees (e.g. Forest Cover Type with 193 trees
in each class) are subject to higher error because each tree contribution has
relatively higher importance to the overall prediction, thus committing a
mistake in one tree has a higher chance of affecting the final result. In the
future, we envision the use of co-design techniques to take this information
into consideration during model training, resulting in an ensemble large
enough to be robust against memristor variation and DAC errors.

###  V-B Comparison with state-of-the-art

Figure 10: Comparison of (a) latency and (b) throughput of this work, GPU and
Booster[26]

Multiple accelerators for tree-based ML models have been proposed [63, 34, 64,
61, 26]. The most promising generally have a large number of LUTs implemented
either on FPGA [61] or with SRAM [26]. Such approaches allow for extreme
parallelization, similar to X-TIME, although in these other cases the
memory/LUTs need to be accessed as many times as the depth of a tree.
Intuitively, each word stores the node attributes (feature identifier and
value) and the left/right child addresses.

Figure 11: (a) Throughput as a function of $N_{trees}$ and $D$. (b) Throughput
as a function of $N_{feat}$.

We benchmarked our proposed architecture on a wide range of models
(corresponding to X-TIME 8bit of Fig. 9) and dataset types (Table II), and
compared latency and throughput (see Fig. 10(a,b)) to GPU performance and
Booster, a purely digital ASIC for tree-based ML [26]. When possible, we
applied input batching and replicated trees to increase the throughput. As
shown, our architecture produces drastically reduced latency, frequently to
$\sim$100ns compared to GPU at 10 $\mu$s to ms, while also demonstrating
significantly improved throughput by 10-120$\times$ across most datasets. Our
architecture shines for large binary classification or regression models with
a peak improvement in latency by $9740\times$ at 119$\times$ higher throughput
for the Churn modeling dataset inference[33] compared to GPU. As tree search
is parallel in each analog CAM array of each core, as well as the in-network
reduction, latency, and throughput are constant with $N_{trees}$ and
$N_{leaves}$ with a delay solely dependant on $N_{feat}$ and $N_{classes}$. As
opposite, on GPU there is a linear dependence on $N_{trees}$ and $D$, which
limit the performance for large models. As an example, we studied the
throughput as a function of $N_{trees}$, $D$ and $N_{feat}$ for GPU and X-TIME
as shown in Fig. 11(a,b). Intuitively, this dramatic latency reduction is
because a single CAM memory operation computes inference of the whole tree
ensemble, and another single memory access operation retrieves leaf values.
This is in stark contrast to the $D$ required memory accesses and comparisons
for each tree on GPU. In addition, our balanced pipelined execution increases
throughput significantly, as new data is fed to the core directly following
the analog CAM array processing of the previous data. The high throughput can
produce an extremely low energy per decision, down to 0.3 nJ/Dec, highlighting
the potential for energy-efficient applications. Due to the massively parallel
operation on the whole feature vector, the pain point for X-TIME is a
dependancy on the number of features as shown in Fig. 11(b), as features must
be broadcasted to all cores, while GPU does not show a clear dependence on the
number of features.

In the case of Booster, while all the trees are inferred in parallel, the tree
traversal still requires $D$ memory accesses, and each time a decision has to
be made on which direction to take based on the input data. The inference time
complexity of each core is then $O(D)$ compared to ours which is $O(1)$, and
the space complexity is in both cases $O(2^{(D+1)})$ (taking into account both
the nodes and the leaves). Note that while this results in moderate overhead
in latency (as shown in Fig. 10(a)), the need for additional bubbles before
feeding new data to each core limits significant throughput, with an $8\times$
reduced speedup compared to X-TIME in the case of the regression dataset [6],
for example. The throughput for Booster is in fact limited by the tree depth
to $1/4D$, assuming 4 cycles to process a node [26], except for cases where
input batching is possible. Moreover, Booster still suffers from load
imbalance between trees, similar to GPU, in which trees with different depths
have different inference times, which results in the need for synchronization
before the reduction operation. Note that (I) in the case of Booster we
consider the same chip architecture of X-TIME, updating only the core
operation, and (II) Booster is optimized for accelerated training, rather than
inference. The same discussion also holds for the state-of-the-art FPGA
implementation [61].

##  VI Related work

Several in-memory computing architectures based on CAMs have been proposed
previously. Architectures for associative computing were proposed [23, 32,
69], whereby recompiling code to perform an iterative associative search, a
set of tasks may be significantly accelerated. Note that in these cases, TCAM
and RAM memory is reprogrammed frequently, which can lead to latency overheads
with emerging memory devices such as memristors. Associative computing has
been extended to graph processing [59], for which custom architectures based
on a mix of crossbar arrays and CAMs have also been proposed [14]. Finite
automata processing architectures based on TCAMs have been presented [29],
with significant improvement in throughput compared to general-purpose
systems. CAM-based architectures for recommender systems have also been
proposed [41]

##  VII Conclusions

In this work, we presented a novel architecture for accelerated tree-based
machine learning inference with in-memory computing based on a novel increased
precision analog non-volatile CAMs. Our approach maps decision trees to analog
CAM ranges, which compute directly the matched results in parallel given an
input feature vector. Leaf values are stored in a local SRAM and accumulated
at core level when multiple trees are mapped in the same core. Outside the
core, an H-tree NoC connects 4096 cores and a co-processor in a single chip.
An in-network computing structure accumulates leaf values as data flows to
limit data movement. The on-chip network is re-configurable to map different
models (regression, multi-class classification, etc) and inference techniques,
such as input batching. Our results show significant improvement in latency –
by almost four orders of magnitude, compared with an NVIDIA V100 GPU, at a
throughput up to $\sim 120\times$ higher across a wide range of dataset types
and model topologies.

## References

  * [1] “Ieee-cis fraud detection competition,” https://www.kaggle.com/code/cdeotte/xgb-fraud-with-magic-0-9600/notebook, accessed: 2022-10-10.
  * [2] “Nvidia profiler user’s guide,” https://docs.nvidia.com/cuda/profiler-users-guide/index.html, accessed: 2022-07-25.
  * [3] “Productionizing distributed xgboost to train deep tree models with large data sets at uber,” https://www.uber.com/blog/productionizing-distributed-xgboost/, accessed: 2022-10-10.
  * [4] “RAPIDS | NVIDIA Developer.” [Online]. Available: https://developer.nvidia.com/rapids
  * [5] “RAPIDS Forest Inference Library: Prediction at 100 million rows per second.” [Online]. Available: https://medium.com/rapids-ai/rapids-forest-inference-library-prediction-at-100-million-rows-per-second-19558890bc35
  * [6] “Rossmann store sales kaggle competition: forecast sales using store, promotion, and competitor data,” accessed: 2022-07-26. [Online]. Available: https://www.kaggle.com/competitions/rossmann-store-sales/overview
  * [7] “State of data science and machine learning 2021,” https://www.kaggle.com/kaggle-survey-2021, accessed: 2022-07-25.
  * [8] A. Ankit, I. E. Hajj, S. R. Chalamalasetti, G. Ndu, M. Foltin, R. S. Williams, P. Faraboschi, W.-m. W. Hwu, J. P. Strachan, K. Roy, and D. S. Milojicic, “PUMA: A Programmable Ultra-efficient Memristor-based Accelerator for Machine Learning Inference,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_. Providence RI USA: ACM, Apr. 2019, pp. 715–731. [Online]. Available: https://dl.acm.org/doi/10.1145/3297858.3304049
  * [9] J. Bergstra, D. Yamins, and D. Cox, “Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures,” in _International conference on machine learning_. PMLR, 2013, pp. 115–123.
  * [10] G. Biau and E. Scornet, “A random forest guided tour,” _TEST_ , vol. 25, no. 2, pp. 197–227, Jun. 2016. [Online]. Available: https://doi.org/10.1007/s11749-016-0481-7
  * [11] J. A. Blackard and D. J. Dean, “Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables,” _Computers and electronics in agriculture_ , vol. 24, no. 3, pp. 131–151, 1999, dataset URL: https://archive.ics.uci.edu/ml/datasets/covertype.
  * [12] BlastChar, “Telco customer churn,” accessed: 2022-07-26. [Online]. Available: https://www.kaggle.com/datasets/blastchar/telco-customer-churn
  * [13] V. Borisov, T. Leemann, K. Seßler, J. Haug, M. Pawelczyk, and G. Kasneci, “Deep Neural Networks and Tabular Data: A Survey,” 2021. [Online]. Available: https://arxiv.org/abs/2110.01889
  * [14] N. Challapalle, S. Rampalli, L. Song, N. Chandramoorthy, K. Swaminathan, J. Sampson, Y. Chen, and V. Narayanan, “GaaS-X: Graph Analytics Accelerator Supporting Sparse Data Representation using Crossbar Architectures,” in _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. Valencia, Spain: IEEE, May 2020, pp. 433–445. [Online]. Available: https://ieeexplore.ieee.org/document/9138911/
  * [15] T. Chen and C. Guestrin, “XGBoost: A Scalable Tree Boosting System,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. San Francisco California USA: ACM, Aug. 2016, pp. 785–794. [Online]. Available: https://dl.acm.org/doi/10.1145/2939672.2939785
  * [16] B. Feinberg, R. Wong, T. P. Xiao, C. H. Bennett, J. N. Rohan, E. G. Boman, M. J. Marinella, S. Agarwal, and E. Ipek, “An Analog Preconditioner for Solving Linear Systems,” in _2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. Seoul, Korea (South): IEEE, Feb. 2021, pp. 761–774. [Online]. Available: https://ieeexplore.ieee.org/document/9407108/
  * [17] A. Gajjar, P. Kashyap, A. Aysu, P. Franzon, S. Dey, and C. Cheng, “Faxid: Fpga-accelerated xgboost inference for data centers using hls,” in _2022 IEEE 30th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2022, pp. 1–9.
  * [18] C. E. Graves, S.-T. Lam, X. Li, L. Kiyama, M. Foltin, M. P. Hardy, J. P. Strachan, C. Li, X. Sheng, W. Ma, S. R. Chalamalasetti, D. Miller, J. S. Ignowski, B. Buchanan, and L. Zheng, “Memristor TCAMs Accelerate Regular Expression Matching for Network Intrusion Detection,” _IEEE Transactions on Nanotechnology_ , vol. 18, pp. 963–970, 2019. [Online]. Available: https://ieeexplore.ieee.org/document/8812926/
  * [19] C. E. Graves, C. Li, G. Pedretti, and J. P. Strachan, “In-Memory Computing with Non-volatile Memristor CAM Circuits,” in _Memristor Computing Systems_ , L. O. Chua, R. Tetzlaff, and A. Slavova, Eds. Cham: Springer International Publishing, 2022, pp. 105–139. [Online]. Available: https://doi.org/10.1007/978-3-030-90582-8_6
  * [20] C. E. Graves, C. Li, X. Sheng, D. Miller, J. Ignowski, L. Kiyama, and J. P. Strachan, “In‐Memory Computing with Memristor Content Addressable Memories for Pattern Matching,” _Advanced Materials_ , vol. 32, no. 37, p. 2003437, Sep. 2020. [Online]. Available: https://onlinelibrary.wiley.com/doi/10.1002/adma.202003437
  * [21] L. Grinsztajn, E. Oyallon, and G. Varoquaux, “Why do tree-based models still outperform deep learning on typical tabular data?” in _Advances in Neural Information Processing Systems, Datasets and Benchmarks Track_. Curran Associates, Inc., 2022.
  * [22] Q. Guo, X. Guo, Y. Bai, and E. İpek, “A resistive TCAM accelerator for data-intensive computing,” in _Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture - MICRO-44 ’11_. Porto Alegre, Brazil: ACM Press, 2011, p. 339\. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2155620.2155660
  * [23] Q. Guo, X. Guo, R. Patel, E. Ipek, and E. G. Friedman, “AC-DIMM: Associative Computing with STT-MRAM,” in _Proceedings of the 40th Annual International Symposium on Computer Architecture_ , ser. ISCA ’13. New York, NY, USA: Association for Computing Machinery, 2013, pp. 189–200, event-place: Tel-Aviv, Israel. [Online]. Available: https://doi.org/10.1145/2485922.2485939
  * [24] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan, “Deep Learning with Limited Numerical Precision,” in _Proceedings of the 32nd International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, F. Bach and D. Blei, Eds., vol. 37. Lille, France: PMLR, Jul. 2015, pp. 1737–1746. [Online]. Available: https://proceedings.mlr.press/v37/gupta15.html
  * [25] 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_ , ser. ISCA ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 495–507. [Online]. Available: https://doi.org/10.1145/3470496.3527424
  * [26] M. He, M. Thottethodi, and T. N. Vijaykumar, “Booster: An accelerator for gradient boosting decision trees training and inference,” in _2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_ , 2022, pp. 1051–1062.
  * [27] M. Hu, R. S. Williams, J. P. Strachan, Z. Li, E. M. Grafals, N. Davila, C. Graves, S. Lam, N. Ge, and J. J. Yang, “Dot-product engine for neuromorphic computing: programming 1T1M crossbar to accelerate matrix-vector multiplication,” in _Proceedings of the 53rd Annual Design Automation Conference on - DAC ’16_. Austin, Texas: ACM Press, 2016, pp. 1–6. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2897937.2898010
  * [28] X. S. Hu, M. Niemier, A. Kazemi, A. F. Laguna, K. Ni, R. Rajaei, M. M. Sharifi, and X. Yin, “In-Memory Computing with Associative Memories: A Cross-Layer Perspective,” in _2021 IEEE International Electron Devices Meeting (IEDM)_ , 2021, pp. 25.2.1–25.2.4.
  * [29] Y. Huang, Z. Chen, D. Li, and K. Yang, “CAMA: Energy and Memory Efficient Automata Processing in Content-Addressable Memories,” in _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ , 2022, pp. 25–37.
  * [30] Y. Huang, L. Zheng, P. Yao, Q. Wang, X. Liao, H. Jin, and J. Xue, “Accelerating graph convolutional networks using crossbar-based processing-in-memory architectures,” in _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ , 2022, pp. 1029–1042.
  * [31] D. Ielmini and H.-S. P. Wong, “In-memory computing with resistive switching devices,” _Nature Electronics_ , vol. 1, no. 6, pp. 333–343, Jun. 2018. [Online]. Available: http://www.nature.com/articles/s41928-018-0092-2
  * [32] M. Imani, A. Rahimi, D. Kong, T. Rosing, and J. M. Rabaey, “Exploring Hyperdimensional Associative Memory,” in _2017 IEEE International Symposium on High Performance Computer Architecture (HPCA)_ , 2017, pp. 445–456.
  * [33] S. Iyyer, “Churn modelling,” accessed: 2022-07-26. [Online]. Available: https://www.kaggle.com/datasets/shrutimechlearn/churn-modelling
  * [34] M. Kang, S. K. Gonugondla, S. Lim, and N. R. Shanbhag, “A 19.4-nJ/Decision, 364-K Decisions/s, In-Memory Random Forest Multi-Class Inference Accelerator,” _IEEE Journal of Solid-State Circuits_ , vol. 53, no. 7, pp. 2126–2135, Jul. 2018. [Online]. Available: https://ieeexplore.ieee.org/document/8353374/
  * [35] R. Karam, P. Ruchir, G. Swaroop, and B. Swarup, “Emerging Trends in Design and Applications of Memory-Based Computing and Content-Addressable Memories,” _Proceedings of the IEEE_ , vol. 103, no. 8, p. 20, Aug. 2015.
  * [36] A. Kazemi, M. M. Sharifi, A. F. Laguna, F. Müller, R. Rajaei, R. Olivo, T. Kämpfe, M. Niemier, and X. S. Hu, “In-Memory Nearest Neighbor Search with FeFET Multi-Bit Content-Addressable Memories,” in _2021 Design, Automation & Test in Europe Conference & Exhibition (DATE)_, 2021, pp. 1084–1089.
  * [37] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu, “LightGBM: A Highly Efficient Gradient Boosting Decision Tree,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017. [Online]. Available: https://proceedings.neurips.cc/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf
  * [38] C. Li, C. E. Graves, X. Sheng, D. Miller, M. Foltin, G. Pedretti, and J. P. Strachan, “Analog content-addressable memories with memristors,” _Nature Communications_ , vol. 11, no. 1, p. 1638, Dec. 2020. [Online]. Available: http://www.nature.com/articles/s41467-020-15254-4
  * [39] C. Li, R. M. Roth, C. Graves, X. Sheng, and J. P. Strachan, “Analog error correcting codes for defect tolerant matrix multiplication in crossbars,” in _2020 IEEE International Electron Devices Meeting (IEDM)_ , 2020, pp. 36.6.1–36.6.4.
  * [40] H. Li, W.-C. Chen, A. Levy, C.-H. Wang, H. Wang, P.-H. Chen, W. Wan, W.-S. Khwa, H. Chuang, Y.-D. Chih, M.-F. Chang, H.-S. P. Wong, and P. Raina, “SAPIENS: A 64-kb RRAM-Based Non-Volatile Associative Memory for One-Shot Learning and Inference at the Edge,” _IEEE Transactions on Electron Devices_ , vol. 68, no. 12, pp. 6637–6643, 2021.
  * [41] M. Li, A. F. Laguna, D. Reis, X. Yin, M. Niemier, and X. S. Hu, “Imars: An in-memory-computing architecture for recommendation systems,” in _Proceedings of the 59th ACM/IEEE Design Automation Conference_ , ser. DAC ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 463–468. [Online]. Available: https://doi.org/10.1145/3489517.3530478
  * [42] R. Liaw, E. Liang, R. Nishihara, P. Moritz, J. E. Gonzalez, and I. Stoica, “Tune: A research platform for distributed model selection and training,” _arXiv preprint arXiv:1807.05118_ , 2018.
  * [43] C.-H. Lin, K. L. J. Wong, T.-Y. Kim, G. R. Xie, D. Major, G. Unruh, S. R. Dommaraju, H. Eberhart, and A. Venes, “A 16b 6gs/s nyquist dac with imd ¡-90dbc up to 1.9ghz in 16nm cmos,” in _2018 IEEE International Solid - State Circuits Conference - (ISSCC)_ , 2018, pp. 360–362.
  * [44] C.-C. Lin, J.-Y. Hung, W.-Z. Lin, C.-P. Lo, Y.-N. Chiang, H.-J. Tsai, G.-H. Yang, Y.-C. King, C. J. Lin, T.-F. Chen, and M.-F. Chang, “7.4 A 256b-wordlength ReRAM-based TCAM with 1ns search-time and 14× improvement in wordlength-energyefficiency-density product using 2.5T1R cell,” in _2016 IEEE International Solid-State Circuits Conference (ISSCC)_ , 2016, pp. 136–137.
  * [45] S. M. Lundberg, G. Erion, H. Chen, A. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S.-I. Lee, “From local explanations to global understanding with explainable AI for trees,” _Nature Machine Intelligence_ , vol. 2, no. 1, pp. 56–67, Jan. 2020. [Online]. Available: http://www.nature.com/articles/s42256-019-0138-9
  * [46] N. Mohan, W. Fung, D. Wright, and M. Sachdev, “Design techniques and test methodology for low-power tcams,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 14, no. 6, pp. 573–586, 2006.
  * [47] K. Ni, X. Yin, A. F. Laguna, S. Joshi, S. Dünkel, M. Trentzsch, J. Müller, S. Beyer, M. Niemier, X. S. Hu, and S. Datta, “Ferroelectric ternary content-addressable memory for one-shot learning,” _Nature Electronics_ , vol. 2, no. 11, pp. 521–529, Nov. 2019. [Online]. Available: http://www.nature.com/articles/s41928-019-0321-3
  * [48] K. Pagiamtzis and A. Sheikholeslami, “Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey,” _IEEE Journal of Solid-State Circuits_ , vol. 41, no. 3, pp. 712–727, Mar. 2006. [Online]. Available: http://ieeexplore.ieee.org/document/1599540/
  * [49] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python,” _Journal of Machine Learning Research_ , vol. 12, pp. 2825–2830, 2011.
  * [50] G. Pedretti, E. Ambrosi, and D. Ielmini, “Conductance variations and their impact on the precision of in-memory computing with resistive switching memory (RRAM),” in _2021 IEEE International Reliability Physics Symposium (IRPS)_. Monterey, CA, USA: IEEE, Mar. 2021, pp. 1–8. [Online]. Available: https://ieeexplore.ieee.org/document/9405130/
  * [51] G. Pedretti, C. E. Graves, S. Serebryakov, R. Mao, X. Sheng, M. Foltin, C. Li, and J. P. Strachan, “Tree-based machine learning performed in-memory with memristive analog CAM,” _Nature Communications_ , vol. 12, no. 1, p. 5806, Oct. 2021. [Online]. Available: https://doi.org/10.1038/s41467-021-25873-0
  * [52] G. Pedretti, C. E. Graves, T. Van Vaerenbergh, S. Serebryakov, M. Foltin, X. Sheng, R. Mao, C. Li, and J. P. Strachan, “Differentiable Content Addressable Memory with Memristors,” _Advanced Electronic Materials_ , p. 2101198, 2022, _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/aelm.202101198. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/aelm.202101198
  * [53] L. Prokhorenkova, G. Gusev, A. Vorobev, A. V. Dorogush, and A. Gulin, “CatBoost: unbiased boosting with categorical features,” in _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31. Curran Associates, Inc., 2018\. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/14491b756b3a51daac41c24863285549-Paper.pdf
  * [54] S. Raschka, J. Patterson, and C. Nolet, “Machine learning in python: Main developments and technology trends in data science, machine learning, and artificial intelligence,” _arXiv preprint arXiv:2002.04803_ , 2020.
  * [55] A. S. Rekhi, B. Zimmer, N. Nedovic, N. Liu, R. Venkatesan, M. Wang, B. Khailany, W. J. Dally, and C. T. Gray, “Analog/Mixed-Signal Hardware Error Modeling for Deep Learning Inference,” in _Proceedings of the 56th Annual Design Automation Conference 2019_ , ser. DAC ’19. New York, NY, USA: Association for Computing Machinery, 2019, event-place: Las Vegas, NV, USA. [Online]. Available: https://doi.org/10.1145/3316781.3317770
  * [56] A. F. Rodrigues, K. S. Hemmert, B. W. Barrett, C. Kersey, R. Oldfield, M. Weston, R. Risen, J. Cook, P. Rosenfeld, E. Cooper-Balis, and B. Jacob, “The Structural Simulation Toolkit,” _SIGMETRICS Perform. Eval. Rev._ , vol. 38, no. 4, pp. 37–42, Mar. 2011, place: New York, NY, USA Publisher: Association for Computing Machinery. [Online]. Available: https://doi.org/10.1145/1964218.1964225
  * [57] J. Salojärvi, K. Puolamäki, J. Simola, L. Kovanen, I. Kojo, and S. Kaski, “Inferring relevance from eye movements: Feature extraction,” in _Workshop at NIPS 2005, in Whistler, BC, Canada, on December 10, 2005._ , 2005, p. 45, dataset URL: https://www.openml.org/d/1044.
  * [58] A. Shafiee, A. Nag, N. Muralimanohar, R. Balasubramonian, J. P. Strachan, M. Hu, R. S. Williams, and V. Srikumar, “ISAAC: A Convolutional Neural Network Accelerator with In-Situ Analog Arithmetic in Crossbars,” in _2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA)_. Seoul, South Korea: IEEE, Jun. 2016, pp. 14–26. [Online]. Available: http://ieeexplore.ieee.org/document/7551379/
  * [59] W. Shim and S. Yu, “GP3D: 3D NAND Based In-Memory Graph Processing Accelerator,” _IEEE Journal on Emerging and Selected Topics in Circuits and Systems_ , vol. 12, no. 2, pp. 500–507, 2022.
  * [60] R. Shwartz-Ziv and A. Armon, “Tabular data: Deep learning is not all you need,” _Information Fusion_ , vol. 81, pp. 84–90, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1566253521002360
  * [61] S. Summers, G. D. Guglielmo, J. Duarte, P. Harris, D. Hoang, S. Jindariani, E. Kreinar, V. Loncar, J. Ngadiuba, M. Pierini, D. Rankin, N. Tran, and Z. Wu, “Fast inference of Boosted Decision Trees in FPGAs for particle physics,” _Journal of Instrumentation_ , vol. 15, no. 05, pp. P05 026–P05 026, May 2020, publisher: IOP Publishing. [Online]. Available: https://doi.org/10.1088/1748-0221/15/05/p05026
  * [62] Z. Sun, G. Pedretti, E. Ambrosi, A. Bricalli, W. Wang, and D. Ielmini, “Solving matrix equations in one step with cross-point resistive arrays,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 10, pp. 4123–4128, Mar. 2019\. [Online]. Available: http://www.pnas.org/lookup/doi/10.1073/pnas.1815682116
  * [63] T. Tracy, Y. Fu, I. Roy, E. Jonas, and P. Glendenning, “Towards machine learning on the automata processor,” in _International Conference on High Performance Computing_. Springer, 2016, pp. 200–218.
  * [64] G. Tzimpragos, A. Madhavan, D. Vasudevan, D. Strukov, and T. Sherwood, “Boosted race trees for low energy classification,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 215–228. [Online]. Available: https://doi.org/10.1145/3297858.3304036
  * [65] A. Vergara, S. Vembu, T. Ayhan, M. A. Ryan, M. L. Homer, and R. Huerta, “Chemical gas sensor drift compensation using classifier ensembles,” _Sensors and Actuators B: Chemical_ , vol. 166-167, pp. 320–329, 2012. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0925400512002018
  * [66] P. K. Wagner, S. M. Peres, R. C. B. Madeo, C. A. de Moraes Lima, and F. de Almeida Freitas, “Gesture unit segmentation using spatial-temporal information and machine learning,” in _The Twenty-Seventh International Flairs Conference_ , 2014, dataset URL: https://archive.ics.uci.edu/ml/datasets/gesture+phase+segmentation.
  * [67] Z. Xie, W. Dong, J. Liu, H. Liu, and D. Li, “Tahoe: tree structure-aware high performance inference engine for decision tree ensemble on GPU,” in _Proceedings of the Sixteenth European Conference on Computer Systems_. Online Event United Kingdom: ACM, Apr. 2021, pp. 426–440. [Online]. Available: https://dl.acm.org/doi/10.1145/3447786.3456251
  * [68] C. Xu, A. Lain, P. Faraboschi, N. Dube, and D. Milojicic, “Feeding the beast: High performance data pipeline for large-scale deep learning,” in _A Collection of White Papers from the BDEC2 Workshop in San Diego, California_ , vol. 1, 2019, p. 14.
  * [69] Y. Zha and J. Li, “Hyper-Ap: Enhancing Associative Processing Through A Full-Stack Optimization,” in _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. Valencia, Spain: IEEE, May 2020, pp. 846–859. [Online]. Available: https://ieeexplore.ieee.org/document/9138935/
  * [70] Z. Zhao, J. Gomez, H. Ye, M. Imani, X. Yin, S. Deng, B. Melanson, J. Zhang, X. Gong, A. Abusleme, S. Datta, and K. Ni, “Computational Associative Memory Based on Monolithically Integrated Metal-Oxide Thin Film Transistors for Update-Frequent Search Applications,” in _2021 IEEE International Electron Devices Meeting (IEDM)_ , 2021, pp. 37.6.1–37.6.4.
  * [71] M. A. Zidan, J. P. Strachan, and W. D. Lu, “The future of electronics based on memristive systems,” _Nature Electronics_ , vol. 1, no. 1, pp. 22–29, Jan. 2018. [Online]. Available: http://www.nature.com/articles/s41928-017-0006-8