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

Abstract

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