Designing and reconfiguring fault-tolerant multiprocessor systems.

Abstract

This thesis presents a general theory for designing multiprocessor computer systems that can tolerate faulty processors. It is especially concerned with structural fault tolerance, defined as the ability to reconfigure around faults in order to preserve the interconnection structure of a multiprocessor. A major goal is to model some important practical design features not previously addressed, including applicability to any multiprocessor structure and any number of faults. Low hardware overhead and efficient reconfigurability are also important goals. The systems of interest and their faults are represented by graphs, and reconfiguration is modeled by graph-to-graph mappings that replace faulty structures by nonfaulty ones. Within this framework, two general design methodologies for fault tolerance are defined. The first approach called node covering performs reconfiguration by mapping a node (processor) to one of a specific subset of other nodes called its covers. The relation between nodes and their covers is represented efficiently by covering graphs. We show how to design k-fault-tolerant trees from their covering graphs. The resulting designs are near-optimal with respect to hardware cost. We also generalize the node-covering approach to arbitrary multiprocessor graphs, and demonstrate that the resulting fault-tolerant designs have low-cost practical implementations. Our second design theory uses graph automorphisms to represent the reconfiguration process. We demonstrate the efficacy of this theory by applying it to hypercube multiprocessors, and obtain fault-tolerant designs that are superior to those proposed in previous work. We also apply automorphisms to local sparing, which associates spare nodes with disjoint groups of processors to simplify reconfiguration. Two local sparing techniques are developed, one to tolerate fault clusters, and the other to tolerate arbitrary faults. The theory underlying the node-covering and automorphic methods, and the relation between them are studied in depth. The two design methods are shown to complement each other over a wide range of different multiprocessor systems. We also demonstrate that they successfully address all the practical design criteria stated earlier. They thus provide a powerful new methodology for designing and evaluating fault-tolerant multiprocessor systems.