Efficient Deadlock-Free Wormhole Routing and Virtual-Channel Reduction in Shuffle-Based Networks
✍ Scribed by Hyunmin Park; Dharma P. Agrawal
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 401 KB
- Volume
- 46
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Many aspects of shuffle-based networks have recently been studied by numerous researchers. However, no attention has been paid to deadlock-free wormhole routing algorithms. In this paper, for a set of shuffle-based networks, we introduce a graph-partitioning technique that enables a deadlock-free routing algorithm with fewer virtual channels than the 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 physical channel, where m is the diameter and r is the radix. Algorithms for the generalized de Bruijn graph, the de Bruijn Cube (dBCube) graph and the Shuffle-Exchange network are introduced, and virtual channel requirements are determined. The dBCube graph of size (r, N b , n) requires a maximum of m -(m -1)/r virtual channels for the outcluster channels, and a maximum of m + 1m/r virtual channels for the incluster 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 with 2 m nodes.