Massively Parallel Continuous Local Search for Hybrid SAT Solving on GPUs
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
MathOptAI.jl: Embed trained machine learning predictors into JuMP models
ConsumerBench: Benchmarking Generative AI Applications on End-User Devices
Versatile and Fast Location-Based Private Information Retrieval with Fully Homomorphic Encryption over the Torus
SecONNds: Secure Outsourced Neural Network Inference on ImageNet
Plug-and-Play Linear Attention for Pre-trained Image and Video Restoration Models
FlashDMoE: Fast Distributed MoE in a Single Kernel
토론
이 논문과 연결된 포럼 글이 아직 없습니다.