Techniques for Communication in Faulty and Irregular Interconnection Networks

Abstract

This research is about some results in structural fault tolerance and graceful degradation, and also in the design of deadlock-free routing algorithms for arbitrary networks. The first main area presents gracefully degrading pipelines: a pipeline is a linear array of processors with an input node at one end and an output node at the other end. Our results are k-gracefully- degradable graphs which, given any set of up to k faults, contain a pipeline that uses all the healthy processor nodes. Our constructions are designed to tolerate faulty input and output nodes, but they can be adapted to provide optimal solutions when the input and output nodes are guaranteed to be healthy. All of our constructions are optimal in terms of the number of nodes and the maximum degree of the processor nodes. The rest of the dissertation considers the problem of deadlock-free routing in arbitrary parallel and distributed computers. We focus on asynchronous routing algorithms which continuously receive new packets to route and which do not discard packets that encounter congestion. Specifically, we examine what we call the deadlock-free routing (DFR) problem. The input to the DFR problem consists of an arbitrary network and an arbitrary set of paths in the network. The output consists of a routing algorithm, which is a list of the buffers used along each of the paths. The routing algorithm is required to be free from deadlock and the goal is to minimize the number of buffers required in any one node. We study the DFR problem by converting it into an equivalent problem which we call the flattest common supersequence (FCS) problem. The input to the FCS problem consists of a set of sequences and the output consists of a single sequence that contains all of the input sequences as (possibly non-contiguous) subsequences. The goal of the FCS problem is to minimize the maximum frequency of any symbol in the output sequence. In this second area, we present three main results. First, we prove that the decision version of the FCS problem is NP-complete, and has no polynomial-time approximation scheme unless P=NP. Next, we propose and experimentally evaluate a range of heuristics for FCS. Our experimental results show that one of these heuristics performs very well over a wide range of inputs. Lastly, we prove that this heuristic is in fact optimal for certain restricted classes of inputs. To support some of the experimental data, we prove that a lower bound given by Cypher for the total number of buffers required in a routing sequence for ascend-order routing in hypercubes is in fact optimal.