A novel deadlock-free routing technique for a class of de Bruijn graph based networks

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-[^m-1/_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-[^m-1/ _r] virtual channels are required for the outcluster channels, and maximum m+1-[^m/_r] virtual channels for the incluster channels, where m is the maximum length of the cluster-to-cluster path