A Novel Adaptive Routing Algorithm for Network-On-Chip

Abstract:

In this paper, we propose a novel adaptive routing algorithm to solve the communication congestion problem for Network-on-Chip (NoC). The strategy competing for output ports in both X and Y directions is employed to utilize the output ports of the router sufficiently, and to reduce the transmission latency and improve the throughput. Experimental results show that the proposed algorithm is very effective in relieving the communication congestion, and a reduction in average latency by 45.7% and an improvement in throughput by 44.4% are achieved compared with the deterministic XY routing algorithm and the simple XY adaptive routing algorithm.

• Periodical: Key Engineering Materials (Volumes 474-476)
• Pages: 413-416
• DOI: https://doi.org/10.4028/www.scientific.net/KEM.474-476.413
• Online since: April 2011
• Authors: Jia Jia, Duan Zhou, Jian Xian Zhang
• Keywords: Adaptive Routing, Arbitration Mechanism, Communication Congestion, NoC

References

[1] N.H.E. Weste and D. Harris. CMOS VLSI Design: A Circuits and Systems Perspective, Addison-Wesley (2004).

[2] A. Hemani, et al. Network on chip: An architecture for billion transistor era, Proceeding of the IEEE NORCHIP Conference, pp.166-173, November (2000).

[3] W.J. Dally and B. Towles. Route Packets, Not Wires: On-Chip Interconnection Networks, Proceedings of the 38th Design Automation Conference, pp.684-689, June (2001).

DOI: 10.1109/dac.2001.935594

[4] L. Benini and G.D. Micheli. NOC A New SOC Paradigm, IEEE Computer, pp.70-78, January (2002).

[5] K. Aoyama and A.A. Chien. The cost of adaptively and virtual lanes in a wormhole router, Journal of VLSI Design (1993).

DOI: 10.1155/1995/49382

[6] M. Palesi, R. Holsmark and S. Kumar. A methodology for design of application specific deadlock-free routing algorithms for NoC systems, Hardware/Software Co-design and System Synthesis, 2006. CODES+ISSS '06. Proceedings of the 4th International Conference (2006).

DOI: 10.1145/1176254.1176289

[7] M. Nickray, M. Dehyadgari and A. Afzali-kusha. Adaptive routing using context-aware agents for networks on chips, Design and Test Workshop (IDT), 2009 4th International (2009).

DOI: 10.1109/idt.2009.5404108

[8] P. Huang and W. Hwang. An adaptive congestion-aware routing algorithm for mesh network-on-chip platform, SOC Conference, 2009 IEEE International (2009).

DOI: 10.1109/soccon.2009.5398015

[9] Y. Thonnart, E. Beigne and P. Vivet. Design and implementation of a GALS adapter for ANoC based architectures, In Proc. the 15th International Symposium on Asynchronous Circuits and Systems, Chapel Hill, USA, pp.13-22, May 17-20 (2009).

DOI: 10.1109/async.2009.13

[10] W.J. Dally, Virtual Channel Flow Control, IEEE Trans. Parallel & Distributed Systems, Vol. 3, pp.194-205, March (1992).

DOI: 10.1109/71.127260