【作者】 刘刚；

【导师】 顾乃杰；

【作者基本信息】 中国科学技术大学 ， 计算机系统结构， 2006， 博士

【摘要】 现代科学、生活的发展越来越迫切地需要更强大的计算能力，而研制具有每秒万亿次、千万亿次处理速度的并行系统需要设计高性能的互连网络来连接大量的处理器。同时，随着系统规模的不断扩大，处理器之间的通信问题变得越来越突出。在大规模科学计算和工程应用中，聚合通信的开销往往占到全部通信开销的绝大部分。因此研究互连网络及相关的聚合通信算法对提高并行计算机的性能，进而提高并行应用程序的执行效率具有重要的意义。 本文围绕如何提高互连网络上聚合通信操作的通信性能这一问题，开展了以下研究工作： 本文首先深入研究了单端口环网结构上全交换操作的实现算法。环网结构是一种具有很好拓扑特性和应用前景的互连网络，是目前很多超级计算机广泛选用的互连拓扑结构。同时，全交换操作在并行计算领域中有着大量而且重要的应用。本文基于高维单端口环网结构设计了新型网络划分策略，并运用该策略在高维单端口环网结构上提出了通信量近似最优的间接全交换算法。与现有的其它相关算法相比，本文提出的高维全交换算法不仅具有很好的可扩展性，而且通信性能有特别显著的提高。 其次，本文改进了单端口二维和三维环网结构上具有最小启动时间的全交换算法。与原有算法相比，改进后的算法采用“自底向上再回送”的通信模式，在取得最小启动时间的同时，提高了算法整体的通信性能。 再次，考虑到目前多端口环网结构上全交换操作的研究不足，本文充分利用了多端口环网的多个通信端口，首次在多端口一维环、二维和四维环网上提出了通信量完全达到理论下限的间接全交换算法。分析结果表明，当消息较长时，与已有的相关算法相比，本文提出的多端口环网上的全交换算法具有更优的通信性能。 然后，基于由多台以太网交换机分层级联而成的机群系统，本文提出通信量达到理论下限的直接全交换算法DCE和间接全交换算法MCCE。全交换算法MCCE不仅达到了通信量的理论下限，而且大幅度地减少了消息启动开销和同步开销，进一步提高了全交换操作的通信性能。实验结果表明，当消息较长时，本文提出的这两个全交换算法在上述机群系统中明显优于MPICH和LAM／MPI中实现的全交换算法。 接下来，针对传统的基于软件层面的多播技术容易导致路由延迟并加剧内存读写瓶颈等问题，本文考虑在路由器和交换机的内部交换结构中采用支持并发多更多还原

【Abstract】 The development of modern science and life has resulted in increased demand for powerful computing capacity, and the design of parallel systems that have the speed of teraflops and even petaflops requires high performance interconnection networks to interconnect numerous processors. Meanwhile, with the growing of the system size, interprocessor communication overhead more and more become a bottleneck. In large-scale scientific computing and engineering applications, the overhead of collective communication usually takes absolute majority of the entire communication overhead. Thus, the research on interconnection networks and collective communication is crucial to increase the performance of multicomputers so as to improve the execution efficiency of parallel applications.The research works presented in this dissertation are mainly concentrated on improving the performance of collective communication operations on interconnection networks.First of all, this dissertation extensively studied the algorithms for complete exchange on single-port torus. Torus has become more and more popular for interconnecting the processors in parallel and distributed systems due to its topological features, and has been widely adopted by many supercomputers today. Moreover, complete exchange, also known as all-to-all personalized communication, occurs in numerous important applications in parallel computing environment. This dissertation proposes a novel network partitioning scheme on multidimensional single-port torus. By adopting the network partitioning scheme, a near-optimal (in terms of transmission time) indirect algorithm has been presented on multidimensional single-port torus. Compared with other existing algorithms, the algorithm for complete exchange not only has a better scalability, but also prominently improves the communication performance.Secondly, this dissertation improves the algorithm for complete exchange, which has minimum startup cost on single-port 2D and 3D torus, by adopting a bottom-up-send-back approach to scheduling parallel communication. Compared with the original algorithm, the improved algorithm not only achieves minimum startup cost, but also has better communication performance.Moreover, there are few researches that have been done for complete exchange on all-port torus. This dissertation firstly proposes indirect algorithms for complete exchange on all-port 1D ring, 2D and 4D torus, which completely achieve the theoretical lower bounds on message transmission. The new algorithms fully utilize all ports and communication links in all-port torus, and transmit messages along shortest paths. The analytical results show that the proposed algorithms on all-port torus have the best communication performance among all existing algorithms, when the message size is enough long.The dissertation proposes the direct algorithm DCE and indirect algorithm MCCE for complete exchange on clusters connected by Ethernet switched hierarchical network. The two algorithms fully utilized the bandwidth in the bottleneck links and theoretically achieve the lower bounds on message transmission. In addition, the algorithm MCCE significantly reduces message startup cost and synchronization cost so as to further improve the communication performance of complete exchange. Experimental results show that the two proposed algorithms significantly outperform other complete exchange algorithms included in MPICH and LAM/MPI, on Ethernet switched更多还原