AUTHORS: N. J. Dimopoulos and R. Sivakuamr 

TITLE:   Deadlock-preventing Routing in Hypercycles

IN:      Proceedings of the Canadian Conference on
         Very Large Scale Integration, Banff, Alberta,
         Canada, pp. 7.1 - 7.6, November 14-16, 1993

ABSTRACT

Hypercycles  are a class of multidimensional graphs 
which are products of circulant graphs obtained by 
allowing each dimension to incorporate more than two 
elements and a cyclic interconnection. Hypercycles, 
offer simple routing, incremental expansion, variable 
diameter, enhanced fault-tolerance, and the ability, 
given a fixed degree, to choose among a number of 
alternative size graphs. These graphs can be used in the 
design of interconnection networks for distributed 
systems tailored specifically to the topology of a 
particular application. In this work, we present a 
deadlock-preventing routing strategy for a subset of 
hypercycles and a 1.2 mm CMOS VLSI Hypercycle 
router component which implements the deadlock 
preventing routing.