Greetings,
We are pleased to announce that the following paper has been accepted in
the 25th International Conference on Tools and Algorithms for the
Construction and Analysis of Systems (TACAS'19). Please find the title
and abstract below.
Title and authors:
"Modular and Efficient Divide-and-Conquer SAT Solver on Top of the
Painless Framework"
Ludovic Le Frioux (1,2)
Souheib Baarir (1,2,3)
Julien Sopena (2,4)
Fabrice Kordon (2)
(1) LRDE, EPITA, F-94043, Le Kremlin-Bicêtre
(2) Sorbonne Université, CNRS, LIP6, UMR 7606, F-75005, Paris
(3) Université Paris Lumières, Université Paris Nanterre, F-92000,
Nanterre
(4) Inria, DELYS Team, F-75005, Paris
Abstract:
Over the last decade, parallel SATisfiability solving has been widely
studied from both theoretical and practical aspects. There are two main
approaches. First divide-and-conquer (D&C) splits the search space, each
solver being in charge of a particular subspace. The second one
portfolio launches multiple solvers in parallel, and the first to find a
solution ends the computation. However although D&C based approaches
seem to be the natural way to work in parallel, portfolio ones
experimentally provide better performances. An explanation resides on
the difficulties to use the native formulation of the SAT problem (i.e.,
the CNF form) to compute an a priori good search space partitioning
(i.e., all parallel solvers process their subspaces in comparable
computational time). To avoid this, dynamic load balancing of the search
subspaces is implemented. Unfortunately, this is difficult to compare
load balancing strategies since state-of-the-art SAT solvers
appropriately dealing with these aspects are hardly adaptable to various
strategies than the ones they have been designed for. This paper aims at
providing a way to overcome this problem by proposing an implementation
and evaluation of different types of divide-and-conquer inspired from
the literature. These are relying on the Painless framework, which
provides concurrent facilities to elaborate such parallel SAT solvers.
Comparison of the various strategies are then discussed.
More information at:
https://www.lrde.epita.fr/wiki/Publications/le-frioux.19.tacas