This paper presents a theoretical model of resource allocations and dependencies in wormhole and virtual cut-through interconnection networks. This model allows various types of message blocking to be described precisely, including deadlock. The model distinguishes between messages involved in deadlock and those simply dependent upon deadlock, thus establishing a framework for evaluating the accuracy and correctness of deadlock detection mechanisms. The paper also identifies the necessary and sufficient conditions for the occurrence and resolution of deadlock in interconnection networks, thus providing efficiency and correctness criteria for deadlock resolution mechanisms. Theorems derived from the model are related to various routing algorithms which are based on deadlock recovery.

This paper characterizes how various network parameters influence message blocking and deadlocks in irregular networks. Information on blocking behavior is provided that is useful in making design trade-offs between restricting routing freedom and allowing the possibility for deadlocks to form in irregular networks. This work also identifies ways in which a network's susceptibility to deadlock can be reduced and provides guidelines for designing irregular networks which maximize routing flexibility and resource utilization. Finally, a new empirical evaluation methodology for classifying irregular topologies and relating network behavior to various classes of network topologies is introduced.

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 OF virtual cut-through switched), it is empirically shown that deadlocks are virtually eliminated in networks with n/spl ges/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.

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. We empirically show that increasing routing freedom, as achieved by allowing unrestricted routing over multiple virtual channels, makes deadlocks highly improbable and reduces the likelihood of other types of correlated message blocking behavior that can degrade performance. Our results further substantiate that recovery-based routing algorithms have a higher potential performance advantage over deadlock avoidance-based routing algorithms which, inherently, allow less routing freedom.