直线引导的Torus结构路由算法

计算机工程与科学

直线引导的Torus结构路由算法

丁毓良，张剑贤，周端，裘雪红

（西安电子科技大学计算机学院，陕西西安 710071）

收稿日期:2016-08-15 修回日期:2016-10-20 出版日期:2017-02-25 发布日期:2017-02-25
基金资助:
国家自然科学基金（61474087）

A Torus network routing algorithm guided by straight line

DING Yuliang，ZHANG Jianxian，ZHOU Duan，QIU Xuehong

（School of Computer Science and Technology,Xidian University,Xi’an 710071,China）

Received:2016-08-15 Revised:2016-10-20 Online:2017-02-25 Published:2017-02-25

摘要/Abstract

摘要：

为了提高片上网络在Torus拓扑结构下的路由通信效率，提出了一种基于直线引导思想的路由算法Tline。该路由算法将Torus拓扑结构的片上网络拓展为类似Mesh结构的坐标平面，以数据包的源节点和目的节点构成的直线为路由转发方向，并根据周围邻近节点的拥塞状况选择传输路径方向实现部分自适应路由。实验结果表明，与XY、OE路由算法相比，在热点流量模式下Tline路由算法具有较好的路由性能，且平均能耗降低约8%。

关键词: 片上网络, Torus拓扑, 路由算法, 直线引导

Abstract:

To increase the communication efficiency of the network on chip in TORUS topology, we propose a new routing algorithm based on straight line guidance, namely Tline routing. The new algorithm extends the Torus topology to a coordinate plane that is similar to the mesh structure. The route forwarding direction is guided by a straight line formed by the source and destination of packets. The partially adaptive routing is realized according to the congestion condition around the neighboring nodes. Experimental results show that the Tline routing can achieve better routing performance in comparison with the XY and OE routing algorithms, and the average power consumption decreases by about 8%.

Key words: network on chip, Torus topology, routing algorithm, straight line guidance

丁毓良，张剑贤，周端，裘雪红. 直线引导的Torus结构路由算法[J]. 计算机工程与科学.

DING Yuliang，ZHANG Jianxian，ZHOU Duan，QIU Xuehong. A Torus network routing algorithm guided by straight line [J]. Computer Engineering & Science.

[1]	高文才, 陈小文. 一种基于混合加固的容软错误NoC路由器[J]. 计算机工程与科学, 2023, 45(08): 1376-1382.
[2]	葛一漩, 李晨, 陈小文, 鲁建壮, 郭阳. 一种定制片上网络设计探索算法的设计与实现[J]. 计算机工程与科学, 2023, 45(06): 970-978.
[3]	康子扬, 彭凌辉, 周干, 林博, 王蕾. 一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法[J]. 计算机工程与科学, 2022, 44(06): 986-993.
[4]	陈小帆, 杨智杰, 彭凌辉, 王世英, 周干, 李石明, 康子扬, 王耀, 石伟, 王蕾. 一种类脑处理器片上网络的验证框架[J]. 计算机工程与科学, 2022, 44(05): 769-778.
[5]	石伟, 龚锐, 刘威, 王蕾, 冯权友, 张剑锋. 面向高带宽I/O的片上网络优化[J]. 计算机工程与科学, 2021, 43(09): 1538-1545.
[6]	齐星云, 戴艺, 赖明澈, 常俊胜, 董德尊. 基于偏折路由的双环片上网络[J]. 计算机工程与科学, 2021, 43(03): 381-388.
[7]	吉慧，周磊. 面向温度优化的片上网络任务调度方法[J]. 计算机工程与科学, 2018, 40(09): 1527-1533.
[8]	任春江，降爱莲. 基于移动状态的车载自组织网络路由算法[J]. 计算机工程与科学, 2018, 40(03): 464-471.
[9]	陈继承，王洪伟，张闯. 一种面向三维众核微处理器的新型NoC拓扑结构[J]. 计算机工程与科学, 2016, 38(08): 1542-1549.
[10]	宋国治，涂遥，张大坤，温越博. 一种用于片上网络布图规划的改进模拟退火与粒子群混合算法[J]. J4, 2016, 38(05): 863-870.
[11]	曹继军，郑义，王克非，肖立权. 具有原路返回特征的改进OSRM胖树路由算法研究[J]. J4, 2014, 36(06): 997-1004.
[12]	孙践知，张迎新，陈丹，韩忠明. 具有退避机制的Epidemic路由算法[J]. J4, 2013, 35(3): 66-71.
[13]	肖灿文,戴泽福,张民选. 新型适应性路由器微体系结构研究[J]. J4, 2013, 35(11): 22-26.
[14]	齐树波，李晋文，乐大珩，赵天磊，张民选. 一种面向片上互连的自适应通道双缓冲延迟模型[J]. J4, 2012, 34(9): 58-63.
[15]	朱幸辉,黄镜如. 片上网络路由算法分析与评估[J]. J4, 2012, 34(5): 63-67.