Amoeba-Inspired Stochastic Hardware SAT Solver

Kazuaki Hara, Naoki Takeuchi, Masashi Aono, Yuko Hara-Azumi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)


Since the end of Dennard scaling is almost approaching, new types of computing methods and architectures are being sought. As one of such architectures, hardware solvers for satisfiability (SAT) problems are getting more attentions these days because combinatorial optimization problems residing in many types of Internet-of-Things (IoT) and embedded systems applications can be transformed to SAT problems. In this paper, we present a novel, fast FPGA-based SAT solver with fine-grained parallelism. We particularly focus on a recently-developed SAT algorithm, AmoebaSAT, which abstracts shape-changing dynamics of an amoeba. Our hardware AmoebaSAT solver can enjoy high parallelism in quickly searching a solution (i.e., a satisfiable combination of variables assignment) for a given SAT instance, with a help of stochastic features to avoid local search. Our evaluations demonstrated that our work can outperform state-of-the-art on WalkSAT, another SAT algorithm which has been popular and widely-used for decades.

Original languageEnglish
Title of host publicationProceedings of the 20th International Symposium on Quality Electronic Design, ISQED 2019
PublisherIEEE Computer Society
Number of pages6
ISBN (Electronic)9781728103921
Publication statusPublished - 2019 Apr 23
Event20th International Symposium on Quality Electronic Design, ISQED 2019 - Santa Clara, United States
Duration: 2019 Mar 62019 Mar 7

Publication series

NameProceedings - International Symposium on Quality Electronic Design, ISQED
ISSN (Print)1948-3287
ISSN (Electronic)1948-3295


Conference20th International Symposium on Quality Electronic Design, ISQED 2019
Country/TerritoryUnited States
CitySanta Clara

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Amoeba-Inspired Stochastic Hardware SAT Solver'. Together they form a unique fingerprint.

Cite this