PDF(1301 KB)
A Fault-Tolerant Routing Algorithm Aiming at a Path Fault and Local Congestion in NoC
OUYANG Yi-ming, HE Xin-cheng, LIANG Hua-guo, YI Mao-xiang, DU Gao-ming, AN Xin
ACTA ELECTRONICA SINICA ›› 2016, Vol. 44 ›› Issue (4) : 920-925.
PDF(1301 KB)
PDF(1301 KB)
A Fault-Tolerant Routing Algorithm Aiming at a Path Fault and Local Congestion in NoC
As a new type of on-chip interconnection architecture,network-on-chip overcomes the bottleneck problem of the system-on-chip during the development.However,a failure arising in a router or a link between routers in network-on-chip will cause the reduction of network performance.To avoid this phenomenon,this paper puts forward a fault-tolerant routing algorithm aiming at a path fault and local congestion in network-on-chip.Firstly,the algorithm designs a fault model that reflects the fault status of the path within two hops.As a result,this novel fault model makes the router achieve a dynamic perception of path state within two hops with less cost.Secondly,a novel congestion model has been proposed for reflecting the state of the local network more accurately,contributing to balance network traffic.Finally,when a fault occurs,the algorithm not only is fault-tolerant but also makes sure the network has a good performance.What's more,the algorithm chooses the optimal path under the condition of fault-free.Experimental results show that the proposed algorithm has 10%~20% lower latency in average and 25% higher throughput rate than the contrast case when the network is fault-free.In the case of defective in the network,the advantage of the present scheme has a bigger superiority.
network-on-chip / fault model / congestion model / fault-tolerant routing algorithm {{custom_keyword}} /
[1] DiTomaso D,Kodi A,Louri A.QORE: A fault tolerant network-on-chip architecture with power-efficient quad-function channel (QFC) buffers[A].IEEE 20th International Symposium on High Performance Computer Architecture (HPCA) [C].IEEE,2014.320-331.
[2] 王新玉,向东,虞志刚.TM: 一种新的片上网络拓扑结构[J].计算机学报,2014,37(11):2327-2341. Wang Xin-yu,Xiang Dong,Yu Zhi-gang.TM: A new topology for networks-on-chip[J].Chinese Journal of Computers,2014,37(11):2327-2341.(in Chinese)
[3] 欧阳一鸣,陈义军,梁华国,等.一种故障通道隔离的低开销容错路由器设计[J].电子学报,2014,42(11): 2142-2149. Ouyang Yi-ming,Chen Yi-jun,Liang Hua-guo.Design of a low-overhead fault channel isolated fault-tolerant router [J].Acta Electronica Sinica,2014,42(11): 2142-2149.(in Chinese)
[4] Liu C,Zhang L,Han Y,et al.Vertical interconnects squeezing in symmetric 3D mesh network-on-chip[A].Proceedings of the 16th Asia and South Pacific Design Automation Conference[C].IEEE,2011.357-362.
[5] 欧阳一鸣,张一栋,梁华国,等.三维片上网络故障及拥塞感知的容错路由器设计[J].电子学报,2013,41(5): 912-917. Ouyang Yi-ming,Zhang yi-dong,Liang Hua-guo.A fault-tolerant design of congestion-aware router in three-dimensional network-on-chip [J].Acta Electronica Sinica,2013,41(5) :912-917.( in Chinese)
[6] 付斌章,韩银和,李华伟,等.面向高可靠片上网络通信的可重构路由算法[J].计算机辅助设计与图形学学报,2011,23(3): 448-455. Fu Bin-zhang,Han Yin-he,Li Hua-wei.Building resilient NoC with a reconfigurable routing algorithm[J].Journal of Computer-Aided Design & Computer Graphics,2011,23(3): 448-455.(in Chinese)
[7] Feng C,Zhang M,Li J,et al.A low-overhead fault-aware deflection routing algorithm for 3D network-on-chip[A].IEEE Computer Society Annual Symposium on VLSI (ISVLSI) [C].IEEE,2011.19-24.
[8] 刘家俊,顾华玺,王长山.mesh 优先级容错路由[J].计算机工程与应用,2009,45(4): 105-107. Liu Jia-jun,Gu Hua-xi,Wang Chang-shan.Priority fault-tolerant routing in mesh[J].Computer Engineering and Applications,2009,45(4): 105-107.(in Chinese)
[9] Ma S,Jerger N E,Wang Z.DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip[A].38th Annual International Symposium on Computer Architecture (ISCA)[C].IEEE,2011.413-424.
[10] Wu J.A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd-even turn model[J].IEEE Transactions on Computers,2003,52(9): 1154-1169.
[11] Zhang Z,Greiner A,Taktak S.A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip[A].45th ACM/IEEE Design Automation Conference[C].IEEE,2008.441-446.
[12] Fick D,DeOrio A,Chen G,et al.A highly resilient routing algorithm for fault-tolerant NoCs[A].Proceedings of the Conference on Design,Automation and Test in Europe[C].European Design and Automation Association,2009.21-26.
[13] Valinataj M,Mohammadi S,Plosila J,et al.A fault-tolerant and congestion-aware routing algorithm for networks-on-chip[A].IEEE 13th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS) [C].IEEE,2010.139-144.
[14] Ascia G,Catania V,Palesi M,et al.Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip[J].IEEE Transactions on Computers,2008,57(6): 809-820.
[15] Ebrahimi M,Daneshtalab M,Farahnakian F,et al.HARAQ: congestion-aware learning model for highly adaptive routing algorithm in on-chip networks[A].Sixth IEEE/ACM International Symposium on Networks on Chip (NoCS) [C].IEEE,2012.19-26.
[16] Ying H,Jaiswal A,Hollstein T,et al.Deadlock-free generic routing algorithms for 3-dimensional networks-on-chip with reduced vertical link density topologies[J].Journal of Systems Architecture,2013,59(7): 528-542.
[17] Dubois F,Sheibanyrad A,Pétrot F,et al.Elevator-first: A deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs[J].IEEE Transactions on Computers,2013,62(3): 609-615.
[18] Chen K C,Kuo C C,Hung H S,et al.Traffic-and-thermal-aware adaptive beltway routing for three dimensional network-on-chip systems[A].IEEE International Symposium on Circuits and Systems (ISCAS) [C].IEEE,2013.1660-1663.
[19] Sedghi M,Koopahi E,Alaghi A,et al.An NoC test strategy based on flooding with power,test time and coverage considerations[A].21st International Conference on VLSI Design[C].IEEE,2008.409-414.
[20] DeOrio A,Fick D,Bertacco V,et al.A reliable routing architecture and algorithm for NoCs[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2012,31(5): 726-739.
PDF(1301 KB)
/
| 〈 |
|
〉 |
