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

Interconnection networks have been widely adopted in multicomputer systems, clusters, or chip multiprocessors (CMPs) for high performance and low latency. Among various routing algorithms in interconnection networks, adaptive routing shows the best performance with most traffic types. In this paper, we propose two practical adaptive routing algorithms, called adaptive injection (AI) and adaptive layer selection (AL), which utilize the pipelined architecture and multi-layer networks. In AI, a node adaptively selects a layer to which it injects a packet according to the current network status. After injection, the packet uses deterministic routing. In AL, a packet can change the layers during its delivery. AI is especially good when the network size is small, while AL shows better performance in general. In addition, these adaptive decisions are made only when the remaining hops are less than some threshold value, or oblivious routing is selected in other cases. 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, AI outperforms existing routing algorithms in terms of throughput by 7.1% ~ 65.2%. AL with AI shows better performance especially when the network size is large. Its throughput is improved by 12.5% ~73.8% in an (8 times 8) mesh network.