Abstract
Due to the increase of physical defects in advanced manufacturing processes, Networks-on-Chip (NoC) system reliability is a critical challenge as faults often occur post manufacturing. Therefore it is important to add fault tolerance to the NoC system. In this paper, a novel routing algorithm for 2D mesh NoCs is proposed which aims to enhance the fault-tolerant capabilities via a look-ahead function. A traffic status informing mechanism is developed to provide information to local NoC routers on the interconnect conditions in far distant routers. In addition, a weighted path mechanism is used to forward the packets. The routing algorithm is implemented and verified on FPGA hardware. Real-time throughput and traffic information were collected by a monitoring unit on the FPGA. Results show that the proposed routing algorithm can maintain the system function under low fault rates and only has a marginal (~5 %) throughput degradation under high fault rate of 20 %. The router area is also relatively low which demonstrated its scalability.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Furber, S.B., Lester, D.R., Plana, L.A., Garside, J.D., Painkras, E., Temple, S., Brown, A.D.: Overview of the SpiNNaker system architecture. IEEE Trans. Comput. 62, 2454–2467 (2013)
Carrillo, S., Harkin, J., McDaid, L.J., Morgan, F., Pande, S., Cawley, S., McGinley, B.: Scalable hierarchical network-on-chip architecture for spiking neural network hardware implementations. IEEE Trans. Parallel Distrib. Syst. 24, 2451–2461 (2013)
Abdelfattah, M.S., Betz, V.: The power of communication: energy-efficient NoCs for FPGAs. In: 23rd International Conference on Field Programmable Logic and Applications (FPL), pp. 1–8 (2013)
Agarwal, A., Raton, B., Iskander, C., Multisystems, H., Shankar, R.: Survey of network on chip (NoC) architectures & contributions. J. Eng. Comput. Architect. 3, 1–15 (2009)
Duong, T.D., Kaneko, K.: Fault-tolerant routing based on approximate directed routable probabilities for hypercubes. In: **ang, Y., Cuzzocrea, A., Hobbs, M., Zhou, W. (eds.) ICA3PP 2011, Part I. LNCS, vol. 7016, pp. 106–116. Springer, Heidelberg (2011)
Feng, C., Lu, Z., Jantsch, A., **wen, L., Zhang, M.: FON: Fault-on-neighbor aware routing algorithm for networks-on-chip. In: 23rd IEEE International SoC Conference, pp. 441–446 (2010)
Zhang, Z., Greiner, A., Taktak, S.: A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip. In: 45th IEEE/ACE Design Automation Conference, pp. 441–446 (2008)
Pratomo, I., Pillement, S.: Gradient - An adaptive fault-tolerant routing algorithm for 2D mesh Network-on-Chips. In: Design and Architectures for Signal and Image Processing (DASIP), pp. 1–8 (2012)
Lotfi-Kamran, P., Rahmani, A.M., Daneshtalab, M., Afzali-Kusha, A., Navabi, Z.: EDXY - A low cost congestion-aware routing algorithm for network-on-chips. J. Syst. Architect. 56, 256–264 (2010)
Mehranzadeh, A., Khademzadeh, A., Mehran, A.: FADyAD- fault and congestion aware routing algorithm based on DyAD algorithm. In: 5th International Symposium on Telecommunications, pp. 274–279 (2010)
Feng, C., Lu, Z., Jantsch, A., Zhang, M., **ng, Z.: Addressing transient and permanent faults in NoC with efficient fault-tolerant deflection router. IEEE Trans. Very Large Scale Integr. VLSI Syst. 21, 1053–1066 (2013)
Ali, M., Welzl, M., Hessler, S., Hellebrand, S.: A fault tolerant mechanism for handling permanent and transient failures in a network on chip. In: 4th International Conference on Information Technology, pp. 1027–1032 (2007)
Aisopos, K., DeOrio, A., Peh, L.-S., Bertacco, V.: ARIADNE: agnostic reconfiguration in a disconnected network environment. In: International Conference on Parallel Architectures and Compilation Techniques, pp. 298–309. IEEE (2011)
Parikh, R., Bertacco, V.: uDIREC: unified diagnosis and reconfiguration for frugal bypass of NoC faults. In: 46th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 148–159 (2013)
Chaix, F., Avresky, D., Zergainoh, N.-E., Nicolaidis, M.: A fault-tolerant deadlock-free adaptive routing for on chip interconnects. In: Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 1–4 (2011)
Ahmed, A.B., Abdallah, A.B.: Graceful deadlock-free fault-tolerant routing algorithm for 3D network-on-chip architectures. J. Parallel Distrib. Comput. 74, 2229–2240 (2014)
Liu, J., Harkin, J., Li, Y., Maguire, L.: Online traffic-aware fault detection for networks-on-chip. J. Parallel Distrib. Comput. 74, 1984–1993 (2014)
Alhussien, A., Wang, C., Bagherzadeh, N.: Design and evaluation of a high throughput robust router for network-on-chip. IET Comput. Digit. Tech. 6, 173–179 (2012)
Liu, J., Harkin, J., Li, Y., Maguire, L., Barranco, A.L.: Low overhead monitor mechanism for fault-tolerant analysis of NoC. In: IEEE 8th International Symposium on Embedded Multicore/Many-core Systems-on-Chip, pp. 189–196, Aizu-Wakamatsu, Japan (2014)
Chen, P., Dai, K., Wu, D., Rao, J., Zou, X.: The parallel algorithm implementation of matrix multiplication based on ESCA. In: 2010 IEEE Asia Pacific Conference on Circuits and Systems, pp. 1091–1094 (2010)
Liu, J., Harkin, J., Li, Y., Maguire, L.: Low cost fault-tolerant routing algorithm for networks-on-chip. Microprocess. Microsyst. 39, 358–372 (2015)
Carrillo, S., Harkin, J., McDaid, L., Pande, S., Cawley, S., McGinley, B., Morgan, F.: Advancing interconnect density for spiking neural network hardware implementations using traffic-aware adaptive network-on-chip routers. Neural Netw. 33, 42–57 (2012)
Acknowledgements
This research was partially supported by the Guangxi Natural Science Foundation under Grant 2015GXNSFBA139256 and 2014GXNSFBA118271, the Research Project of Guangxi University of China under Grant ZD2014022, Guangxi Key Lab of Multi-source Information Mining & Security under Grant MIMS14-04, Guangxi Key Lab of Wireless Wideband Communication & Signal Processing under Grant GXKL0614205, the Education Development Foundation and the Doctoral Research Foundation of Guangxi Normal University, the State Scholarship Fund of China Scholarship Council under Grant [2014]3012.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Liu, J., Harkin, J., Maguire, L., Li, Y., Wan, L., Luo, Y. (2015). Fine-Grained Fault-Tolerant Adaptive Routing for Networks-on-Chip. In: Wang, G., Zomaya, A., Martinez, G., Li, K. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2015. Lecture Notes in Computer Science(), vol 9531. Springer, Cham. https://doi.org/10.1007/978-3-319-27140-8_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-27140-8_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27139-2
Online ISBN: 978-3-319-27140-8
eBook Packages: Computer ScienceComputer Science (R0)