PRESTO: A Processing-in-Memory-Based k-SAT Solver Using Recurrent Stochastic Neural Network With Unsupervised Learning

In this article, we introduce a processing-in-memory (PIM)-based satisfiability (SAT) solver called Processing-in-memory-based SAT solver using a Recurrent Stochastic neural network (PRESTO), a mixed-signal circuit-based PIM (MSC-PIM) architecture combined with a digital finite state machine (FSM) for solving SAT problems. The presented design leverages a stochastic neural network with unsupervised learning. PRESTO's architecture supports fully connected <tex-math notation="LaTeX">k</tex-math> -SAT clauses with mixed- <tex-math notation="LaTeX">k</tex-math> problems, highlighting its versatility in handling a wide range of SAT challenges. A test chip is fabricated in 65-nm CMOS technology with a core size of 0.4 mm <tex-math notation="LaTeX">²</tex-math> and demonstrates an operating frequency range of 100–500 MHz and a peak power of 35.4 mW. The measurement results show that PRESTO achieves a 74.0% accuracy for three-SAT problems with 30 variables and 126 clauses.