News for hackers. Stuff that matters.
Re:Parallelization of SAT Algorithms on GPUs [pdf] by mate_soos on Friday February 17, 2017 @06:50AM (#13667565)
This approach is unworkable, it has been demonstrated many times. I have not only been developing a SAT solver for >7 years (with >9000 commits) but also have participated in the SAT competition in all these years. I used to get a proposal like this a lot (thankfully, they dried up). None of them made it work. I used to work on programming GPGPUs in a professional setting, (rainbow table generators&lookup systems), so I'm not unfamiliar with their advantages and restrictions.

This approach is unworkable because: * propagation needs modification of the watchlist (or it needs to have all literals of all clauses attached, which is incredibly slow and also unworkable) * propagation is actually only about 50-60% of what a solver is doing: conflict resolution, clause database management and inprocessing takes a lot of time * propagation is hard to parallelize as you need to update a global data structure of propagated literals and then act on that * etc

This proposal will not work (and I sure it did not, if it was ever tried) and I don't understand how it got this high at ycombinator. If you want to look at good SAT solvers, look at lingeling, COPMinisat, MiniSat, or CryptoMiniSat. You may learn a lot from them. Easy starting is MiniSat. Good luck :)

Re:Parallelization of SAT Algorithms on GPUs [pdf] by dang on Friday February 17, 2017 @02:05PM (#13670795)
> I don't understand how it got this high at ycombinator

Oh that's easy: because most of us know nothing about SAT solvers other than (maybe) what they are and that they're cool. We need people like you to teach us, so I'm glad you showed up! (A great example of https://meta.wikimedia.org/wiki/Cunningham's_Law.)

Re:Parallelization of SAT Algorithms on GPUs [pdf] by mafribe on Friday February 17, 2017 @08:16AM (#13668054)

   If you want to look at good SAT 
   solvers, look ... CryptoMiniSat.
Any personal relationship with CryptoMiniSat? ;)
Re:Parallelization of SAT Algorithms on GPUs [pdf] by mate_soos on Friday February 17, 2017 @08:56AM (#13668242)
Considering that CryptoMiniSat got 3rd place (after 1st and 2nd both being lingeling) in Parallel SAT solving the last competition, I think it was fair to include it. Sure, it's mine, but I also put it at the end :) Other solvers that are good to look at: glucose and riss. Note that a lot of solvers are variations of MiniSat. riss, ligeling, PrecoSat and CryptoMiniSat are the only ones that substantially differ from MiniSat.
Re:Parallelization of SAT Algorithms on GPUs [pdf] by dlo on Friday February 17, 2017 @09:53AM (#13668588)
Thanks for the recommendations. I love SAT solvers and have been looking for a way to get into them.
Re:Parallelization of SAT Algorithms on GPUs [pdf] by mtve on Friday February 17, 2017 @09:47AM (#13668547)
Google does not know "COPMinisat", would you please clarify?

PicoSAT is also small and easy to embed, however in CryptoMiniSat we trust, thank you very much!

Re:Parallelization of SAT Algorithms on GPUs [pdf] by mate_soos on Friday February 17, 2017 @10:09AM (#13668684)
Sorry, wanted to say CoMiniSatPS, here:

http://cs.nyu.edu/~chanseok/cominisatps/index.html

One of its variants won the Main track of the SAT Competition of 2016, see

http://baldur.iti.kit.edu/sat-competition-2016/index.php?cat...

For all the solvers' source codes, see

http://baldur.iti.kit.edu/sat-competition-2016/solvers/

Re:Parallelization of SAT Algorithms on GPUs [pdf] by pettou on Saturday February 18, 2017 @04:42AM (#13674198)
Please, do you have any recommendations for books about SAT solving for beginners?