EUVIMEDEUVIMED entdecken
Crossref

SKI-SAT: A CMOS-Compatible Hardware for Solving SAT Problems

Ahmet Yusuf Salim, Bart Selman, Henry Kautz, Zeljko Ignjatovic, Selçuk Köse

IEEE Transactions on Circuits and Systems I: Regular Papers · 2025-10 · 72 (10) · 5926-5937

DOI: 10.1109/tcsi.2025.3554145 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Circuits and Systems I: Regular Papers, 2025-10. Verfasst von Ahmet Yusuf Salim und 4 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 23 Literaturangaben. Gefördert von: Defense Advanced Research Projects Agency (DARPA) Quantum-Inspired Classical Computing (QuICC) Program under the Air Force Research Laboratory.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Nature-inspired computation is receiving increasing attention. Various Ising machine (IM) 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 software-based SAT solvers by significant margins, achieving more than 10 times faster solution and over 300 times less power.

Förderung

  • Defense Advanced Research Projects Agency (DARPA) Quantum-Inspired Classical Computing (QuICC) Program under the Air Force Research Laboratory

Zitieren

APA

Salim, A. Y., Selman, B., Kautz, H., Ignjatovic, Z., & Köse, S. (2025). SKI-SAT: A CMOS-Compatible Hardware for Solving SAT Problems. IEEE Transactions on Circuits and Systems I: Regular Papers, 72(10), 5926-5937. https://doi.org/10.1109/tcsi.2025.3554145

Vancouver

Salim AY, Selman B, Kautz H, Ignjatovic Z, Köse S. SKI-SAT: A CMOS-Compatible Hardware for Solving SAT Problems. IEEE Transactions on Circuits and Systems I: Regular Papers. 2025;72(10):5926-5937. doi:10.1109/tcsi.2025.3554145

BibTeX
@article{Salim2025,
  author = {Salim, Ahmet Yusuf and Selman, Bart and Kautz, Henry and Ignjatovic, Zeljko and Köse, Selçuk},
  title = {SKI-SAT: A CMOS-Compatible Hardware for Solving SAT Problems},
  journal = {IEEE Transactions on Circuits and Systems I: Regular Papers},
  year = {2025},
  volume = {72},
  number = {10},
  pages = {5926--5937},
  doi = {10.1109/tcsi.2025.3554145}
}
Kostenlos starten →