An Efficient Technique for In-order Packet Delivery with Adaptive Routing Algorithms in networks on Chip

Authors

M. Palesi, University of CantaniaFollow
Rickard Holsmark, Jonkoping University
X. Wang, University of Nevada, Las VegasFollow
S. Kumar, Jonkoping University
Mei Yang, University of Nevada, Las VegasFollow
Yanan Jiang, University of Nevada, Las VegasFollow
V. Catania, University of Catania

Document Type

Conference Proceeding

Publication Date

9-1-2010

Publication Title

13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010

Publisher

IEEE

First page number:

37

Last page number:

44

Abstract

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.

Keywords

Algorithm design and analysis; Delay; Hardware; Out of order; Routing; System recovery; Topology

Disciplines

Electrical and Computer Engineering | Electrical and Electronics | Electronic Devices and Semiconductor Manufacturing | Systems and Communications | VLSI and Circuits, Embedded and Hardware Systems

Language

English

Comments

Conference held: Lille, 1-3 Sept. 2010

Permissions

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.

Repository Citation

Palesi, M., Holsmark, R., Wang, X., Kumar, S., Yang, M., Jiang, Y., Catania, V. (2010). 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 37-44. IEEE.