类超立方体网络上的容错通信性能研究

By the improving of the performance of the high-performance parallel computer, the number of its processors is becoming larger. Meanwhile, the failure probability of processor nodes and the connection links is also increasing. When the faults occur, a good interconnection network should have fault-tolerant communication performance to ensure the efficient and reliable data transmission between processor nodes. In a parallel system, the communication performance is closely related to the diameter of the network topology, which decides the maximum communication delay among the processors. The hypercube-like network is a kind of typical interconnect network, which includes the hypercube and its variety variants. However, in existing research, there are only some works of fault diameter, wide diameter and the problem of diameter variance with faulty edges problems in a few special hypercube variants; furthermore, these existing works above lack general method and the methods used in the existing studies cannot be applied to hypercube-like networks; and there are loss of related researches on experiments and applications. In this project, we will study the fault-tolerant communication performance of hypercube-like networks, and give a general result and provide a general method on the fault diameter, the wide diameter, and the diameter variance with faulty edges problems of hypercube-like networks. Finally, we will apply the optimal node-disjoint paths sets between node pairs obtained in solving the wide diameter problem to design the routing algorithms in feature space of human contact network.

随着高性能并行计算机性能的不断提高，它的处理器数量越来越庞大。同时，处理器结点和连接链路发生故障的概率也在增大。当故障发生时，一个良好的互连网络应具有一定的容错通信性能，保证数据能在处理器结点间高效、可靠的传输。互连网络的通信性能与直径密切相关，它决定了数据传输的最大通信延迟。类超立方体网络是一类典型的互连网络，它包含超立方体及其若干变型。然而，在现有研究中，只有几种超立方体变型上宽直径、故障直径以及边故障时直径变化问题的部分研究成果；且现有的方法缺乏一般性，不适用于类超立方体；同时缺乏有关的实验和应用研究。本项目拟研究类超立方体网络上的容错通信性能，给出在类超立方体网络上求解宽直径、故障直径和边故障时直径的变化问题的通用方法和一般结果，并将求解宽直径过程中构造的顶点对间最优顶点不相交路径组应用在人类联系网络的特征空间中来设计多路径路由算法。

高性能并行计算机是一个国家综合科技实力的体现，是支撑国家实力持续发展的关键技术之一，在科研、教育、石油、气象等相关领域发挥着日益重要的作用。随着高性能并行计算机性能的不断提高，它所拥有的处理器（处理机）数量变得越来越庞大。同时，处理器结点和连接链路发生故障的概率也在增大。当故障发生时，一个良好的互连网络应具有一定的容错通信性能，保证数据能在处理器结点间高效、可靠的传输。互连网络的通信性能与直径密切相关，它决定了数据传输的最大通信延迟。类超立方体网络是一类典型的性能良好的互连网络，它包含超立方体及其若干变型。本项目研究类超立方体网络上的容错通信性能，并进行模拟实验和应用研究。研究取得的成果主要如下：1.求解得到类超立方体网络的一个特殊变型：局部扭立方体(LTQ)的故障直径和宽直径。证明n维局部扭立方体的故障直径(Dn(LTQn-1f))和宽直径(Dn(LTQn))如下：对于n≥7的奇数，Dn(LTQn-1f)=Dn(LTQn)=D(LTQ)+2；对于n≥8的偶数，Dn(LTQn-1f)≤Dn(LTQn)≤D(LTQ)+2。2.研究了类超立方体网络的故障直径和宽直径，得到n维类超立方体的故障直径和宽直径的上界。3.研究了递归构造网络：交叉立方体、WK-递归图、交换群图、3元n立方体、BCube和DCell上的容错通信性能问题。4.进行模拟实验和应用研究：分析了特殊超立方体变型上宽直径和故障直径的共性，总结出了类超立方体网络上求解较短顶点不相交路径的一般方法，给出了构造顶点对间较优顶点不相交路径组的通用算法，完成了模拟程序的设计和验证。这些研究成果说明类超立方体等网络结构具有良好的容错通信性能，在数据传输的效率和可靠性上具有一定优势，适合信息的并行传输、安全分发和设计可靠性传输协议，对将其应用于互连网络、P2P覆盖网络、片上网络、数据中心网络、人类接触等网络上具有重要的理论和实践指导意义。