基于并行系统互连网络的条件连通性及故障诊断问题的研究

The properties of interconnection network of parallel computer system deter- mine its whole performance. This project plans to use some indices in graph theo- ry, including k-restricted edge connectivity, k-restricted connectivity, R^k- connectivity and k-good neighbor conditional diagnosability, to study the con- nectivity and fault diagnosis of interconnection network. On the one hand, for the important interconnection network models, including hypercube, its variations and its generalized networks, we shall investigate the structure pro- perties related to these parameters and the relationships between these parame- ters, design the algorithms to find the k-restricted edge cut, k-restricted cut, R^k-cut and k-good neighbor conditional fault set, and compute the k-restricted edge connectivity, k-restricted connectivity, R^k-connectivity and k-good neighbor conditional diag- nosability. On the other hand, we shall further research the k-restricted edge connectivity, k-restricted connectivity, R^k-connectivity and k-good neighbor conditional diagnosability of general graphs, and present the sufficient conditions and necessary conditions for these parameters in general graphs to be optimal by exploring the relationships between these parameters and other graph parameters, properties of special subgraphs. The expected results of this project will provide theoretical basis for engineers to design and select the intercon- nection network of parallel computer system.

互连网络的性质决定着并行计算机系统的整体性能。本项目拟利用图论指标——k-限制边连通度、k-限制连通度、R^k-连通度和k-好邻条件诊断度，研究互连网络的连通性和故障诊断。一方面，研究重要的互连网络模型——超立方体及其变形和推广网络中与这些参数相关的结构性质以及这些参数之间的关系，设计求解k-限制边割、k-限制割、R^k-割和k-好邻条件故障集的算法，并计算这些网络的k-限制边连通度、k-限制连通度、R^k-连通度和k-好邻条件诊断度。另一方面，从更广的角度研究一般图的k-限制边连通度、k-限制连通度、R^k-连通度和k-好邻条件诊断度，探索一般图中这些参数与图的其它参数以及特殊子图的性质之间的关系，给出一般图中这些参数达到最优时的充分条件和必要条件。预期的研究成果可以为并行计算机系统互连网络的设计和选择提供理论依据。

本项目主要研究并行系统互连网络的拓扑性质，属于数学和计算机科学学科的基础应用研究，旨在对并行系统互连网络的设计和分析起到一定的指导意义。本项目重点对互连网络的可靠性进行研究，讨论了网络的连通性、故障诊断和路、圈嵌入三个方面的问题.. 在网络的连通性研究方面，我们完成了k元n方体和分层星图网络在最小度限制下的连通性的刻画，证明了其Rg-连通度的计算公式；完成了3元n方体网络的最小分支阶数限制下的连通性——g超连通性的刻画，证明了其g-超连通度的计算公式；讨论了无三角图网络的最小分支阶数限制下边连通性——g-限制边连通性，证明了无三角图的g-限制边连通度超级最优时的充分条件。. 在网络的故障诊断研究方面，我们讨论了k元n方体、分层星图和排列图网络中g-好邻条件诊断度与Rg-连通度的关系，证明了PMC和MM*模型下k元n方体、分层星图和排列图的g-好邻条件诊断度的计算公式；讨论了超立方体和折叠超立方体中g-超条件诊断度和g-限制连通度之间的关系，证明了MM*模型下超立方体和折叠超立方体的g-超条件诊断度的计算公式；讨论了对称网络中g-超条件诊断度和g-限制连通度之间的关系，并由此提出BC网络和3元n方体网络在PMC和MM*模型下的g-超条件诊断度的计算公式。. 在网络的路、圈嵌入问题的研究方面，研究了环网中连接网络中连接k对相异的起点和终点的k条不相交的容错路覆盖，它覆盖了环网中所有顶点，证明了非二部环网是2n-3边故障二不交路覆盖的。