News for hackers. Stuff that matters.
Re:Parallelization of SAT Algorithms on GPUs [pdf] by mafribe on Friday February 17, 2017 @08:07AM (#13667995)
There is quite a bit of work on parallelising SAT solving, as it's one of the most important algorithmic problems, both in theory and in practise, but (as far as I'm aware) the top sequential algorithms still beat parallel solvers. The most successful approach at this point seems to be Cube-and-Conquer [1], but I don't think this is considered a good approach in itself. There is a huge amount of scope for new ideas. I doubt that anything naive will work, as SAT solving is a rather competitive research field.

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.

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