DISTRIBUTED FAULT-DIAGNOSIS IN MULTISTAGE NETWORK-BASED MULTIPROCESSORS

This paper is concerned with a distributed, system-level fault diagnos is scheme for multistage network-based multiprocessors, The target sys tem, which we choose as a representative, employs a multistage interco nnection network (MIN) with 4 x 4 switching elements. We propose a fas t diagnostic method which uses a quadtree [1] and its coupler structur e, These two quadtree structures partition the system into a number of Link-Independent Groups (LIGs), This partitioning provides an importa nt diagnostic property; the communication paths in each LIG are either identical or disjoint. Several previous works in fault diagnosis inve stigated the multistage interconnection network only. This paper prese nts an entire multiprocessor diagnosis, including the detection and lo cation of single faults caused by processor nodes, switching elements, and communication links. In addition, the diagnosis of a group of mul tiple faults partitioned by the tree structures is also discussed.