Processor interconnection networks from Cayley graphs

Cayley graphs of groups are presently being considered by the computer science community as models of architectures for large scale parallel processor computers. In the first section of this paper the authors discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for these types of computers. Observing that routing on a Cayley graph is equivalent to a certain factoring problem in the associated group, they have been able to use a known powerful factoring technique in computational group theory to produce a fast efficient routing algorithm on the associated Cayley graph. In the second section of this paper the authors present this work. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. Believing that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance, the authors designed Cayley graphs to be used in a special study performed at the Supercomputing Research Center (SRC). The importance of the average diameter in determining network performance was supported by the fact that the graphs which they found had the smallest average diameter and outperformed all other graphs evaluated in the study. In fact, before being driven into saturation, one of the authors’ graphs sustained 9.4% more network traffic than the next best candidate, a butterfly architecture, and 74.3% better than the benchmark 2-d mesh. The last section of the present paper is devoted to this work. This paper is divided into three sections. In the first section the authors discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for parallel computers. In the second section they present their research on the routing problem. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. In the last section the authors present some evidence that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance.