互连网络容错理论

Interconnection network has brought great changes for humanity. Its further development needs the support of the basic research. Mass data processing and complex problem solving have higher and higher demands for performance of parallel computer systems. The interconnection network determines the performance of a parallel computer system. In the design of an interconnection network, one of the most fundamental considerations is the fault tolerance of the network. In order to measure the fault tolerance of hierarchical interconnection networks, firstly, we plan to research the subnet preclusion problem, and solve the preclusion number and edge preclusion number of subnets of some hierarchical interconnection networks. We also design effective algorithms to find the preclusion sets and the edge preclusion sets of some hierarchical interconnection networks. Secondly, we plan to solve the conditional matching preclusion number (or set) and strong preclusion number (or set) of some famous interconnection networks. Thirdly, we will determine the fault tolerance of panconnectivity and pancyclicity for some popular networks with good structural properties under these fault models and conditional fault models. Finally, we will study the relationship between the high-dimensional restricted edge connectivity of graphs and other graph parameters and present some sufficient conditions and necessary conditions for a graph to be optimal in terms of the k-restricted edge connectivity. The expected results of this project will provide theoretical basis for engineers when designing or selecting underlying interconnection networks for parallel computer systems.

互连网络已经为人类带来了大的变化。她的进一步发展，更需要基础研究的支撑。海量数据的处理和复杂问题的解决对并行计算机系统性能的要求愈来愈高；互连网络对并行计算机系统的性能起着决定性的作用。容错性是设计互连网络时的一个基本考虑。本项目拟研究分层网络的子网络的排除问题，探索求解若干分层网络的子网络排除数和边排除数及其算法；拟求解若干著名网络的条件匹配排除数及其最优条件匹配排除集和强匹配排除数及其最优强匹配排除集；拟研究一些著名网络的容错泛连通性，容错泛圈性和条件容错泛连通性；拟研究网络的高阶限制边连通度与网络的其它性质之间的关系，给出网络在k限制边连通度下最优的一些充分条件和必要条件。为并行计算机系统的互连网络的设计和选择提供理论依据。

互连网络已经为人类带来了大的变化。她的进一步发展，更需要基础研究的支撑。海量数据的处理和复杂问题的解决对并行计算机系统性能的要求愈来愈高；互连网络对并行计算机系统的性能起着决定性的作用。容错性是设计互连网络时的一个基本考虑。本项目研究了若干著名网络的条件匹配排除数及其最优条件匹配排除集和强匹配排除数及其最优强匹配排除集。如给出了二部环面网络的强匹配排除数和整个的最优强匹配排除集，同时给出了2维非二部环面网络的强匹配排除数和整个的最优强匹配排除集。本项目研究了若干分层网络的子网络的排除问题。如给出了排列图的一些子网络排除数和边排除数及其排列图的子网络排除数和边排除数的上下界。k元n立方网络是并行与分布式系统常用的互连网络拓扑之一。本项目研究了k元n立方网络的容错泛连通性，容错泛圈性和条件容错泛连通性和给出了相应的结果。本项目研究了网络的高阶限制边连通度与网络的其它性质之间的关系。给出了一个图是极大k限制边连通的充分条件；给出了度条件对于图是极大k限制边连通和超级k限制边连通；给出了度条件对于图是极大k等周边连通的充分条件和给出了一个图是超k限制边连通的充分条件。给出了一些著名网络的诊断度。为并行计算机系统的互连网络的设计和选择提供理论依据。