.png){kind=icon}
.png){kind=icon}
Return
Accelerating a continuous-time analog SAT solver using GPUs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cpc.2020.107469.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Recently, a continuous-time, deterministic analog solver based on ordinary differential equations (CTDS) was introduced, to solve Boolean satisfiability (SAT), a family of discrete constraint satisfaction problems. Since SAT is NP-complete, efficient algorithms would benefit solving a large number of decision type problems, both within industry and the sciences. Here we present a graphics processing units (GPU) based implementation of the CTDS and its variants and show that one can achieve significantly improved performance within a wide range of SAT problems. We present and discuss three versions of our GPU implementation and compare their performance to CPU implementations, showing an improvement factor of up to two orders of magnitude. We illustrate the performance of our GPU-based solver on random SAT problems and a notoriously difficult graph coloring problem, the Ramsey number problem R(3, 3, 3, 3), and compare it with the state-of-the-art SAT solver MiniSAT's performances on CPUs. (c) 2020 Elsevier B.V. All rights reserved.
Keywords:
GPU acceleration
Boolean satisfiability
NP-complete
Continuous-time algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
1.2W
Citations:
3.7W