Augmenting an electronic Ising machine to effectively solve boolean satisfiability

Anshujit Sharma, Matthew K. Burns, Andrew W. Hahn, Michael HuangScientific 2023 · DOI

TL;DR

Researchers have developed an "Augmented" Ising Machine for SAT (AIMS) that overcomes the traditional limitations of physics-based solvers by adding native support for cubic interactions and a novel, hardware-friendly "semantic-aware" annealing schedule. The result is a projected speedup of two to three orders of magnitude over state-of-the-art software and GPU-based SAT solvers.

What Problem Does This Paper Address?

Boolean Satisfiability (SAT) is the "gold standard" of NP-complete problems, used in everything from circuit design to software verification. While conventional von Neumann computers (CPUs) have become incredibly efficient at solving SAT through decades of heuristic refinement, they are hitting a performance wall.

Ising machines—physical systems that solve optimization problems by finding a minimum energy state—offered a promising alternative. However, they faced two major hurdles with SAT:

  1. The Quadratization Tax: Standard Ising machines only support quadratic (2-node) interactions. To solve 3-SAT, the problem must be "quadratized," which increases the number of variables by 4–5x, destroying any initial speed advantage.
  2. Blind Searching: Most Ising machines use problem-agnostic annealing (randomly flipping bits to escape local minima). In contrast, modern software solvers use "semantic" insights—they know which variables are causing the most trouble—to navigate the search space much faster.

Methods

The authors propose AIMS (Augmented Ising Machine for SAT), which introduces two primary innovations:

  • cBRIM (Cubic BRIM): They modified the Bistable Resistively-coupled Ising Machine (BRIM) to natively support cubic interactions ($x_i x_j x_k$). By using simple AND gates as multipliers and exploiting the sparse nature of SAT problems, they kept hardware complexity manageable ($O(N^2)$ instead of $O(N^3)$) while eliminating the need for quadratization.
  • Tanh-Make-Break (TMB) Heuristic: This is a novel annealing schedule inspired by Stochastic Local Search (SLS). It calculates a "make count" (how many clauses flipping a bit would satisfy) and a "break count" (how many it would break). AIMS uses a hardware-friendly tanh function to determine the probability of flipping a bit based on these counts. Crucially, unlike software solvers that flip one bit at a time, AIMS allows multiple variables to flip in parallel without synchronization.

Datasets

The system was evaluated using numerical simulations (verified against Cadence circuit simulations) on several well-known benchmarks:

  • SATLIB: A standard library for SAT instances.
  • 2011 SAT Competition: High-difficulty benchmarks used to test top-tier solvers.
  • Custom "Hard" Instances: The authors generated uniform random instances with a clause-to-variable ratio ($M/N$) of 4.25 and "scale-free" industrial-like instances to test scalability up to 500 variables.

Key Insights and Ideas

  • Parallelism is the Secret Sauce: Software solvers like WalkSAT are limited by sequential bit-flipping. AIMS's dynamical system allows for massive, asynchronous parallel flips, leading to an average flip-rate of 4,250 flips/µs compared to just 6 flips/µs for WalkSAT.
  • Hardware-Native Semantics: By deriving the "make" and "break" counts directly from the incoming electric currents at each node, the researchers proved that "smart" searching doesn't require the overhead of a von Neumann architecture.
  • Stability Matters: The authors performed a Lyapunov stability analysis to prove that their cubic system naturally seeks the local minima of the energy function and stays there once a solution is found (latching).

Key Results

  • Orders of Magnitude Speedup: AIMS is projected to be 2–3 orders of magnitude faster than state-of-the-art software solvers like KISSAT and WalkSAT.
  • GPU Comparison: It outperformed the GPU-based solver ParaFrost by approximately 517x.
  • Efficiency: AIMS visited 134x fewer "phase points" (states) than a basic cubic Ising machine without the TMB heuristic, proving that the semantic-aware annealing is critical for navigating complex landscapes.
  • Physical Footprint: A 500-variable AIMS chip is estimated to consume only ~300 mW of power on a 13 x 13 mm² area using 45nm technology.

Limitations and Future Work

  • Simulation vs. Silicon: The results are based on high-fidelity numerical simulations. While verified against circuit-level tools like Cadence, a physical hardware implementation is required to confirm these projections in the real world.
  • Scalability: The current study focused on problems up to 500 variables. While the $O(N^2)$ complexity is promising, real-world industrial SAT problems can involve millions of variables, necessitating multi-chip architectures or further sparsification techniques.
  • Heuristic Optimization: The authors noted that while the tanh function works well, it may not be the mathematically "optimal" function for the TMB heuristic, leaving room for further algorithmic tuning.

Summary updated

Abstract

With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an "Augmented" Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.
BibTeX
@inproceedings{sharma2023augmenting,
  author = {Anshujit Sharma and Matthew K. Burns and Andrew W. Hahn and Michael Huang},
  title = {{Augmenting an electronic Ising machine to effectively solve boolean satisfiability}},
  booktitle = {Scientific},
  year = {2023},
  doi = {10.1038/s41598-023-49966-6},
}
Figure