Abstract
FASTDIAGP is a parallelized evolution of the FASTDIAG algorithm designed to identify inconsistent constraints in complex systems. By employing speculative programming to pre-calculate consistency checks across multiple CPU cores, the algorithm achieves up to a 40% reduction in runtime. Evaluation on large-scale Linux kernel configurations demonstrates its effectiveness, particularly in high-cardinality diagnosis tasks.
Introduction
In constraint-based applications—such as software configuration, scheduling, or recommendation systems—users often provide requirements that conflict with the underlying rules of the knowledge base. When this occurs, systems typically return a "no solution found" error. To resolve this, algorithms like FASTDIAG are employed to find a "preferred minimal diagnosis": the smallest set of user requirements that must be modified to restore consistency.
However, FASTDIAG relies heavily on consistency checks—expensive calls to a solver—which are traditionally performed sequentially. For massive knowledge bases, such as the Linux kernel configuration, this sequential bottleneck makes real-time, interactive diagnosis impossible. FASTDIAGP addresses this by parallelizing the search process through speculative execution.
Methods
FASTDIAGP integrates a speculative look-ahead mechanism into the diagnosis process. Instead of waiting for the main algorithm to request a consistency check, FASTDIAGP "guesses" which checks might be needed next based on the current state of the search tree.
Speculative Programming and Dual-Branch Prediction
Because FASTDIAG is a divide-and-conquer algorithm, the look-ahead mechanism explores two scenarios simultaneously: "What if the current set is consistent?" and "What if it is inconsistent?" It then schedules checks for both paths in parallel.
Global LOOKUP Table and Resource Management
All results from speculative checks are stored in a shared global lookup table. When the main algorithm requires a result, it performs a simple O(1) lookup instead of an expensive solver call. To prevent system saturation, the algorithm uses a resource-aware scheduling parameter (maxGCC) to limit speculative tasks based on available CPU cores.
Results
The researchers evaluated FASTDIAGP using the Linux-2.6.33.3 feature model, which contains over 6,000 features and 7,000 constraints. By testing over 20,000 inconsistent requirement sets with varying diagnosis cardinalities, the authors found that FASTDIAGP consistently outperformed the sequential version. Speedup values ranged between 1.28x and 1.65x, representing a runtime reduction of up to 40%.
Interestingly, performance peaked at 8 CPU cores. Beyond this point, the overhead of managing speculative "guesses" began to outweigh the benefits of additional parallel solver calls. The algorithm proved particularly effective as the "diagnosis cardinality" (the number of conflicting constraints) increased, demonstrating superior scalability for complex "broken" configurations.
Conclusion
FASTDIAGP provides a significant performance boost for direct diagnosis in large-scale configuration tasks. By leveraging speculative parallelism, it moves closer to the goal of providing near-instant feedback to users. Future work will explore breadth-first search strategies for the speculative mechanism and further optimize the look-ahead logic to better utilize high-core-count architectures.
Summary updated