Compressed High-Order Ising Machines

Abstract

We propose a "compressed" memory-centric high-order Ising machine (IM) architecture for solving hard optimization problems, featuring guaranteed log-linear hardware area scaling with the number of variables. The key feature of the proposed architecture is a novel unit cell for coupling spins, more complex than comparable IM cells. This unit cell keeps a local copy of a specific spin value, which can be updated when receiving a message of that variable's change on a common bus. The unit cell also includes circuitry for computing a high-degree product that contributes to the partial derivative of another spin. Because the position of the coupling term in the coupling matrix array is no longer determined by the row and column indices of the constituent spins, we observe up to 75% unit cell utilization in relevant benchmarks. The compressed architecture is especially useful for Boolean satisfiability (SAT) problems, the focus of this study, in that it enables implementation of an "enhanced" Ising machine architecture that preserves clause-variable membership information of the mapped problem. K-SAT problems can be embedded in their native form, allowing such problems to be solved not only by conventional simulated-annealing-based high-order Ising machine dynamics but also with more competitive heuristics inspired by the state-of-the-art SAT solving algorithms. A detailed circuit architecture and design automation methods for mapping SAT problems are presented, and post-layout SPICE simulations are performed. Modeling results for solving random uniform problems show that even the simplest, sequential version of the proposed approach, in which only one spin is flipped at a time, is significantly faster and has comparable energy efficiency while being almost an order of magnitude more compact than previously reported work on combinatorial optimization solvers.