Abstract Combinatorial optimization (CO) underpins critical applications in science and engineering, ranging from logistics to electronic design automation. A classic example of CO is the NP-complete Traveling Salesman Problem (TSP). Finding exact solutions for large-scale TSP instances remains computationally intractable; on von Neumann architectures, such solvers are constrained by the memory wall, incurring compute-memory traffic that grows with instance size. Metaheuristics, such as simulated annealing implemented on compute-in-memory (CiM) architectures, offer a way to mitigate the von Neumann bottleneck. This is accomplished by performing in-memory optimization cycles to rapidly find approximate solutions for TSP instances. Yet this approach suffers from degrading solution quality as instance size increases, owing to inefficient state-space exploration. To address this, we present LIMO, a programmable mixed-signal computational macro that implements an in-memory annealing algorithm with reduced search-space complexity. The annealing process is aided by the stochastic switching of spin-transfer-torque magnetic-tunnel-junctions (STT-MTJs) to escape local minima. For large instances, our macro co-design is complemented by a refinement-based divide-and-conquer algorithm amenable to parallel optimization in a spatial architecture. Consequently, our system comprising several LIMO macros achieves superior solution quality and faster time-to-solution on instances up to 85,900 cities compared to prior hardware annealers. The modularity of our annealing peripherals allows the LIMO macro to be reused for other applications, such as vector-matrix multiplications (VMMs). This enables our architecture to support neural network inference. As an illustration, we show image classification and face detection with software-comparable accuracy, while achieving lower latency and energy consumption than baseline CiM architectures.
Holla et al. (Sat,) studied this question.