基于通用比较模型的t-可诊断系统的特征化及并行诊断算法

The Characterization of t-Diagnosable Systems Based on the Generalized Comparison Model and a Parallel Algorithm for Diagnosis

文中介绍了一种系统级故障诊断模型——通用比较模型 .该模型允许处理器作为自身的比较器 ,综合了经典的 PMC模型和 Maeng/ Malek模型的优点 .基于该模型 ,分析了多处理器系统的 t- 可诊断性问题 ,给出了 t- 可诊断系统的特征化 ,证明了一个系统成为 t- 可诊断系统的新的充分必要条件 .其次 ,证明了在通用比较模型中 ,确定故障处理器集的问题等价于求解一个超图的最小横切集 (Minimum traversal) ,该超图是根据多处理器的通信图和比较图求得的 .最后 ,给出了特定情况下的一个系统级故障诊断并行算法 ,该算法是完全分布的 。

A model, namely the generalized comparison model, is introduced for system level fault diagnosis in this paper. It allows a processor to be the comparator of itself and another processor, and combines the advantages of both the classical PMC model and the Maeng/Malek model. Based on this model, the problem of t -diagnosability of multiprocessor systems is analyzed, the characterization of t -diagnosable systems is presented and a new necessary and sufficient condition for a system to be t -diagnosable is proven. Once a multiprocessor system is judged to be t -diagnosable, the following problem is to identify all the faulty processers. It is shown in this paper that the problem of identifying the set of faulty processors in the system is equivalent to the problem of finding a minimum traversal of a hypergraph which is constructed according to the interconnection graph and the comparison graph of a given multiprocessor system. The way to construct the hypergraph under the general comparison model is somewhat different from that under the MM model. Since finding a minimum traversal of a hypercube is a difficult problem, a special case is considered and a parallel algorithm for system level fault diagnosis is given. This algorithm is fully distributed and optimal with respect to the number of message transmissions.