HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Community and LBD-Based Clause Sharing Policy for Parallel SAT Solving

Abstract : Modern parallel SAT solvers rely heavily on effective clause sharing policies for their performance. The core problem being addressed by these policies can be succinctly stated as “the problem of identifying high-quality learnt clauses”. These clauses, when shared between the worker nodes of parallel solvers, should lead to better performance. The term “high-quality clauses” is often defined in terms of metrics that solver designers have identified over years of empirical study. Some of the more well-known metrics to identify high-quality clauses for sharing include clause length, literal block distance (LBD), and clause usage in propagation. In this paper, we propose a new metric aimed at identifying high-quality learnt clauses and a concomitant clause-sharing policy based on a combination of LBD and community structure of Boolean formulas. The concept of community structure has been proposed as a possible explanation for the extraordinary performance of SAT solvers in industrial instances. Hence, it is a natural candidate as a basis for a metric to identify high-quality clauses. To be more precise, our metric identifies clauses that have low LBD and low community number as ones that are high-quality for applications such as verification and testing. The community number of a clause C measures the number of different communities of a formula that the variables in C span. We perform extensive empirical analysis of our metric and clause-sharing policy, and show that our method significantly outperforms state-of-the-art techniques on the benchmark from the parallel track of the last four SAT competitions.
Complete list of metadata

Contributor : Fabrice Kordon Connect in order to contact the contributor
Submitted on : Friday, July 24, 2020 - 7:10:38 PM
Last modification on : Thursday, February 3, 2022 - 11:17:52 AM

Links full text



Vincent Vallade, Ludovic Le Frioux, Souheib Baarir, Julien Sopena, Vijay Ganesh, et al.. Community and LBD-Based Clause Sharing Policy for Parallel SAT Solving. SAT 2020 - 23rd International Conference on Theory and Applications of Satisfiability Testing, Jul 2020, Alghero / Virtual, Italy. pp.11-27, ⟨10.1007/978-3-030-51825-7_2⟩. ⟨hal-02906505⟩



Record views