A novel deadlock-free routing technique for a class of de Bruijn graph based networks
H. Park, Dharma Prakash Agrawal · 2002
This paper introduces a new deadlock-free routing algorithm with fewer virtual channels than the known algorithm for a generalized de Bruijn digraph of m virtual channels, where m is the maximum message path length and r is a radix. Our new algorithm requires maximum m-[/sup m-1///sub r/] virtual channels per physical channel. Extension to this algorithm for a generalized de Bruijn graph and a dBCube graph is introduced, and virtual channel requirements have also been identified. In most of dBCube graphs, maximum m-[/sup m-1///sub r/] virtual channels are required for the outcluster channels, and maximum m+1-[/sup m///sub r/] virtual channels for the incluster channels, where m is the maximum length of the cluster-to-cluster path.>