Presenting a Multi-Criteria QoS-Aware Fault Tolerant Routing Algorithm for Network-On-Chips
Subject Areas : electrical and computer engineering
Alireza Mahjoub
1
,
Fatemeh Vardi
2
*
,
Roya Rad
3
1 - Islamic Azad University, Karaj branch
2 -
3 -
Keywords: Network on chip, routing algorithm, fault tolerance, adaptive approach, reliability,
Abstract :
Network-on-chip is a router-based paradigm that determines the path of packet passing from the source to destination by a routing pattern through simplified protocols of the public data communication network. Sometimes, it is impossible to send packets from source to destination due to the communication problems caused by network elements in NoC such as routers and faulty links. In most cases, fault-tolerant algorithms select a reliable path using definite criteria. Therefore, in this paper, a reliable path is selected using a multi-criteria decision making technique through an adaptive approach according to the density status received from the adjacent nodes along with the path length so that when a failure occurs, a reliable path with similar QoS features is replaced by rating different paths among network nodes. The weight path selection strategy in NoCs to detect the minimal output port and multi-criteria decision making approach with VIKOR method has improvement over the basic routing algorithm in terms of delay and throughput. The algorithm hardware overhead has a reasonably low cost that maintains scalability for large scale On-Chip networks implementations.
[1] K. Lahiri, A. Raghunathan, and S. Dey, "Evaluation of the traffic-performance characteristics of system-on-chip communication architectures," in Proc. of the 14th Int. Conf. on VLSI Design. IEEE, pp. 29-35, Bangalore, India, 7- Jan. 2001.
[2] T. Bjerregaard and S. Mahadevan, "A survey of research and practices of network-on-chip," ACM Computing Surveys J., vol. 38, no. 1, Article No. 1-es, Jun. 2006.
[3] L. Benin and G. De Micheli, "Networks on chips: a new SoC paradigm," Computer, vol. 35, no. 1, pp. 70-78, Jan. 2002.
[4] R. Kamal, P. Goyal, and V. Nehra, "Network on chip: topologies, routing, implementation," International J. of Advances in Science and Technology, vol. 4, no. 1, pp. 24-34, Feb. 2012.
[5] J. Duato and S.Y alamanchili, Interconnection Networks - An Engineering Approach, Morgan Kaufmann, 2003.
[6] A. Ben Achballah, S. Ben Othman, and S. Ben Saoud, "Problems and challenges of emerging technology networks-on-chip: a review," Microprocessors and Microsystems, vol. 53, pp. 1-20, Aug. 2017.
[7] S. K. Rahimi and F. S. Haug, Distributed Database Management Systems: A Practical Approach, Wiley, 2010.
[8] S. Konstantinidou and L. Snyder, "The chaos router," IEEE Trans. on Computers, vol. 43, no. 12, pp. 1386-1397, Dec. 1994.
[9] M. Atagoziyev, Routing Algorithms for on Chip Networks, MSc. Thesis in Electrical and Electronics Engineering, Middle East Technical University, 2007.
[10] P. Lotfi-Kamran, A. M. Rahmani, M. Daneshtalab, and A. Afzali-Kusha, "EDXY-a low cost congestion-aware routing algorithm for network-on-chips," J. of Systems Architecture, vol. 56, no. 7, pp. 256-264, Jul. 2010.
[11] J. Hu and R. Marculescu, "DyAD-smart routing for networks-on-chip," in Proc. 41st Design Automation Conf., pp. 260-263, San Diego, CA, USA, 7-11 Jul. 20042004.
[12] M. Li, Q. Zeng, and W. Jone, "DyXY-a proximity congestion-aware deadlock-free dynamic routing method for network on chip," in Proc. 43rd ACM/IEEE Design Automation Conf, pp. 849-852, San Francisco, CA, USA, 24-28 Jul. 2006
[13] G. M. Chiu, "The odd-even turn model for adaptive routing," IEEE Trans. on Paralleland Distributed Systems, vol. 11, no. 7, pp. 729-738, Jul.. 2000.
[14] N. Dahir, T. Mak, R. Al-Dujaily, and A. Yakovlev, "Highly adaptive and deadlock-free routingfor three-dimensional network-on-chip," Computers and Digital Techniques, IET, vol. 7, no. 6, pp. 255-263, Nov. 2013.
[15] R. Saini and M. Ahmed, "Restricted turn model fault tolerant routing techniques for 3D mesh network-on-chip: an evaluation," in Proc. of Int. Congress on Information and Communication Technology, ICICT’16, pp. 113-122, Bangkok, Thailand, 12-13 Dec. 2016.
[16] Z. Lu, A. Jantsch, and L. Ji, "A reconfigurable fault-tolerant deflection routing algorithm based on reinforcement learning for network-on-chip," in Proc. of the 3rd Int. Workshop on Network on Chip Architectures, pp. 11-16, Atlanta, GA, USA, 4-4 Dec. 2010.
[17] J. Liu, J. Harkin, Y. Li, and L. Maguire, "Low cost fault-tolerant routing algorithm for networks-on-chip," Microprocessors and Microsystems, vol. 39, no. 6, pp. 358-372, Aug. 2015.
[18] D. Sinha, A. Roy, K. V. Kumar, P. Kulkarni, and J. Soumya, "Dn-FTR: fault-tolerant routing algorithm for mesh based network-on-chip," in Proc. 4th Int'l Conf. on Recent Advances in Information Technology RAIT’18, 5 pp., Dhanbad, India, 15-17 Mar. 2018.
[19] J. Khichar and S. Choudhary, "Fault aware adaptive routing algorithm for mesh based NoCs," in Proc. Int. Conf. on Inventive Computing and Informatics, ICICI’17, pp. 584-589, Coimbatore, India, 23-24 Nov. 2017.
[20] M. F. Yota Kurokawa, "XY based fault-tolerant routing with the passage of faulty nodes," IET Computers & Digital Techniques, vol. 13, no. 3, pp. 224-23, Nov. 2018.
[21] Z. Zhang, W. Serwe, J. Wu, T. Yoneda, H. Zheng, and C. Myers, "An improved fault-tolerant routing algorithm for a network-on-chip derived with formal analysis," Science of Computer Programming, vol. 118, pp. 24-39, Mar. 2016.
[22] J. Wu, Z. Zhang, and C. Myers, A Fault-Tolerant Routing Algorithm for a Network-on-Chip Using a Link Fault Model, Virtual Worldwide Forum for PhD Researchers in Electronic Design Automation, 2011.
[23] E. K. Gawish, M. W. El-Kharashi, and M. F. Abu-Elyazeed, "Variability-tolerant routing algorithms for networks-on-chip," Microprocessors and Microsystems, vol. 38, no. 8, pt. B, pp. 1037-1045, Nov. 2014.
[24] Y. Ren, L. Liu, S. Yin, Q. Wu, S. Wei, and J. Han, "A VLSI architecture for enhancing the fault tolerance of NoC using quad-spare mesh topology and dynamic reconfiguration," in Proc. IEEE Int. Symp. on Circuits and Systems, pp. 1793-1796, Beijing, China, 19-23 May 2013.
[25] S. Opricovic and G. H. Tzeng, "Compromise solution by MCDM methods: a comparative analysis of VIKOR and TOPSIS," European J. of Operational Research, vol. 156, no. 2, pp. 445-455, Jul. 2004.
[26] J. Kim, D. Park, T. Theocharides, N. Vijaykrishnan, and C. R. Das, "A low latency router supporting adaptivity for on-chip interconnects," in Proc. 42nd Annual Design Automation Conf., pp. 559-564, Anaheim, CA, USA, 13-17 Jun 2005.
[27] M. E. Shaheen and A. Abukmail, "A fault tolerant deadlock-free multicast algorithm for 2D mesh multicomputers," The J. of Management and Engineering Integration, vol. 5, no. 2, pp. 1-9, Winter 2012.
[28] A. Alhussien, C. Wang, and N. Bagherzadeh, "Design and evaluation of a high throughput robust router for network-on-chip," Digital Techniques, vol. 6, no. 3, pp. 173-179, May 2012.
[29] A. Alhussien, C. Wang, and N. Bagherzadeh, "Planar-adaptive routing: low-cost adaptive networks for multiprocessors," ACM J., vol. 42, no. 1, pp. 91-123, Jan. 1995.
[30] M. Palesi, D. Patti, and F. Fazzino, Noxim: Network on Chip Simulator, http://www.noxim.org, 2010".
[31] G. Ascia, V. Catania, M. Palesi, and D. Patti, "Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip," IEEE Trans. on Computers, vol. 57, no. 6, pp. 809-820, Jun. 2008.
[32] P. A. Tsai, Y. H. Kuo, E. J. Chang, H. K. Hsin, and A. Y. Wu, "Hybrid path-diversity-aware adaptive routing with latency prediction model in network-on-chip systems," in Proc. Int. Symp. VLSI Design Autom. Test, 4 pp., Hsinchu, Taiwan, 22-24 Apr. 2013.
[33] S. Carrillo, J. Harkin, L. J. McDaid, F. Morgan, S. Pande, and S. Cawley, "Scalable hierarchical network-on-chip architecture for spiking neural network hardware implementations," IEEE Trans. on Parallel and Distributed Systems, vol. 24, no. 12, pp. 2451-2461, Dec. 2013.
[34] S. Carrillo, J. Harkin, L. McDaid, S. Pande, S. Cawley, B. McGinley, and F. Morgan, "Advancing interconnect density for spiking neural network hardware implementations using traffic-aware adaptive network-on-chip routers," Neural Networks, vol. 33, no. 9, pp. 42-57, Sept. 2012.
[35] J. Liu, J. Harkin, Y. Li, and L. Maguire, "Online traffic-aware fault detection fornetworks-on-chip," J. Parall. Distrib. Comput., vol. 74, no. 1, pp. 1984-1993, Jan. 2014.
[36] A. Vitkovskiy, V. Soteriou, and C. Nicopoulos, "Dynamic fault-tolerant routing algorithm for networks-on-chip based on localised detouring paths," IET Computers & Digital Techniques, vol. 7, no. 2, pp. 93-103, Mar. 2013.
[37] N. E. Jerger and L. S. Peh, "On-Chip Networks," San Rafael, CA, USA: Morgan and Claypool, 2009.