不规则拓扑NOWs中路由算法的研究

摘要

近年来,工作站机群系统(NOWs)蓬勃发展,占据了并行计算领域的主导地位.发展NOWs的关键,是提高互连网络的性能.路由算法决定了消息在网络中如何选取路径,其效率对网络的性能起着关键的作用.Autonet,Myrinet等用于NOWs的交换式高速网络使布线灵活、系统可扩展能力加强,但其拓扑的不规则性使路由避免死锁的问题变得复杂.该文主要研究了不规则拓扑结构NOWs中的路由算法.深入剖析了最经典的up*/down*路由算法,指出其中的链路方向指派存在任意性、通道利用极不平衡等缺点,并给出两种相应的改进措施.经模拟验证,改进后的算法较up*/down*路由算法性能有了显著提高.

目录

文摘

英文文摘

第一章绪论

1.1课题背景

1.2论文主要内容

1.3本人的主要工作

第二章机群系统

2.1机群的基本概念

2.2机群系统的优点

2.3发展NOWs的关键

2.4小结

第三章互连网络

3.1网络拓扑结构和性质

3.2交换技术

3.2.1消息格式

3.2.2交换技术的种类

3.2.3虫孔路由(Wormhole routing)

3.3流控机制

3.3.1通道的空闲问题

3.3.2虚通道的流控制

3.4网络的性能指标

3.5小结

第四章路由算法

4.1路由算法的概念与分类

4.1.1路由算法的概念

4.1.2路由算法的分类

4.2路由算法需解决的问题

4.2.1连通、死锁与活锁

4.2.2解决死锁的方法

4.3直接网络的路由算法

4.3.1确定性路由算法

4.3.2部分自适应路由算法

4.4小结

第五章不规则拓扑NOWS中的路由算法

5.1图论的预备知识

5.2网络模型

5.3基于树的路由算法

5.3.1生成树路由算法

5.3.2 Up*/down*路由算法

5.3.3 UD-DFS路由算法

5.3.4 z-算法(z-algorithm)

5.4小结

第六章对UP*/DOWN*路由算法的改进

6.1 GREEDY-UD路由方法

6.1.1 Up*/down*路由链路方向指派的任意性

6.1.2基于贪婪算法思想的链路方向指派方法

6.1.3链路方向指派的具体算法与网络实例比较

6.2 FIRST-UP与LAST-DOWN路由方法

6.2.1 Up*/down*路由策略中通道利用的不均衡

6.2.2扩展方向的链路指派方法

6.2.3确定基于链路方向的限制路由规则

6.2.4适用于各种不同的不规则拓扑网络的灵活性

6.3路由表的构建

6.4性能评价

6.4.1网络仿真的概念

6.4.2网络模型

6.4.3模拟结果

6.5小结

结束语

附录：论文发表情况

致谢

参考文献