Optimal Fully Adaptive Wormhole Routing for Meshes

A deadlock-free fully adaptive routing algorithm for 2D meshes which is optimal in the number of virtual channels required and in the number of restrictions placed on the use of these virtual channels is presented. The routing algorithm imposes less than half as many routing restrictions as any previous fully adaptive routing algorithm. It is also proved that, ignoring symmetry, this routing algorithm is the only fully adaptive routing algorithm that achieves both of these goals. The implementation of the routing algorithm requires relatively simple router control logic. The new algorithm is extended, in a straightforward manner, to arbitrary dimension meshes. It needs only 4n \Gamma 2 virtual channels, the minimumnumber for an n-dimensional mesh. All previous algorithms require an exponential number of virtual channels in the dimension of the mesh. Keywords: wormhole routing, mesh architectures, routing algorithms, deadlock freedom, optimality. 1 Introduction Wormhole routing [6] ha..