Interconnection networks: Regularity and richness

In this dissertation we investigate a model of a general-purpose parallel machine commonly referred to as a massively parallel processor array (MPPA). An MPPA is able to solve large problems efficiently by employing a large number of intercommunicating processing elements. It is our thesis that certain structural properties of interconnection networks, which we will refer to as regularity and richness, impact on the computational behavior of MPPAs in essential ways. We support this thesis by examining the significant role these structural properties have in the understanding of parallel computation productivity. In the Prolegomena (Part 0) we introduce terminology, our computational model, and mathematical preliminaries. We show how both structured, regular networks and unstructured, random-like networks are constructed. For each of these two classes of networks we examine their computational strengths and weaknesses. In Part 1 we focus on the issue of fault tolerance of MPPA machines. We show that MPPAs built upon certain structurally regular, decomposable networks have an ability to perform efficient computations even when the PEs fail randomly. We develop a formal framework in which to design reconfiguration algorithms that allow a MPPA possessing randomly distributed faulty PEs to emulate the computations of a fault-free network of the same size and topology. Our results show that, with high probability, an n-node torus network with uniformly distributed faulty processors can emulate a fault-free n-node torus network with a slowdown factor of $O(\sqrt{{\rm log}\ n})$. For the n-node deBruijn and the n-node butterfly networks, our reconfiguration algorithm yields an emulation that incurs a slowdown factor of O(loglog n). In Part 2 we present a case study that suggests a network cannot simultaneously achieve regularity and richness. We show that Cayley graphs do not yield the rich connectivity properties associated with random-like graphs when the algebraic structure of the underlying group is not complicated. By deriving upper bounds on the size of node bisectors, and lower bounds on the diameters of these classes of Cayley graphs we show that such regularly structured graphs cannot enjoy the expansion property that has been shown to be such a useful tool in theoretical studies. (Abstract shortened with permission of author.