| 标题 | 结构故障下k—元n—立方体网络的容错哈密顿圈嵌入模拟实验 |
| 范文 | 吕雅丽 摘要：该文给出了在存在结构故障的情况下，k-元n-立方体网络容错哈密顿圈嵌入的构造算法及实验结果。在这些实验中，得到了相应的数据，为互连网络多播算法的应用提供了依据。 关键词：结构故障；k-元n-立方体网络；哈密顿圈 中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）27-0217-02 1 概述 随着高性能计算机在国防太空、生物制药、天气预报等领域应用的不断深入，迫切需要速度更快的高性能计算机系统，进而开辟了并行分布式系统的研究领域。在并行分布式系统中，多处理器之间连接的拓扑结构（称为互连网络）至关重要。互连网络的选择直接影响到并行分布式系统的性能和功能的实现。迄今，已有许多著名的互连网络被相继提出。例如：超立方体、类超立方体（BC网络）、星图、k-元n-立方体、蝶形图等。k-元n-立方体网络是一类重要的网络。它具有许多优良的性质，例如直径小、正则性、迭代性等。它包含一些重要的网络拓扑作为它的子类，如环网络，mesh，torus和超立方体网络。目前许多并行分布式系统都是用k-元n-立方体网络作为其连接模式，例如IBM BlueGene/L超级计算机、Cray T3D、Cray T3E以及J-machine等。 互连网络可以表示为一个图，图的顶点表示系统中的处理器，边表示处理器之间的通信链路。在实际的应用系统中，设备或通信链路发生故障是在所难免的。当网络出现故障时，如何使得网络能够正常地工作，原网络的性能如何得到最大程度的保持，即容错性，是互连网络研究必须考虑的问题。评估互连网络容错性的一个重要参数是连通度。图G的连通度，记为[κ]（G），是使得图G不连通或成为平凡图所需删除的最小顶点数。连通度常常用于评价一个系统的容错性。这一评价存在明显的缺点。它假设一个顶点的所有邻接点可能同时出现故障。Esfahanian指出在实际多处理器系统中，一个无故障顶点的所有邻接点同时出现故障的情况是几乎不存在的[1]。为了讨论更一般性的故障情形，Harary提出条件连通度的概念，对删除故障顶点后的图加上了一定的限制条件[2]。随后，多种条件连通度被相继提出并得以广泛研究，比如g-超连通度与Rg-连通度。至今，关于容错性的研究主要关注于单个顶点或者单个边出现故障，没有考虑一个顶点的状态（故障与否）与它的邻接点的状态的关联。实际应用中，故障点和边的分布可能比较集中或局部化。同样，随着片上网络的提出和发展，一个或一些顶点出现故障，就认为其所在“片”不可用。这些都启发我们在研究容错性时，不能仅考虑顶点故障，还应考虑图的某些子图或子结构故障，这类故障称为结构故障。 Lin等提出了结构故障的概念，定义了两种新的连通度，结构连通度和子结构连通度，并对超立方体网络的这两种连通度进行了研究[3]。本文作者对k-元n-立方体网络的结构连通度进行了研究[4]，同时对其结构故障情况下的哈密顿性质进行了研究[5]。这里我们给出结构故障下k-元n-立方体网络的容错哈密顿圈嵌入的模拟实验。 2 相关定义 一条路是哈密顿路当且仅当它通过G中的每一个顶点一次且仅一次。经过图G中所有顶点一次且仅一次的圈称为哈密顿圈。一个图如果包含有哈密顿圈，则称该图是哈密顿的。一个图中如果任意两个顶点之间都存在哈密顿路，则称该图G是哈密顿连通的。互连网络的哈密顿性质在网络通信中具有重要的应用，哈密顿路可以用于双路径或多路径的路由算法，以減少或避免死锁或拥塞的出现。考察网络可靠性和容错性的一个重要方面就是其容错哈密顿性质，即故障网络中是否存在无故障的哈密顿圈和哈密顿路，以及如何构造。当k是偶数时，k-元n-立方体网络是二分图，任何二分图都不是哈密顿连通的，所以本文我们讨论k是奇数情形下k-元n-立方体网络的容错哈密顿圈嵌入问题。 3 容错哈密顿圈的构造算法 在一个存在结构故障的图[Qkn]中，我们首先选择一个无故障顶点s作为起始顶点，用顶点集合C记录圈中的顶点。将顶点s加入C，然后查找任何一个与s相邻但未加入圈C的顶点s1； 然后将顶点s1加入C，然后查找任何一个与s1相邻但未加入圈C的顶点s2，…，直到到达一个顶点t，其所有的无故障邻接点都已加入C为止。此时如果C中包含所有无故障顶点并且顶点t是顶点s的邻接点，则构造成功，C为哈密顿圈。否则选择顶点s的其它无故障邻接点，执行上述过程，直到构造成功或者顶点s的所有无故障邻接点均查找完毕，返回失败。算法hamiltonCycle给出了我们的构造方法的伪代码。 5 总结 本文我们结合前期研究的理论基础，给出了在存在结构故障的情况下，k-元n-立方体网络容错哈密顿圈嵌入的构造算法，并编程实现了算法并给出了实验结果。在这些实验中，我们得到了相应的数据，为互连网络多播算法的应用提供了依据。 参考文献： [1] Abdol-Hossein Esfahanian. Generalized measures of fault tolerance with application to n-cube networks[J]. IEEE Transactions on Computers， 1989， 38（11）：1586-1591. [2] Frank Harary. Conditional connecticity[J]. Networks， 1983， 13（3）：347-357. [3] Cheng-Kuan Lin， Lili Zhang， Dajin Wang and Jianxi Fan. Structure connectivity and substructure connectivity of hypercubes[J]. Theoretical Computer Science， 2016， 634： 97-107. [4] Yali Lv， Jianxi Fan， D. Frank Hsu， Cheng-Kuan Lin. Structure Connectivity and Substructure Connectivity of k-Ary n-Cube Networks[J]. Information Sciences， 2018， 433：115-124. [5] Yali Lv， Cheng-Kuan Lin， Jianxi Fan. Hamiltonian Cycle and Path Embeddings in k-Ary n-Cubes Based on Structure Faults[J]. The Computer Journal， 2017， 60（2）：159-179. [通联编辑：代影] |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。