导　　师： 顾乃杰

学科专业： H1201

授予学位： 博士

作　　者： ;

机构地区： 中国科学技术大学

摘　　要： 现代科学、生活的发展越来越迫切地需要更强大的计算能力，而研制具有每秒万亿次、千万亿次处理速度的并行系统需要设计高性能的互连网络来连接大量的处理器。同时，随着系统规模的不断扩大，处理器之间的通信问题变得越来越突出。在大规模科学计算和工程应用中，聚合通信的开销往往占到全部通信开销的绝大部分。因此研究互连网络及相关的聚合通信算法对提高并行计算机的性能，进而提高并行应用程序的执行效率具有重要的意义。 本文围绕如何提高互连网络上聚合通信操作的通信性能这一问题，开展了以下研究工作： 本文首先深入研究了单端口环网结构上全交换操作的实现算法。环网结构是一种具有很好拓扑特性和应用前景的互连网络，是目前很多超级计算机广泛选用的互连拓扑结构。同时，全交换操作在并行计算领域中有着大量而且重要的应用。本文基于高维单端口环网结构设计了新型网络划分策略，并运用该策略在高维单端口环网结构上提出了通信量近似最优的间接全交换算法。与现有的其它相关算法相比，本文提出的高维全交换算法不仅具有很好的可扩展性，而且通信性能有特别显著的提高。 其次，本文改进了单端口二维和三维环网结构上具有最小启动时间的全交换算法。与原有算法相比，改进后的算法采用“自底向上再回送”的通信模式，在取得最小启动时间的同时，提高了算法整体的通信性能。 再次，考虑到目前多端口环网结构上全交换操作的研究不足，本文充分利用了多端口环网的多个通信端口，首次在多端口一维环、二维和四维环网上提出了通信量完全达到理论下限的间接全交换算法。分析结果表明，当消息较长时，与已有的相关算法相比，本文提出的多端口环网上的全交换算法具有更优的通信性能。 然后，基于由多台以太网交换机分层级联而成的机群系统，本文提出通信量达到理论下限的直接全交换算法dce和间接全交换算法mcce。全交换算法mcce不仅达到了通信量的理论下限，而且大幅度地减少了消息启动开销和同步开销，进一步提高了全交换操作的通信性能。实验结果表明，当消息较长时，本文提出的这两个全交换算法在上述机群系统中明显优于mpich和lam/mpi中实现的全交换算法。 接下来，针对传统的基于软件层面的多播技术容易导致路由延迟并加剧内存读写瓶颈等问题，本文考虑在路由器和交换机的内部交换结构中采用支持并发多播等通信方式的多级互连网络，从而在硬件层面上实现并发多播等通信方式。在深入研究了广义非阻塞型多播网络的低代价构建和多播路由算法的优化等问题之后，本文提出了一种低代价的广义非阻塞四级clos网络及相关的多播路由算法。与现有广义非阻塞多播网络相比，本文构造的多播网络具有如下特色：①网络的硬件代价降低到12nз/2个交叉点以下，仅相当于广义非阻塞置换网络的常数倍；②时间复杂度为o(n)的多播路由算法简单、高效，易于硬件实现；③降低了单个交叉开关模块的引脚(端口)数目，更有利于vlsi芯片的集成。④增加的一级开关模块可以有效地平衡多播负载，增加网络的灵活性。 最后，本文深入研究了能够支持并发多播目标端口重叠的广义非阻塞k-fold多播网络及相关的多播路由算法。该网络可以用较低的硬件代价来有效地减少多播连接的外部阻塞，从而为多播通信提供更好的qos性能。本文通过重新计算广义非阻塞四级clos多播网络的中间两级开关个数，以提供足够的网络内部路径来实现k-fold多播路由。基于此思路，本文提出了两个广义非阻塞k-fold多播路由算法及相应的硬件条件。 需要说明的是，虽然本文整体的研究工作是根据并行分布式多处理机系统的特点以及特定的应用需求展开的，但是其中提出的广义非阻塞多播网络并不局限于多处理机系统，也适用于广域网、局域网的路由器和交换机中。

关 键 词： 互连网络 聚合通信 环网 全交换操作 机群 网 并行通信模型

分 类 号： [TN915.04 TP301.6]

领　　域： [电子电信] [电子电信] [自动化与计算机技术] [自动化与计算机技术]