Characterization of deadlocks in k-ary n-cube networks

A spate of deadlock avoidance-based and deadlock recovery-based routing algorithms have been proposed in recent years without full understanding of the likelihood and characteristics of actual deadlocks in interconnection networks. This work models the interrelationships between routing freedom, message blocking, correlated resource dependencies, and deadlock formation. It is empirically shown that increasing routing freedom, as achieved by allowing unrestricted routing over multiple physical and virtual channels, reduces the probability of deadlocks and the likelihood of other types of correlated message blocking that can degrade performance Moreover, when true fully adaptive routing is used in k-ary n-cube networks with two or more virtual channels (wormhole or virtual cut-through switched), it is empirically shown that deadlocks are virtually eliminated in networks with n greater than or equal to 2. These results indicate that deadlocks are very infrequent when the network and routing algorithm inherently provide sufficient routing freedom, thus increasing the viability of deadlock recovery routing strategies.