Simple and Effective Adaptive Routing Algorithms Using Multi-Layer Wormhole Networks

Abstract — Interconnection networks have been adopted in multicomputer systems, clusters, or chip multiprocessors (CMPs). Among various routing algorithms in interconnection networks, adaptive routing shows the best performance with most traffic types. In this paper, we propose new adaptive routing algorithms considering the remaining hops in addition to local network status. The proposed algorithms make adaptive decisions only when the remaining hops are less than some threshold and congestion is detected, or they do oblivious routing in other cases. As a result, the number of adaptive decisions is greatly reduced. Consequently our proposed algorithms have less adaptive over-head. We propose two practical adaptive routing algorithms which utilize the pipelined router architecture and multi-layer networks. The first proposed scheme is called Adaptive Injection. Since it does not affect the virtual channel allocation stage, its pipeline length is the same as non-adaptive routing pipelines. Adaptive Injection is especially good when the network size is small, because it has limited adaptability. While the first scheme has non-overhead but small improvement, the second adaptive routing algorithm we propose, called Adaptive Layer Selection, has some processing overhead and better performance. The simulation results show that considering the remaining hops successfully decreases the number of adaptive decisions and two proposed routing schemes show better performance than previous adaptive algorithms. On the average, Adaptive Injection outperforms existing routing algorithms in terms of throughput by 7.1 % ∼ 65.2%. Adaptive Layer Selection with Adaptive Injection shows better performance especially when the network size is large. Its throughput is improved by 12.5 % ∼ 73.8 % in an (8 x 8) mesh network. I