Improved Survey Propagation on Graphics Processing Units

摘要

The development of graphic processing units (GPUs) ensures a significant improvement in parallel computing performance. However, it also leads to an unprecedented level of complexity in algorithm design because of its physical architecture. In this paper, we propose an improved survey propagation (SP) algorithm to solve the Boolean satisfiability problem on GPUs. SP is a CPU-based incomplete algorithm that can solve hard instances of k-CNF problems with large numbers of variables. In accordance with the analysis on NVIDIA Kepler GPU architecture, a more efficient algorithm is designed with methods of changing data flow, parallel computing, and hiding communication. For NVIDIA K20c and Intel Xeon CPU E5-2650, our proposed algorithm can obtain speed 4.76 times faster than its CPU counterpart.