2008 IEEE International Performance Computing and Communications Conference (IPCCC)
Download PDF

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 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.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles