ADAPTIVE FAULT-TOLERANT DEADLOCK-FREE ROUTING IN MESHES AND HYPERCUBES

We present an adaptive deadlock-free routing algorithm which decompose s a given network into two virtual interconnection networks, VIN1 and VIN2. VIN1 supports deterministic deadlock-free routing, and VIN2 supp orts fully-adaptive routing. Whenever a channel in VIN1 or VIN2 is ava ilable, it can be used to route a message. Each node is identified to be in one of three states: safe, unsafe, and faulty. The unsafe state is used for deadlock-free routing, and an unsafe node can still send a nd receive messages. When nodes become faulty/unsafe, some channels in VIN2 around the faulty/unsafe nodes are used as the detours of those channels in VIN1 passing through the faulty/unsafe nodes, i.e., the ad aptability in VIN2 is transformed to support fault-tolerant deadlock-f ree routing. Using information on the state of each node's neighbors, we have developed an adaptive fault-tolerant deadlock-free routing sch eme for n-dimensional meshes and hypercubes with only two virtual chan nels per physical link. In an n-dimensional hypercube, any pattern of faulty nodes can be tolerated as long as the number of faulty nodes is no more than [n/2]. The maximum number of faulty nodes that can be to lerated is 2(n-1), which occurs when all faulty nodes can be encompass ed in an (n-1)-cube. in an n-dimensional mesh, we use a more general f ault model, called a disconnected rectangular block. Any arbitrary pat tern of faulty nodes can be modeled as a rectangular block after findi ng both unsafe and disabled nodes (which are then treated as faulty no des). This concept can also be applied to k-ary n-cubes with four virt ual channels, two in VIN1 and the other two in VIN2. Finally, we prese nt simulation results for both hypercubes and 2-dimensional meshes by using various workloads acid fault patterns.