Chinese Journal of Computers   Full Text
Title	Deadlock-Free Adaptive Routing in Fault-Tolerant Mesh Networks
Authors	XIANG Dong1) ZHANG Yue-Li2)
Address	1)(School of Software, Tsinghua University, Beijing 100084) 2)(Department of Computer Science and Technology, Tsinghua University, Beijing 100084)
Year	2007
Issue	No.11(1954—1962)
Abstract &   Background	Abstract A new deadlock-free routing algorithm is proposed for 3-dimensional meshes. Most of the recent commercial machines are constructed using 2D or 3D meshes. The planar adaptive routing scheme was proposed and effective deadlock avoidance technique use only three virtual channels for each physical channel in 3-dimensional or higher dimensional mesh networks. However, there exist two idle virtual channels for all channels along the first dimension, and one idle virtual channel for channels along the third dimension. A new deadlock avoidance technique is proposed for 3-dimensional meshes using only two virtual channels for each physical channel. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm. keywords fault-tolerant routing; fully adaptive routing; partially adaptive routing; planar adaptive routing; mesh; networks background Mesh-connected networks have been widely used in recent experimental or commercial multi-computers. A mesh network has an n-dimensional grid structure with k nodes in each dimension (called mesh for short). Performance of a multi-computer highly depends on the routing algorithm. It is quite possible for one or more of the system nodes or links between any pair of nodes to become faulty in a large scale system. An effective fault-tolerant routing algorithm in a mesh network is essential for a high-performance multi-computer system. In this paper, a new deadlock-free adaptive routing algorithm is proposed for meshes with only two virtual channels per physical channel. The number of virtual channels per physical channel required for deadlock-free routing is important for cost-effective and high-performance system design. The planar adaptive routing scheme is an effective deadlock avoidance technique using only three virtual channels for each physical channel in 3-dimensional or higher dimensional mesh networks. However, there exist idle virtual channels for all channels along the first dimension, and one idle virtual channel for channels along the last dimension in a mesh network. A new deadlock avoidance technique is proposed for 3-dimensional meshes using only two virtual channels, where a virtual channel can be shared by two consecutive planes without any cyclic channel dependency. The deadlock-free adaptive routing scheme is then modified to a deadlock-free adaptive fault-tolerant routing scheme based on a planarly constructed minimum connected components (MCCs) fault model.