FYalSAT: High-Throughput Stochastic Local Search K-SAT Solver on FPGA

Abstract

The satisfiability (SAT) problem is a fundamental challenge in computing and has a broad range of applications. This problem is NP-complete, and many algorithmic and architectural improvements have aimed at accelerating the SAT solver. But most existing stochastic local search (SLS) hardware solvers still rely on the outdated WalkSAT algorithm, and they have a reduced performance when handling problems with a large number of literals per clause. In this paper, we present FYalSAT, a field-programmable gate array (FPGA) based SLS SAT solver designed for high throughput. We incorporate a conflict-free data rearrangement scheme and a novel synchronization method to increase the parallelism. We also apply various optimizations such as clause prefetching, module overlapping, and pipelining to improve the performance. Experimental results demonstrate that FYalSAT outperforms the throughput of existing SLS FPGA solvers by $9.07\times $ – $110\times $ for benchmarks with a large number of literals per clause.

Keywords

• Field-programmable gate arrays
• satisfiability problem
• stochastic local search
• accelerator architecture