Dagster: Parallel Structured Search
Mark Alexander Burgess, Charles Gretton, Josh Milthorpe, Luke Croak, Thomas Willingham, Alwen Tiu
Abstract
We demonstrate Dagster, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments. Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems. Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes. We demonstrate Dagster using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).
BibTeX
@article{Burgess_Gretton_Milthorpe_Croak_Willingham_Tiu_2024, title={Dagster: Parallel Structured Search}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/27060}, DOI={10.1609/aaai.v37i13.27060}, abstractNote={We demonstrate Dagster, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments.
Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems.
Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes.
We demonstrate Dagster using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).}, number={13}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Burgess, Mark Alexander and Gretton, Charles and Milthorpe, Josh and Croak, Luke and Willingham, Thomas and Tiu, Alwen}, year={2024}, month={Jul.}, pages={16404-16406} }