UC Santa Barbara

Many of the hardest and most fascinating problems in science and engineering can be formulated as optimization tasks. Learning in biological systems and artificial neural networks, for example, is an optimization process, as are challenges in logistics, robotics, and biomedical applications that require finding exact or near-optimal ground states of discrete polynomial functions of arbitrary order. Many such problems are NP-Hard/Complete and remain computationally expensive to solve on conventional computers. This has driven the development of Ising machines that are hardware solvers that aim to find the absolute/approximate ground state of the Ising model, to which the objectives of the original optimization problem have been mapped. Despite their success in solving optimizations with quadratic objective functions, most state-of-the-art Ising machines, being limited to natively implementing up to second-order interactions, are likely to incur considerable penalties in convergence times on higher-order optimization problems such as Boolean Satisfiability (K-SAT), Max-K-Cut and Max-K-SAT. This is due to an exponential increase in search space caused by the order reduction step that converts the high-order objective function to a quadratic one. Nevertheless, high-order problems are widespread in fields like electronic structure prediction, network routing, model verification, cryptography, and this necessitates the development of high-order Ising Machines. This dissertation attempts to address this need through advancements in algorithm, architecture, and integrated circuit design. We present a new hardware paradigm that enables massively parallel computation of high-order gradients using mixed-signal in-memory computing circuits. It is shown for the first time, that a pair of back-to-back connected crossbar arrays with appropriate peripheral circuits can provide extremely fast solutions to high-order optimization problems with hardware complexity that scales linearly with the number of variables and terms in the objective function but independent of the order (K). This approach is experimentally validated with an optimization chip (tuned to solving K-SAT), taped out in 55 nm CMOS technology. The integrated circuit features custom SRAM based in-memory computing arrays, analog-input Winner-Take-All circuits, and achieves one to two orders of magnitude speedup over prior solvers, despite implementing a legacy SAT-solving algorithm. We introduce a new probabilistic SAT-solving algorithm that leverages the bipartite clause-variable relationship to update multiple variables per iteration, thereby improving navigational efficiency and outperforming several prior algorithms. A second chip demonstrating this algorithm is taped out in 55 nm CMOS technology. It improves upon the parallelization capabilities of the previous chip and incorporates dynamic comparator based Probabilistic-bits (p-bits) to eliminate the need for ADCs or analog-domain reduction circuits (a critical bottleneck in analog in-memory computing). The chip exhibits the fastest-to-date convergence times on small-scale K-SAT problems and outperforms prior hardware (including those designed in more advanced 28 nm) by 4-13 times. Through hardware-aware simulations, we present a framework for implementing different flavors of gradient computing circuits in high-order ising machines, as well as extended circuit implementations for natively mapping and solving high-order XOR/parity-based constraints. Furthermore, we present a multi-tile architecture that enables scaling these solvers to handle large high-order optimization problems. The architecture consists of mixed-signal in-memory compute cores interconnected by a field programmable gate array-inspired reconfigurable routing fabric. Analog computations are performed locally within each tile, whereas ADC-free peripheral circuits confine inter-tile communication to the digital domain. Finally, an outlook to the future of such solvers is presented, in addition to progress and preliminary results on hardware architectures for accelerating complete SAT solvers and tape-out of a Floating-gate based analog in-memory computing macro for implementing high-order Ising machines with multi-bit weights.