Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Achlioptas, D., Moore, C.: Random k-SAT: two moments suffice to cross a sharp threshold. SIAM J. Comput. 36(3), 740–762 (2006)
Braunstein, A., Mézard, M., Weigt, M., Zecchina, R.: Constraint satisfaction by survey propagation. In: Computational Complexity and Statistical Physics, p. 107 (2005)
Braunstein, A., Mézard, M., Zecchina, R.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27(2), 201–226 (2005)
Braunstein, A., Zecchina, R.: Survey propagation as local equilibrium equations. J. Stat. Mech. Theory Exp. 2004(06), P06007 (2004)
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM (1971)
Dechter, R.: Constraint Processing. Morgan Kaufmann, Burlington (2003)
Fujii, H., Fujimoto, N.: GPU acceleration of BCP procedure for SAT algorithms. IPSJ SIG Notes 8, 1–6 (2012)
Gallager, R.G.: Low-density parity-check codes. IRE Trans. Inf. Theory 8(1), 21–28 (1962)
Levin, L.A.: Average case complete problems. SIAM J. Comput. 15(1), 285–286 (1986)
Luo, Z., Liu, H.: Cellular genetic algorithms and local search for 3-SAT problem on graphic hardware. In: IEEE Congress on Evolutionary Computation, CEC 2006, pp. 2988–2992. IEEE (2006)
Manolios, P., Zhang, Y.: Implementing survey propagation on graphics processing units. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 311–324. Springer, Heidelberg (2006)
Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812–815 (2002)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Burlington (2014)
Tao, T., Xuejun, Y., Yisong, L.: Locality analysis and optimization for stream programs based on iteration sequence. J. Comput. Res. Dev. 6, 027 (2012)
Wang, J.: Average-case computational complexity theory. In: Complexity Theory Retrospective II, pp. 295–328 (1997)
Wen, M., Su, H., Wei, W., Wu, N., Cai, X., Zhang, C.: High efficient sedimentary basin simulations on hybrid CPU-GPU clusters. Cluster Comput. 17(2), 359–369 (2014)
Zhang, H.: SATO: an efficient prepositional prover. In: McCune, W. (ed.) CADE 1997. LNCS, vol. 1249, pp. 272–275. Springer, Heidelberg (1997)
Zhang, H., Bonacina, M.P., Hsiang, J.: PSATO: a distributed propositional prover and its application to quasigroup problems. J. Symbolic Comput. 21(4), 543–560 (1996)
Acknowledgements
This work is funded by National Science Foundation of China (number 61303070). Dr. Jingfei Jiang was an academic visitor at University of Manchester. We acknowledge TianHe-1A supercomputing system service.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhao, Y., Jiang, J., Wu, P. (2016). Improved Survey Propagation on Graphics Processing Units. In: Huang, X., Xiang, Y., Li, KC. (eds) Green, Pervasive, and Cloud Computing. Lecture Notes in Computer Science(), vol 9663. Springer, Cham. https://doi.org/10.1007/978-3-319-39077-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-39077-2_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-39076-5
Online ISBN: 978-3-319-39077-2
eBook Packages: Computer ScienceComputer Science (R0)