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

An Efficient Random Oblivious Routing Algorithm Based on the Torus Network

作　　者：任一曼 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387

出　　处：《软件工程》2017年第1期12-14,8,共4页Software Engineering

摘　　要：一个好的路由算法应同时满足:最小的路由跳数以减小传输延时,保持通讯的局域性;最大的平均情况和最坏情况吞吐率;简单的路由器结构。随机Oblivious路由算法在低功耗并行计算机互联网络以及片上网络中得到广泛应用。针对Torus网络下已提出的Oblivious路由算法所需虚通道数目多的缺点,提出了随机Oblivious路由算法WRD,该算法仅使用两条虚拟通道即可实现算法的无死锁性。通过仿真对所提算法的性能进行了验证,结果表明,该算法与使用两条虚拟通道的O1TURN路由算法相比,WRD路由算法在所有通讯模式下的网络吞吐率均有所提升。与使用四条虚拟通道的RLB算法相比,新提出的WRD路由算法性能接近于RLB算法,甚至在多个通讯模式下的网络吞吐率要好于RLB算法,而且WRD路由算法仅使用两条虚拟通道,降低了网络系统成本和功耗。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 the algorithm.The performance of the proposed algorithm is verified through simulation.The results show that the algorithm has improved the network throughput of WRD routing algorithm in all communication modes compared with the O1 TURN routing algorithm using two virtual channels.Compared with the RLB algorithm using four virtual channels,the newly proposed WRD routing algorithm is close to the RLB algorithm,and even in multiple communication moes, the network throughput is better than that of the RLB algorithm,and the WRD routing algorithm uses only two virtual channels, reducing network system costs and power consumption.

关 键 词：TORUS网络 随机Oblivious路由算法 平均情况网络吞吐率 最坏情况网络吞吐率 虚拟通道 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]