TL;DR
This paper introduces PQSOLVE, a novel distributed algorithm for solving Quantified Boolean Formulas (QBFs), a computationally challenging problem. By parallelizing an efficient sequential QSAT solver (QSOLVE) and employing advanced scheduling heuristics, PQSOLVE achieves significant speedups, demonstrating the viability of distributed approaches for QBF evaluation.
What Problem Does This Paper Address?
Quantified Boolean Formulas (QBFs) are a generalization of the well-known Boolean Satisfiability (SAT) problem. While SAT is NP-complete, QBFs are PSPACE-complete, making them even harder to solve. QBFs appear in various fields like automated reasoning, computer-aided design, and planning. The challenge lies in efficiently determining whether a given QBF is satisfiable, especially as the number of variables and quantifiers grows. Existing sequential QSAT solvers, while improving, still struggle with large instances. This paper addresses the need for a more scalable solution by exploring parallel and distributed approaches.
Methods
The core of this work is the development of QSOLVE, a sequential QSAT solver that builds upon the Davis-Putnam procedure for SAT. QSOLVE incorporates several enhancements:
- Improved Data Structures: Generalizing SAT-solver data structures to efficiently handle clause and variable deletions and undos.
- Heuristic Enhancements: Implementing and refining heuristics like Trivial Truth (TTH) and Trivial Falsity (TFH) for early pruning of the search space.
- Inverting Quantifiers (IQ): A novel approximation algorithm for the IQ heuristic, allowing its use during the evaluation process to potentially simplify the problem.
- Adaptive Heuristics: Using history-based heuristics to dynamically decide when to apply expensive tests like TTH and TFH, optimizing their usage.
Building on QSOLVE, the paper presents PQSOLVE, a distributed QSAT solver. The parallelization strategy is inspired by techniques used in distributed game tree search (specifically, chess programs). Key aspects include:
- Dynamic Load Balancing: Idle processors request work from busy ones, and a master-slave relationship is established for subproblem evaluation.
- Scheduling Heuristics: To manage the complexities of distributed search, several heuristics are introduced:
- Helpful Master Scheduling (HMS): Allows a master processor to request work from its slave when waiting for a result, preventing idle time.
- Young Brothers Wait Scheduling (YBWS): Delays the parallel evaluation of siblings until at least one successor is fully evaluated, aiming to leverage cutoffs from the sequential search. This is applied to blocks of variables in PQSOLVE.
- Unique IDs: Each node in the search tree is assigned a unique ID to manage message ordering and validity in a distributed environment.
Datasets
The paper evaluates PQSOLVE on a set of 48 randomly generated QSAT instances. These instances are based on Model A from (Gent and Walsh 1999), featuring approximately 120 variables, clause length of four, and a fraction of ∃-variables of 25%. The number of clauses varies from 416 to 736. These instances are described as "hard," requiring considerable time for sequential solvers.
Key Insights and Ideas
- Parallelism is Effective for QSAT: The paper demonstrates that distributed computing can significantly accelerate QSAT solving, a problem known for its PSPACE-completeness.
- Heuristics are Crucial for Efficiency: The success of both the sequential QSOLVE and the parallel PQSOLVE hinges on the intelligent application of various heuristics (TTH, TFH, IQ, and scheduling heuristics). These heuristics are not just about finding a solution but about pruning the search space effectively.
- "Superlinear" Speedup is Possible: The authors observe speedups greater than the number of processors used, a phenomenon attributed to the highly irregular search trees of QSAT instances and the effectiveness of load balancing in exploiting these irregularities. This suggests that the sequential algorithm might not be optimal in its search order.
- Distributed Game Tree Techniques Translate Well: The parallelization strategy, borrowed from chess programs, proves effective for QSAT, highlighting commonalities in tackling complex search problems.
Key Results
- QSOLVE Performance: The sequential QSOLVE solver is shown to be faster than previously known QSAT solvers like EVALUATE, QKN, and QBF on benchmark instances.
- PQSOLVE Speedup: On 128 processors, PQSOLVE achieves an impressive speedup of about 114 over the sequential version. This represents an efficiency of approximately 90%.
- Reduced Recursions: PQSOLVE requires about 30% fewer recursions than QSOLVE, indicating that the parallel version does less overall work, contributing to the superlinear speedup.
- Trivial Falsity Test Impact: The paper highlights that the new Trivial Falsity test, combined with HMS scheduling, leads to significant savings in terms of recursions and running time (average savings of 11.57% in time).
Limitations and Future Work
- Random Instances: The encouraging results were obtained on randomly generated instances. The authors plan to test PQSOLVE on structured instances in the future.
- Trivial Falsity Test Improvement: The authors are currently analyzing the Trivial Falsity test, exploring potential improvements by modifying how the conflict-free set is determined or by using multiple sets.
- Further Analysis of Trivial Falsity: The test for trivial falsity might offer new theoretical insights into the nature of randomly generated QSAT instances.
- Adaptive Heuristic Tuning: The constants used in the adaptive heuristics (e.g., for TTH) were determined through program optimization on small benchmarks, suggesting that further tuning might be beneficial.
Summary updated