A Condition of Deadlock-Free Routing in Mesh Network

Mesh topology is one of the most popular architectures in interconnection networks. Although many deadlock-free schemes for mesh networks have been proposed, deadlock avoidance is still the most difficult issue to solve. In this paper, we propose a new concept of channel class dependency for deadlock-free routing algorithm in mesh networks. Based on the channel class dependency graph, a new condition of the presence of cycle in the channel dependency graph of routing algorithms is introduced. Since the number of channel classes and channel class dependencies is not dependent on the size of mesh networks, the channel class dependency graph is easy to be implemented. So the proposed deadlock-free routing condition is the key for the design of deadlock-free routing algorithms, which employs minimum routing restrictions and as few virtual channels as possible.