论文部分内容阅读
随着计算机科学和信息化网络技术的发展,高性能计算机在社会各个领域发挥着日益重要的作用。高性能计算机的性能在很大程度上取决于其系统内部处理器之间的连接方式(互连网络)。互连网络的拓扑结构及其性质的研究是并行计算领域的研究重点之一。互连网络一般可以用一个简单图G=(V(G),E(G))来表示,其中V(G)表示图G中的顶点集合,代表互连网络中的处理器,E(G)表示图G中的边集合,代表处理器之间的链路。随着互连网络规模的不断扩大,网络中处理器和链路的数目也逐渐增多,处理器或链路发生故障的概率也会随之增加。在网络发生故障的情况下网络中某些特性能否继续保持,这就是网络的容错性,它是衡量互连网络性能的一项关键指标。超立方体网络是多处理器系统中一种常用的互连网络,它具有很多优越的性质,例如直径较小、结构对称、递归构造、可扩展性强等。基于该网络,研究者们已经提出了许多性能优越的超立方体变型网络,例如交叉立方体、扭立方体、莫比乌斯立方体等。因此,超立方体网络已成为多处理器系统中最基础也最重要的网络模型之一。本文在结合理论分析的基础上,就超立方体网络的容错性提出了新的测量方法,并且在该方法的限制条件下,研究了超立方体网络上的条件连通度,容错单播路由算法以及容错哈密顿性质。主要研究内容如下:1.本文提出一种与距离相关的新的条件(边)连通度――(g,d,k)-条件(边)连通度。与其他条件连通度相比,(g,d,k)-条件(边)连通度的要求更符合实际情况,并且允许存在更多的故障顶点(边)。它为研究超立方体等网络的容错性提供了新的衡量指标。2.本文研究了超立方体网络上某些特定的(g,d,k)-条件(边)连通度,包括κ1,1,k(Qn),κ1,d,2(Qn),λ1,1,1(Qn)和λ1,d,2(Qn)。这些结果为后续研究超立方体网络上其他(g,d,k)-条件(边)连通度提供了参考,也为在超立方体变型网络等其他网络上研究(g,d,k)-条件(边)连通度提供了方法上的指导。3.本文在(1,1,1)-条件连通的情况下提出了一种基于局部信息的容错单播路由算法,该算法通过构建长度不超过3的跨越路径来选择用于路由的维度。本文分析了该算法的时间复杂度以及空间复杂度,并且和现有的几种单播路由算法从成功率,运行时间,路径长度等方面进行了比较。4.本文结合(g,d,k)-条件边连通的概念,提出了一种新的条件容错哈密顿性质:f-(g,d,k)条件边容错哈密顿。本文证明,当n≥4时,n维超立方体是(4n-13)-(3,0,0)条件边容错哈密顿的,并且这一结果是最优的。最后,对本文工作进行了总结,并对后续的研究工作进行了展望。