3SAT on an all-to-all-connected CMOS Ising solver chip

Husrev Cilasun, Ziqing Zeng, Ramprasath S, Abhimanyu Kumar, Hao Lo, William Cho, William Moy, Chris H. Kim, Ulya R. Karpuzcu, Sachin S. Sapatnekar

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

This work solves 3SAT, a classical NP-complete problem, on a CMOS-based Ising hardware chip with all-to-all connectivity. The paper addresses practical issues in going from algorithms to hardware. It considers several degrees of freedom in mapping the 3SAT problem to the chip—using multiple Ising formulations for 3SAT; exploring multiple strategies for decomposing large problems into subproblems that can be accommodated on the Ising chip; and executing a sequence of these subproblems on CMOS hardware to obtain the solution to the larger problem. These are evaluated within a software framework, and the results are used to identify the most promising formulations and decomposition techniques. These best approaches are then mapped to the all-to-all hardware, and the performance of 3SAT is evaluated on the chip. Experimental data shows that the deployed decomposition and mapping strategies impact SAT solution quality: without our methods, the CMOS hardware cannot achieve 3SAT solutions on SATLIB benchmarks. Under the assumption of some hardware improvements, our chip-based 3SAT solver demonstrates a remarkable 250× acceleration compared to Tabu search in dwave-hybrid on a CPU.

Original languageEnglish (US)
Article number10757
JournalScientific reports
Volume14
Issue number1
DOIs
StatePublished - Dec 2024

Bibliographical note

Publisher Copyright:
© The Author(s) 2024.

PubMed: MeSH publication types

  • Journal Article

Fingerprint

Dive into the research topics of '3SAT on an all-to-all-connected CMOS Ising solver chip'. Together they form a unique fingerprint.

Cite this