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

任一曼

摘 要：一个好的路由算法应同时满足：最小的路由跳数以减小传输延时，保持通讯的局域性；最大的平均情况和最坏情况吞吐率；简单的路由器结构。随机Oblivious路由算法在低功耗并行计算机互联网络以及片上网络中得到广泛应用。针对Torus网络下已提出的Oblivious路由算法所需虚通道数目多的缺点，提出了随机Oblivious路由算法WRD，该算法仅使用两条虚拟通道即可实现算法的无死锁性。通过仿真对所提算法的性能进行了验证，结果表明，该算法与使用两条虚拟通道的O1TURN路由算法相比，WRD路由算法在所有通讯模式下的网络吞吐率均有所提升。与使用四条虚拟通道的RLB算法相比，新提出的WRD路由算法性能接近于RLB算法，甚至在多个通讯模式下的网络吞吐率要好于RLB算法，而且WRD路由算法仅使用两条虚拟通道，降低了网络系统成本和功耗。

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

中图分类号：TP393 文献标识码：A