Tradeoffs in system level diagnosis of multiprocessor systems

The development of LSI technology makes it possible to partition a system into replaceable modules, and the advent of low-cost microprocessors makes possible networks of hundreds (or more) of interconnected modules. The problem of repairing such a system is becoming a matter of major importance in digital systems.

In this paper a new procedure for defining an optimal design with respect to cost of repair for a system consisting of replaceable modules (processors) is introduced. Also the tradeoff between the number of repetitions of the diagnostic test (speed of diagnosis), the number of testing links in the system (complexity), and the number of replaced fault-free modules (accuracy) is considered.

In an early paper, Preparata, Metze, and Chien⁴ formulated a model of system level diagnosis and defined two types of diagnosability measures, i.e. one-step t-fault diagnosability, and sequential t-fault diagnosability. They proved that D_δt is one-step t-fault diagnosable and single loop connection is sequentially t-fault diagnosable. Friedman¹² later generalized this measure to one-step t-out-of-S (t/S) diagnosability, in which t faults are diagnosed to within S ≥ t modules. This introduces the possibility of inexact diagnosis---i.e. such that some fault-free modules may have to be replaced in order to repair a system in one step.

So far most of the results that are available are only for single-loop or D_δt design, and the results for a system in between these two extreme cases are not available. A D_δt system needs more testing links and a single-loop system needs more steps in order to be repaired. In this paper we have defined a design in between D_δt and single-loop systems; also the tradeoff between the number of repetitions of the diagnostic test (speed of diagnosis), the number of testing links (complexity), and the number of replaced fault-free modules (accuracy) is considered, and the optimal design with respect to cost of repair is defined.