二进制递归网络的多故障容错性分析

The performance of a parallel computing system heavily depends on the effectiveness of the underlying interconnection network that connects the computing nodes. With the size of a parallel computing system increasing, it becomes much likely that some computing nodes fail to work in the interconnection network. Hence, in order that the system continues to function in the presence of failures, it is essential to investigate the fault tolerance of the interconnection network, i.e., the ability to exchange data between healthy computing nodes in a faulty network. As an important generalization of hypercube, the Binary Recursive Network (BRN) is regular in structure and easy to be split, which has become a popular network topology both in theoretical research and practical application. Most of the existing results on the fault tolerance of BRNs are under the assumption that the number of faulty nodes is smaller than the connectivity such that the network remains connected. These results cannot reflect the degree of damage to the network wherein the number of faulty nodes is larger than the connectivity such that the network may be disconnected. This proposal addresses the fault tolerance of BRN with more faulty nodes, which partially answers the three key scientific questions in the study of fault tolerance of BRNs. First, we propose two fault tolerant metrics: the size of largest connected component and eigen connectivity based on eigenvalues of adjacent matrix, which can efficiently measure the fault tolerance of disconnected networks. Second, we investigate the size of maximal recursive subnetwork and embeddability of longest cycle and path in a faulty network, which reveals the characteristics of interconnection networks of high fault tolerance. Finally, we improve the traditional BRN according to the theory of small-world network, and design a new hypercube-variant network with superior fault tolerant performance. The expected results will greatly enrich the evaluation system of fault tolerance of interconnection networks, as well as provide theoretical guidelines and technical supports for the development of trusted high-performance computer in China.

并行计算系统的性能很大程度上取决于连接计算结点的互连网络的有效性。为了保证系统在某些结点出现故障时仍能继续运行的能力，非常有必要研究互连网络的容错性。二进制递归网络（BRN）具有结构规则、易于分割等优点，是理论研究和实际应用中颇受欢迎的网络结构。现有的BRN容错性研究成果大多基于故障数小于连通度、网络仍然连通的少故障假设，不能反映故障数大于连通度、网络不再连通的多故障模式下网络被破坏的程度。本项目针对BRN多故障容错性研究中的3个关键科学问题开展研究，首先，提出最大连通分支规模和基于邻接矩阵特征值的特征连通度参数，解决不连通网络容错性度量问题；其次，研究故障网络中最大递归子网络规模和最长圈/路径嵌入性，给出容错性好的网络具有的特征；最后，基于小世界网络理论改进BRN，设计容错性好的小世界立方体网络。预期成果能够完善互连网络容错性度量体系，为我国高性能可信计算机的发展提供理论依据和技术支持。

现实世界中许多系统都可以抽象为网络模型。为了保证网络受到结点攻击时的数据交换能力，非常有必要研究网络的容错性。本项目从哈密尔顿圈存在性、关键传播结点识别及其在推荐系统中的应用3个方面开展研究。首先，针对现有广义蜂窝环网络上哈密尔顿圈构造方法不完备的问题，我们设计了奇数阶的广义蜂窝环网络中哈密尔顿圈的一系列构造方法，并证明了这些方法的正确性和完备性。其次，我们提出VoteRank算法来识别复杂网络中的一组去中心化的、具有最优传播能力的重要节点，真实网络上的SIR和SI实验结果表明，该算法在时间复杂度、信息传播速度和最终影响范围上都优于现有方法。最后，我们在现有基于网络结构的推荐算法中考虑用户社交网络、用户偏好的时间效应、可调参数的遍历等信息，并在真实数据集上将其与原始算法进行对比，实验结果表明改进算法进一步提高了推荐结果的准确率和多样性。基于上述研究成果，我们共计发表7篇SCI期刊论文，另有1篇论文被SCI期刊Physica A录用待发表，1篇论文已投稿SCI期刊Mobile Information Systems，目前正在审稿中。