Fault-tolerant and Congestion Balanced Routing Algorithm for 2D Mesh NoCs

Authors

  • Jiao Guan State Key Discipline Laboratory of Wide Band Gap Semiconductor Technology, School of Microelectronics, Xidian University, Xi’an, China, Institute of Information and Navigation, Air Force Engineering University, Xi’an, China
  • Jueping Cai State Key Discipline Laboratory of Wide Band Gap Semiconductor Technology, School of Microelectronics, Xidian University, Xi’an, China
  • Yequn Wang Institute of Information and Navigation, Air Force Engineering University, Xi’an, China
  • Jian Liu Institute of Information and Navigation, Air Force Engineering University, Xi’an, China

DOI:

https://doi.org/10.13052/jwe1540-9589.19786

Keywords:

Network-on-Chip (NoC), fault-tolerant routing algorithm, path channels, freebuffer length

Abstract

With the number of cores and nodes in networks-on-chips (NoCs) growing, the node fault occurrence probability is increasing. Although the existing turn model can route packets around the fault area and avoid deadlocks, a large traffic load is generated in the non-rightmost column of the fault region. This paper presents a novel fault-tolerant and congestion balanced (FTCB) routing algorithm that chooses a lower load area as the optimal router path by calculating the maximum path channels to balance traffic load and avoid network congestion. Two methods are proposed to calculate path channels for the fault-free mesh and the fault mesh. The improved odd-even turn rule is introduced to calculate path channels for the fault-free mesh. To balance the network load, free buffer length information is added to path channel calculations, which reflects the global perception. For the non-fault region, we update path channels by using the back formulas from the destination node to the source node. In a fault region, the modified calculation rules of path channels and fault-location odd-even turn rules are given. Compared to the other two related works, the throughput of the FTCB algorithm is improved by 6.92% and 10.7%. Meanwhile, the traffic load of FTCB is decreased to some degree in whole mesh, which shows the FTCB routing algorithm can obviously improve network load balanced, saturation throughput and network latency.

Downloads

Download data is not yet available.

Author Biographies

Jiao Guan, State Key Discipline Laboratory of Wide Band Gap Semiconductor Technology, School of Microelectronics, Xidian University, Xi’an, China, Institute of Information and Navigation, Air Force Engineering University, Xi’an, China

Jiao Guan received the B.S. and M.S. degrees in Computer communication engineering from Air Force Engineering University, Xi’an, China, in 2004 and 2009 respectively. She is currently working towards a Ph.D. degree with the school of Microelectronics at Xidian University, Xi’an, China. Her research interests include fault-tolerant system design and share memory in network-on-chips.

Jueping Cai, State Key Discipline Laboratory of Wide Band Gap Semiconductor Technology, School of Microelectronics, Xidian University, Xi’an, China

Jueping Cai received the B.S. and M.S. degrees in Electronic Engineering from Xidian University, Xi’an, China, in 1998 and 2001 respectively, and received the Ph.D. degree from Shanghai Jiaotong University, Shanghai, China, in 2004. He is currently an professor in school of Microelectronics, Xi’an, China. His research interests are singal processing, low-power mixed-signal integrated circuits and IC design.

Yequn Wang, Institute of Information and Navigation, Air Force Engineering University, Xi’an, China

Yequn Wang received the M.S.and Ph.D degrees from Air Force Engineering University, Xi’an, China, in 2009 and 2012 respectively, where he is currently a Lecturer with the Information and Navigation College. His main research interests include aeronautical communication, ad hoc networks, satellite communication, and HF communication.

Jian Liu, Institute of Information and Navigation, Air Force Engineering University, Xi’an, China

Jian Liu received the M.S. degree from Air Force Engineering University (AFEU), in 2003, and the Ph.D. degree from the National University of Defense Technology (NUDT), in 2007. He is currently an Associate Professor with the Information and Navigation College, Air Force Engineering University (AFEU). His main research interests include integration of radar and communication, and electronic warfare and array signal processing.

References

Rohbani, N., Shirmohammadi, Z., Zare, M., &Miremadi, S. G., Laxy: a location-based aging-resilient xy-yx routing algorithm for network on chip, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1-1,2017.

Bogdan, P., Tudor Dumitraș, & Muarculescu, R., Stochastic communication: a new paradigm for fault-tolerant networks-on-chip. VLSI Design, special issue on Networks-on-Chip, 17, 2007.

Yu Ren, Leibo Liu, Shouyi Yin, Jie Han, & Shaojun Wei, A fault tolerant noc architecture using quad-spare mesh topology and dynamic reconfiguration. Journal of Systems Architecture, 59(7), 482-491, 2013.

Glass, C. J., & Ni, L. M., The Turn Model for Adaptive Routing. Computer Architecture, 1992. Proceedings. The 19th Annual International Symposium on. ACM, 1992.

Zhang Zhen,Alain Greiner,Sami Taktak, A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip[A].Proceedings of Design Automation Conference. 441-446, 2008.

Jiang, S. Y., Luo, G., Liu, Y., Jiang, S. S., & Li, X. T., Fault-tolerant routing algorithm simulation and hardware verification of noc. IEEE Transactions on Applied Superconductivity, 24(5), 1-5, 2014.

Liu, Y., Ruan, Y., Lai, Z., & Sun, L., A reconfigurable routing method for fault-tolerant mesh-based network on chip. Journal of Information and Computational Science, 10(1), 157-165, 2013.

Fu, B., Han, Y., Li, H., & Li, X., Zonedefense: a fault-tolerant routing for 2-d meshes without virtual channels. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 22(1), 113-126, 2014.

Wu, J., A fault-tolerant and deadlock-free routing protocol in 2d meshes based on odd-even turn model. Computers IEEE Transactions, 52(9), 1154-1169, 2003.

Boppana, R. V., & Chalasani, S., [ACM Press the 1994 ACM/IEEE conference - Washington, D.C. (1994.11.14-1994.11.18)] Proceedings of the 1994 ACM/IEEE conference on Supercomputing, - Supercomputing "94 - Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks. (pp.693), 1994.

Chiu, G. M., The odd-even turn model for adaptive routing. IEEE Transactions on Parallel and Distributed Systems, 11(7), 0-738, 2000.

Xie, R., Cai, J., Xin, X., & Yang, B., Lbft: a fault-tolerant routing algorithm for load-balancing network-on-chip based on odd–even turn model. The Journal of Supercomputing, 2016.

Hu, J., & Marculescu, R. Dyad - smart routing for networks-on-chip, 2004.

Gratz, P., Grot, B., & Keckler, S. W, Regional congestion awareness for load balance in networks-on-chip, 2008.

Chang, En Jui, et al., Path-Congestion-Aware Adaptive Routing With a Contention Prediction Scheme for Network-on-Chip Systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33(1),113-126, 2014.

Bahrebar, Poona, and D. Stroobandt,Adaptive and reconfigurable fault-tolerant routing method for 2D Networks-on-Chip. International Conference on Reconfigurable Computing & Fpgas IEEE, 2015.

Fu, Binzhang, et al.,An abacus turn model for time/space-efficient reconfigurable routing. International Symposium on Computer Architecture, 2011.

Ebrahimi, M., Daneshtalab, M., Plosila, J., & Tenhunen, H., Minimal-path fault-tolerant approach using connection-retaining structure in Networks-on-Chip. Networks on Chip (NoCS), 2013 Seventh IEEE/ACM International Symposium on. ACM, 2013.

Ramakrishna, M., Kodati, V. K., Gratz, P. V., & Sprintson, A., Gca:global congestion awareness for load balance in networks-on-chip. IEEE Transactions on Parallel and Distributed Systems, 27(7), 2022-2035, 2016.

Wang, J., Huang, L., Li, G., Wang, X., & Mak, T., A Fault-Tolerant Routing Algorithm for NoC Using Farthest Reachable Routers, 2013.

Ebrahimi, M., Daneshtalab, M., Plosila, J., & Mehdipour, F., MD: Minimal path-based fault-tolerant routing in on-Chip Networks. 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 2013.

Chaix, F., Avresky, D., Zergainoh, N. E., & Nicolaidis, M., A Fault-Tolerant Deadlock-Free Adaptive Routing for On Chip Interconnects. Design, Automation & Test in Europe Conference & Exhibition (DATE), 2011. IEEE, 2011.

Chen, Y. Y., Chang, E. J., Hsin, H. K., Chen, K. C., & Wu, A. Y., Path-diversity-aware fault-tolerant routing algorithm for network-on-chip systems. IEEE Transactions on Parallel and Distributed Systems, 1-1, 2016.

Dally, William, and B. Towles, Principles and Practices of Interconnection Networks, 2004.

Lin, Shu Yen, et al., Traffic-Balanced Routing Algorithm for Irregular Mesh-Based On-Chip Networks.IEEE Transactions on Computers, 57(9),1156-1168, 2008.

Cai, Jueping, Xin, Yang, Bo, & Xie, et al. (2017). Mcar: non-local adaptive network-on-chip routing with message propagation of congestion information. Microprocessors and microsystems.

Downloads

Published

2020-12-23

How to Cite

Guan, J. ., Cai, J., Wang, Y. ., & Liu, J. . (2020). Fault-tolerant and Congestion Balanced Routing Algorithm for 2D Mesh NoCs. Journal of Web Engineering, 19(7-8), 1049–1066. https://doi.org/10.13052/jwe1540-9589.19786

Issue

2020: Vol 19 Iss 7-8

Section

Advanced Practice in Web Engineering