学位论文 > 优秀研究生学位论文题录展示

二进制立方形递归网络拓扑性质研究

作　者: 孙云
导　师: 李舟军
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 并行计算互连网络超立方体二进制立方形递归网络直径故障直径连通度 Hamilton圈几乎泛圈性
分类号: TP393.02
类　型: 博士论文
年　份: 2007年
下　载: 51次
引　用: 1次
阅　读: 论文下载

内容摘要

互连网络技术在并行计算机、计算机体系结构领域被广泛研究。在众多互连网络拓扑中,超立方体及其变体是一类具有良好拓扑性质和网络参数的互连网络模型,关于它们的研究与应用在互连网络的研究中备受青睐。本文在定义了一类特殊的超立方体变体的基础上,对该类互连网络的网络参数及环网可嵌入问题进行了系统而深入的研究。我们通过对二进制递归网络拓扑结构的对比分析发现,研究者最感兴趣的一类二进制递归网络都有一个共同特征:它们均以3维立方体和扭3立方体作为基本模式进行网络互连。根据这一特征,本文对该类特殊的二进制递归网络进行了代数定义,并称其为“二进制立方形递归网络”。二进制立方形递归网络虽然只是二进制递归网络的一个子集,但却是当前二进制递归网络中的重点研究对象。由于网络的很多参数和性质都是与网络的拓扑结构直接相关的,所以真正了解并正确刻画网络的拓扑结构,对得出与网络拓扑相关的正确结论,以及更好地对网络进行优化起着至关重要的作用。本文借助超网的概念,对二进制立方形递归网络的拓扑结构进行了详细分析,对其拓扑特征给出了精确描述。网络直径是用来衡量网络性能的一个重要参数,直径的大小直接决定着网络的通信时延,任何一种新型网络的产生都离不开对网络直径的讨论。本文给出了n维二进制立方形递归网络直径的上确界和下确界,并根据二进制立方形递归网络的特征描述证明了结论的正确性。这不仅能为试图寻找具有更小网络直径的新型二进制立方形递归网络提供可行性参考,还能指导人们在实际算法中设定消息接收的最大与最小等待时间。路由算法是网络算法中最基本和最重要的算法之一,它的目的是在网络拓扑图上寻求由源点到目的点的路径,它是所有其它网络算法的基础。给出了一个适用于所有二进制立方形递归网络的路由算法,该算法能使几种非常重要的二进制立方形递归网络取得最短路径。网络的连通度是衡量一种互连网络可靠性的重要参数。证明了相同维数的所有二进制递归网络的连通度相同,这说明那些直径小于超立方体直径的变体在降低了超立方体直径的情况下并没有降低网络的可靠性。网络的故障直径是与网络连通度密切相关的一种网络参数,它指出了系统中某些给定数目的处理机发生故障时的最大传输延迟。本文确定了n维二进制立方形递归网络故障直径的上确界和下确界,说明了任何二进制立方形递归网络的最大故障时延不会高于超立方体的最大故障时延。环(圈)可嵌入问题是互连网络研究中的又一个重要议题。网络中可以嵌入Hamilton圈,说明该网络中可以嵌入与它具有相同顶点数量的环网。利用二进制立方形递归网络的拓扑特征,给出了在二进制立方形递归网络中嵌入Hamilton圈的构造算法,打破了使用归纳假设方法证明超立方体及其变体中Hamilton圈存在性的传统,为实际应用提供了保证。依据该Hamilton圈的构造算法,给出了二进制立方形递归网络具有几乎泛圈性的一个充分条件,同时给出了在二进制立方形递归网络中构造任意长圈的构造算法,使得环网中的并行计算算法直接用于超立方体及其变体成为可能。

二进制立方形递归网络拓扑性质研究

内容摘要

全文目录

相似论文