Implementing Survey Propagation on Graphics Processing Units
Panagiotis Manolios and Yimin Zhang.
SAT 2006, International Conference on Theory and Applications of Satisfiability Testing. © Springer Verlag
We show how to exploit the raw power of current graphics
processing units (GPUs) to obtain implementations of SAT solving
algorithms that surpass the performance of CPU-based
algorithms. We have developed a GPU-based version of the survey
propagation algorithm, an incomplete method capable of solving
hard instances of random k-CNF problems close to the critical
threshold with millions of propositional variables. Our
experimental results show that our GPU- based algorithm attains
about a nine-fold improvement over the fastest known CPU-based
algorithms running on high-end processors.
PDF (110K) © Springer Verlag