FASTDIAGP: An Algorithm for Parallelized Direct Diagnosis

Viet-Man Le, Cristian Vidal Silva, Alexander Felfernig, David Benavides, José A. Galindo, Thi Ngoc Trang TranAAAI 2023 · DOI

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.

Example of user requirements ($c_{10}$ to $c_{13}$) used as input for the diagnosis algorithm.

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.

The FASTDIAGP search tree illustrates the recursive divide-and-conquer approach and the return values for each sub-problem.

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

BibTeX
@inproceedings{le2023fastdiagp,
  author = {Viet-Man Le and Cristian Vidal Silva and Alexander Felfernig and David Benavides and José A. Galindo and Thi Ngoc Trang Tran},
  title = {{FASTDIAGP: An Algorithm for Parallelized Direct Diagnosis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25792},
}
Figure