----------------------------------------------
|          TECHNICAL REPORT ECE-94-2           |
|                  April 1994                  |
| Dept. of Electrical and Computer Engineering |
|           University of Victoria             |
 ----------------------------------------------

TITLE:   Topological Optimization in Hypercycle based 
	 Interconnection Networks

AUTHORS: R. Sivakumar and N. J. Dimopoulos

NOTE:    Submitted for publication

ABSTRACT

A major step in designing a highly efficient and reliable
interconnection network for parallel computer systems is 
finding a topology with minimum diameter and average distance 
for a given set of constraints such as the number of nodes, 
degree and dimension of the network. The average distance is 
related to the network latency and hence dictates the 
performance of a parallel computer. This work focuses on 
hypercycles which are a class of multidimensional, symmetric 
graphs for computer interconnection networks with variable 
diameter, simple routing and incremental expandability. These 
graphs encompass a wide spectrum of interconnection networks
including the ring, torus, binary $n$-cube, $k$-ary $n$-cubes, 
generalized hypercubes and can be viewed as products of 
circulant graphs. In this report, we present new results on 
the synthesis of cost optimal hypercycle network topologies 
for average distance, diameter and product of degree and 
diameter. Analytical solutions are derived, wherever possible  
and these are compared with numerical results of the 
optimization.