Cluster Based Hierarchical Routing Algorithm for Network on Chip


This paper presents a new logical mechanism called as Cluster Based Hierarchical Routing (CBHR) to improve the efficiency of NoC. This algorithm comprises the following steps: 1) the network is segmented logically into clusters with same size or different sizes; 2) algorithms are assigned for internal and global routing; 3) routers working functions are modified logically to support local and global communication. The experiments have conducted for CBHR algorithm for two dimensional mesh and torus architectures. The performance of this mechanism is analyzed and compared with other deterministic and adaptive routing algorithms in terms of energy, throughput with different packet injection ratios.

Share and Cite:

U. Saravanakumar, R. Rangarajan, R. Haripriya, R. Nithya and K. Rajasekar, "Cluster Based Hierarchical Routing Algorithm for Network on Chip," Circuits and Systems, Vol. 4 No. 5, 2013, pp. 401-406. doi: 10.4236/cs.2013.45053.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] ITRS, International Technology Roadmap for Semicon ductors, 2012.
[2] T. N. Theis, “The Future of Interconnection Technology,” IBM Journal of Research and Development, Vol. 44, No. 3, 2000, pp. 379-390. doi:10.1147/rd.443.0379
[3] W. J. Dally and B. Towles, “Route Packets, Not Wires: On-Chip Interconnection Networks,” Proceedings of the 38th Design Automation Conference (DAC), Las Vegas, 18-22 June 2001.
[4] T. Bjerregaard and S. Mahadevan, “A Survey of Research and Practices of Network-on-Chip,” ACM Computing Surveys, Vol. 38, No. 1, 2006. doi:10.1145/1132952.1132953
[5] L. Benini and G. De Micheli, “Networks on Chips: A New SoC Paradigm,” Computer, Vol. 35, No. 1, 2002, pp. 70-78. doi:10.1109/2.976921
[6] J. Nurmi, “Network-on-Chip: A New Paradigm for Sys tem-on-Chip Design,” Proceedings of International Sym posium on System-on-Chip, Tampere, 17 November 2005, pp. 2-6.
[7] J. Henkel, W. Wolf and S. T. Chakradhar, “On-Chip Net works: A Scalable, Communicationcentric Embedded Sys tem Design Paradigm,” Proceedings of 17th International Conference on VLSI Design, Mumbai, 5-9 January 2004, p. 845. doi:10.1109/ICVD.2004.1261037
[8] W. J. Dally and C. L. Seitz, “Torus Routing Chip,” Dis tributed computing, Vol. 1, No. 4, 1986, pp. 187-196. doi:10.1007/BF01660031
[9] M. Dehyadgari, M. Nickray, A. Afzali-kusha and Z. Na vabi, “Evaluation of Pseudo Adaptive XY Routing Using an Object Oriented Model for NOC,” Proceedings of the 17th International Conference on Microelectronics, Is lamabad, 13-15 December 2005.
[10] Intel Corporation, “A Touchstone DELTA System De scription,” Intel Corporation, Portland, 1991.
[11] S. Lillevik, “The Touchstone 30 Gigaflop DELTA Proto type,” Proceedings of 6th Distributed Memory Computing Conference, Portland, 28 April-1 May 1991.
[12] G.-M. Chiu, “The Odd-Even Turn Model for Adaptive Routing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 11, No. 7, 2000, pp. 729-738. doi:10.1109/71.877831
[13] W. Zhang, L. Hou, J. Wang, S. Geng and W. Wu, “Com parison Research between XY and Odd-Even Routing Algorithm of a 2-Dimension 3X3 Mesh Topology Net work-on-Chip,” Proceedings of the WRI Global Congress on Intelligent Systems (GCIS '09),” Washington DC, 19-21 May 2009, pp. 329-333. doi:10.1109/GCIS.2009.110
[14] R. Holsmark, S. Kumar, M. Palesi and A. Mejia, “HiRA: A Methodology for Deadlock Free Routing in Hierarchi cal Networks on Chip,” Proceedings of 3rd ACM/IEEE International Symposium on Networks-on-Chip, San Die go, 10-13 May 2009, pp. 2-11.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.