Design of fault-tolerant hypercube computers.

This thesis addresses the design of hypercube or hypercube-like message-passing computers that combine high fault tolerance with high performance. The computers are modeled by graphs in which nodes represent processors and edges represent bidirectional communication links between processors. The main issues addressed are fault-tolerant communication, structural reconfiguration strategies, and gracefully degradable designs. First, a deadlock-free fault-tolerant routing scheme is developed for an n-dimensional hypercube based on a novel "unsafe" node concept. Information about the unsafe nodes provides guidance for messages to avoid excessive routing delays due to faults. The length of a message path is no longer than the minimum path length plus two, if the number of faults is no more than $\lceil n/2\rceil$. Broadcasting is achieved with at most n + 1 steps. Compared to prior methods, our approach significantly reduces the communication performance degradation under fault conditions. Next, we examine the important area of reconfiguration which has received little attention. We point out that by carefully embedding the application graphs, important structural properties can be preserved under fault conditions, and reconfiguration can be carried out efficiently. The basic idea is to embed application graphs so that spare nodes are always close to failed nodes whenever reconfiguration is needed. The application graphs considered include paths, even-length loops, meshes, toruses and complete binary trees. The node utilization of these embeddings is reasonably high, while the reconfiguration process is relatively fast. Finally, we consider modifying the structure of an n-dimensional hypercube by adding nodes and links to increase its fault tolerance. A new measure of performance degradation is introduced. This characterizes a fault-tolerant hypercube as k-fault-tolerant (k-FT) g-step-degradable (g-SD) if the removal of any k nodes reduces the dimension of the largest fault-free subcube by at most g. We show how to construct k-FT g-SD hypercubes for values of k up to 16 and g = 0, 1 or 2. We also propose a construction method that uses small k-FT g-SD designs as seeds to construct k-FT g-SD designs of larger sizes. This results in fault-tolerant hypercubes in which reconfiguration can be first done locally, and then easily extended to the entire system.PhDComputer Science and EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/105231/1/9116234.pdfDescription of 9116234.pdf : Restricted to UM users only