A TRAFFIC-BALANCED ADAPTIVE WORMHOLE ROUTING SCHEME FOR 2-DIMENSIONALMESHES

In this paper, we analyze several issues involved in developing low la tency adaptive wormhole routing schemes for two-dimensional meshes. It is observed that along with adaptivity, balanced distribution of traf fic has a significant impact on the system performance. Motivated by t his observation, we develop a new fully adaptive routing algorithm cal led positive-first-negative-first for two-dimensional meshes. The algo rithm uses only two virtual channels per physical channel creating two virtual networks. The messages are routed positive-first in one virtu al network and negative-first in the other. Because of this combinatio n, the algorithm distributes the system load uniformly throughout the network and is also fully adaptive. It is shown that the proposed algo rithm results in providing better performance in terms of the average network latency and throughput when compared with the previously propo sed routing algorithms.