并行系统规则互连网络的容错性研究

The functions of parallel computer systems rely heavily on the interconnection networks of these systems. Fault tolerance of the interconnection networks can characterize the ability to remain some properties in the presence of failures, and is a crucial factor to evaluate the performance of the interconnection networks. Using graph theory as a tool, the project intends to study the regular interconnection networks’ ability to remain the following properties: the existence of perfect (or almost perfect) matchings and the existence of sub-networks. The main research contents include four aspects. (1) For several classes of attractive regular interconnection networks, we will study the measures of fault tolerance regarding the existence of perfect (or almost perfect) matchings under random fault model and conditional fault model, respectively, and design the corresponding algorithms to find perfect (or almost perfect) matchings. (2) We will seek sufficient conditions for regular interconnection networks to have high ability to remain the property of having perfect (or almost perfect) matchings in the presence of failures. (3) For several classes of recursive regular interconnection networks, we will study the measures of fault tolerance regarding the existence of sub-networks and design the corresponding algorithms to search for sub-networks. (4) The probability-based prediction of sub-networks for some specific regular interconnection networks will be made and the relevant numerical simulation analysis will be done. The research results of this project will not only have very important significance for analyzing fault tolerance of regular interconnection networks, but also be useful for designing and optimizing interconnection networks of large scale parallel systems.

并行计算机系统功能的实现很大程度上依赖于系统互连网络的性能。互连网络的容错性是衡量网络性能的关键指标，它用于表征有故障发生时网络中某些特有性质的保持能力。本项目拟以图论为工具重点研究规则互连网络在出现故障的情况下对可匹配性以及子网络存在性的保持能力，主要内容包括：(1) 对于几类著名规则互连网络，分别在随机故障和条件故障下研究度量可匹配性的容错参数，并设计相应的匹配查找算法；(2) 探究能确保规则互连网络对可匹配性有较强容错能力的充分条件；(3) 对于几类具有迭代结构的著名规则互连网络，研究衡量子网络保持程度的容错参数，设计相应的子网络搜索算法；(4) 对一些特定的规则互连网络中低维子网络的存在性进行概率预测研究，并进行数值模拟分析。本项目的研究成果有助于科学地分析规则互连网络的容错性，可以为大规模并行系统互连网络的设计与优化提供有益参考。

并行计算机系统将多个处理器按照某种互连网络连接起来，使得这些处理器通过信息传输互相配合，从而提高运算能力。系统互连网络的性能对系统功能的实现起着至关重要的作用。互连网络的容错性是度量网络性能的关键指标之一，它用于表征有故障发生时网络中某些特有性质的保持能力。本项目以图论为数学工具研究了几类著名规则互连网络在出现故障的情况下对可匹配性以及子网络存在性的保持能力，主要内容包括：（1）在随机故障下对n维环面网络的强匹配排除问题进行了研究，这一工作使n维环面网络相应的强匹配排除性质得到了完整刻画，并为在这类网络中设计无故障匹配搜索算法提供了解决策略；（2）在条件故障下对k元n方体网络的强匹配排除问题进行了研究，对这类网络在条件故障下的匹配容错能力进行了量化；（3）在点故障模型下对(n,k)-星图网络的子网络排除问题进行了研究，给出了使得(n,k)-星图网络中不存在(n-m,k-m)-星图子网络所需要破坏的最小点数的上下界；（4）在概率故障模型下得出了k元n方体网络中k元(n-1)方体子网络的可靠性的上下界，给出了该可靠性的一个近似值，并设计了在发生点故障的k元n方体网络中搜寻k元(n-1)方体子网络的算法。本项目的研究成果丰富了规则互连网络容错性分析的研究方法，可以为大规模并行计算机系统互连网络的设计与优化提供理论参考。