DEADLOCK-PREVENTING ROUTING IN HYPERCYCLES

Hypercycles make up a class of multidimensional graphs obtained by all owing each dimension to incorporate more than two elements and a cycli c interconnection. Hypercycles offer simple routing and the ability, g iven a fixed degree, to choose among a number of graphs of varying siz e. These graphs can be used in the design of interconnection networks for distributed systems tailored specifically to the topology of a par ticular application. We present and prove a deadlock-preventing routin g strategy for a subset of hypercycles, and a VLSI hypercycle router c omponent which implements the deadlock-preventing routing.