Massively Parallel Continuous Local Search for Hybrid SAT Solving on
  GPUs
Yunuo Cen Zhiwei Zhang Xuanyao Fong
Although state-of-the-art (SOTA) SAT solvers based on conflict-driven clause
learning (CDCL) have achieved remarkable engineering success, their sequential
nature limits the parallelism that may be extracted for acceleration on
platforms such as the graphics processing unit (GPU). In this work, we propose
FastFourierSAT, a highly parallel hybrid SAT solver based on gradient-driven
continuous local search (CLS). This is realized by a novel parallel algorithm
inspired by the Fast Fourier Transform (FFT)-based convolution for computing
the elementary symmetric polynomials (ESPs), which is the major computational
task in previous CLS methods. The complexity of our algorithm matches the best
previous result. Furthermore, the substantial parallelism inherent in our
algorithm can leverage the GPU for acceleration, demonstrating significant
improvement over the previous CLS approaches. We also propose to incorporate
the restart heuristics in CLS to improve search efficiency. We compare our
approach with the SOTA parallel SAT solvers on several benchmarks. Our results
show that FastFourierSAT computes the gradient 100+ times faster than previous
prototypes implemented on CPU. Moreover, FastFourierSAT solves most instances
and demonstrates promising performance on larger-size instances.