Towards High-Order Ising Machine Accelerators and SAT Solvers

What is it about?

High-order Combinatorial Optimization Problems (COPs) are widespread and arise in circuit routing, software verification, protein folding, electronic structure prediction and other areas in operations research. The objective of the solvers of such problems is to find minima of a polynomial function and gradient computation constitutes the core operation. Iterative gradient computation for all variables is a computationally intensive task due to the large number of matrix-vector multiplications involved. On the other hand, current state-of-the-art hardware is restricted to computing gradients of quadratic polynomial functions and not scalable to high-order functions. In this paper we lay down the foundational architectural principles behind a new hardware paradigm that can compute gradients directly in the native high-order space, in a massively parallel fashion using principles of in-memory computing (to perform computation using memory). This could enable the advent of hardware accelerators like physical High-Order Ising Machines, SAT solvers to name a few, for solving increasingly relevant high-order COPs.

Featured Image

Photo by Igor Omilaev on Unsplash

Photo by Igor Omilaev on Unsplash

Why is it important?

Solving large-scale instances of NP-hard/complete Combinatorial Optimization Problems (COPs) using conventional computers is intractable due to fundamental limitations in the underlying Von Neumann architecture of such computing schemes. This is why dedicated hardware accelerators for solving COPs are receiving increasing focus in both academia and industry. However, when it comes to high-order COPs (for example the k-Boolean Satisfiability problem, with k > 2), current state-of-the-art hardware cannot be directly used as they are restricted to second-order gradient computations. High-order functions need to be quadratized before they can be implemented on such hardware. This leads to exponentially increased search space due to addition of extra variables and therefore solution times scale poorly with increasing problem size and order. Our proposed hardware can compute gradients directly in the native high-order space and therefore prevents blowing up of search space. Our experimentally grounded models show that such hardware when designed using mixed-signal integrated CMOS-memristor technology, could lead to several orders of magnitude improvement in speed and energy efficiency compared to current alternative computing methods.