Routing Based on Routing Table for Irregular Mesh NoC

doi:10.3969/j.issn.1000-3428.2013.10.060

Abstract

Abstract: Network-on-Chip(NoC) system often integrates many heterogeneous components which have different sizes. This NoC has an irregular topology. In the irregular mesh, traditional routing algorithm may not be usable any more. To solve the routing problem, this paper proposes a novel routing algorithm, called INC routing algorithm. INC routing is based on two small routing tables, FDT and IFDT. The simulation result shows that the routing scheme can find the shortest path between two nodes in most cases, which reduces the latency a lot. And the routing tables FDT and IFDT have a fixed size of 12 items. Their sizes do not increase when mesh grows.

Key words: Network-on-Chip(NoC), irregular topology structure, routing algorithm, routing table, routing node, fault-tolerant

摘要： 片上网络(NoC)系统通常集成很多不同尺寸大小的IP模块，具有不规则的拓扑结构，传统的路由算法可能不再适用。针对NoC不规则拓扑结构的路由问题，提出INC路由算法。该算法采用2个很小的路由表，即FDT路由表和IFDT路由表。实验结果证明，INC路由算法在多数情况下能找到2个节点之间的最短路径，平均延时小，而且FDT和IFDT路由表只有固定的12项，大小不会随着片上网络规模的增大而增大。

关键词: 片上网络, 不规则拓扑结构, 路由算法, 路由表, 路由节点, 容错

CLC Number:

TP393

LI Hui-min, SHEN Hai-bin. Routing Based on Routing Table for Irregular Mesh NoC[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.10.060.

李惠民，沈海斌. 不规则Mesh NoC上基于路由表的路由[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.10.060.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2013.10.060

http://www.ecice06.com/EN/Y2013/V39/I10/279

References

(上接第282页) 参考文献 [1] 徐欣, 王长山. 一种不规则2D Mesh的NoC路由算法[J]. 计算机与现代化, 2010, (5): 111-114. [2] Dally W J, Seitz C L. Deadlock-free Message Routing in Multiprocessor Interconnection Networks[J]. IEEE Trans. on Computers, 1987, 36(5): 547-553. [3] Zhang Zhen, Greiner A, Taktak S. A Reconfigurable Routing Algorithm for a Fault-tolerant 2D-mesh Network-on-Chip[C]// Proc. of the 45th ACM/IEEE Design Automation Conference. Anaheim, USA: IEEE Press, 2008: 441-446. [4] Mohtashamzadeh M, Momeni L, Rezazadeh A, et al. A New Routing Algorithm for Irregular Mesh NoCs Without Virtual Channel[C]//Proc. of the 5th European Symposium on Computer Modeling and Simulation. [S. l.]: IEEE Press, 2011: 335-338. [5] Schafer M K F, Hollstein T, Zimmer H, et al. Deadlock-free Routing and Component Placement for Irregular Mesh-based Networks-on-Chip[C]//Proc. of IEEE/ACM International Conference on Computer-aided Design. [S. l.]: IEEE Press, 2005: 238-245. [6] 段新明, 杨愚鲁. 基于不规则Mesh的无死锁路由[J]. 小型微型计算机系统, 2008, 29(7): 1215-1218. [7] Schonwald T, Zimmermann J, Bringmann O, et al. Fully Adaptive Fault-tolerant Routing Algorithm for Network-on- Chip Architectures[C]//Proc. of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools. [S. l.]: IEEE Press, 2007: 527-534. [8] Bolotin E, Cidon I, Ginosar R, et al. Routing Table Minimi- zation for Irregular Mesh NoCs[C]//Proc. of Conference on Design, Automation and Test in Europe. [S. l.]: IEEE Press, 2007: 1-6. [9] Wu Jie. A Fault-tolerant and Deadlock-free Routing Protocol in 2D Meshes Based on Odd-even Turn Model[J]. IEEE Trans. on Computers, 2003, 52(9): 1154-1169. [10] Sui Pao-Hwa, Wang Shengde. An Improved Algorithm for Fault-tolerant Wormhole Routing in Meshes[J]. IEEE Trans. on Computers, 1997, 46(9): 1040-1042. 编辑顾逸斐

[1]	WANG Wenxin, HE Yuhang, CHEN Gang. UCaps Network Based on EM-Routing Algorithm for Medical Image Segmentation [J]. Computer Engineering, 2022, 48(2): 268-274.
[2]	LIU Boyang, HU Shukai, SHI Dejun, LU Hongsheng. VTFTR: Deadlock-Free Fault-Tolerant Routing Algorithm in k-Dimension Fat-Tree [J]. Computer Engineering, 2022, 48(12): 38-44,53.
[3]	MIAO Yisheng, ZHAO Chunjiang, WU Huarui. Farmland WSN Routing Optimization Method Based on Improved Particle Swarm Optimization [J]. Computer Engineering, 2022, 48(10): 218-223.
[4]	CHEN Hui, GAO Yan. Uneven Clustering Routing Algorithm for WSNs Based on Double Cluster Heads [J]. Computer Engineering, 2022, 48(10): 184-192.
[5]	ZHANG Ji, XIE Zaipeng, MAO Yingchi, XU Yuanyuan, ZHU Xiaorui, LI Bowen. Fault-Tolerant Algorithm Combined with Distributed Coding Computing in MapReduce Framework [J]. Computer Engineering, 2021, 47(4): 173-179.
[6]	PAN Chengsheng, LIANG Zhiming, SHI Huaifeng, KONG Zhixiang. Optimization Algorithm of Satellite Network Service Function Chain for Concurrent Services [J]. Computer Engineering, 2021, 47(3): 196-201.
[7]	XIE Yongsheng, YANG Yuwang, QIU Xiulin, WANG Yinyin. Optimized FANET Routing Algorithm with Reinforcement Learning Based on Function Approximation [J]. Computer Engineering, 2021, 47(11): 207-213.
[8]	LI Cuiran, LI Ang. Energy Efficient Routing Algorithm for Linear WSN with Solar Energy Harvesting [J]. Computer Engineering, 2020, 46(9): 178-185.
[9]	ZHANG Taijiang, LI Yongjun, ZHAO Shanghong. Optimization Design of Routing Algorithm Based on GEO/LEO Double-Layer Satellite Network [J]. Computer Engineering, 2020, 46(7): 198-205.
[10]	LI Hongbing, LIU Zilu, CHEN Qiang, LIU Sha, LI Xiaolong, LIANG Yuqiao, YANG Zhen, CHEN Liwan. Clustering Routing Algorithm for Wireless Sensor Network Based on Hierarchical Neighboring Nodes [J]. Computer Engineering, 2020, 46(6): 187-195.
[11]	SUN Zeyu, YAN Ben, NIE Yalin, LIU Baoluo, JIA Fuqian, LAI Chunxiao. An Optimized Clustering Routing Algorithm with Controllable Threshold Parameter [J]. Computer Engineering, 2020, 46(3): 184-191.
[12]	YANG Li, QI Yaowen, PAN Chengsheng. SDN-based Transmission Strategies for Heterogeneous Spatial Information Network [J]. Computer Engineering, 2019, 45(7): 71-77,85.
[13]	SUN Li, SU Yu, ZHANG Chi, ZHANG Tao. Research on Fault-Tolerant Method of Erasure Code for Distributed Storage System [J]. Computer Engineering, 2019, 45(11): 74-80.
[14]	ZHANG Bushuo,Lü Na,CHEN Kefan,CAO Fangbo,LIU Chuang. Routing Algorithm with Low Delay and High Reliability for Aeronautic Swarm Network [J]. Computer Engineering, 2018, 44(9): 89-94,100.
[15]	ZHAI Yong,LI Ning,WANG Xiaofei. Routing Algorithm with Exponential Function Modulation Based on Bandwidth Utilization [J]. Computer Engineering, 2018, 44(6): 93-99,103.

Please choose a citation manager

Content to export