HordeSat

HordeSat: a massively parallel portfolio SAT solver. 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. par 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.


References in zbMATH (referenced in 14 articles )

Showing results 1 to 14 of 14.
Sorted by year (citations)

  1. Froleyks, Nils; Heule, Marijn; Iser, Markus; Järvisalo, Matti; Suda, Martin: SAT competition 2020 (2021)
  2. Manthey, Norbert: The \textscMergeSatsolver (2021)
  3. Schreiber, Dominik; Sanders, Peter: Scalable SAT solving in the cloud (2021)
  4. Heisinger, Maximilian; Fleury, Mathias; Biere, Armin: Distributed cube and conquer with Paracooba (2020)
  5. Pulina, Luca; Seidl, Martina: The 2016 and 2017 QBF solvers evaluations (QBFEVAL’16 and QBFEVAL’17) (2019)
  6. Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman: Sequential and parallel algorithms and data structures. The basic toolbox (2019)
  7. Avis, David; Jordan, Charles: \textttmplrs: a scalable parallel vertex/facet enumeration code (2018)
  8. Audemard, Gilles; Lagniez, Jean-Marie; Szczepanski, Nicolas; Tabary, Sébastien: A distributed version of Syrup (2017)
  9. Bychkov, Igor; Oparin, Gennady; Feoktistov, Alexander; Bogdanova, Vera; Sidorov, Ivan: The service-oriented multiagent approach to high-performance scientific computing (2017)
  10. Le Frioux, Ludovic; Baarir, Souheib; Sopena, Julien; Kordon, Fabrice: Painless: a framework for parallel SAT solving (2017)
  11. Lindauer, Marius; Hoos, Holger; Leyton-Brown, Kevin; Schaub, Torsten: Automatic construction of parallel portfolios via algorithm configuration (2017)
  12. Nejati, Saeed; Newsham, Zack; Scott, Joseph; Liang, Jia Hui; Gebotys, Catherine; Poupart, Pascal; Ganesh, Vijay: A propagation rate based splitting heuristic for divide-and-conquer solvers (2017)
  13. Balyo, Tomáš; Lonsing, Florian: HordeQBF: a modular and massively parallel QBF solver (2016)
  14. Balyo, Tomáš; Sanders, Peter; Sinz, Carsten: HordeSat: a massively parallel portfolio SAT solver (2015)