CAFT: Cost-aware and Fault-tolerant routing algorithm in 2D mesh Network-on-Chip

Subject Areas : Computer Architecture and Digital Systems

Akram Reza ¹ , Parisa Jolani ² , Midia Reshadi ³

1 - Department of Computer Engineering, Shahr-e-Qods Branch, Islamic Azad University, Tehran, Iran
2 - Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.
3 - Computer Engineering Department, Science and Research Branch, Islamic Azad University,Tehran,Iran

Received: 2018-06-17 Accepted : 2019-07-25 Published : 2019-11-01

Keywords: Fault tolerance, Adaptive routing, Deadlock-free, 2D-NOC, Network-on-Chip, routing algorithm,

Abstract :

By increasing, the complexity of chips and the need to integrating more components into a chip has made network on- chip known as an important infrastructure for network communications on the system, and is a good alternative to traditional ways and using the bus. By increasing the density of chips, the possibility of failure in the chip network increases and providing correction and fault tolerance methods is one of the principles of today's chip design. Faults may have undesirable effects on the correct system operation and system performance. In this paper the communication infrastructure failure has been considered as same as link and router failure and the fault tolerance low cost routing algorithm has been suggested base on local fault information By using quad neighbor fault information to avoid back tracking in routing in order to select possible minimal path to destination. In this article, we have suggested cost aware fault tolerance (CAFT) routing algorithm. Our contribution in this algorithm is minimum local fault information, minimum routing decision overhead by implementing routing logic base and determining shortest possible path. For deadlock freedom using an additional virtual channel along Y dimension and prohibiting certain routing turns. In order to evaluate the performance of our routing, we compared it with other fault tolerant routing in terms of average packet latency, throughput and power.

References:

[1] Moadeli, M., Shahrabi, A., Vanderbauwhede, W. and Ould-Khaoua, M., 2007, May. An analytical performance model for the Spidergon NoC. In Advanced Information Networking and Applications, 2007. AINA'07. 21st International Conference on (pp. 1014-1021). IEEE.
[2] Yaghini, P.M., Eghbal, A. and Bagherzadeh, N., 2015. On the design of hybrid routing mechanism for mesh-based network-on-chip. INTEGRATION, the VLSI journal, 50, pp.183-192.
[3] Wu, Z., Fu, F., Lu, Y. and Wang, J., 2015. A role-changeable fault-tolerant management strategy towards resilient NoC-based manycore systems. Microelectronics Journal, 46(12), pp.1371-1379.
[4] Ahmed, A.B. and Abdallah, A.B., 2014. Graceful deadlock-free fault-tolerant routing algorithm for 3D Network-on-Chip architectures. Journal of Parallel and Distributed Computing, 74(4), pp.2229-2240.
[5] Duato, J., 1995. A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks. IEEE Transactions on Parallel and Distributed Systems, 6(10), pp.1055-1067.
[6] Glass, C.J. and Ni, L.M., 1998, August. The turn model for adaptive routing. In 25 years of the international symposia on Computer architecture (selected papers) (pp. 441-450). ACM.
[7] Xie, R., Cai, J. and Xin, X., 2016. Simple fault-tolerant method to balance load in network-on-chip. Electronics letters, 52(10), pp.814-816.
[8] Xie, R., Cai, J. and Xin, X., 2016. Simple fault-tolerant method to balance load in network-on-chip. Electronics letters, 52(10), pp.814-816.
[9] Glass, C.J. and Ni, L.M., 1996. Fault-tolerant wormhole routing in meshes without virtual channels. IEEE transactions on parallel and distributed systems, 7(6), pp.620-636.
[10] Dally, W.J. and Seitz, C.L., 1988. Deadlock-free message routing in multiprocessor interconnection networks.
[11] Valinataj, M., Mohammadi, S., Plosila, J., Liljeberg, P. and Tenhunen, H., 2011. A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip. AEU-International Journal of Electronics and Communications, 65(7), pp.630-640.
[12] Zhou, J., Li, H., Wang, T. and Li, X., 2016. LOFT: A low-overhead fault-tolerant routing scheme for 3D NoCs. Integration, the VLSI Journal, 52, pp.41-50.
[13] Huang, L., Zhang, X., Ebrahimi, M. and Li, G., 2016. Tolerating transient illegal turn faults in NoCs. Microprocessors and Microsystems, 43, pp.104-115.
[14] Kumar, M., Laxmi, V., Gaur, M.S., Daneshtalab, M., Ebrahimi, M. and Zwolinski, M., 2014, October. Fault tolerant and highly adaptive routing for 2D NoCs. In Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT), 2014 IEEE International Symposium on (pp. 104-109). IEEE.
[15] Ebrahimi, M., Daneshtalab, M. and Plosila, J., 2013, February. High performance fault-tolerant routing algorithm for NoC-based many-core systems. In Parallel, Distributed and Network-Based Processing (PDP), 2013 21st Euromicro International Conference on (pp. 462-469). IEEE.
[16] Valinataj, M., Mohammadi, S., Plosila, J., Liljeberg, P. and Tenhunen, H., 2011. A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip. AEU-International Journal of Electronics and Communications, 65(7), pp.630-640.
[17] Sinha, D., Roy, A., Kumar, K.V., Kulkarni, P. and Soumya, J., 2018, March. D n-FTR: Fault-tolerant routing algorithm for Mesh based network-on-chip. In 2018 4th International Conference on Recent Advances in Information Technology (RAIT) (pp. 1-5). IEEE.
[18] Xie, R., Cai, J., Xin, X. and Yang, B., 2017. Low-cost adaptive and fault-tolerant routing method for 2D Network-on-Chip. IEICE TRANSACTIONS on Information and Systems, 100(4), pp.910-913
[19] M. Palesi, D. Patti and F. Fazzino, "http://www.noxim.org/," University of Catania, 2005-2010. [Online].