Fault-tolerant interconnection networks for multiprocessors.

Abstract

This thesis presents a general theory for analyzing and designing interprocessor communication networks in multiprocessor computers that can tolerate faulty processors and interconnections. Various network architectures containing communication components such as point-to-point connections, shared buses, and dynamic switches are considered. Two fault-tolerance criteria are of concern. Connective fault tolerance requires that the processor connectivity of the system be maintained in the presence of faults, and structural fault tolerance requires the maintenance of a specific interconnection structure. We use graph-theoretic models to represent the systems of interest. We present a novel model, called the processor-bus-link (PBL) graph, in which processors and communication components are represented by two different types of nodes, P-nodes and B-nodes, respectively. This model is simple, but is more general and powerful than previously proposed graph models. We use PBL graphs to study the connective fault tolerance of multiprocessors with respect to processor and interconnection faults. We present a systematic approach to characterizing the maximum number of faults a system can tolerate. We also characterize the minimum fault sets that destroy the processor connectivity of the system. We show that our approach is useful for the design and analysis of highly connected multiprocessors. To address structural fault tolerance, we first consider systems with point-to-point connections. We use ordinary and nonhomogeneous graph models, in which nodes represent components such as processors and I/O devices, and edges represent point-to-point connections among the components. While previous designs use spare nodes (processors) to tolerate faulty edges (dedicated connections), we develop more efficient designs that employ only spare edges. We introduce the concept of critical graph to characterize designs that contain no useless spare edges. This leads to a class of optimal designs that contain the minimum number of spare edges. We also consider using shared buses as the main interconnection mechanism to reduce the interconnection complexity of structurally fault-tolerant multiprocessors. PBL graphs again serve as the system model in this case. We present a method for designing structurally fault-tolerant systems that can efficiently tolerate both processor and bus faults. The systems obtained have lower interconnection cost than most prior designs, and can be implemented by relatively simple switching circuits. They also have the advantages of no single-point failures, low redundancy, local replacement, and fast reconfiguration.