Optimal Fully Adaptive Minimal Wormhole Routing for Meshes
Abstract
A deadlock-free fully adaptive minimal routing algorithm for meshes
that 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. It is also proved that, ignoring symmetry, this routing
algorithm is the only fully adaptive routing algorithm with
uniform routers that achieves both of these goals. This new algorithm
requires only 4n-2 virtual channels for an n-dimensional mesh. In
addition, if more than the minimum number of virtual channels is
available, the routing algorithm can use these additional channels
with the fewest possible number of restrictions. The proofs are first
presented for the 2D mesh and then generalized to n-dimensional
meshes.
Return to the Publication list.
Last updated by Loren Schwiebert Email: 
on Jun-06-2001