EFFICIENT DEADLOCK-FREE WORMHOLE ROUTING AND VIRTUAL-CHANNEL REDUCTION IN SHUFFLE-BASED NETWORKS

Many aspects of shuffle-based networks have recently been studied by n umerous researchers. However, no attention has been paid to deadlock-f ree wormhole routing algorithms. In this paper, for a set of shuffle-b ased networks, we introduce a graph-partitioning technique that enable s a deadlock-free routing algorithm with fewer virtual channels than t he known algorithms. This is achieved for the de Bruijn digraphs which are shown to require a maximum of m-[(m-1)/r] virtual channels per ph ysical channel, where m is the diameter and r is the radix, Algorithms for the generalized de Bruijn graph, the de Bruijn Cube (dBCube) grap h and the Shuffle-Exchange network are introduced, and virtual channel requirements are determined. The dBCube graph of size (r, N-b, n) req uires a maximum of m-[(m-1)/r] virtual channels for the outcluster cha nnels, and a maximum of m + 1 - [m/r] virtual channels for the inclust er channels in most cases, where m = [log(r) N-b], r is the radix of a generalized de Bruijn graph of size N-b, and n represents the number of dimensions in a binary hypercube. We also show that a maximum of m- [(m-1)/2] virtual channels are required in shuffle-exchange networks w ith 2(m) nodes. (C) 1997 Academic Press.