吕雅丽

摘要：该文给出了在存在结构故障的情况下，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等。

互连网络可以表示为一个图，图的顶点表示系统中的处理器，边表示处理器之间的通信链路。在实际的应用系统中，设备或通信链路发生故障是在所难免的。当网络出现故障时，如何使得网络能够正常地工作，原网络的性能如何得到最大程度的保持，即容错性，是互连网络研究必须考虑的问题。评估互连网络容错性的一个重要参数是连通度。……