A multiprocessor system is fault-tolerant (FT) if it preserves a fault-free subsystem of a predetermined interconnection structure when faults appear. We present a new method for designing FT multiprocessors that can efficiently tolerate both processor and interconnection faults. The approach is general, in that it can be applied to any multiprocessor topology. Shared buses serve as the main interconnection mechanism to minimize the switching logic needed for reconfiguration. We employ processor-bus-link (PBL) graphs to model multiprocessors with either dedicated or shared buses. Both processors and buses are represented as nodes so that bus faults can be considered explicitly and tolerated efficiently by spare buses instead of by spare processors. A minimum number of spare processors and buses are used to reduce hardware overhead. The node covering concept and the maximum-weight spanning tree algorithm are then employed to construct FT systems that have lower interconnection cost than most previous designs. We also present a cost-effective implementation method which is suitable for both static and dynamic reconfiguration techniques. The FT systems obtained have the advantages of no critical single point of failure, low redundancy, local replacement, and simple circuitry for fast reconfiguration.

We present an efficient approach to characterizing the fault tolerance of multiprocessor systems that employ multiple shared buses for interprocessor communication. Of concern is connective fault tolerance, which is defined as the ability to maintain communication between any two fault-free processors in the presence of faulty processors, buses, or processor-bus links. We introduce a model called processor-bus-link (PBL) graphs to represent a multiple-bus system's interconnection structure. The model is more general than previously proposed models, and has the advantages of simple representation, broad application, and the ability to model partial bus failures. The PBL graph implies a set of component adjacency graphs that highlights various connectivity features of the system. Using these graphs, we propose a method for analyzing the maximum number of faults a multiple-bus system can tolerate, and for identifying every minimum set of faulty components that disconnects the processors of the system. We also analyze the connective fault tolerance of several proposed multiple-bus systems to illustrate the application of our method.

We study the structure of fault-tolerant multiprocessor systems that allow one or more communication links to fail. Spare links are employed to tolerate link failures; no redundant processing units are required. Such a multiprocessor is modeled by a graph G whose nodes and edges correspond to the processing units and the links, respectively. G is a k-edge fault-tolerant design of a basic graph H, denoted k-EFT(H), if every graph obtained by removing any k edges from G embeds H. If G contains the fewest edges among all k-EFT designs of H, then G is said to be optimally k-EFT with respect to H. We introduce the concept of critical edges and graphs and derive some of their properties that are generally useful in designing optimal EFT supergraphs. We investigate the theory of edge fault tolerance for tree-structured networks, in particular, nonhomogeneous trees and stars. For both cases, we obtain optimal k-EFT designs for all k. © 1996 John Wiley & Sons, Inc.

A system is structurally fault-tolerant (SFT) if it preserves a fault-free subsystem of a pre-determined interconnection structure when faults appear. We present a systematic approach to designing SFT VLSI-based systems that use shared buses as the main communication mechanism. To represent the target systems, we introduce a processor-bus-link (PBL) graph in which processing elements (PEs) and buses are both modeled as nodes. PE and bus faults correspond to the removal of nodes from the PBL graph. The node covering concept and the minimum-weight spanning arborescence algorithm are then applied to the design of SFT systems that can tolerate both PE and bus faults. The designs obtained have fewer spare communication ports than prior designs, no critical single point of failure, and simple circuitry for reconfiguration.>