基于TORUS网络的高效路由算法研究

摘要

最小的传输延时和最大的吞吐率是设计一个好的路由算法最重要的性能指标。理想情况下，我们希望一个好的路由算法同时满足:(1)最小的路由跳数以减小传输延时，保持通讯的局域性;(2)最大的平均情况和最坏情况吞吐率;(3)简单的路由器结构。随机Oblivious路由算法路由时不需要考虑网络状态，通过随机地选择在源节点到目的节点之间存在的多条路径进行路由，具有较高的路由灵活性，在低功耗并行计算机互连网络以及片上网络中得到广泛应用。
　　目前已提出的Oblivious路由算法普遍使用了多条虚拟通道，使用增加虚拟通道的数目可以避免死锁的产生，但是虚拟通道的数目并不是越多越好，增加虚拟通道的数目会影响网络的性能以及增大成本与功耗。所以研究如何在确保性能不会下降，甚至在某些通讯模式下有所提升的前提下，进一步提出低虚拟通道数量、低传输延时的新的Oblivious路由算法具有重要意义。
　　本文运用RLB算法与O1TURN算法的核心思想，提出了一个2D-Torus网络上随机Oblivious路由算法——WRD路由算法，该算法与使用两条虚拟通道的O1TURN路由算法相比，WRD路由算法在所有通讯模式下的网络吞吐率均有所提升。与使用四条虚拟通道的RLB算法相比，新提出的WRD路由算法性能接近于RLB算法，甚至在多个通讯模式下的网络吞吐率要好于RLB算法，而且WRD路由算法仅使用两条虚拟通道，降低了网络系统成本和功耗。
　　WRD路由算法虽然只使用两条虚拟通道，这是它的优势，但对网络吞吐率的提高并不是很大。而好的吞吐率是我们设计一个好的路由算法追求的目标。通过对RLB算法存在的缺点进行分析与改进，进一步提出了一个2D-Torus网络上高性能随机Oblivious路由算法——M2TURNS路由算法。该算法与O1TURN路由算法相比，M2TURNS路由算法在绝大多数通讯模式下的吞吐率都远高于O1TURN。特别是在平均情况下，M2TURNS路由算法的表现非常好，并且随着网络规模的增大，吞吐率优势越来越大。与使用四条虚拟通道的RLB算法相比，M2TURNS路由算法在大多数通讯模式下的网络吞吐率均有提高，并且在某些通讯模式中有明显提升。而且M2TURNS路由算法减少了虚拟通道的使用数目，其仅需要三条虚拟通道。最后M2TURNS路由算法拥有更短的路由跳数，其传输消息的路由跳数不超过RLB路由算法的75％，拥有更小的消息传输延时。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 研究现状

1．3 存在的问题和发展趋势

1．4 研究内容和目标

1．5 论文组织结构

第二章 Torus网络路由算法的基础研究

2．1 硬件模型

2．2 路由器

2．3 交换方式

2．4 虚拟通道

2．5 死锁、活锁及饿死

2．6 转弯模型

2．7 通讯模式

2．8 路由算法

2．8．1 路由算法分类

2．8．2 确定性路由算法

2．8．3 随机路由算法

2．8．4 自适应路由算法

2．9 网络性能指标

第三章 一种新的Torus网络Oblivious路由算法WRD

3．1 提出WRD算法的过程

3．2 WRD算法的设计思想

3．3 算法描述

3．4 实验仿真

3．5 算法总结

第四章 一种新的Torus网络高效Oblivious路由算法M2TURNS

4．1 提出M2TURNS算法的过程

4．2 M2TURNS算法的设计思想

4．3 算法描述

4．4 实验仿真

4．5 算法总结

第五章 总结与展望

5．1 论文工作总结

5．2 下一步工作展望

参考文献

致谢