A Stochastic Analog Boolean Satisfiability Solver

Shiyu Su

doi:10.1109/JSSC.2025.3617458

A Stochastic Analog Boolean Satisfiability Solver

2025-10-24

0

PRE

AI

DOI：10.1109/JSSC.2025.3617458

Original

Original request for help

Save

Abstract

En 中文

This article presents a stochastic analog Boolean satisfiability (SAT) solver, featuring a fast open-loop architecture with continuous-time (CT) self-loopback pull-up switches, a discrete-time (DT) scrambling scheme, and a cost-efficient hybrid random code generator. The SAT prototype demonstrates 100% solvability and 3.5- $\mu $ s solution time with 8.6-nJ energy consumption for 1000 hard benchmark problems (20 variables and 91 clauses) in 65-nm complementary metal–oxide–semiconductor (CMOS), achieving over $1000\times $ improvement in solution time compared to the prior analog SAT solver, and more than $10\times $ improvement compared to state-of-the-art digital SAT solvers implemented in a similar process without additional pre-processing. Moreover, the proposed SAT solver is highly flexible and modular, allowing a low-complexity, low-cost, and scalable design.

Keywords:

Accelerator

analog

complementary metal–oxide–semiconductor (CMOS)

computing

continuous-time (CT)

discrete-time (DT)

pseudo-noise (PN) generator

satisfiability (SAT)

solver

stochastic

A Stochastic Analog Boolean Satisfiability Solver

Abstract

Journal

Organization