30000字硕士毕业论文如何设计并行系统在互连网络负载均衡算法中的应用
论文类型：硕士毕业论文
论文字数：30000字
论点：并行,计算机,立方体
论文概述：
绪论 1.1研究背景随着电子器件、工艺和体系结构等技术的发展，计算机已经经历了五代的发展历程。其性能上，每代都比前代有了数量级的提高。发展时代的划分是基于器件并体现在体系结构
论文正文：
绪论 1.1研究背景随着电子器件、工艺和体系结构等技术的发展，计算机已经经历了五代的发展历程。其性能上，每代都比前代有了数量级的提高。发展时代的划分是基于器件并体现在体系结构上，说明体系结构的实现离不开器件和工艺的支持，决定因素还是器件。体系结构不外乎是合理利用现有器件性能的支持，采用新的概念、技术和方法构造新的体系结构，实现性能更高的计算机系统。一个时期的器件和体系结构决定了该时期计算机的性能和,I}价比。虽然增大投入可获得更高的性能，但这是有条件的，当原理上可行而实际上不可行时，投入便失去了意义。这是便需要新技术的支持。如原理上SMP系统可通过增加处理器的数量来提高系统的性能，但由于存在访存瓶颈，可增加的处理器数量是有限的。MPP系统可以避免SMP系统可扩展性差的问题，但也是在微处理器出现后才得以实现。当然，互联网络的性能又可能成为限制MPP规模扩展的瓶颈。微处理器的出现不仅为构造计算机系统，特别是可扩展并行计算机系统提供了高性价比的构件支持，也改变了传统计算机系统的设计思想和方法。以市场大量销售的主流微处理机芯片、主板甚至微机或工作站为基本单元构成并行计算机已成为发展高性能计算机的主要方向。 微处理机芯片与并行处理是促使计算机性能飞速增长的两项主要技术。传统的以独家使用的芯片为主的高性能计算机将逐渐退出市场。过去人们常用的巨、大、中、小、微计算机分类也将逐步被两大类机器取代:一类是只有单处理机的微机与工作站(除了操作系统不同以外，高档微机与工作站的界限也日益模糊。)，另一类是各种不同档次的并行计算机，机器的性能与规模将取决于系统所包含的处理机数目。以并行处理技术为基础的高性能计算机被认为是高技术的一个致高点，美、日、西欧等发达国家和一些发展中国家都制定了国家科研计划下大力气发展高性能计算机。我国也开始重视发展以并行处理技术为基础的高性能计算机产业和推广应用并行计算机。1.1.1并行计算机的发展趋势并行处理机80年代初开始较大量地进入市场。一开始多数采用SIMD和向量机方式，以Cray公司为代表，保持巨型机的领先地位。从80年代中期基于RISC技术的微处理芯片问世以来，计算机的性能有明显提高。86年以前向量机与小巨型机的性能每年平均增长35%左右，86年以后，微机工作站与基于微处理机的多处理机性能平均每年增加55%以上，也就是说，每隔一年半左右，计算机的性能就翻一番。由于MIMD计算机性能价格比高，可扩展性强，近几年发展较快，逐步抢占了传统向量机的市场。目前人们一致认为传统的向量机很难突破万亿次大关，MIMD分布存储多处理机是唯一可以达到万亿次速度(Teraflops)的技术。 高性能的并行计算机的主流究竟是“蚁群”方式(上百万台功能较弱的机器构成一个大系统)还是“象阵”方式(最多几千台功能较强的机器组成)，80年代曾有一场大争论。1989年，并行处理的两位权威人士G.Bell(VAX系列总设计师)和W.Hillis(ConnectionMachine的总设计师)曾公开打赌，赌到1995年哪一类机器会成为主流机型。到今天，结论己经不言自明。CM系列并行机已不再生产，ThinkMachine公司已申请破产保护，转为并行软件公司。以市场上容易买到的主流微处理机芯片为基础构造包含几十到几千台处理的多处理机或多计算机系统无疑已成为并行机的主流产品。连技术上十分先进但采用自家专门设计CPU芯片的KSR公司也濒于破产。一只无形的手在控制着并行机的发展，这就是市场。只有在市场上有竞争力的并行机产品才有生命力。并行机的体系结构已逐步殊途同归，SGI(Cray)、IBM,DEC,SUN等几大公司生产的并行机几乎都是采用现成的工作站或微机主板，甚至直接采用工作站或微机(多处理机)整机做基本单元，通过总线或专门设计的互连网络连成一台并行机，体系结构已逐渐走向标准化。专家们预测这种相对稳定的体系结构20年内不会有大的变化。由于芯片集成度提高，今后处理机芯片中将包含更多存储单元(一级和二级Cache)，出现处理器嵌在大量存储单元中的所谓主动存储器或智能存储器，克服存储速度远远跟不上处理机速度这一明显瓶颈。过去十分热门的并行机拓扑结构问题现在已不大受人关注，因为通信开销主要在软件，多经过几个结点不是大问题，而且采用Wormhole等传输技术以后，传送信息的时间与机器中结点距离关系不大。体系结构的逐步一致化为并行机的推广奠定了基础。 1.1.2并行处理技术的主要发展方向一台通用性较强、性能很高的并行机，不仅要实现低延迟高带宽的互连网络接口，而且应具有可扩展性(Scalability)，单一系统形象(SingleSystemimage)，友好的并行编程环境，并行计算机水平高低也主要反映在这几项关键技术上。(1)可扩展性(Scalability)Scalable这一术语最近几年使用越来越频繁，在文献中被翻译成可扩展、可伸缩、可扩缩等，中文里似乎找不到一个恰当的词表达其丰富的内涵。美国HPCC计划的目标不称为MPP而称可扩展高性能计算机(ScalableHighPerformanceComputer)。Scalable的含义不只是系统中处理机数目可多可少，也不仅仅是系统可达到接近线性的加速比。 参考文献[1〕杨晓东，陆松，牟胜梅.并行计算机体系结构[M].北京:科学出版社，2009. Efe K.A variation of the hypercube with lower diameter[J].IEEE Transactions on Computers, 1991, 40 (1):1312-1316 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. Efe K. The crossed cube architecture for parallel computation[J].IEEE Transactions on Parallel and Distributed Systems, 1992, 3(5):513-524. 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. Akers S B, Krishnamurthy B.A group-theoretic model for symmetric interconnectionnetworks仁J].IEEE Transactions on Computers, 1989, 38(4):555-565. Esfahanian A H. Generalized measures of fault tolerance with application to n-cubenetwords[J].IEEE Transactions on Computers, 1989, 38 (11):1586-1591. Latifi S, Hedge M, Naraghi-Pour M. Conditional connectivity measures for largemultiprocessors systems[J].IEEE Transactions on Computers, 1994, 43 (2):218-222. 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 1.1 研究背景 8-12 1.1.1 并行计算机的发展趋势 8-9 1.1.2 并行处理技术的主要发展方向 9-12 1.2 并行处理系统相关研究的进展 12-13 1.3 本文工作及章节安排 13-15 2 互连网络的相关概念 15-26 2.1 互连网络的功能和特征 15-19 2.1.1 互连网络的功能 15-16 2.1.2 互连网络的特征 16-19 2.2 互连网络的结构 19-26 2.2.1 静态互连网络 20-22 2.2.2 动态互连网络 22-26 3 交叉立方体网络CQ 26-40 3.1 CQ网络简介 26-31 3.1.1 CQ网络拓扑的结构特性 26-28 3.1.2 CQ网络拓扑的容错性 28-31 3.2 CQ网络负载平衡算法的设计 31-40 3.2.1 无错误交叉立方体的负载平衡算法 31-32 3.2.2 出错交叉立方体的负载平衡算法 32-38 3.2.3 算法模拟 38-40 4 交换立方体网络 EH 40-50 4.1 EH网络简介 40-41 4.2 EH网络的结构特性 41-44 4.3 EH网络平衡负载算法的设计 44-50 4.3.1 n维超立方体的负载平衡算法 44-45 4.3.2 交换立方体的负载平衡算法 45-50 5 工作展望 50-51 结论 51-52 参考文献 52-55 攻读硕士学位期间发表学术论文情况 55-56 致谢 56-57