Cayley networks: A group-theoretic approach to the design and analysis of parallel networks.

摘要

Cayley network is defined to be a parallel network that has an underlying topology of a Cayley graph. Many families of parallel networks built in practice and proposed in the literature can be characterized as Cayley networks, and a multitude of structural and computational benefits ensue from their underlying group-theoretic structure. Also, the structural uniformity of Cayley networks can be exploited to attack many problems from within a single framework.;In the first part of this thesis we study Cayley networks with respect to the issues of communication, reliability and the mapping problem. We discuss several schemes for performing point-to-point routing in Cayley networks and present a general strategy for finding efficient permutation routes. The strategy applies to many familiar networks in the literature, including toroidal mesh networks, hypercube networks, butterfly networks, star networks and a large class of double-ring networks. Often, the routes we derive are the most efficient currently known to exist. On the topic of reliability, we study the connectivity of Cayley graphs and derive a general inductive tool for this purpose. Specific applications of this tool include new proofs of results by Godsil (49) and Akers and Krishnamurthy (3). With regard to the mapping problem, we present several methods for embedding a Cayley graph in a direct product graph. As a consequence, we describe work-preserving emulations of Cayley networks on a family of smaller networks, thereby exposing a processor-time tradeoff.;In the second part of this thesis we prove the following combinatorial results: (1) We present an embedding of the N-node deBruijn network into the N-node hypercube network with dilation