TL;DR
This paper introduces DART, a novel algorithm for diagnosing hardware faults in computer systems by leveraging hierarchical design models. By breaking down diagnosis into manageable levels, DART significantly reduces the computational cost of test generation, making it practical for complex modern systems.
What Problem Does This Paper Address?
Diagnosing hardware failures in complex computer systems is a significant challenge. Traditional diagnostic approaches often rely on extensive rule-based systems that associate symptoms with specific faults, which are difficult and time-consuming to build and maintain for new devices. Furthermore, existing test generation algorithms, like the d-algorithm, become computationally intractable for the large number of components in modern systems due to their gate-level focus and exponentially growing test generation costs. The paper aims to address this by developing a more efficient and scalable diagnostic approach.
Methods
DART employs a general inference procedure, specifically linear-input resolution guided by meta-level control rules, to diagnose faults. Its core innovation lies in exploiting the hierarchical structure inherent in most computer system designs. The diagnosis process starts at a high level of abstraction, identifying suspect subcomponents, and then progressively refines the diagnosis by focusing on lower levels of detail until a replaceable part is identified. This hierarchical approach keeps the number of components under consideration at any one time small, thus managing the cost of test generation.
For diagnosis at each level, DART uses a deductive procedure. It reasons backward from observed symptoms (violations of expected behavior) to identify justifications for these violations. All components mentioned in these justifications become suspects. To discriminate among suspects, DART generates tests by working forward from behavioral rules to observable outputs and backward to modifiable inputs, creating specific input-output expectations.
The system uses a design description language called SUBTLE, which can represent both structural and behavioral information at various levels of abstraction. Key assumptions like the "single fault assumption" (at most one component is faulty) and "nonintermittency" (devices behave consistently over time) can be formally encoded to improve efficiency.
Datasets
Not discussed in the paper. The paper focuses on the algorithm and its application to a hypothetical circuit and mentions testing on the IBM 4331 teleprocessing facility.
Key Insights and Ideas
- Hierarchical Diagnosis is Key: The most significant insight is that exploiting the hierarchical nature of system designs dramatically reduces the complexity of fault diagnosis. This allows for manageable test generation costs even for very large systems.
- Design Models as the Foundation: DART's reliance on structural and behavioral design models, rather than pre-programmed fault rules, makes it adaptable to new devices. If a design is available in a computer-aided design system, it can be directly used by DART.
- Deductive Reasoning from Symptoms: The algorithm's ability to reason backward from symptoms to identify suspect components and then generate discriminating tests is a powerful approach.
- Efficiency Gains: The paper quantifies the computational advantage of hierarchical diagnosis, showing that for a device with H levels and N gates per level, the cost can be reduced from F(NH) to H*F(N), a significant saving, especially for non-linear cost functions.
Key Results
The paper demonstrates that DART can generate appropriate tests and diagnose underlying faults. While specific quantitative results are not detailed for all examples, the authors state that the algorithm was tested on simple circuits and complex systems like the IBM 4331 teleprocessing facility. The diagnosis time for these cases was on the order of minutes when running on a VAX-11/780. The program was able to diagnose large circuits without significant slowdown.
Limitations and Future Work
- Completeness: The authors acknowledge that the DART algorithm is "almost complete." While a variant using ancestry-filtered resolution is guaranteed to generate every test, the described version might sometimes produce a set of tests that is inadequate to localize every fault due to the limited vocabulary at a given description level.
- Efficiency: While hierarchical diagnosis offers substantial computational savings, the worst-case runtime for test generation is still NP-complete, meaning it can be exponential in the number of subparts.
- Future Work: The paper suggests that the implementation could be improved with more efficient programming styles. The authors also highlight the promise of DART for coping with the increasing complexity of modern computer system designs.
Summary updated