Full Text:   <1080>

Summary:  <1120>

CLC number: TN913

On-line Access: 2021-05-17

Received: 2020-02-11

Revision Accepted: 2020-06-16

Crosschecked: 2021-03-29

Cited: 0

Clicked: 2082

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Akram Reza

https://orcid.org/0000-0003-3853-2734

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2021 Vol.22 No.5 P.741-755

http://doi.org/10.1631/FITEE.2000069


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


Author(s):  Shahrouz Yasrebi, Akram Reza, Mohammad Nikravan, Seena Vazifedan

Affiliation(s):  Department of Computer Engineering, Shahr-e-Qods Branch, Islamic Azad University, Tehran, Iran; more

Corresponding email(s):   a.reza@qodsiau.ac.ir, a.ak.reza@gmail.com

Key Words:  Network on chip, Routing algorithm, Congestion control, Fuzzy logic


Shahrouz Yasrebi, Akram Reza, Mohammad Nikravan, Seena Vazifedan. A fuzzy integrated congestion-aware routing algorithm for network on chip[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(5): 741-755.

@article{title="A fuzzy integrated congestion-aware routing algorithm for network on chip",
author="Shahrouz Yasrebi, Akram Reza, Mohammad Nikravan, Seena Vazifedan",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="22",
number="5",
pages="741-755",
year="2021",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000069"
}

%0 Journal Article
%T A fuzzy integrated congestion-aware routing algorithm for network on chip
%A Shahrouz Yasrebi
%A Akram Reza
%A Mohammad Nikravan
%A Seena Vazifedan
%J Frontiers of Information Technology & Electronic Engineering
%V 22
%N 5
%P 741-755
%@ 2095-9184
%D 2021
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000069

TY - JOUR
T1 - A fuzzy integrated congestion-aware routing algorithm for network on chip
A1 - Shahrouz Yasrebi
A1 - Akram Reza
A1 - Mohammad Nikravan
A1 - Seena Vazifedan
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 22
IS - 5
SP - 741
EP - 755
%@ 2095-9184
Y1 - 2021
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000069


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

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

Shahrouz YASREBI1,Akram REZA1,Mohammad NIKRAVAN1,Seena VAZIFEDAN2
1伊斯兰阿扎德大学Shahr-e-Qods分校计算机工程系,伊朗德黑兰市
2伊斯兰阿扎德大学科学与研究分校计算机体系结构系,伊朗德黑兰市

摘要:片上网络(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%。

关键词:片上网络;路由算法;拥塞控制;模糊逻辑

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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 11th 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 14th Int Symp on High Performance Computer Architecture, p.203-214.

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

[14]Khan GN, Chui S, 2017. Congestion aware routing for on-chip communication in NoC systems. Proc 11th 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 42nd 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 43rd 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 38th 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 3rd 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 6th 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 1st 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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE