Re:Parallelization of SAT Algorithms on GPUs [pdf]
by panic on Friday February 17, 2017 @09:52AM
(#13668576)
Here's a non-paywalled link to [2] if anyone else is looking for it: http://www.ki.inf.tu-dresden.de/~norbert/webdata/publication...
Re:Parallelization of SAT Algorithms on GPUs [pdf]
by p1esk on Friday February 17, 2017 @03:02PM
(#13671230)
the top sequential algorithms still beat parallel solvers
Wow, that's interesting! Are there any other examples where a sequential algorithm beats a parallel one?
Re:Parallelization of SAT Algorithms on GPUs [pdf]
by tlb on Saturday February 18, 2017 @02:14AM
(#13673932)
It is an open question whether there exist algorithms that cannot be parallelized. Some that are most likely to be inherently sequential are listed here: https://en.wikipedia.org/wiki/P-complete#P-complete_problems
The annual SAT competition http://www.satcompetition.org has a track for parallel solving.
See [2, 3, 4] for an overview of the field.
[1] M. J. H. Heule, O. Kullmann, S. Wieringa, A. Biere, Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads.
[2] S. Hölldobler, N. Manthey, V. H. Nguyen, J. Stecklina, P. Steinke, A Short Overview on Modern Parallel SAT-Solvers.
[3] S. Wieringa, K. Heljanko, Asynchronous Multi-Core Incremental SAT Solving.
[4] Y. Hamadi, C. M. Wintersteiger, Seven Challenges in Parallel SAT Solving.