Implementing Survey Propagation on Graphics Processing Units

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

Last modified: Thu Jul 20 06:07:30 EDT 2006 manolios@cc.gatech.edu

Back to Pete's home page College of Computing