Fault-tolerant and Congestion Balanced Routing Algorithm for 2D Mesh NoCs
DOI:
https://doi.org/10.13052/jwe1540-9589.19786Keywords:
Network-on-Chip (NoC), fault-tolerant routing algorithm, path channels, freebuffer lengthAbstract
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
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.
