对基于不规则拓扑的并行系统通信中路由算法的研究

论文摘要

并行分布式系统是计算机行业和日常生活中不断增长的应用领域,特别是在分布式计算、工业控制、军事航天领域、以及商务应用等。对实现有如此关键性应用的分布式系统来说,努力提高其可用性、可靠性、适用性,具有十分重要的现实意义。工作站集群(NOWs)被认为是一种低价并行计算机的替代品,越来越广泛应用于各种分布式计算和协同作业之中。而在一个实时系统中,必须满足有限响应时间的要求,否则将导致严重的后果。因此有效的进程间通信机制是分布式系统中的一个不可或缺的组成部分,对分布式系统的性能是至关重要的。以往的分布式并行计算机系统大多采用规则的拓扑网络,这种处理器之间的连接方式下的路由就变得固定而且相对容易,却带来了容错性差等缺点,只要有一个节点出现差错,就导致整个网络的不可用。基于开关交换的不规则拓扑网络互连就提供了布线的灵活性、可测量性和递增可扩充性,而这些特性正是分布式系统所需要的环境。然而,正是由于网络的不规则也使系统中路由和死锁的避免变得十分的复杂。设计网络路由的目的也变得十分的明确,就是在防止死锁和增加自适应性的基础之上,提高其运行效率。已经商业化的产品里,分布式UP*/DOWN*路由算法被用于实践之中。因为其比较呆板和非最短路径性,人们又对它提出了种种改进措施。除此之外,为进一步提高性能,虫孔交换和虚通道等相关技术也被用于并行机的通信之中。本文在介绍了当前人们已经提出的几种消息传递方式的基础之上,使用虫孔交换,结合已有算法的优点,提出自己的三段式路由方案,用三个不同的路由算法,采取虚通道技术,分别实现了高效、自适应、无死锁的功能。以期达到降低网络延迟和提高网络性能的效果。文章最后对提出的改进后的路由方案进行了模拟实验,给出实验结果,并和现有的路由方式下的性能数据加以对比,以此说明了三段式算法的有效性。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 分布式集群的发展现状及前景
• 1.2 通信在多机中的巨大作用
• 1.3 国内外的研究现状
• 1.4 文章结构
• 1.5 本章小结
• 2 并行机的互连网络体系结构
• 2.1 并行机的互连网络体系结构
• 2.2 并行机的网络互连方式
• 2.3 互连网络的交换方式
• 2.3.1 电路交换
• 2.3.2 报文交换
• 2.3.3 虚跨步交换
• 2.3.4 虫孔交换
• 2.4 互连网络的拓扑结构
• 2.5 互连网络的路由方式
• 2.6 本章小结
• 3 并行互连网络路由的算法设计
• 3.1 商业化应用于NOWS 的UP*/DOWN*路由
• 3.2 设计路由方案的主要目标
• 3.2.1 无死锁、活锁
• 3.2.2 自适应
• 3.2.3 高效
• 3.3 进行NOWS 通信部分设计时应注意的问题
• 3.3.1 通道流水钱
• 3.3.2 分配缓冲大小
• 3.3.3 流量控制
• 3.4 本章小结
• 4 虫孔交换与虚通道的结合
• 4.1 虫孔交换
• 4.2 虚通道
• 4.3 采用虚通道的相关问题
• 4.4 本章小结
• 5 路由算法内容
• 5.1 使用虚通道
• 5.1.1 合理使用虚通道
• 5.1.2 增加更多的虚通道
• 5.2 最短路径算法（第一高效算法）
• 5.3 自适应-迹算法（第二自适应算法）
• 5.4 对UP*/DOWN*算法改进（第三无死锁算法）
• 5.5 路由方案的具体算法
• 5.6 本章小结
• 6 性能评估
• 6.1 评测中要考虑的因素
• 6.2 性能评估中出现的问题及参数的设定
• 6.3 模拟结果数据及分析
• 6.4 本章小结
• 7 结语及对未来的展望
• 致谢
• 参考文献
• 附录
• 独创性声明
• 学位论文版权使用授权书