星形图上无死锁受限条件及路由算法

论文摘要

由于具有正则性、对称性、可嵌入性、并行性和可扩展性等优良特性,星形图(Star Graph)和超立方体(Hypercube)互联网络受到了研究者们的广泛关注,成为并行计算机互联网络中的重要拓扑结构。随着现在的并行计算机互联网络规模越来越大,网络中出现处理机故障或处理机间的链路故障的可能性也越来越大;这就使得并行计算机互联网络的容错性及其研究也变得越来越重要,因此,设计具有较好容错性的路由算法对并行计算机互联网络有着重要意义。 到目前为止,人们已经对星形图和超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面分别进行了深入的研究,并基于星形图和超立方体互联网络的拓扑特性分别建立了一些容错模型及其容错路由算法,但是仍有许多问题有待研究。本文研究星形图互联网络的受限条件的无死锁路径算法和超立方体互联网络的安全通路容错算法。 在对星形图互联网络的拓扑特性及其容错模型与容错路由算法方面,针对星形图中可能产生死锁的问题,本文对星形图上无死锁的路径算法进行了研究,得到了星形图上的二类最小无死锁受限条件,并给出了一个满足该二类最小无死锁受限条件的无死锁路径算法。此外,本文还提出了星形图上两类基于单缓冲和双缓冲技术的无死锁受限条件,并给出了相应的无死锁路径算法。 在对超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面,本文首先综述了目前国内、国际上在超立方体互联网络研究方面所做的主要研究工作,并基于已有的一些研究成果,提出了一种新的超立方体互联网络的容错模型及其容错路由算法:即基于安全通路向量的容错模型SPV(Safety Path Vectors)及其容错路由算法。与基于最优通路矩阵的容错模型OPM(Optimal Path Matrix)以及基于扩展最优通路矩阵的容错模型EOPM(Extended Optimal Path Matrix)及其容错路由算法相比较,SPV的存储开销指数级低于OPM和EOPM的存储开销,而且SPV能记录到OPM和EOPM无法记录到的最优通路信息。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 星形图与超立方体互联网络简介
• 1.1.1 星形图互联网络简介
• 1.1.2 超立方体互联网络简介
• 1.1.3 星形图与超立方体互联网络的比较
• 1.2 课题研究的意义
• 1.3 国内外研究现状分析
• 1.3.1 星形图互联网络拓扑特性与路由算法的研究
• 1.3.2 超立方体互联网络拓扑特性与路由算法的研究
• 1.4 本文的主要研究内容
• 1.5 本文结构
• 第2章 星形图上最小无死锁受限条件及无死锁路由算法
• 2.1 概述
• 2.2 预备知识
• 2.3 最小无死锁受限条件及无死锁路由算法
• 2.3.1 最小无死锁受限条件
• 2.3.2 满足最小无死锁受限条件的路由算法
• 2.4 试验结果及分析
• 2.5 小结
• 第3章 星形图上基于单缓冲机制的无死锁路由算法
• 3.1 概述
• 3.2 预备知识
• 3.3 基于单缓冲机制的无死锁路由算法
• 3.4 试验结果及分析
• 3.5 小结
• 第4章 星形图上基于双缓冲机制的无死锁路由算法
• 4.1 概述
• 4.2 基于双缓冲机制的无死锁路由算法
• 4.3 试验结果及分析
• 4.4 小结
• 第5章 超立方体互联网络中基于安全通路向量的容错模型及其容错路由算法
• 5.1 概述
• 5.2 基于安全通路向量的容错模型及性质分析
• 5.2.1 预备知识
• 5.2.2 SPV容错模型的构造
• 5.2.3 SPV容错模型的性质
• 5.2.4 安全通路向量的赋值算法
• 5.3 基于安全通路向量的容错路由算法与性能分析
• 5.3.1 基于安全通路向量的容错路由算法
• 5.3.2 性能分析与比较
• 5.4 小结
• 结论
• 参考文献
• 致谢
• 附录A（攻读学位期间所发表的学术论文目录）