多计算机互连网络上聚合通信算法的研究

论文摘要

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

论文目录

摘要

Abstract

第1章绪论

1.1 并行计算与互连网络

1.2 并行计算机体系结构

1.3 互连网络分类

1.3.1 共享介质网络

1.3.2 直接网络

1.3.3 间接网络

1.3.4 混合网络

1.4 流控制机制

1.5 交换技术

1.5.1 线路交换

1.5.2 包交换

1.5.3 虚拟直通

1.5.4 虫蚀交换

1.6 路由算法

1.7 本文的研究内容和研究思路

1.8 本文的组织结构

第2章并行通信模型和聚合通信

2.1 消息传递模型

2.2 点对点通信

2.3 聚合通信

2.3.1 一对全通信

2.3.2 全对一通信

2.3.3 全对全通信

2.3.4 聚合通信的同步功能

2.3.5 多播操作

2.4 并行通信模型

2.4.1 Hockney通信模型

2.4.2 LogP通信模型

2.4.3 LogGP通信模型

2.4.4 LogGP模型的其它扩展模型

2.4.5 基于虫蚀交换技术的通信模型

2.5 小结

第3章单端口环网上的全交换算法研究

3.1 全交换操作概述

3.1.1 全交换问题的提出

3.1.2 相关的研究工作

3.2 系统模型

3.3 单端口环网上通信量近似最优的全交换算法

3.3.1 一维环上的全交换算法

3.3.2 二维环网上的全交换算法

3.3.3 高维环网结构上的全交换算法

3.3.4 改进后的三维算法

3.3.5 k维环网上的全交换算法MTK

3.3.6 性能分析和比较

3.4 具有最小启动时间的全交换算法

3.4.1 二维环网上的全交换算法

3.4.2 三维环网上的全交换算法

3.4.3 性能分析和比较

3.5 小结

第4章多端口环网上通信量最优的全交换算法

4.1 多端口一维环结构上的全交换算法

4.1.1 通信模式

4.1.2 通信时间复杂度分析

4.2 多端口二维环网上的全交换算法

4.2.1 算法概述

4.2.2 通信模式

4.2.3 数组结构

4.2.4 通信时间复杂度分析

4.3 多端口四维环网上的全交换算法

4.4 性能分析与比较

4.5 小结

第5章机群系统中的通信算法研究

5.1 机群系统的通信研究概述

5.2 机群系统上的传统全交换算法

5.2.1 环算法（Ring）

5.2.2 成对交换算法（Pairwise exchange）

5.3 以太网机群上通信量最优的全交换算法

5.3.1 系统模型

5.3.2 全交换算法DCE

5.3.3 全交换算法MCCE

5.3.4 实验结果

5.4 小结

第6章广义非阻塞多播网络

6.1 概述

6.2 交换网络

6.2.1 传统的三级Clos网络

6.2.2 Clos网上的多播

6.2.3 目前研究现状

6.3 广义非阻塞四级Clos多播网络

6.3.1 四级Clos网的结构及相关定义

6.3.2 PMPM网上的多播路由算法

6.3.3 广义非阻塞多播网络PMPM的硬件条件

6.3.4 分析与比较

6.4 广义非阻塞k-fold多播

6.4.1 在k-PMPM网上实现广义非阻塞k-fold多播

6.4.2 在k-MMMM网上实现广义非阻塞k-fold多播

6.4.3 分析与比较

6.5 小结

第7章总结

7.1 本文工作总结

7.2 本文的主要贡献与创新之处

7.3 进一步的研究工作

附录A.多端口二维环网上全交换算法的描述示例

参考文献

致谢

在读期间发表和录用的学术论文

攻读学位期间所参加的科研项目

多计算机互连网络上聚合通信算法的研究

论文摘要

论文目录

相关论文文献

猜你喜欢