论文部分内容阅读
随着信息化社会的飞速发展,高性能计算已经成为继理论科学和实验科学之后科学研究的第三大支柱。从战略高度方面讲,高性能计算技术是一个国家综合国力的表现,在国防安全、高科技发展和国民经济建设等各个领域都占有不可或缺的重要地位。在高性能计算的研究中,提升运行效率一直是其发展的首要目标。并行计算(Parallel Computing)是提高计算机系统计算速度和处理能力的一种有效手段。并行计算系统中的处理单元之间的连接方式可视为一个网络,我们称之为互连网络。互连网络一般可以抽象为一个简单图G=(V(G),E(G)),其中G中顶点集合V(G)表示互连网络中的处理器集合,G中边集合E(G)表示处理器之间的链路集合。随着系统计算需求的不断增加,网络中处理器数目逐渐增多,继而导致处理器发生故障的概率增加。当网络中处理器发生故障时,网络能否继续保持正常运作取决于该网络的容错性,它是衡量互连网络优劣的一项关键指标。其中,连通度是衡量网络容错性的一个重要参数。然而在实际情况中,条件连通度中的限制连通度和额外连通度相较于传统的连通度能够更准确地衡量一个网络的容错性。同时,在某些处理器发生故障并删除后仍然保持连通的网络中如何进行处理器之间的路由是网络的容错性需要研究的重要课题。广义超立方体是多处理器系统中一种常用的互连网络,具有正则性、对称性、良好的嵌入性和可扩展性等许多优良特性。目前,广义超立方体已经被应用于多种大型多处理器并行系统、数据中心网络和光纤通讯网络的构建中。本文研究了广义超立方体的限制连通度和额外连通度,并给出了相应条件下的容错路由算法。主要研究内容如下:(1)基于限制连通度的定义,本文给出了r-维广义超立方体G(mr,mr-1,...,m1)的1-限制连通度,并给出了其详细证明。同时,本文给出了G(mr,mr-1,...,m1)中的故障顶点个数小于1-限制连通度,且满足1-限制连通度条件的容错路由算法,该算法的时间复杂度为O(κ(G(mr,mr-1,...,m1))3),其中κ(G(mr,mr-1,...,m1))表示G(mr,mr-1,...,m1)的连通度。(2)基于额外连通度的定义,本文给出了r-维广义超立方体G(mr,mr-1,...,m1)的1-额外连通度和2-额外连通度,并给出了其详细证明。同时,本文给出了G(mr,mr-1,...,m1)中的故障顶点个数小于2-额外连通度,且满足2-额外连通度条件的容错路由算法,该算法的时间复杂度为O(κ(G(mr,mr-1,...,m1))3)。