A Compute-in-Memory Annealing Processor With Interaction Coefficient Reuse and Sparse Energy Computation for Solving Combinatorial Optimization Problems

Abstract

Since combinatorial optimization problems (COPs) are a class of non-deterministic polynomial-time (NP)-hard prob- lems, it is impracticable to solve them in brute-force searches, which results in high energy consumption and long computation latency. The annealing processors based on the Ising model are naturally oriented to find approximate solutions. However, these processors face the challenges of frequent data movement between computing elements and memory units, resulting in significantly large area and high energy consumption. To address these issues, we present a fully digital annealing processor based on compute-in-memory (CIM) architecture. To enhance area efficiency, a CIM coefficient array is designed with an interaction coefficient reuse strategy. Moreover, a sparsity-aware adder tree is proposed to reduce unnecessary add operations, which can improve the energy efficiency. For searching the lowest energy state of the Ising model, a nonlinear probability flipping (NPF) approximate circuit is designed, which is based on a voting mechanism and on-chip random number generation with low hardware overhead. The proposed annealing processor is fabricated in a 55-nm CMOS process and used to solve the max-cut problem as well as the image segmentation problem. The measured results confirm the high energy efficiency (2.4 fJ at 0.9 V per spin) and the high area efficiency (402 µm2 per spin).