一类新型并行系统互连网络及其关键性质的研究

The capability of the interconnection network largely decides the performance of parallel computing. However, the number of processors in the parallel system becomes increasingly larger, because of the continuous increase of the application requirements. The performance improvement of parallel computing faces great challenges of how to connect a large number of processors in building an interconnection network with promising performance. Traditional interconnection networks have issues of link complexity, scale expansion difficulty, etc.. Recently proposed interconnection networks such as hypercube, hypercube-like network, k-ary n-cube, etc., have better communication performance and fault tolerance. However, for hypercube and k-ary n-cube, the topology structure scales too rapidly as the number of processors increases; for hypercube-like network, reducing link complexity typically compromises communication performance and connectivity performance. Based on the above considerations, we propose new interconnection networks, called exchanged 3-ary n-cube networks (E3C). Compared with the existing interconnection network, the E3C networks have greater advantages in the connection mode and contain better performances. Furthermore, we will study the static properties of E3C networks, such as vertex degree, connectivity, diameter, and etc.; communication routing algorithm; diagnosis. Then, we will analyze the performance and time complexities of the proposed algorithm, and conduct simulations accordingly in E3C networks. Such research will provide the basis for design and implementation of a new family of parallel systems.

并行系统互连网络的性能很大程度上决定并行计算的性能，但随着应用需求的不断提高，并行系统中的处理器数量变得越来越庞大。如何将大量处理器连接起来，从而构建一个性能良好的互连网络，是提升并行计算性能所面临的一个挑战。传统的互连网络存在链路复杂和扩展困难等问题，目前提出的超立方体、类超立方体和k-元n-立方体等互连网络具有较好的通信和容错性能，但超立方体和k-元n-立方体随处理器数量增加其边的数目急剧增加，直接影响到硬件成本；类超立方体降低了边的复杂性，但连通性和通信路由性能有所降低。本项目提出一类新型互连网络交换3-元n-立方体网络E3C，其连接方式相比现存的互连网络具有较大的优越性，同时具有了良好的性能。进一步，我们将研究E3C网络的静态性质如顶点度数、连通度、直径等；通信路由算法；诊断度。同时，我们将分析算法的性能及时间复杂度并进行模拟实验。该研究将为新型并行系统的设计和应用提供重要依据。

互连网络是并行计算机的核心，其性能对整个并行计算机系统的硬件消耗、通信性能、路由算法的可行性等都起着重要的作用。本项目运用图论的方法对并行分布式系统互连网络的容错、通信等性能进行研究。项目基于现有的互连网络，在维持其良好特性并改善既有缺点的目标下，构造总体性能较好且降低网络成本的并行系统互连网络交换3-元n-立方体网络E3C，其降低了网络的复杂性，同时保留了良好的性能。项目研究并给出了E3C网络的连通度、直径、同构、子图划分等性质，验证了网络的优越性；项目也研究了E3C网络的通信性能，在求解最短路径和路由的基础上，设计了通信路由算法，并进行模拟实验和算法分析，对其网络通信的有效实现提供了依据；项目同时也研究了E3C网络的可诊断性，分析并给出了其在PMC模型和MM*模型下的诊断度，E3C网络在PMC模型和MM*模型下的诊断度都是min{2t+2, 2s+2, 2r+2}，为研究互连网络的容错性能和故障诊断提供了重要依据。项目研究的结论为新型并行系统的设计和应用提供重要的依据。