| 摘 要: 一个好的路由算法应同时满足：最小的路由跳数以减小传输延时，保持通讯的局域性；最大的平均情况和 最坏情况吞吐率；简单的路由器结构。随机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 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 O1TURN 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. |
| Keywords: the Torus network;the random oblivious routing algorithm;average network throughput;worst case network throughput;virtual channels |
