An efficient technique for in-order packet delivery with adaptive routing algorithms in networks on chip
Although adaptive routing algorithms promise higher communication performance, as compared to deterministic routing algorithms, they suffer from the out-of-order packet delivery problem. In the context of Network on Chip, the area and computational overhead of ordering packets at the destination is high and may reverse any gain achieved through the use of adaptivity of the routing algorithm. In this paper, we describe a novel scheme for ensuring in-order packet delivery while retaining the performance advantages of adaptive routing. The hardware architecture of a router that supports the proposed scheme is described. Although the basic idea in our proposal is topology independent we evaluate and compare the performance of our scheme with both deterministic as well as adaptive routing algorithms for 2D mesh NoC. As compared to the XY routing algorithm, our technique significantly reduces the packet delay and improves the saturation point. The impact on router area and power dissipation is also discussed. Although the power consumption of routers increase, the energy consumption per flit increases less than 2% on average, since the higher performance allows for draining more traffic during a certain time window.
Algorithm design and analysis; Delay; Hardware; Out of order; Routing; System recovery; Topology
Electrical and Computer Engineering | Electrical and Electronics | Electronic Devices and Semiconductor Manufacturing | Systems and Communications | VLSI and Circuits, Embedded and Hardware Systems
Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.
An efficient technique for in-order packet delivery with adaptive routing algorithms in networks on chip.
13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010