SKI-SAT: A CMOS-compatible Hardware for Solving SAT Problems
Preprint
Abstract
Nature-inspired computation is receiving increasing attention. Various Ising machine implementations have recently been proven to be effective in solving numerous combinatorial optimization problems including maximum cut, low density parity check (LDPC) decoding, and Boolean satisfiability (SAT) problems. In this paper, a novel method is presented to solve SAT or MAX-SAT problems with a CMOS circuit implementation. The technique solves a SAT problem by mapping the SAT variables onto quantized capacitor voltages generated by an array of nodes that interact through a network of coupling units. The nodal interaction is achieved through coupling currents produced by the coupling units, which charge or discharge capacitor voltages, implementing a gradient descent along the SAT problem's cost function to minimize the number of unsatisfied clauses. The system also incorporates a unique low-complexity perturbation scheme to avoid settling in local minima, greatly enhancing the performance of the system. The simulation results demonstrate that the proposed SKI-SAT is a high-performance and low-energy alternative that surpasses existing solvers by significant margins, achieving more than 10 times faster solution and 300 times less power.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- 3SAT on an all-to-all-connected CMOS Ising solver chipScientific Reports, 2024
- Utilizing Multi-Body Interactions in a CMOS-Based Ising Machine for LDPC DecodingIEEE Transactions on Circuits and Systems I: Regular Papers, 2023
- Experimental investigation of performance differences between coherent Ising machines and a quantum annealerScience Advances, 2019
- Boolean Satisfiability Solvers and Their Applications in Model CheckingProceedings of the IEEE, 2015
- Critical behavior in the computational cost of satisfiability testingArtificial Intelligence, 1996