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

文中介绍了一种系统级故障诊断模型－－通用比较模型，该模型处理器作为自身的比较器，综合经典的ＰＭＣ模型和Ｍａｅｎｇ／Ｍａｌｅｋ模型的优点，基于该报多处理器系统的ｔ＿可诊断性问题，给出了ｔ＿可诊断系统的特征化，证明了一个系统成为ｔ－可诊断系统的新的充分必要条件，其次，证明在通用比较模型中，确定故障顺集的问题等价于求解一个超图的最小横切集（Ｍｉｎｉｍｕｍ ｔｒａｖｅｒｓａｌ），该超图是根据多处理器的通信

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

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.