Simple and Effective Adaptive Routing Algorithms in Multi-Layer Wormhole Networks
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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 adoptively 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 8) mesh network. 2008 IEEE.
name of conference
2008 IEEE International Performance, Computing and Communications Conference
