TL;DR
This paper introduces "phase-to-primitive decomposition," a hardware-software co-design methodology that allows irregular, multi-phase algorithms to run entirely on-chip using in-memory computing (IMC). By mapping the distinct phases of Monte Carlo Tree Search (MCTS) to specialized memory primitives (CAM, SRAM, RRAM, and combinational logic), the authors created an accelerator that consumes just ~60 mW. This architecture delivers up to a 2,059× energy efficiency boost over an NVIDIA H100 GPU, enabling data-center-grade AI planning on power-constrained edge devices.
What Problem Does This Paper Address?
Monte Carlo Tree Search (MCTS) is a powerful decision-making algorithm responsible for milestones in AI like AlphaGo, as well as practical applications in robotic path planning and molecular optimization. However, MCTS is notoriously power-hungry, typically drawing 55–300 W on conventional processors. This high power consumption confines MCTS to data centers and keeps it out of reach for milliwatt-scale embedded platforms like autonomous drones, surgical robots, or wearable medical devices.
The root cause is structural: MCTS relies on irregular tree traversals, heavy control-flow branching, and frequent statistical updates. These operations parallelize poorly on standard CPUs and GPUs, leading to massive energy waste from data movement. While in-memory computing (IMC) drastically reduces data movement by co-locating compute and storage, it has traditionally only been compatible with highly regular, uniform workloads like deep learning matrix multiplications. This paper addresses the fundamental challenge of adapting IMC to irregular, multi-phase algorithms.
Methods
The authors propose a four-step framework called phase-to-primitive decomposition: profile the algorithm's phases, match each phase to a native IMC primitive, reformulate incompatible phases, and compose them into an end-to-end on-chip pipeline.
They applied this methodology to create IMC-MCTS, mapping the four core phases of MCTS to four distinct hardware primitives on a single substrate:
- Selection: Restructured from a pointer-chasing hash-table traversal into a parallel associative lookup using a Content-Addressable Memory (CAM) array, enabling $O(1)$ single-cycle selection.
- Expansion: Handled by a Game Logic Unit (GLU) built from combinational logic, evaluating all board cells simultaneously to generate legal moves in a single cycle.
- Rollout: Replaced variable-length random simulations with a fixed-latency neural network evaluator mapped onto an analog Resistive RAM (RRAM) crossbar, eliminating weight-fetching overhead.
- Backpropagation: Executed via in-place read-modify-write operations directly inside an on-chip SRAM bank using saturating counters, keeping all search data on-chip.
A Ternary CAM (TCAM)-based Finite State Machine (FSM) orchestrates the entire four-stage pipeline to maintain deterministic timing and prevent pipeline stalls.
Datasets
The primary benchmark used to evaluate decision quality and hardware scaling was the game of Go (evaluated on board sizes ranging from $2\times2$ up to $19\times19$, with $9\times9$ as the primary baseline).
To demonstrate that the architecture is application-agnostic, the authors also evaluated the exact same hardware substrate across eight grid-based decision applications spanning four AI domains:
- Strategy Games: Connect Four, Othello, Hex, and Go.
- Navigation: FrozenLake and MiniGrid.
- Scientific Optimization: Hydrophobic-polar (HP) protein folding.
- Puzzles: Minesweeper.
Key Insights and Ideas
- Heterogeneous IMC Substrates: Traditional IMC architectures rely on a single primitive (usually an analog crossbar for matrix math). This paper demonstrates that co-locating multiple, qualitatively distinct primitives (analog RRAM alongside digital CAM and SRAM) yields massive efficiency gains for complex algorithms.
- Load-Bearing Co-Dependence: The hardware primitives reinforce one another. For example, the CAM's single-cycle lookup latency prevents pipeline stalls that would otherwise leave the analog RRAM crossbar sitting idle.
- Algorithmic Noise Absorption: Analog RRAM crossbars are prone to hardware non-idealities like conductance noise. Crucially, the authors realized that MCTS's inherent statistical averaging over hundreds of search iterations naturally absorbs this analog noise, meaning device-level imperfections do not degrade overall playing strength.
Key Results
- Exceptional Energy Efficiency: At a 22-nm process node, the IMC-MCTS chip consumes only ~60 mW during a sustained 5,000-iteration search on $9\times9$ Go. This achieves a 96× energy efficiency gain over a CPU baseline and a 65× to 2,059× gain over an NVIDIA H100 GPU (depending on the GPU's batch size).
- Uncompromised Decision Quality: In a 1,050-game tournament, the IMC-MCTS hardware achieved a European Go Federation (EGF) rating of ~1727 (3 kyu), performing on par with established open-source software engines (Michi-C and Pachi-UCT) at matched compute.
- Substrate Reusability: Without any architectural modifications or rewriting RTL, the chip successfully executed all eight cross-domain tasks simply by reprogramming the RRAM crossbar weights.
Limitations and Future Work
- Grid-World Constraints: The current accelerator specifically targets grid-representable state spaces. Adapting the architecture to non-grid spaces (such as continuous robotic control or large-graph routing) will require encoding modifications.
- Silicon Validation: While the hardware was modeled using parameters from fabricated RRAM arrays and characterized via standard tools (Synopsys Design Compiler, CACTI, SST), full end-to-end physical silicon validation is still noted as the next step.
- Scaling for Professional Play: The current neural evaluator is lightweight (trained on a 2,000-position budget). Scaling up to professional-tier play (dan level) will require expanding the crossbar capacity to accommodate larger, deeper neural networks.
Summary updated