如何设计并行系统在互连网络负载平衡算法中的应用
绪论
研究背景随着电子器件、工艺和体系结构等技术的发展，计算机已经
经历了五代的发展历程。其性能上，每代都比前代有了数量级的提高。发
展时代的划分是基于器件并体现在体系结构上，说明体系结构的实现离不
开器件和工艺的支持，决定因素还是器件。体系结构不外乎是合理利用现
有器件性能的支持，采用新的概念、技术和方法构造新的体系结构，实现
性能更高的计算机系统。一个时期的器件和体系结构决定了该时期计算机
的性能和,I}价比。虽然增大投入可获得更高的性能，但这是有条件的，
当原理上可行而实际上不可行时，投入便失去了意义。这是便需要新技术
的支持。如原理上SMP系统可通过增加处理器的数量来提高系统的性能，
但由于存在访存瓶颈，可增加的处理器数量是有限的。MPP系统可以避免S
MP系统可扩展性差的问题，但也是在微处理器出现后才得以实现。当然，
互联网络的性能又可能成为限制MPP规模扩展的瓶颈。微处理器的出现不
仅为构造计算机系统，特别是可扩展并行计算机系统提供了高性价比的构
件支持，也改变了传统计算机系统的设计思想和方法。以市场大量销售的
主流微处理机芯片、主板甚至微机或工作站为基本单元构成并行计算机已
成为发展高性能计算机的主要方向。
微处理机芯片与并行处理是促使计算机性能飞速增长的两项主要技术。
传统的以独家使用的芯片为主的高性能计算机将逐渐退出市场。过去人们
常用的巨、大、中、小、微计算机分类也将逐步被两大类机器取代:一类
是只有单处理机的微机与工作站(除了操作系统不同以外，高档微机与工
作站的界限也日益模糊。)，另一类是各种不同档次的并行计算机，机器
的性能与规模将取决于系统所包含的处理机数目。以并行处理技术为基础
的高性能计算机被认为是高技术的一个致高点，美、日、西欧等发达国家
和一些发展中国家都制定了国家科研计划下大力气发展高性能计算机。我
国也开始重视发展以并行处理技术为基础的高性能计算机产业和推广应用
并行计算机。并行计算机的发展趋势并行处理机80年代初开始较大
量地进入市场。一开始多数采用SIMD和向量机方式，以Cray公司为代表，
保持巨型机的领先地位。从80年代中期基于RISC技术的微处理芯片问世以
来，计算机的性能有明显提高。86年以前向量机与小巨型机的性能每年平
均增长35%左右，86年以后，微机工作站与基于微处理机的多处理机性能
平均每年增加55%以上，也就是说，每隔一年半左右，计算机的性能就翻
一番。由于MIMD计算机性能价格比高，可扩展性强，近几年发展较快，逐
步抢占了传统向量机的市场。目前人们一致认为传统的向量机很难突破万
亿次大关，MIMD分布存储多处理机是唯一可以达到万亿次速度(Teraflops
)的技术。
高性能的并行计算机的主流究竟是“蚁群”方式(上百万台功能较弱的机
器构成一个大系统)还是“象阵”方式(最多几千台功能较强的机器组成)
，80年代曾有一场大争论。1989年，并行处理的两位权威人士(VAX
系列总设计师)和(ConnectionMachine的总设计师)曾公开打赌，
赌到1995年哪一类机器会成为主流机型。到今天，结论己经不言自明。CM
系列并行机已不再生产，ThinkMachine公司已申请破产保护，转为并行软
件公司。以市场上容易买到的主流微处理机芯片为基础构造包含几十到几
千台处理的多处理机或多计算机系统无疑已成为并行机的主流产品。连技
术上十分先进但采用自家专门设计CPU芯片的KSR公司也濒于破产。一只无
形的手在控制着并行机的发展，这就是市场。只有在市场上有竞争力的并
行机产品才有生命力。并行机的体系结构已逐步殊途同归，SGI(Cray)、I
BM,DEC,SUN等几大公司生产的并行机几乎都是采用现成的工作站或微机主
板，甚至直接采用工作站或微机(多处理机)整机做基本单元，通过总线或
专门设计的互连网络连成一台并行机，体系结构已逐渐走向标准化。专家
们预测这种相对稳定的体系结构20年内不会有大的变化。由于芯片集成度
提高，今后处理机芯片中将包含更多存储单元(一级和二级Cache)，出现
处理器嵌在大量存储单元中的所谓主动存储器或智能存储器，克服存储速
度远远跟不上处理机速度这一明显瓶颈。过去十分热门的并行机拓扑结构
问题现在已不大受人关注，因为通信开销主要在软件，多经过几个结点不
是大问题，而且采用Wormhole等传输技术以后，传送信息的时间与机器中
结点距离关系不大。体系结构的逐步一致化为并行机的推广奠定了基础。
并行处理技术的主要发展方向一台通用性较强、性能很高的并行机
，不仅要实现低延迟高带宽的互连网络接口，而且应具有可扩展性(Scala
bility)，单一系统形象(SingleSystemimage)，友好的并行编程环境，并
行计算机水平高低也主要反映在这几项关键技术上。(1)可扩展性(Scalab
ility)Scalable这一术语最近几年使用越来越频繁，在文献中被翻译成可
扩展、可伸缩、可扩缩等，中文里似乎找不到一个恰当的词表达其丰富的
内涵。美国HPCC计划的目标不称为MPP而称可扩展高性能计算机(Scalable
HighPerformanceComputer)。Scalable的含义不只是系统中处理机数目可
多可少，也不仅仅是系统可达到接近线性的加速比。
参考文献
[1〕杨晓东，陆松，牟胜梅.并行计算机体系结构[M].北京:科学出
版社，2009. [2] Efe variation of the hypercube with
lower diameter[J].IEEE Transactions on Computers, 1991, 40
(1):1312-1316 [3] Kulasinghe P, Bettayeb G. Embedding
binary trees into crossed cubes[J].IEEETransactions on
Computers, 1995, 44 (7):923-929.
[4〕樊建席.交叉立方体在两种策略下的可诊断性【J].计算机学报
，1998, 21(5) :456-462. [5] Efe K. The crossed cube
architecture for parallel computation[J].IEEE Transactions on
Parallel and Distributed Systems, 1992, 3(5):513-524. [6]
Chien-Ping Chang, Ting-Yi Sung. Edge congestion and topological
properties of crossed cubes[J].IEEE Transactions on Parallel and
Distributed Systems, 2000, 11(1):61-80.
[7〕喻听，吴敏，王国军，付朝晖.交叉立方体内顶点不交叉路径长
度的研究[J].小型微型计算机系统，2007, 28 (8) :1382-1386.
[8] Akers S B, Krishnamurthy group-theoretic model for
symmetric interconnectionnetworks仁J].IEEE Transactions on
Computers, 1989, 38(4):555-565. [9] Esfahanian A H.
Generalized measures of fault tolerance with application to n-
cubenetwords[J].IEEE Transactions on Computers, 1989, 38
(11):1586-1591. [10] Latifi S, Hedge M, Naraghi-Pour M.
Conditional connectivity measures for largemultiprocessors
systems[J].IEEE Transactions on Computers, 1994, 43 (2):218-222.
[11] Wu J. Adaptive fault-tolerant routing in cube-
based multicomputers using safetyvectors[J].IEEE Transactions on
Parallel and Distributed Systems, 1998, 9(4):321-334.
[12」高峰，李忠诚.用最优通路矩阵实现超立方体多处理机系统的
容错路由【J].计算机学报，2000, 23 (3):242-247.
[13]王雷，林亚平，陈治平等.超立方体系统中基于安全通路向量的
容错路由「J].软件学报，2004, 15 (5):783-790.
[14〕王国军，陈建二，陈松乔.具有大量错误结点的超立方体网络
中的高效路由算法的设计与讨论[J].计算机学报，2001, 24 (9) :909-
916.
[15]闰宇琦，高太平.交叉立方体互联网络的容错性研究〔J].计算
机工程与应用，2009, 45 (11):95-101. [16] R. L. Sharma.
Network topology optimization-The art and science of
networkdesign[M].Van Nostrand Reinhold, 1990.
摘要 4-5 Abstract 5 1 绪论 8-15
研究背景 8-12
并行计算机的发展趋势 8-9
并行处理技术的主要发展方向 9-12
并行处理系统相关研究的进展 12-13
本文工作及章节安排 13-15 2 互连网络的相关概念 15-26
互连网络的功能和特征 15-19
互连网络的功能 15-16 互连网络的特征
16-19 互连网络的结构 19-26
静态互连网络 20-22 动态互连网络 22-26
3 交叉立方体网络CQ 26-40 CQ网络简介 26-
31 CQ网络拓扑的结构特性 26-28
CQ网络拓扑的容错性 28-31
CQ网络负载平衡算法的设计 31-40
无错误交叉立方体的负载平衡算法 31-32
出错交叉立方体的负载平衡算法 32-38
算法模拟 38-40 4 交换立方体网络 EH 40-50
EH网络简介 40-41 EH网络的结构特性 41-44
EH网络平衡负载算法的设计 44-50
n维超立方体的负载平衡算法 44-45
交换立方体的负载平衡算法 45-50 5 工作展望 50-51
结论 51-52 参考文献 52-55
攻读硕士学位期间发表学术论文情况 55-56 致谢 56-57
