并行系统互连网络负载平衡算法的设计与实现

摘要

在并行计算领域，互连网络的拓扑结构一直是国际上研究的热点。当前，人们已提出了多种互连网络拓扑结构，其中超立方体(hypercube)是最流行的互连网络拓扑结构之一。它已被应用于商用和研究用的并行计算系统中，不少学者对它进行了深入研究。近年来的研究发现，它并不是各方面拓扑性质最好的互连网络，它自身存在着许多性能上的缺点，例如网络直径比较大，随着维数增大规模增长过快等等。于是人们开展了对超立方体的变型的研究。
　　 Efe首次提出了超立方体的一个变种网络，即交叉立方体结构，PeterK.K.Loh等人提出了超立方体的又一个变种，即交换立方体。已经证明这两个变种在结构上都对超立方体自身某些缺点进行了改进。但是，基于这些互联网络拓扑上的负载均衡算法却还停留在超立方体的阶段。以前针对超立方体设计的负载平衡算法显然不能够直接应用于其变种互联网络。
　　 本文基于当前在高性能计算的互联网络领域的研究成果，并针对两种具体的网络拓扑结构的具体特征，设计适合二者应用的负载平衡算法。验证结果可以表明，给出的算法在允许的误差范围内能够使得多处理节点间的负载达到平衡，从而可以提高整个系统的性能。

目录

文摘

英文文摘

声明

1 绪论

1.1 研究背景

1.1.1并行计算机的发展趋势

1.1.2并行处理技术的主要发展方向

1.2并行处理系统相关研究的进展

1.3 本文工作及章节安排

2互连网络的相关概念

2.1 互连网络的功能和特征

2.1.1互连网络的功能

2.1.2互连网络的特征

2.2互连网络的结构

2.2.1静态互连网络

2.2.2动态互连网络

3交叉立方体网络CQ

3.1 CQ网络简介

3.1.1 CQ网络拓扑的结构特性

3.1.2 CQ网络拓扑的容错性

3.2 CQ网络负载平衡算法的设计

3.2.1无错误交叉立方体的负载平衡算法

3.2.2 出错交叉立方体的负载平衡算法

3.2.3算法模拟

4交换立方体网络EH

4.1 EH网络简介

4.2 EH网络的结构特性

4.3 EH网络平衡负载算法的设计

4.3.1 n维超立方体的负载平衡算法

4.3.2交换立方体的负载平衡算法

5工作展望

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢