一种基于Torus网络的高效随机Oblivious路由算法.PDF

第20卷第1期 Vol.20 No.1 2017年1月 软件工程 SOFTWARE ENGINEERING Jan. 2017 文章编号：2096-1472(2017)-01-12-03 一种基于Torus网络的高效随机Oblivious路由算法 任一曼 （天津工业大学计算机科学与软件学院，天津 300387） 摘 要：一个好的路由算法应同时满足：最小的路由跳数以减小传输延时，保持通讯的局域性；最大的平均情况和 最坏情况吞吐率；简单的路由器结构。随机Oblivious路由算法在低功耗并行计算机互联网络以及片上网络中得到广泛 应用。针对Torus网络下已提出的Oblivious路由算法所需虚通道数目多的缺点，提出了随机Oblivious路由算法WRD， 该算法仅使用两条虚拟通道即可实现算法的无死锁性。通过仿真对所提算法的性能进行了验证，结果表明，该算法与 使用两条虚拟通道的O1TURN路由算法相比，WRD路由算法在所有通讯模式下的网络吞吐率均有所提升。与使用四条 虚拟通道的RLB算法相比，新提出的WRD路由算法性能接近于RLB算法，甚至在多个通讯模式下的网络吞吐率要好于 RLB算法，而且WRD路由算法仅使用两条虚拟通道，降低了网络系统成本和功耗。 关键词：Torus网络；随机Oblivious路由算法；平均情况网络吞吐率；最坏情况网络吞吐率；虚拟通道 中图分类号：TP393 文献标识码：A An Efficient Random Oblivious Routing Algorithm Based on the Torus Network REN Yiman ( School of Computer Science and Software ,Tianjin University of Technology ,Tianjin 300387,China) Abstract:A good routing algorithm should satisfy:the minimum number of routing hops to reduce the propagation delay and maintain the localization of the communication.The maximum average case and the worst case throughput.The simple router structure.The random Oblivious routing algorithm is widely used in low-power parallel computer interconnection networks and on-chip networks with its high routing flexibility.Aiming at the shortcomings of the number of virtual channels required by the Oblivious routing algorithm proposed in the Torus network,the paper proposes a random Oblivious routing algorithm WRD.The algorithm uses only two virtual channels to achieve the deadlock-freeness of