A fuzzy integrated congestion-aware routing algorithm for network on chip

Shahrouz YASREBI; Akram REZA; Mohammad NIKRAVAN; Seena VAZIFEDAN

doi:10.1631/FITEE.2000069

Your Location：

Home >

Browse articles >

A fuzzy integrated congestion-aware routing algorithm for network on chip

Regular Papers | Updated：2022-05-19

- A fuzzy integrated congestion-aware routing algorithm for network on chip
- 面向片上网络的一种模糊集成拥塞感知路由算法
- Frontiers of Information Technology & Electronic Engineering Vol. 22, Issue 5, Pages: 741-755(2021)
- Affiliations：
  
  Department of Computer Engineering, Shahr-e-Qods Branch, Islamic Azad University, Tehran, Iran
  Department of Computer Architecture, Science and Research Branch, Islamic Azad University, Tehran, Iran
- Author bio：
  
  Akram REZA, E-mail: a.reza@qodsiau.ac.ir; a.ak.reza@gmail.com
- Funds：
- DOI：10.1631/FITEE.2000069
  CLC： TN913
- Received：11 February 2020，
  
  Revised：2021-;5-29，
  
  Published：2021-05
- Accepted：
Scan QR Code
Shahrouz YASREBI, Akram REZA, Mohammad NIKRAVAN, et al. A fuzzy integrated congestion-aware routing algorithm for network on chip[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(5): 741-755.
DOI：

Shahrouz YASREBI, Akram REZA, Mohammad NIKRAVAN, et al. A fuzzy integrated congestion-aware routing algorithm for network on chip[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(5): 741-755. DOI： 10.1631/FITEE.2000069.

摘要

片上网络（NoC）是一种为多处理器芯片提供通信平台的基础设施。共享资源的虫孔交换方法在提升其效率的同时，也可能导致拥塞问题的出现。然而，处理这种拥塞问题需更多能耗，从而增加了耗电量。此外，耗电量的增加会产生更多热量并加剧热量波动，从而削减基础设施寿命，更严重的是降低网络性能。考虑到这些复杂性，提出控制拥塞的方法是一个重大挑战。本文提出一种模糊逻辑拥塞控制路由算法，以提高NoC在面对拥塞时的性能。为避免拥塞，所提算法采用被占用的输入缓冲区、相邻节点的总占用缓冲区以及从瞬时相邻节点到终点最短路径下最大可能的路径多样性作为选择参数。为强化路径选择函数，利用了模糊逻辑算法的不确定性。结果表明，平均时延、功耗和最大时延分别降低14.88%、7.98%和19.39%。此外，该方法提高了14.9%的吞吐量和11.59%的接收数据包总数。为凸显所提算法的重要性，采用转置流量模式进行检验，平均延迟改善15.3%。TMPEG-4（三倍MPEG-4）、QPIP（四倍PIP）和TVOPD（三倍VOPD）的平均延迟分别降低3.8%、36.6%和20.9%。

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).

关键词

Keywords

references

G Ascia , , , V Catania , , , M Palesi , , , 等 . . Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip . . IEEE Trans Comput , , 2008 . . 57 ( ( 6 ): ): 809 - - 820 . . DOI: 10.1109/TC.2008.38 http://doi.org/10.1109/TC.2008.38 . .

HG Badr , , , S Podar . . An optimal shortest-path routing policy for network computers with regular mesh-connected topologies . . IEEE Trans Comput , , 1989 . . 38 ( ( 10 ): ): 1362 - - 1371 . . DOI: 10.1109/12.35831 http://doi.org/10.1109/12.35831 . .

L Benini , , , G de Micheli . . Networks on chip: a new paradigm for systems on chip design . . Design, Automation and Test in Europe Conf and Exhibition , , 2002 . . p.418 - - 419 . . DOI: 10.1109/DATE.2002.998307 http://doi.org/10.1109/DATE.2002.998307 . .

V Catania , , , A Mineo , , , S Monteleone , , , 等 . . Cycle-accurate network on chip simulation with Noxim . . ACM Trans Model Comput Simul , , 2016 . . 27 ( ( 1 ): ): 4 DOI: 10.1145/2953878 http://doi.org/10.1145/2953878 . .

EJ Chang , , , HK Hsin , , , SY Lin , , , 等 . . Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems . . IEEE Trans Comput Aided Des Integr Circ Syst , , 2014 . . 33 ( ( 1 ): ): 113 - - 126 . . DOI: 10.1109/TCAD.2013.2282262 http://doi.org/10.1109/TCAD.2013.2282262 . .

GM Chiu . . The odd-even turn model for adaptive routing . . IEEE Trans Parall Distrib Syst , , 2000 . . 11 ( ( 7 ): ): 729 - - 738 . . DOI: 10.1109/71.877831 http://doi.org/10.1109/71.877831 . .

WJ Dally , , , H Aoki . . Deadlock-free adaptive routing in multicomputer networks using virtual channels . . IEEE Trans Parall Distrib Syst , , 1993 . . 4 ( ( 4 ): ): 466 - - 475 . . DOI: 10.1109/71.219761 http://doi.org/10.1109/71.219761 . .

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

M Ebrahimi , , , H Tenhunen , , , M Dehyadegari . . Fuzzy-based adaptive routing algorithm for networks-on-chip . . J Syst Arch , , 2013 . . 59 ( ( 7 ): ): 516 - - 527 . . DOI: 10.1016/j.sysarc.2013.03.006 http://doi.org/10.1016/j.sysarc.2013.03.006 . .

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

WC Feng , , , KG Shin . . Impact of selection functions on routing algorithm performance in multicomputer networks . . Proc 11 th Int Conf on Supercomputing , , 1997 . . p.132 - - 139 . . DOI: 10.1145/263580.263616 http://doi.org/10.1145/263580.263616 . .

P Gratz , , , B Grot , , , SW Keckler . . Regional congestion awareness for load balance in networks-on-chip . . IEEE 14 th Int Symp on High Performance Computer Architecture , , 2008 . . p.203 - - 214 . . DOI: 10.1109/HPCA.2008.4658640 http://doi.org/10.1109/HPCA.2008.4658640 . .

JC Hu , , , R Marculescu . . DyAD-smart routing for networks-on-chip . . Proc 41 st Annual Design Automation Conf , , 2004 . . p.260 - - 263 . . DOI: 10.1145/996566.996638 http://doi.org/10.1145/996566.996638 . .

GN Khan , , , S Chui . . Congestion aware routing for on-chip communication in NoC systems . . Proc 11 th Int Conf on Complex on Complex, Intelligent, and Software Intensive Systems , , 2017 . . p.547 - - 556 . . DOI: 10.1007/978-3-319-61566-0_50 http://doi.org/10.1007/978-3-319-61566-0_50 . .

J Kim , , , D Park , , , T Theocharides , , , 等 . . A low latency router supporting adaptivity for on-chip interconnects . . Proc 42 nd Design Automation Conf , , 2005 . . p.559 - - 564 . . DOI: 10.1109/DAC.2005.193873 http://doi.org/10.1109/DAC.2005.193873 . .

M Li , , , QA Zeng , , , WB Jone . . DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip . . Proc 43 rd Annual Design Automation Conf , , 2006 . . 849 - - 852 . . DOI: 10.1145/1146909.1147125 http://doi.org/10.1145/1146909.1147125 . .

L Liu , , , ZM Zhu , , , D Zhou , , , 等 . . A fair arbitration for network-on-chip routing with odd-even turn model . . Microelectron J , , 2017 . . 64 1 - - 8 . . DOI: 10.1016/j.mejo.2017.04.002 http://doi.org/10.1016/j.mejo.2017.04.002 . .

S Ma , , , NE Jerger , , , ZY Wang . . DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip . . Proc 38 th Annual Int Symp on Computer Architecture , , 2011 . . p.413 - - 424 . . DOI: 10.1145/2000064.2000113 http://doi.org/10.1145/2000064.2000113 . .

SM Mamaghani , , , MAJ Jamali . . A load-balanced congestion-aware routing algorithm based on time interval in wireless network-on-chip . . J Amb Intell Human Comput , , 2019 . . 10 ( ( 7 ): ): 2869 - - 2882 . . DOI: 10.1007/s12652-018-1020-z http://doi.org/10.1007/s12652-018-1020-z . .

R Marculescu , , , UY Ogras , , , LS Peh , , , 等 . . Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives . . IEEE Trans Comput Aid Des Integr Circ Syst , , 2008 . . 28 ( ( 1 ): ): 3 - - 21 . . DOI: 10.1109/TCAD.2008.2010691 http://doi.org/10.1109/TCAD.2008.2010691 . .

JC Martinez , , , F Silla , , , P López , , , 等 . . On the influence of the selection function on the performance of networks of workstations . . Proc 3 rd Int Symp on High Performance Computing , , 2000 . . p.292 - - 299 . . DOI: 10.1007/3-540-39999-2_27 http://doi.org/10.1007/3-540-39999-2_27 . .

ST Muhammad , , , M Saad , , , AA El-Moursy , , , 等 . . CFPA: congestion aware, fault tolerant and process variation aware adaptive routing algorithm for asynchronous networks-on-chip . . J Parall Distrib Comput , , 2019 . . 128 151 - - 166 . . DOI: 10.1016/j.jpdc.2019.03.001 http://doi.org/10.1016/j.jpdc.2019.03.001 . .

E Nilsson , , , M Millberg , , , J Oberg , , , 等 . . Load distribution with the proximity congestion awareness in a network on chip . . Design, Automation and Test in Europe Conf and Exhibition , , 2003 . . p.1126 - - 1127 . . DOI: 10.1109/DATE.2003.1253765 http://doi.org/10.1109/DATE.2003.1253765 . .

PP Pande , , , C Grecu , , , M Jones , , , 等 . . Performance evaluation and design trade-offs for network-on-chip interconnect architectures . . IEEE Trans Comput , , 2005 . . 54 ( ( 8 ): ): 1025 - - 1040 . . DOI: 10.1109/TC.2005.134 http://doi.org/10.1109/TC.2005.134 . .

V Pano , , , S Lerner , , , I Yilmaz , , , 等 . . Workload-aware routing (WAR) for network-on-chip lifetime improvement . . IEEE Int Symp on Circuits and Systems , , 2018 . . p.1 - - 5 . . DOI: 10.1109/ISCAS.2018.8351621 http://doi.org/10.1109/ISCAS.2018.8351621 . .

RS Ramanujam , , , B Lin . . Destination-based adaptive routing on 2D mesh networks . . Proc 6 th ACM/IEEE Symp on Architectures for Networking and Communications Systems , , 2010 . . p.1 - - 12 . . DOI: 10.1145/1872007.1872030 http://doi.org/10.1145/1872007.1872030 . .

M Rezaei-Ravari , , , V Sattari-Naeini . . Reliable congestion-aware path prediction mechanism in 2D NoCs based on EFuNN . . J Supercomput , , 2018 . . 74 ( ( 11 ): ): 6102 - - 6125 . . DOI: 10.1007/s11227-018-2515-2 http://doi.org/10.1007/s11227-018-2515-2 . .

H Shu , , , PJ Ma , , , JY Shi , , , 等 . . SRNoC: a novel high performance shared-resource routing scheme for network-on-chip . . Microelectron J , , 2014 . . 45 ( ( 8 ): ): 1103 - - 1117 . . DOI: 10.1016/j.mejo.2014.05.008 http://doi.org/10.1016/j.mejo.2014.05.008 . .

HC Touati , , , F Boutekkouk . . A weighted minimal fully adaptive congestion aware routing algorithm for network on chip . . Proc 1 st Int Conf on Embedded & Distributed Systems , , 2017 . . p.1 - - 5 . . DOI: 10.1109/EDIS.2017.8284033 http://doi.org/10.1109/EDIS.2017.8284033 . .

GV Varatkar , , , R Marculescu . . On-chip traffic modeling and synthesis for MPEG-2 video applications . . IEEE Trans Very Large Scale Integr Syst , , 2004 . . 12 ( ( 1 ): ): 108 - - 119 . . DOI: 10.1109/TVLSI.2003.820523 http://doi.org/10.1109/TVLSI.2003.820523 . .

Views

208

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Jointly optimized congestion control, forwarding strategy, and link scheduling in a named-data multihop wireless network

A dynamic signal coordination control method for urban arterial roads and its application

A framework for analysis of extended fuzzy logic

Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems

Related Author

Cheng-cheng LI

Ren-chao XIE

Tao HUANG

Yun-jie LIU

Guo-jiang SHEN

Yong-yao YANG

Farnaz SABAHI

M.-R. AKBARZADEH-T

Related Institution

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications

Beijing Advanced Innovation Center for Future Internet Technology, Beijing University of Technology

College of Computer Science and Technology, Zhejiang University of Technology

Zhejiang Zheda Supcon Information Technique Co., Ltd.

Center of Excellence on Soft Computing and Intelligent Information Processing, Department of Electrical Engineering, Ferdowsi University of Mashhad, Mashhad

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰