Indian Journal of Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Congestion Aware Routing Algorithm for Mesh Network-on-chip Platform


Affiliations
1 Department of Electrical Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran, Islamic Republic of
2 Islamic Azad University, Science and Research Branch, Tehran, Iran, Islamic Republic of
 

The routing algorithm plays an important role in the performance of the network on chip. In this paper we propose an adaptive routing, which uses a fuzzy controller to combine two congestion metrics free buffers and crossbar demand. The objective of the proposed routing algorithm is, choosing channel that has more free-slots input buffer beyond adjacent routers and the less number of active requester for a given output port. Simulation results show that the proposed method applied to odd-even routing algorithm can effectively improves average delay and throughput to meet load balance requirement and avoid hotspot with low hardware overhead.

Keywords

Network on Chip, System on Chip, Fuzzy Controller, Congestion, Routing
User

  • Ascia G, Catania V, Palesi M and Patti D (2008) Implementation and analysis of a new selection strategy for adaptive routing in network-on-chip. IEEE Transac. Comp. 57(6), 809-820.

  • Benini L and De Micheli G (2002) Network on chips: A new SoC paradigm. IEEE Computers. 35(1), 70-78.

  • Class CJ and Ni LM (1994) The turn model for adaptive routing. J. ACM. 41, 874-902.

  • Chiu GM (2000) The odd-even turn model for adaptive routing. IEEE Transact. Parallel & Distributed Sys. 11, 729-738.

  • Duato J, Yalamanchili Y and Ni L (2002) Interconnection networks: An engineering approach, Morgan Kaufmann.

  • Driankov D, Hellendoorn H and Reinfrank M (1993) An introduction to fuzzy control, Springer-Verlag, Berlin, NY.

  • Ebrahimi M, Daneshtalab M, Liljeberg P, Plosila J and Tenhunen H (2011) Efficient congestion-aware selection method for on-chip networks. IEEE workshop on Reconfigurable Commun.-centric Sys.Chip (ReCoSoC).

  • Feng WC and Shin KG (1997) Impact of selection functions on routing algorithm performance in multicomputer networks. Supercomputing. pp: 132-139.

  • Kumar S, Jantsch A , Soininen JP, Millberg M, Oberg J, Tiensyria K and Hemani A (2002) A network on chip architecture and design methodology.ISVLSI. pp: 117- 122.

  • Gratz P, Grot B and Keckler SW (2008) Regional congestion awareness of load balance in network-onchips. Proc. Intl. Symp. High Performance Comput.Architec. pp: 203-214.

  • Hu JC and Marculescu R (2004) DyAD smart routing for networks-on-chip. Design Automation Conf. pp: 260-263.

  • Li M, Zeng QA and Jone WB (2006) DyXY a proximity congestion-aware deadlock-free dynamic routing method for network on chip. Design Automation Conf. pp: 849-852.

  • Lotfi-Kamran P, Daneshtalab M, Navabi Z and Lucas C (2008) BARP a dynamic routing protocol for balanced distribution of traffic in NoCs to avoid congestion. ACM/IEEE design automation & test inEurope Conf. ( DATE). pp: 1408-1413.

  • Noxim (2008) Network-on-chip simulator, http://sourceforge.net/projects/noxim

  • Palesi M, Holsmark R, Kumar S and Catania V (2006) A methodology for design of application specific deadlock-free routing algorithms for NoC systems hardware-software co design and system. Synthesis. pp: 142-147.

  • Palesi M, Holsmark R, Kumar S and Catania V (2009) Application specific routing algorithms for networks on chip. IEEE Transact. Parallel & Distributed Sys. 20(3),316-330.

  • Schweibert L and Bell R (2002) Performance tunning of adaptive wormhole routing through Selection Function Choice. J. Parallel & Dstributed Comput. 62(7), 1121-1141.

  • Salehi N, Khademzadeh A and Dana A (2010) Power distribution in NoCs through a fuzzy based selection Strategy for Adaptive Routing 13th Euromicro Conference on Digital System Design: Architectures,Methods & Tools. pp: 45-52.

  • Salehi N, Khademzadeh A and Dana A (2011) Minimal fully adaptive fuzzy-based routing algorithm for Networks-on-Chip IEICE Elect. Express. 8(13), 1102-1108.

  • Tedesco L, Rosa Th, Clermidy F, Calazans N and Moreas F (2010) Implementation and evaluation of a congestion aware routing algorithm for networks-onchip. Symposium on integrated circuits and systemdesign. pp: 91-96.

  • Vander Tol EB and Jaspers EGT (2002) Mapping of MPEG-4 decoding on a flexible architecture platform SPIE. pp: 1-13.

  • Wu D, Al-hashimi BM and Schmits MT (2006) Improving routing efficiency for network-on-chip through contention-aware input selection Asia and South Pacific. Design Automation. pp: 36-41.

  • Ye TT, Benini L and Micheli GD (2004) Packetization and routing analysis of on-chip multiprocessor Networks. J.Sys. Architectures. 50, 81-104.


Abstract Views: 472

PDF Views: 159




  • Congestion Aware Routing Algorithm for Mesh Network-on-chip Platform

Abstract Views: 472  |  PDF Views: 159

Authors

Arash Dana
Department of Electrical Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran, Islamic Republic of
Nastaran Salehi
Islamic Azad University, Science and Research Branch, Tehran, Iran, Islamic Republic of

Abstract


The routing algorithm plays an important role in the performance of the network on chip. In this paper we propose an adaptive routing, which uses a fuzzy controller to combine two congestion metrics free buffers and crossbar demand. The objective of the proposed routing algorithm is, choosing channel that has more free-slots input buffer beyond adjacent routers and the less number of active requester for a given output port. Simulation results show that the proposed method applied to odd-even routing algorithm can effectively improves average delay and throughput to meet load balance requirement and avoid hotspot with low hardware overhead.

Keywords


Network on Chip, System on Chip, Fuzzy Controller, Congestion, Routing

References





DOI: https://doi.org/10.17485/ijst%2F2012%2Fv5i6%2F30470