PaperlayerView exact revision on arXiv

Source-linked AI summary

Tree-based machine learning performed in-memory with memristive analog CAM

Giacomo Pedretti, Catherine E. Graves, Can Li, Sergey Serebryakov, Xia Sheng, Martin Foltin, Ruibin Mao, John Paul Strachan

arXiv:2103.08986v2cs.ET

TL;DR

Tree-based models can be difficult to optimize for fast, accurate inference in von Neumann architectures because of non-uniform memory access. This paper maps tree inference and forest voting to analog CAM–RRAM arrays, reporting substantially improved throughput, power, and energy per decision versus prior accelerators.

  • Problem

    Tree-based models can be difficult to optimize for fast inference without accuracy loss in von Neumann architectures because of non-uniform memory access patterns.

    Source: ABSTRACT · p. 14

  • Method

    The design maps root-to-leaf paths to analog CAM rows for tree traversal and uses an RRAM array for random-forest majority voting.

    Source: Analog CAM compact model · p. 2, Mapping DT/RF to analog CAM · p. 5

  • Results

    Compared with the state of the art, the scaled architecture reports ∼2x lower power, ∼103x higher throughput, and ∼102x reduced energy per decision.

    Source: Discussion · p. 8

  • Takeaways & Limitations

    The results indicate potential for analog-CAM hardware to accelerate tree-based machine-learning models, including workloads with high training and inference energy use.

    Source: Performance evaluation · p. 8, Discussion · p. 8

Abstract

from arXiv · show

Tree-based machine learning techniques, such as Decision Trees and Random Forests, are top performers in several domains as they do well with limited training datasets and offer improved interpretability compared to Deep Neural Networks (DNN). However, while easier to train, they are difficult to optimize for fast inference without accuracy loss in von Neumann architectures due to non-uniform memory access patterns. Recently, we proposed a novel analog, or multi-bit, content addressable memory(CAM) for fast look-up table operations. Here, we propose a design utilizing this as a computational primitive for rapid tree-based inference. Large random forest models are mapped to arrays of analog CAMs coupled to traditional analog random access memory (RAM), and the unique features of the analog CAM enable compression and high performance. An optimized architecture is compared with previously proposed tree-based model accelerators, showing improvements in energy to decision by orders of magnitude for common image classification tasks. The results demonstrate the potential for non-volatile analog CAM hardware in accelerating large tree-based machine learning models.

Results

The results establish a compact analog CAM model, map tree paths and forest voting to CAM–RRAM arrays, and optimize their storage and operating parameters. At 16 nm, the architecture outperforms prior accelerators in throughput and energy per decision, with accuracy preserved above a clock-period threshold.

Analog CAM compact model

Mapping DT/RF to analog CAM

  • Decision-tree paths map to CAM rows, with ranges and wildcards encoding feature tests; parallel tree outputs feed RRAM majority voting.RF classification takes four clock cycles, approximately independent of the number of trees.Source: Mapping DT/RF to analog CAM · p. 5

Architecture optimization

  • Reordering features and packing nonempty rows into H×W tiles permits empty right-side arrays to be removed; autoencoder preprocessing further compresses memory at a cost of a few percentage points of accuracy.The autoencoder reduces the feature vector to 32 elements.Source: Architecture optimization · pp. 5, 7

Performance evaluation

  • For tCLK > 1 ns, accuracy is preserved while throughput reaches 60×10^6 decisions/sec; the selected tile size is 16×480.The clock-period condition allows match-line discharge in the chosen conductance range.Source: Performance evaluation · p. 7, Figure 5 · p. 8
  • At 16 nm, the architecture outperforms existing accelerators in throughput and energy per decision; pipelining trades power against throughput at constant energy.The comparison uses constant-field scaling; the trade-off allows power and throughput to be modulated.Source: Performance evaluation · pp. 7–8

Discussion

The proposed analog-CAM tree accelerator maps root-to-leaf paths to array rows for rapid inference. At a scaled technology node, it reports lower power, higher throughput, and reduced energy per decision than the state of the art.

Discussion

  • At a scaled technology node, the design achieves ∼2x lower power, ∼103x higher throughput, and ∼102x reduced energy per decision versus the state of the art.The comparison table caption reports up to 103x better throughput and up to ∼2x less power.Source: Discussion · p. 8, Table 1 · p. 8

Methods

The methods integrate memristors with CMOS, simulate and model analog CAM behavior, train and tune Random Forests, and estimate power for a pipelined architecture.

Memristor integration

  • Memristors were integrated monolithically on CMOS fabricated at a 180 nm technology node.The device stack uses a 4.5 nm tantalum oxide switching layer between patterned electrodes.Source: Memristor integration · p. 9

Analog CAM circuit simulation

  • Analog CAM arrays were simulated in Cadence Virtuoso with TSMC 180 nm and 16 nm libraries, using custom scripts to configure array dimensions, conductances, and input voltages.Post-processing used HP-SPICE.Source: Analog CAM circuit simulation · p. 9

Analog CAM model

  • The behavioral CAM model fits circuit-simulation outputs with simplified physical laws, modeling input transistors in subthreshold or ohmic regimes and the inverter as a sigmoid.The output transistor is modeled in saturation during the initial discharge phase; post-layout parasitics are included in the model setup.Source: Analog CAM model · p. 9

Models training

  • Random Forests were trained on the benchmark’s eight classes and 2,300 training and 200 testing images, with tree count and maximum depth tuned to reach 96.5% analog-CAM accuracy.The reference model used 64 trees with maximum depth 6 and 94% accuracy.Source: Models training · p. 9

Power consumption calculation

  • Pipelined-architecture power estimates separate voltage-divider static power, data-line charging, and match-line charging and discharging.The match-line calculation treats its first term as charging energy and its second as per-cell discharging energy.Source: Power consumption calculation · pp. 9–10

Author contributions statement

The statement assigns the paper’s tree-mapping, compact-model, experimental, analysis, and machine-learning design work to named authors, and identifies supervision and manuscript review.

Author contributions statement

ABSTRACT

The paper maps large Random Forests to analog CAM arrays coupled with RAM for rapid tree inference, using analog CAM features for compression and performance. Its comparison with prior tree-model accelerators reports orders-of-magnitude improvements in energy per decision for common image-classification tasks.

ABSTRACT

  • Orders-of-magnitude improvement in energy per decision is reported for common image-classification tasks versus previously proposed tree-based accelerators.The abstract attributes the design to analog CAM arrays coupled with traditional RAM and says analog CAM features enable compression and high performance.Source: ABSTRACT · p. 14
  • The measured 64×64 memristor matrix includes devices stuck at low or high conductance, so cumulative-distribution plots use the best 128 of 256 devices.Source: Figure 1 · p. 15
  • The traffic-image input is resized from 32×32 to 16×16, histogram-equalized, converted to grayscale, and flattened before CAM lookup and RAM-based majority voting.Source: Figure 4 · p. 19
  • The Random Forest hyperparameter scan varies tree count and maximum depth, excluding accuracy values below 0.96 to match the reference 0.94 accuracy once non-idealities are included.Source: Figure 5 · p. 20

Related papers

Loading 2103.08986v2…