News for hackers. Stuff that matters.
Re:The Silent (R)evolution of SAT by thesz on Friday May 26, 2023 @10:44AM (#36084856)
GPU's are not friends with pointer chasing, which is the basis of contemporary CDCL solvers, because internal lazily-updateable structures are multi-linked lists.

They are not friends with bottlenecks like clause queues used in contemporary stochastic SAT solvers.

They can be good at something like survey and/or belief propagation [1].

[1] https://simons.berkeley.edu/talks/belief-survey-propagation

The problem is that survey/belief propagatin is effective in the area of random CNF problems and it is not a complete solution technique. It may compute a solution but it cannot provide you with the evidence that there is no soolution.

Re:The Silent (R)evolution of SAT by bmc7505 on Friday May 26, 2023 @11:48AM (#36085729)
My hunch is that CDCL is probably the wrong approach to take for parallelization due to synchronization issues. You want an algorithm that is communication-free or makes belief propagation wall-clock competitive for large set of instances. It should be possible to modify BP to be asymptotically complete by using a special-purpose PRNG that ensures samples are drawn uniformly without replacement from the search space, but I'm not sure how to make it more sample-efficient.