SAT Solving with GPU Accelerated Inprocessing
Open Access
- 20 March 2021
- book chapter
- Published by Springer Nature
- Vol. 12651, 133-151
Abstract
Since 2013, the leading SAT solvers in the SAT competition all use inprocessing, which unlike preprocessing, interleaves search with simplifications. However, applying inprocessing frequently can still be a bottle neck, i.e., for hard or large formulas. In this work, we introduce the first attempt to parallelize inprocessing on GPU architectures. As memory is a scarce resource in GPUs, we present new space-efficient data structures and devise a data-parallel garbage collector. It runs in parallel on the GPU to reduce memory consumption and improves memory access locality. Our new parallel variable elimination algorithm is twice as fast as previous work. In experiments our new solver ParaFROST solves many benchmarks faster on the GPU than its sequential counterparts.Keywords
This publication has 34 references indexed in Scilit:
- Reducing Higher-Order Theorem Proving to a Sequence of SAT ProblemsJournal of Automated Reasoning, 2013
- Parallel Variable Elimination on CNF FormulasLecture Notes in Computer Science, 2013
- Efficient reconstruction of biological networks via transitive reduction on general purpose graphics processorsBMC Bioinformatics, 2012
- GPUs as an opportunity for offloading garbage collectionACM SIGPLAN Notices, 2012
- Simulating Circuit-Level Simplifications on CNFJournal of Automated Reasoning, 2011
- An Extensible SAT-solver2004
- On a generalization of extended resolutionDiscrete Applied Mathematics, 1999
- GRASP: a search algorithm for propositional satisfiabilityIEEE Transactions on Computers, 1999
- Symbolic Model Checking without BDDs1999
- Combinational test generation using satisfiabilityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996