Abstract: network on chip (NoC) is an infrastructure providing a communication platform to multiprocessor chips. Furthermore, the wormhole-switching method, which shares resources, was used to increase its efficiency; however, this can lead to congestion. Moreover, dealing with this congestion consumes more energy and correspondingly leads to increase in power consumption. Furthermore, consuming more power results in more heat and increases thermal fluctuations that lessen the life span of the infrastructures and, more importantly, the network’s performance. Given these complications, providing a method that controls congestion is a significant design challenge. In this paper, a fuzzy logic congestion control routing algorithm is presented to enhance the NoC’s performance when facing congestion. To avoid congestion, the proposed algorithm employs the occupied input buffer and the total occupied buffers of the neighboring nodes along with the maximum possible path diversity with minimal path length from instant neighbors to the destination as the selection parameters. To enhance the path selection function, the uncertainty of the fuzzy logic algorithm is used. As a result, the average delay, power consumption, and maximum delay are reduced by 14.88%, 7.98%, and 19.39%, respectively. Additionally, the proposed method enhances the throughput and the total number of packets received by 14.9% and 11.59%, respectively. To show the significance, the proposed algorithm is examined using transpose traffic patterns, and the average delay is improved by 15.3%. The average delay is reduced by 3.8% in TMPEG-4 (treble MPEG-4), 36.6% in QPIP (quadruplicate PIP), and 20.9% in TVOPD (treble VOPD).

面向片上网络的一种模糊集成拥塞感知路由算法

[1]Ascia G, Catania V, Palesi M, et al., 2008. Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip. IEEE Trans Comput, 57(6):809-820.

[2]Badr HG, Podar S, 1989. An optimal shortest-path routing policy for network computers with regular mesh-connected topologies. IEEE Trans Comput, 38(10):1362-1371.

[3]Benini L, de Micheli G, 2002. Networks on chip: a new paradigm for systems on chip design. Design, Automation and Test in Europe Conf and Exhibition, p.418-419.

[4]Catania V, Mineo A, Monteleone S, et al., 2016. Cycle-accurate network on chip simulation with Noxim. ACM Trans Model Comput Simul, 27(1):4.

[5]Chang EJ, Hsin HK, Lin SY, et al., 2014. Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems. IEEE Trans Comput Aided Des Integr Circ Syst, 33(1):113-126.

[6]Chiu GM, 2000. The odd-even turn model for adaptive routing. IEEE Trans Parall Distrib Syst, 11(7):729-738.

[7]Dally WJ, Aoki H, 1993. Deadlock-free adaptive routing in multicomputer networks using virtual channels. IEEE Trans Parall Distrib Syst, 4(4):466-475.

[8]Dally WJ, Towles BP, 2004. Principles and Practices of Interconnection Networks. Elsevier, Francisco, USA.

[9]Ebrahimi M, Tenhunen H, Dehyadegari M, 2013. Fuzzy-based adaptive routing algorithm for networks-on-chip. J Syst Arch, 59(7):516-527.

[10]Fazzino F, Palesi M, Patti D, 2008. Noxim: Network-on-Chip Simulator. http://sourceforge.net/projects/noxim

[11]Feng WC, Shin KG, 1997. Impact of selection functions on routing algorithm performance in multicomputer networks. Proc 11^th Int Conf on Supercomputing, p.132-139.

[12]Gratz P, Grot B, Keckler SW, 2008. Regional congestion awareness for load balance in networks-on-chip. IEEE 14^th Int Symp on High Performance Computer Architecture, p.203-214.

[13]Hu JC, Marculescu R, 2004. DyAD-smart routing for networks-on-chip. Proc 41^st Annual Design Automation Conf, p.260-263.

[14]Khan GN, Chui S, 2017. Congestion aware routing for on-chip communication in NoC systems. Proc 11^th Int Conf on Complex on Complex, Intelligent, and Software Intensive Systems, p.547-556.

[15]Kim J, Park D, Theocharides T, et al., 2005. A low latency router supporting adaptivity for on-chip interconnects. Proc 42^nd Design Automation Conf, p.559-564.

[16]Li M, Zeng QA, Jone WB, 2006. DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip. Proc 43^rd Annual Design Automation Conf, p.849-852.

[17]Liu L, Zhu ZM, Zhou D, et al., 2017. A fair arbitration for network-on-chip routing with odd-even turn model. Microelectron J, 64:1-8.

[18]Ma S, Jerger NE, Wang ZY, 2011. DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip. Proc 38^th Annual Int Symp on Computer Architecture, p.413-424.

[19]Mamaghani SM, Jamali MAJ, 2019. A load-balanced congestion-aware routing algorithm based on time interval in wireless network-on-chip. J Amb Intell Human Comput, 10(7):2869-2882.

[20]Marculescu R, Ogras UY, Peh LS, et al., 2008. Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives. IEEE Trans Comput Aid Des Integr Circ Syst, 28(1):3-21.

[21]Martinez JC, Silla F, López P, et al., 2000. On the influence of the selection function on the performance of networks of workstations. Proc 3^rd Int Symp on High Performance Computing, p.292-299.

[22]Muhammad ST, Saad M, El-Moursy AA, et al., 2019. CFPA: congestion aware, fault tolerant and process variation aware adaptive routing algorithm for asynchronous networks-on-chip. J Parall Distrib Comput, 128:151-166.

[23]Nilsson E, Millberg M, Oberg J, et al., 2003. Load distribution with the proximity congestion awareness in a network on chip. Design, Automation and Test in Europe Conf and Exhibition, p.1126-1127.

[24]Pande PP, Grecu C, Jones M, et al., 2005. Performance evaluation and design trade-offs for network-on-chip interconnect architectures. IEEE Trans Comput, 54(8):1025-1040.

[25]Pano V, Lerner S, Yilmaz I, et al., 2018. Workload-aware routing (WAR) for network-on-chip lifetime improvement. IEEE Int Symp on Circuits and Systems, p.1-5.

[26]Ramanujam RS, Lin B, 2010. Destination-based adaptive routing on 2D mesh networks. Proc 6^th ACM/IEEE Symp on Architectures for Networking and Communications Systems, p.1-12.

[27]Rezaei-Ravari M, Sattari-Naeini V, 2018. Reliable congestion-aware path prediction mechanism in 2D NoCs based on EFuNN. J Supercomput, 74(11):6102-6125.

[28]Shu H, Ma PJ, Shi JY, et al., 2014. SRNoC: a novel high performance shared-resource routing scheme for network-on-chip. Microelectron J, 45(8):1103-1117.

[29]Touati HC, Boutekkouk F, 2017. A weighted minimal fully adaptive congestion aware routing algorithm for network on chip. Proc 1^st Int Conf on Embedded & Distributed Systems, p.1-5.

[30]Varatkar GV, Marculescu R, 2004. On-chip traffic modeling and synthesis for MPEG-2 video applications. IEEE Trans Very Large Scale Integr Syst, 12(1):108-119.