基于S_3变换的TriBA-Net最短路径路由机制  

A shortest path routing mechanism based on S_3 for TriBA-Net

作　　者：石峰[1] 陈旭[1] 尹飞 王小军[1] 胡森森[1] 计卫星[1] 王一拙[1] 高玉金[1] 卫晋 

机构地区：[1]北京理工大学计算机学院,北京100081

出　　处：《中国科学：信息科学》2018年第1期100-114,共15页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61300011;61300010)资助项目

摘　　要：片上网络中路由算法的设计对芯片的性能有直接的影响.本文针对TriBA-Net网络提出一种新颖的最短路径.路由算法.首先,基于TriBA-Net网络设计了一种编码方法,该编码方法中所用到的文字1,3,2的集合与群论中的三文字集S_3群具有相同的含义.其次,设计了一种相隔节点间的通信模型,根据通信路径端点的可能状态,将通信划分为6种宏观数据流动模式.最后,利用S_3群的循环置换特性对通信模型进行简化,在XC6VLX550TL芯片上完成了SPR4T路由器的设计实现.实验结果表明,在27个节点的TriBA-Net网络性能测试中,在均衡负载模式下,与SPORT路由算法相比,SPR4T路由算法的饱和注入率提升7.5%,吞吐率提升7.7%,而且有效降低了硬件以及功耗的开销.The routing algorithm of a Network-on-Chip（NoC） is essential to its performance and power consumption. This paper presents a novel shortest path routing algorithm for TriBA-Net. First, the algorithm designs a coding scheme based on the topological features of TriBA-Net. The set of words 1, 3, and 2, used in the coding scheme, has the same meaning as the well-known group S3 on 3-letters. Second, a communication model,which contains 6 types of flow modes, has been proposed for reflecting the status of the path within two hops.Finally, the algorithm is simplified by the cyclic permutation characteristic of the S3 group. What＇s more, the implementation of the SPR4T router is completed under the XC6VLX550TL chip. Experimental results show that under the uniform traffic pattern in the 27-node TriBA-Net performance test, SPR4T routing algorithm has a 7.5% higher saturation injection rate and a 7.7% higher throughput rate, with the obvious savings of hardware overhead and lower power consumption when compared to the SPORT routing algorithm.

关 键 词：片上网络 路由算法 编码方法 拓扑结构 性能评估 

分 类 号：TN47[电子电信—微电子学与固体电子学]