DMC: A Distributed Model Counter

DMC: A Distributed Model Counter

Jean-Marie Lagniez, Pierre Marquis, Nicolas Szczepanski

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1331-1338. https://doi.org/10.24963/ijcai.2018/185

We present and evaluate DMC, a distributed model counter for propositional CNF formulae based on the state-of-the-art sequential model counter D4. DMC can take advantage of a (possibly large) number of sequential model counters running on (possibly heterogeneous) computing units spread over a network of computers. For ensuring an efficient workload distribution, the model counting task is shared between the model counters following a policy close to work stealing. The number and the sizes of the messages which are exchanged by the jobs are kept small. The results obtained show DMC as a much more efficient counter than D4, the distribution of the computation yielding large improvements for some benchmarks. DMC appears also as a serious challenger to the parallel model counter CountAntom and to the distributed model counter dCountAntom.
Keywords:
Constraints and SAT: SAT
Constraints and SAT: SAT: Solvers and Tools