Panagiotis (Pete) Manolios
College of Computer and Information Science
Northeastern University

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