HordeSat: a massively parallel portfolio SAT solver
From MaRDI portal
Abstract: A simple yet successful approach to parallel satisfiability (SAT) solving is to run several different (a portfolio of) SAT solvers on the input problem at the same time until one solver finds a solution. The SAT solvers in the portfolio can be instances of a single solver with different configuration settings. Additionally the solvers can exchange information usually in the form of clauses. In this paper we investigate whether this approach is applicable in the case of massively parallel SAT solving. Our solver is intended to run on clusters with thousands of processors, hence the name HordeSat. HordeSat is a fully distributed portfolio-based SAT solver with a modular design that allows it to use any SAT solver that implements a given interface. HordeSat has a decentralized design and features hierarchical parallelism with interleaved communication and search. We experimentally evaluated it using all the benchmark problems from the application tracks of the 2011 and 2014 International SAT Competitions. The experiments demonstrate that HordeSat is scalable up to hundreds or even thousands of processors achieving significant speedups especially for hard instances.
Recommendations
Cites work
- A high-performance, portable implementation of the MPI message passing interface standard
- A parallelization scheme based on work stealing for a class of SAT solvers
- An overview of parallel SAT solving
- GridSAT: Design and implementation of a computational grid application
- scientific article; zbMATH DE number 5613972 (Why is no real title available?)
- Incorporating clause learning in grid-based randomized SAT solving
- Inprocessing rules
- Lazy clause exchange policy for parallel SAT solvers
- ManySAT: a parallel SAT solver
- Space/time trade-offs in hash coding with allowable errors
- Theorem proving using lazy proof explication.
Cited in
(18)- \texttt{mplrs}: a scalable parallel vertex/facet enumeration code
- SAT competition 2020
- The \textsc{MergeSat} solver
- Scalable SAT solving in the cloud
- Solving SAT in a distributed cloud: a portfolio approach
- The 2016 and 2017 QBF solvers evaluations (QBFEVAL'16 and QBFEVAL'17)
- Deterministic parallel DPLL
- HordeQBF: a modular and massively parallel QBF solver
- Community branching for parallel portfolio SAT solvers
- ManySAT: a parallel SAT solver
- Distributed domain propagation
- Computing storyline visualizations with few block crossings
- Automatic construction of parallel portfolios via algorithm configuration
- The service-oriented multiagent approach to high-performance scientific computing
- Towards better heuristics for solving bounded model checking problems
- Unsatisfiability proofs for distributed clause-sharing SAT solvers
- Parallel clause sharing strategy based on graph structure of SAT problem
- Producing proofs of unsatisfiability with distributed clause-sharing SAT solvers
Describes a project that uses
Uses Software
This page was built for publication: HordeSat: a massively parallel portfolio SAT solver
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453220)
