Turbosat: GPU-CPU Hybrid System Achieves 200x Acceleration of Boolean Satisfiability with Gradient-Guided Optimization

Boolean satisfiability, a fundamental problem in computer science and artificial intelligence, continues to challenge computational resources, and progress in accelerating its solution remains limited. Steve Dai, Cunxi Yu, and Kalyan Krishnamani from NVIDIA, along with Brucek Khailany from NVIDIA, present a novel approach that dramatically accelerates SAT solving by integrating the strengths of parallel and sequential computation. The team formulates the SAT problem in a way that allows it to be optimised using techniques borrowed from neural network training, specifically by treating it as a matrix operation. This allows them to harness the massive parallelism of GPUs to rapidly explore potential solutions, then refine these partial solutions using the established efficiency of CPU-based sequential search, resulting in a hybrid system that achieves speedups exceeding 200x compared to current state-of-the-art solvers on standard benchmark problems.

Differentiable SAT Solving with GPU Acceleration

This research introduces a new method for solving the Boolean Satisfiability Problem, or SAT, by combining the power of GPU-accelerated optimization with traditional CPU-based techniques. The team successfully reformulates SAT as a differentiable problem, allowing them to leverage gradient-based optimization methods for efficient exploration of potential solutions. This innovative approach combines the broad search capabilities of GPUs with the precision of established SAT solvers, resulting in significant performance improvements. The method represents the SAT problem as a differentiable binarized matrix multiplication, enabling the use of powerful parallel processing on GPUs.

This allows the solver to explore a vast solution space much more quickly than traditional methods. The team then integrates this GPU-based optimization with a CPU-based Conflict-Driven Clause Learning solver, guiding its search and improving its efficiency. Experiments demonstrate substantial performance gains compared to standalone CPU solvers, particularly on challenging SAT benchmarks. The approach effectively balances exploration and exploitation of the search space, leading to faster convergence and improved solution quality. The method also demonstrates scalability, showing promise for tackling even larger and more complex SAT instances. The solver achieved a high score in SAT competitions, demonstrating its competitive performance against other state-of-the-art solvers. This versatile technique integrates effectively with different CPU-based solvers, further highlighting its adaptability and potential.

SAT Solving via Parallel Matrix Multiplication

Scientists have pioneered a novel approach to solving the Boolean satisfiability problem, or SAT, by transforming it into a matrix multiplication operation suitable for parallel processing on modern graphics processing units, or GPUs. Unlike traditional sequential SAT solvers, this work converts the core search process into a high-throughput optimization task, taking full advantage of the inherent parallelism of GPU architecture. The method encodes a SAT problem, consisting of variables and clauses, into a Problem Matrix and an Assignment Matrix, enabling the parallel evaluation of numerous potential solutions. The team constructed the Problem Matrix, representing clauses and literals, with dimensions determined by the number of clauses and variables in the SAT problem.

Each row corresponds to a single clause, and columns represent either a variable or its negation, using binary values to indicate presence or absence. Simultaneously, the Assignment Matrix encodes multiple candidate variable assignments, allowing for the parallel evaluation of all assignments across all clauses using GPU hardware. The core of the method involves multiplying these two matrices, resulting in a Result Matrix that indicates the number of satisfied literals in each clause for each attempted assignment. This matrix multiplication, performed in parallel on the GPU, dramatically accelerates the evaluation of potential solutions.

The team then analyzes the Result Matrix to determine which assignments satisfy all clauses, effectively solving the SAT problem. By increasing the number of attempted assignments, the researchers expanded the search space and improved the likelihood of finding a solution. This innovative approach achieved runtime speedups exceeding 200x compared to state-of-the-art CPU-based solvers on benchmark SAT problems.

Hybrid Solver Achieves Major SAT Speedups

Scientists have developed a novel hybrid solving technique for Boolean satisfiability, or SAT, problems, achieving significant speedups over state-of-the-art CPU-based solvers. The work combines parallel differentiable optimization on GPUs with sequential conflict-driven search on CPUs, leveraging the strengths of both approaches. The team formulated the SAT problem as a binarized matrix-matrix multiplication, enabling optimization using a differentiable objective function and gradient-based exploration of the solution space. Experiments conducted on a high-performance computing system equipped with advanced GPUs and CPUs demonstrate substantial performance gains.

The solver achieved runtime speedups ranging from 5. 03x to 258. 08x on satisfiable benchmark problems from the 2024 SAT Competition, compared to the CaDiCaL solver. Notably, the technique achieved a speedup of 1367. 73x during the CDCL refinement phase alone, demonstrating the benefit of initializing with gradient-guided partial assignments.

The method involves extracting assignments for a small fraction of variables from the GPU-driven optimization, using gradient magnitudes to quantify confidence in those assignments. These confident assignments are then used to initialize CPU-based solvers, significantly reducing the time required to find complete solutions. For benchmarks with over 74,000 variables and 393,000 clauses, the solver achieved greater than 10x speedup, and successfully solved problems within 1000 seconds for which the baseline solver timed out after two hours. Specifically, the most challenging benchmarks were solved in seconds, compared to over 20 minutes required by the baseline solver. The team’s approach effectively transforms conflict-driven clause learning from under-informed search into targeted refinement, delivering substantial efficiency gains.

Hybrid Solver Accelerates Boolean Satisfiability Problems

This research presents a novel approach to solving the Boolean satisfiability problem, or SAT, by integrating the strengths of both parallel and sequential search techniques. Scientists successfully reformulated SAT as a differentiable binarized matrix multiplication task, enabling the use of gradient-based optimization on GPUs to rapidly explore potential solutions. This parallel exploration is then combined with the targeted precision of CPU-based conflict-driven search, resulting in a hybrid solver that significantly accelerates the process of finding solutions to complex logical problems. The team demonstrated substantial performance gains, achieving speedups exceeding 200x compared to a state-of-the-art CPU-based solver on standard SAT benchmarks.

Results indicate the solver effectively balances parallel exploration with sequential refinement, consistently solving more problems within a given timeframe and maintaining performance advantages even as problem complexity increases. The achieved PAR2 SAT score of 972. 28, attained without employing techniques like clause sharing or parallel solving, underscores the effectiveness of this innovative hybrid approach. Future work could focus on optimizing the communication between GPUs and CPUs, as well as investigating the potential for applying this hybrid approach to other combinatorial optimization problems beyond SAT.