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 we 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, we 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 we 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, we 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 found by us had the smallest average diameter and outperformed all other graphs evaluated in the study. In fact, before being driven into saturation, one of our graphs sustained 9.4% more network traffic than the next best candidate, a butterfly architecture, and 74.3% better than the bench mark 2-d mesh. The last section of our paper is devoted to this work.

This paper is divided into three sections. In the first section we 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 we present our 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 we present some evidence that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance.