（计算机系统结构专业论文）基于分布树的负载均衡模型研究和应用.pdf

上海大学硕上学位论文 摘要 在并行计算中，随着问题规模增大，需要考虑如何分配负载来达到均衡。 在一个由多个处理机组成的集群系统中，相互作用的任务必须分配到多个处理 机上，以充分利用系统资源。许多科学计算和应用中都是以树作为数据结构的， 所以研究分布树的负载均衡模型具有非常现实的意义，除了可应用于电磁散射 的并行精确计算以外，对以树结构为计算基础的工程应用，也有推广和参考价 值。如果分布树的负载不均衡，则将导致整个并行算法的效率降低，而且体现 不出并行算法的优点。 本文分析了几种不同的构建分布树的模型，每种构建模型都代表不同的负 载划分方法，并对模型的优缺点进行了阐述，指出其适合的应用范围。在对几 种不同模型的研究基础上，提出了一种新的构建分布树的模型，即均分某一层 ( 非最细层) 的方式来构建分布树。此模型可以避免使用传统的基于最细层分 配所导致的负载不均衡现象，适合空结点比较多、且同一层上每个结点的孩子 数不规则的树型结构。 在对并行多层快速多极子算法( m l f m a ) 原理研究的基础上，将不同的 分布树构建模型在并行m l f m a 中实现，从而更加具体、详细地来分析每种模 型，并且通过实验来分析负载均衡情况及其对整个并行算法效率的影响。 关键词：分布树，负载均衡，并行计算，多层快速多极子算法 v 上海大学硕士学位论文 a b s t r a c t i np a r a l l e lc o m p u t a t i o n ，i tn e e d st oc o n s i d e rh o wt od i s t r i b u t el o a dt or e a c ht h e e q u i l i b r i u mw i t l lt h ei n c r e a s eo fq u e s t i o ns c a l e i nac l u s t e rs y s t e mc o m p o s e do fa n u m b e ro f p r o c e s s o r s ，t h ei n t e r a c t i v et a s km u s tb ea s s i g n e dt om u l t i p l ep r o c e s s o r si n o r d e rt om a k ef u l lu s eo fs y s t e mr e s o u r c e al o to fs c i e n t i f i cc o m p u t i n ga n d a p p l i c a t i o n sr e g a r dt r e ea sd a t as t r u c t u r e ，s oi th a sav e r yr e a l i s t i cm e a n i n gt os t u d y t h el o a db a l a n c i n gm o d e lo fd i s t r i b u t i o nt r e e b e s i d e sa p p l y i n gt oa c c u r a t ep a r a l l e l c a l c u l a t i o no fe l e c t r o m a g n e t i cs c a t t e r i n g , t h e r ea r ea l s op o p u l a r i z a t i o na n dr e f e r e n c e v a l u et op r o j e c ta p p l i c a t i o nw h i c hr e g a r d st h et r e es t r u c t u r e 勰c a l c u l a t i o nf o u n d a t i o n t h eu n b a l a n c e dd i s t r i b u t i o nt r e eo fl o a dw i l ll e a dt or e d u c ee f f i c i e n c yo ft h ee n t i r e p a r a l l e la l g o r i t h m ，t h u sc a n te m b o d yt h ea d v a n t a g eo ft h ea l g o r i t h m t h i sp a p e ra n a l y s e ss e v e r a ld i f f e r e n tc o n s t r u c t i o nm o d e l so fd i s t r i b u t i o nt r e e ， e a c hk i n do fm o d e lr e p r e s e n t i n gd i f f e r e n tm e t h o do fl o a dd i v i d e d ，a n de x p l a i n st h e a d v a n t a g e sa n dd i s a d v a n t a g e so fe a c hm o d e l ，p o i n t i n go u ti t s s u i t a b l er a n g eo f a p p l i c a t i o n b a s e do nt h es t u d yo fs e v e r a lk i n d so fd i f f e r e n tm o d e l s ，t h ep a p e r p r e s e n t san e wc o n s t r u c t i o nm o d e lo fd i s t r i b u t i o nt r e et h a ti s ，d i v i d i n ge q u a l l ys o m e o n el a y e r ( n o n - f i n a ll a y e r ) t oc o n s t r u c td i s t r i b u t i o nt r e e t h i sm e t h o dc a na v o i d u n b a l a n c e dp h e n o m e n o no fl o a dc a u s e db yt h et r a d i t i o n a lu s eo ft h ed i s t r i b u t i o n b a s e do nt h es m a l l e s tl a y e r i ti ss u i t a b l ef o rt h et y p eo ft r e es t r u c t u r ew h i c hh a s m a n ye m p t yn o d e sa n dt h ec o u n t so fc h i l dn o d e sf o re a c hn o d eo nt h es a m el a y e ra r e i r r e g u l a r b a s e do nt h es t u d yo fp a r a l l e lm u l t i l e v e lf a s tm u l t i p o l ea l g o r i t h m ，w ea p p l yt h e d i f f e r e n tm e t h o d st ot h ep r o c e s so fp a r a l l e lc o n s t r u c t i n gd i s t r i b u t i o nt r e e si np a r a l l e l m l f m a i ti sf i tf o ru st oa n a l y z ee v e r ym e t h o di nd e t a i l a l s ow ed oal o to f e x p e r i m e n t st os h o w l o a db a l a n c ea n dp a r a l l e le f f i c i e n c y k e y w o r d s ：d i s t r i b u t i o nt r e e ，l 0 a db a l a n c i n g , p a r a l l e lc o m p u t i n g , m l f m a v l 上海大学硕上学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：盗：尘垫e l 期：圣竺箜型2 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 1 1 日期： 上海大学硕上学位论文 1 1 研究背景 第一章绪论 随着科学技术的发展，计算对硬件的要求越来越高。但是，单机计算往往 非常耗时。虽然计算机的单机性能有了很大的提高，但是在处理复杂大规模问 题的时候仍显得力不从心。当代科学技术的快速发展对大规模科学与工程的计 算提出了极高的具有挑战性的要求，如用计算来预报全球未来一段时间的天气、 模拟飞行器的风洞实验、人造卫星的图像处理、石油资源的勘探、核工程的研 究等；另一方面计算机单机性能的提高又受到元器件制造工艺等许多因素的限 制，面对具有挑战性的大规模计算课题有限的计算资源，人们尝试采用器件组 合等多种并行处理技术来实现高性能的计算机系统，以及通过把一个大的计算 问题分解成许多彼此独立但又相关的子问题，把它们映射到各个处理器上并发 执行从而最终解决问题，由于计算任务的并发性、同时性、因此可以大大减少 整个计算过程的时间，获得较高的计算效率。 高性能计算是大规模复杂计算领域中不可缺少的高端计算工具。上世纪9 0 年代以来，以高性能计算机为基础的计算科学得到了长足的发展，它与理论科 学和实验科学相辅相成、彼此印证，成为人类科学研究必不可少的方法之一。 在许多工业领域，如汽车、航空航天器的设计制造、石油勘探、地震资料处理 及国防等，并行计算已经成为首选研究方法。 负载平衡问题主要分为静态负载平衡和动态负载平衡【l 】。人们利用系统的 相关信息，以数学公式或者是其它方法将静态任务进行划分并分配到集群系统 的各个节点上，间接地实现了静态负载平衡。而根据系统当前的负载状态，依 照相关策略将各节点上的任务进行调度，动态做出负载迁移的决定，直接地实 现了动态负载平衡。在大部分状况下，动态负载平衡所表现出来的系统性能明 显优于静态负载平衡。 早期的集群计算中，每个处理器拷贝一份负载，但是随着问题规模的增大， 需要考虑如何分配负载来达到均衡。在一个由多个处理机组成的集群系统中， 上海人学硕士学位论文 相互作用的任务必须分配到多个处理机上，以充分利用系统资源。在任务分配 到处理机的过程中，有两种类型的成本任务，即在某个处理机上的执行成本和 处理机之间的通信成本。为了改进分布系统的性能，必须满足两个条件：处理 机之间的通信成本要降到最低；在不同处理机上的任务的执行成本需要平衡， 使得处理机之间通信成本和任务的执行时间都尽可能最小化。在高性能并行计 算的研究中，如何有效地平衡各处理器的负载并且减少处理器间的通信，是当 今的一个研究热点。 许多科学计算和应用中都是以树作为数据结构的，所以研究分布树的负载 均衡模型具有非常现实的意义，除了可应用于电磁散射的并行精确计算以外， 对以树结构为计算基础的工程应用，也有推广和参考价值，具有非常现实的意 义。对于电磁应用中的多层快速多极子来讲，其串行算法时间和空间复杂度均 为n l o g n ，在此基础上要大幅度提高其计算能力已非常困难。而大量事实证 明，并行是进一步提升多层快速多极子求解能力的关键，相应的串行的树结构 需要演化为分布树结构。串行树的划分方案对整个并行算法的效率有很大的影 响。分布树的建立是实现并行m l f m a 的基础，由于多层快速多极子的所有计 算都是基于非空组的树型结构，所以分布树的建立对整个并行算法的效率有很 大影响。负载均衡的分布树是提高并行m l f m a 算法的关键问题。 1 2 国内外研究概况 1 2 1 国外研究概况 关于分布树负载均衡模型的研究，许多文献都是基于某一方面的应用，很 少有文献来专门研究这种模型。由于应用目的不同，所以采取不同的分布树建 立方式来达到负载均衡。 1 9 8 9 年，耶鲁大学( y a l eu n i v e r s i t y ) 的v r o k h l i n 教授将快速多极子方法 f m m ( f a s tm u l t i p o l em e t h o d ) 用于静电场问题的泊松方程的求解，f m m 的计算 和存储复杂度都是o ( n 1 5 ) ，其后伊利诺伊大学香槟分校( u i u c ) 的w c c h e w 教授对f m m 进行了单层向多层的推广和完善，从而形成了多层快速多极子算 2 上海人学硕士学位论文 法m l f m a ( m u l t il e v e lf a s tm u l t i p o l ea l g o r i t h m ) ，是计算和存储的复杂度降低 到了o ( n l o g n ) 量级，并且推出了具有实用价值的f i s c ( f a s t i l l i n o i ss o l v e rc o d e ) 。 虽然多层快速多极子方法能精确计算目标的r c s ，但多层快速多极子方法 对内存的需求为o ( n l o g n ) ，其时间复杂度也为o ( n l o g n ) 。因此，当工程应用 涉及到复杂的电大尺寸三维目标时，随着未知数目的增大，内存需求和计算时 间就成为制约求解问题规模的关键因素。另外，随着并行技术的发展，特别是 对集群并行计算技术的深入研究，于是有学者提出采用分布式存储、并行计算 的方式来解决内存瓶颈的问题。上世纪9 0 年代锡拉丘兹大学( s y r a c u s e u n i v e r s i t y ) 首先在这方面做出了尝试，实现了并行矩量法程序。其后，伊利诺 伊大学香槟分校的w c c h e w 教授实现了并行的多层快速多极子程序s c a l e m e ( s c a l ea b l em l f m ae n g i n e ) ，并且利用s c a l em e 完成了在雷达工作频率为 8 g h z 下的验模飞机v f y 2 1 8 的电磁散射问题的求解，未知量高达1 0 ，0 0 0 ， 0 0 0 2 - 4 。 1 2 2 国内研究概况 国内关于分布树负载均衡模型的研究，也都是基于某一方面的应用，几乎 没有文献来专门研究这种模型。一般情况下，根据不同的应用需求，采取不同 的分布树建立方式。 国内电子科技大学聂在平、胡俊、王浩刚等人于1 9 9 9 年开发了三维矢量 电磁散射分析的多层快速多极子方法数值程序，在单机( 内存1 g b ) 上成功求解 了未知量在十万量级以内的散射问题，并合作开发了基于工作站网络的并行多 层快速多极子方法，进一步提升了多层快速多极子方法的求解能力【5 。8 】。 多层快速多极子的几何建模和电磁建模就是基于分布树模型的，分布树的 负载均衡模型对于加快整个算法起着重要的作用。因此，研究分布树的负载均 衡模型不仅具有推广和应用价值，而且具有非常现实的意义。 1 3 论文的章节结构 本论文以作者攻读硕士学位期间参与的项目“飞行器r c s 精确分析计算并 3 上海大学硕七学位论文 行化研究及实现”、“飞行器多层快速多极子算法精确并行计算软件研发、“飞 行器r c s 精确并行计算软件研发及工程应用研究 工作为基础，主要研究在分 布式并行环境下，建立在树模型基础上，在减少处理器之间通信的情况下，如 何合理地构造并行分布树，从而达到良好的负载均衡效果。分析了几种不同的 构建分布树模型的优缺点及其适合的应用范围，并将这些不同的模型应用到并 行多层快速多极子算法中，来更加具体地分析每种模型的特点。在实际的工程 应用中，可以根据不同的需求来选择合适的构造分布树的方法，从而达到不同 的结果。 本文的结构安排如下： 第一章中介绍了课题的研究背景，国内外研究的现状以及本论文的主要研 究内容。 第二章介绍了并行计算的一些基础知识，并行计算机、集群系统以及并行 算法。 第三章介绍了负载均衡的理论知识，分析了几种不同的建立分布树的模型， 并且对每种模型的优缺点及其适用的范围进行了研究。 第四章阐述了快速多极子算法和多层快速多极子算法的原理，并对并行多 层快速多极子算法中的分布树做了一些分析。 第五章基于前面的分析，将不同的建立分布树的模型应用到并行多层快速 多极子算法中，通过实验结果，从而更加具体详细地来分析每种方案。 第六章总结全文并提出进一步的工作方向。 4 上海大学硕上学位论文 2 1 并行计算 第二章并行计算基础 并行计算( p a r a l l e lc o m p u t a t i o n ) 是指在并行计算机上，将一个计算任务分 解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执 行子任务，从而达到加快求解速度，提高求解规模的目的【9 】。 并行计算的发展主要基于两方面的原因。第一，单机性能不能满足大规模 科学与工程问题的计算需求，并行计算是实现高性能计算问题的唯一途径；第 二，同时性和并行性是物质世界的一种普遍属性，具有实际物理背景的计算问 题在许多情况下都可以划分成能够并行计算的多个子任务。针对某一具体应用 问题，我们可以利用它们内部的并行性，设计并行算法，将其分解成为互相独 立但彼此又有一定联系的若干个子问题，分别交给各台处理机，而所有的处理 机按并行算法完成初时应用问题的求解，例如，根据几十个常用应用软件的统 计，6 0 8 0 的标量计算可以被向量化，而9 0 左右的串行计算可以并行化。 为什么要采用并行计算? 这是因为第一，它可以加快速度即在更短的时间 内解决相同的问题或在相同的时间内解决更多更复杂的问题特别是对一些新出 现的巨大挑战问题不使用并行计算是根本无法解决的。第二，节省投入并行计 算可以以较低的投入完成串行计算才能够完成的任务。第三，物理极限的约束 光速是不可逾越的速度极限设备和材料也不可能做得无限小只有通过并行才能 够不断提高速度。 2 2 并行计算机 并行计算机即能在同一时间内执行多条指令( 或处理多个数据) 的计算机， 并行计算机是并行计算的物理载体。 上海大学硕士学位论文 2 2 1f iy n n 分类法 并行计算机即并行计算环境是并行算法赖以生存的物质基础它们的发展直 接影响着并行算法的设计和实现。 1 9 6 6 年m j f l y n n 提出了著名的f l y n n 分类法，根据指令流与数据流方 式的不同将计算机系统分类。指令流是指机器执行的指令序列；数据流指指令 调用的数据序列，包括输入数据和中间结果。据此，可以把计算机系统分成： 单指令流单数据流s i s d ( s i n g l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m ) 单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l e d a t a s t r e a m ) 多指令流单数据流m i s d ( m u l t i p l ei n s t r u c t i o ns t r e a ms i n g l ed a t a s t r e a m ) 多指令流多数据流m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t a s t r e a m ) s i s d 计算机就是传统的单处理器计算机，指令顺序执行，一次只执行一条 指令并且只对一个操作部分分配数据。直到目前，还很少见到m i s d 类型的计 算机。s i m d 型和m i m d 型并行计算机是研究和开发的主流。 ( 1 ) 向量处理s i m d 型计算机 向量处理机是典型的s i m d 并行机。向量机的特点是利用流水线的概念， 把一个计算部件拆成几段，在流水线的每一部分操作一个子功能，通过时间重 叠实现并行加速，其代表机型为c r a y - 1 向量机。s i m d 类型并行机对并行计算 机的发展起到了重要推动作用，但由于微处理芯片技术的发展，单处理器的性 能都非常强大。9 0 年代以后，并行机均朝着m i m d 方向发展。s i m d 类型并行 机基本退出了历史舞台。 ( 2 ) 共享存储m i m d 并行多处理机 共享存储m i m d 并行多处理机将多台处理机通过互连网络共享一个统一的 内存空间，并通过该内存空间来实现处理机之间的协调，如下图2 1 所示。 6 海 - l 半似论 十 h 处n 胜月 m “ 他 的 圃 囹 幽2 1 共旱内存升礼计算机不意图 内存窄问也町以由多个存储器模块构成，在此类并行机巾，何台处理机u j 以执 行相同或不同的指令流，可以直接访问到所有的数据。处理机叫的通信是借助 主存柬实现的。 该系统的优点是并行化的效率较高，相对容易编o ；并行程序。由十处理器 问传送数据经由共享存储器进行，延迟较小。凼此，容易设计出小粒度、负载 平衡、高效的并行程序。其缺点是系统中处理器太多时，对共享内存的竞争会 严重影响效率，可以使用高速缓冲存储( c a c h e ) 和交叉丌戈存储( c r o s s b a rs w i t c h m e m o r y l 等技术，柬减少竞争现象。但这些技术依然有些难以克服的缺点， 如高速缓冲存储技术：系统中每个处理器有一个独立的高速缓冲存储模组， 以减少处理器对共享内存的防问，f r 在共享内存中写入某内存母元，应同时更 改存在各高速缓冲存储中相关单元的内容，称为缓冲存储一致性问韪，虽然己 经有许：多方法解决此问题，但仍无叮避免地对系统性能产牛负面影响。通过l 迷措施u r 以减少竞争，但处理器的数h 一般不能超过1 0 0 个，从们影响此类系 统的发展。 ( 3 ) 分布式存储m i m d 并行多处理器 为了突破共享存储并行机系统中处理嚣与内存系统问的瓶颈，分布存储 m i m d 并行多处理机器系统应运而生。该系统中每台处理机有自己的局部存储 器构成一个竹独的节点，节点之间通过互连m 互相连接。每台处理机只能直 一嗣剥藿堡 f _ _ l i _ i 上海大学硕士学位论文 接访问局部内存，不能访问其它处理机的存储器，它们之间的协调以消息传递 的方式进行，如下图2 2 所示： 图2 。2 分布式内存并行计算机示意图 与共享存储器并行机比较，分布式存储并行机具有很好的可扩展性，可以 最大限度地增加处理机的数量，是目前实现超大规模科学与工程计算的唯一途 径。但由于它的每个节点机需要依赖消息传递来相互通信，而消息传递对编程 者是不透明的，所以，分布存储并行多处理机系统的编程较共享存储复杂。正 是由于具有这种存储结构，就需要有软件上的访问支持，也就要求在进行程序 开发的时候对于这种存储结构给予充分的考虑。 本文中所采用的是m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 作为通信库。现在最为常 用的通信库有m p i 和p v m ( p a r a l l e lv i r t u a lm a c h i n e ) ，而m p i 以其高效性和通 用性在高性能计算( 又称为科学计算) 中得到了广泛的应用。m p i 并不是一种 语言，也不是指某种具体的实现，而是一种与语言和平台无缘的并行标准。自 从1 9 9 3 年m p l l 0 标准出现以来，m p i 得到了快速的发展，目前已经有m p l 2 的标准。m p i 有诸多的实现版本，如m p i c h ，c h i m p ，l a m 。 分布存储m i m d 并行多处理机主要有m p p 系统和c l u s t e r 系统两种形式。 m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r s ) 系统是最常见的并行系统，由成百上千的 上海火学硕士学位论文 功能相同的处理机通过互连网络连接而成，m p p 的优点是拥有良好的伸缩性， 只要为系统增加更多的结点，便能增加系统的计算峰值，现时市场上大部分的 高性能计算机都是m p p ，如i n t e rp a r a g o nx p s ，c r a yt 3 d 、国产y i i 3 和曙光 系列等。但是，m p p 的缺点是较难为其开发并行程序，程序员需要根据系统的 特点来平衡并行程序的粒度和结点间通信量。 计算机集群( c l u s t e r ) 也叫计算机机群，是指把两个以上高性能的工作站或高 档次c p 用互连网连接在一起，并配以相应的支撑软件，构成一个分布式并行 计算机系统，结点间的消息传递和程序执行均是并行化的。具有并行计算性能 而且可以加速作业的执行，这是和一般的网络系统不同的。c l u s t e r 的互连大多 采用通用局部网，如e t h e r n e t ，f d d i ，a t m 等。集群系统包括工作站 n o w ( n e t w o r k o fw o r k s t a t i o n s ) ，p c 机群，全对称s m p 机群等。 2 2 2 并行计算机的应用与发展 作为并行计算的物质基础的计算机硬件在不断的更新。最初是在单处理机 内部增设流水线处理部件、多功能单元、关联存储器等来开发指令级的并行性， 为了进一步提高并行度，必然导致向开发程序级和任务级的并行性多计算机系 统的发展。把多台计算机联合起来，互相配合，各尽其能。利用功能专门化、 多机群和网络化这三种基本技术向着异构型多处理机系统、同构型多处理机系 统和分布式处理系统发展。 1 9 7 2 年在美国诞生了世界上第一台并行计算机i l l i a c n ，其为8 8 = 6 4 的阵列机。但是它的加速比还是满足不了求解超大规模计算问题的要求，因此 9 0 年代，开始研究大规模并行机与网络并行机群。 并行计算机是一种高性能的超级计算机，其运算速度应达到每秒万亿次、 百亿次甚至于更高，以此来解决诸如气象模拟、流体分析、污染分析、人类染 色体、海洋环境以及核试验模拟等一系列的问题。 目前，高性能计算的发展应用可分为以下两大类： ( 1 ) 面向高端用户，追求细粒度、超高速的大规模并行计算机系统，由数百 以至更大多数目的c p u 组成，如以下系统： 9 上海人学硕上学位论文 陈列处理机如d a p 。 向量并行机如c a r y - 1 、国产银河1 等。 s i m d 并行机如t h i n km a c h i n e 公司的c m 2 ，m p i ，m p 2 等。 大规模并行机( m p p ) 如i b m s p 2 、i n t e lp a r a g o n 、c m 5 、国产曙光机等。 这类系统由于其价格昂贵、使用不方便，因此主要面向高端用户，难于普 及，不利于开发这类系统的软件及相关的并行算法。 ( 2 ) 基于网络技术的并行计算环境 此类系统一般由p c 微机通过网络构建而成。一般微机的平均使用率只有 3 0 左右，随着网络技术高速发展，性能在过去几年高速增长。由大量计算机 通过网络组成的虚拟并行计算环境，其能力足以进行高性能计算，其优点为可 伸缩可扩展性强、能利用现有资源组建并行计算环境、价格便宜、系统灵活等。 这类网络并行多计算机系统中，各台计算机具有自己的存贮器地址空间，通过 消息传递( m e s s a g e - p a s s i n g ) 来进行并行计算。典型的实现方式有： 扩充现有的顺序高级语言的语法和保留字来处理消息传递( 如c 、c + + ， f o r t r a n 扩展为并行c 、c + + 、f o r t r a n ) 。 设计专用的并行程序设计语言( 如o c c a m 并行语言) 。 利用现有的顺序高级语言并提供用于消息传递的外部函数库( 如 e x p r e s s 、m p i m e s s a g ep a s s i n gi n t e r f a c e 和p v m - p a r a l l e lv i r t u a l m a c h i n e ) 。 2 3 集群系统 近年来，随着计算机硬件技术的高速发展，处理器和网络的性能不断地迅 速提高和价格的日益下降，使得并行计算日益从传统的超级计算平台转移到由 一组高性能节点或工作站p c 机构成的称之为集群的计算平台上，从而集群成 为构建可扩展并行计算机的一大趋势。 集群( c l u s t e r ) 系统是一种并行或分布式处理系统，它包含多个由互连网络连 接起来的独立计算节点，能够通过集群系统软硬件形成一个统一的计算资源。 在集群系统中，计算节点可以是单处理器系统，也可以是多处理器系统。这些 1 0 上海大学硕士学位论文 计算节点各自带有c p u 、存储器、f o 设备以及独立的操作系统。集群系统的 多个节点通过通用网络或者其它高速网络进行互连，从而向用户和应用提供一 个单系统的映像。 2 3 1 集群系统的特点 集群系统一般都采用成熟的、容易获得的计算机技术和通信技术以及硬件 设备，这也使得集群系统具有价格便宜、扩展性好等特点。 首先，集群系统造价便宜。构造系统所使用的全部硬件均为通用的商品化 产品，造价便宜。构建系统所用的软件，如m p i c h 编程环境、测试工具软件 等，可以从网上免费下载，甚至操作系统也可以使用网上下载免费l i n u x 版本。 其次，集群系统具有很好的可扩展性。可以根据需要方便地向集群中加入 或删除工作节点，可以通过简单的增加新的节点来扩充集群的处理能力或增加 新的功能。 最后，集群系统的每一个节点都是一台独立的计算机，在集群没有任务进 行处理的时候每一个节点都可以单独使用，这样可以大大提高设备的利用率。 2 3 2 集群系统的分类 目前应用最为广泛的计算机集群可以分为三大类：高可用性集群、高性能 计算集群和负载均衡集群。下面对这三种集群做一简单的介绍。 高可用性集群 高可用( h i g ha v a i l a b i l i t y ) 集群，简称h a 集群。目的是在系统出现故障 时，仍能继续对外提供服务。高可用性集群的设计思想就是要最大限度地减少 服务中断时间，这类集群致力于提供高度可靠的服务，是指以减少服务中断( 当 机) 时间为目的的服务器集群技术。 高性能计算集群 高性能计算集群( h i g hp e r f o r m a n c ec o m p u t i n gc l u s t e r ，简称h p cc l u s t e r ) ， 是指以提高科学计算能力为目的计算机集群技术。高性能计算 ( h i g h p e r f o r m a n c ec o m p u t i n g ) 是计算机科学的一个分支，它致力于开发超级 上海大学硕士学位论文 计算机，研究并行算法和开发相关软件，即是采用集群技术来研究高性能计算。 h p cc l u s t e r 是一种并行计算集群的实现方法。并行计算是指将一个应用程序分 割成多块可以并行执行的部分并指定到多个处理器上执行的方法。目前的很多 计算机系统可以支持s m p ( 对称多处理器) 架构并通过进程调度机制进行并行 处理，但是s m p 技术的可扩展性是十分有限的，比如在目前的i n t e l 架构上最 多只可以扩展到8 个c p u 。为了满足某些“计算能力饥渴”的科学计算任务， 并行计算集群的方法被引入到计算机界。著名的“深蓝”计算机就是并行计算 集群的一种具体实现。 负载均衡集群 负载均衡集群技术就是带均衡算法的服务器集群。目的是提供和节点个数 成正比的负载能力。负载均衡集群通过在系统节点间合理分配工作负载来提高 系统的整体性能，如减少系统的平均响应时间等。这类集群很适合提供大访问 量的网络服务。负载均衡集群在多节点之间按照一定的策略( 算法) 分发网络 或计算处理负载。负载均衡建立在现有网络结构之上，它提供了一种廉价有效 的方法来扩展服务器带宽，增加吞吐量，提高数据处理能力，同时又可以避免 单节点故障。 2 3 3 本文使用的集群系统 本文所使用的是上海大学“自强3 0 0 0 超级计算机系统。该高性能计算 平台共有1 9 6 个s m p ( 对称多处理机) 结点，每个结点的配置为i n t e lx e o n 3 0 6 g h z ，2 g 内存，结点之间采用1 0 g b p s 的i n f i n i b a n d 高速通信网进行通信。 其所用的m p i 环境是m p i c h l 2 5 。 “自强3 0 0 0 的l i n p a c k 值1 5 1 1 g f l o p s ，在第2 3 届t o p 5 0 0 居1 2 6 位，在 2 0 0 4 年的中国t o p l 0 0 居第6 位，国内高校为第二位。 2 4 小结 本章介绍了一些并行计算的基础知识，包括并行计算、并行计算机、集群 系统三个方面。首先，简要介绍了什么是并行计算。接着介绍并行计算机，对 1 2 上海大学硕十学位论文 并行计算机按照指令和数据的不同对其进行划分，即f l y n n 分类法是一种经典 的方法，之后介绍了并行计算机的发展。最后介绍了集群系统的特点、分类及 本文所使用的上海大学“自强3 0 0 0 高性能集群机。 1 3 上海大学硕士学位论文 第三章分布树负载均衡模型的研究 3 1 负载均衡 在计算机硬件价格下降、计算机网络拓扑发展的情况下，分布式计算机系 统给用户提供了一个丰富的资源集合。人们在研究分布式系统时，就注意到了 这样一个问题：在一个由网络连接起来的多计算机环境中，在某一时刻，一些 计算机的负载比较重，而另外一些计算机的负载却比较轻。平衡各计算机之间 的负载是任务分配一个主要目标，它能够提高整个系统的性能。 为了改善集群系统的性能，通过在多台计算机之间合理地分配负载，使各 台计算机的负载基本均衡，这种计算能力共享的形式，通常被称为负载平衡。 也就是说，负载均衡是指计算负载在集群中均匀分布，使得集群中的每个计算 结点都做等量的工作。“负载平衡 要达到的目标是使各台计算机之间的负载基 本均衡。当然，平衡各结点的负载需要在计算能力和通信开销之间进行权衡。 均衡负载和处理机间的通信开销是相互冲突的两个因素，它们左右着任务 分配策略，影响着系统的性能。负载均衡可以提高整个系统的吞吐量，因为它 试图将任务尽可能均等地分配给各处理机。但由于处理机间的通信开销又迫使 分配策略不得不尽可能把较多的任务分配给尽可能少的处理机。任务分配策略 就是要设法摆平这两个因素，将任务分配给处理机，使整个系统的性能提至最 高。在任务分配到处理机的过程中，有两种类型的成本任务，即在某个处理机 上的执行成本和处理机之间的通信成本。为了改进分布系统的性能，这两个目 标必须满足即：处理机之间的通信成本要降到最低；在不同处理机上的任务的 执行成本需要平衡，使得处理机之间通信成本和任务的执行时间都不错尽可能 最小化。 3 1 1 负载均衡的分类 负载均衡有许多的分类方法 1 , 1 2 】，但是从整体上说可以分为静态负载均衡和 1 4 上海大学硕士学位论文 动态均衡两大类。 静态负载均衡又称为状态无关均衡，就是根据以往的经验或系统本身信息 集，把外来的任务分配给各个结点，或对某些结点上的任务进行重新分配。静 态负载均衡方法的优点是实现简单，在一定的应用中有其优势，但其效率取决 于系统本身及交互的任务是否有充分的了解，如各任务的执行代价和任务之间 的通讯代价，处理机的性能以及硬件设置等。由于这些先验知识常常是不可能 得到的或不准确的，所以目前常用动态负载均衡方法。 动态负载均衡又称为状态相关平衡，其决策取决于系统当前的状态，也就 是说，系统可以根据当前的负载分布情况，对各个节点上的负载进行动态的调 整，使己分配给超载结点上的任务，通过通讯设备，迁移到轻载的结点上去， 从而达到提高系统的资源利用率，减小任务的平均响应时间的目的。 3 1 2 负载均衡算法的评价标准 为了充分利用高度并行的系统资源，提高整个系统的吞吐率，就需要负载 平衡技术的支持。负载平衡技术的核心就是调度算法，即将各个任务比较均衡 地分布到不同的处理节点并行计算，从而使各节点的利用率达到最大。 针对负载平衡系统的一般评价标准包括： 吞吐率( t h r o u g h p u t ) ：并行系统上运行的应用程序的响应时间或平均完 成时间。这是负载平衡系统最主要的衡量尺度。 可扩展性( s c a l a b i l i t y ) ：系统规模增大或总负载大小变化时系统的适应 能力。 容错性( f a u l t t o l e r a n t ) ：发生处理机故障后任务恢复运行的能力。 3 1 3 负载均衡的主要难点 在集群系统上，负载平衡要解决的问题主要有以下几点： ( 1 ) 系统资源使用不均。在并行计算中常常会出现这样的现象，某个节点 的c p u 处于十分繁忙的状态，而另一些节点却非常空闲。这导致了系统资源 的极大浪费和并行效率的下降。在集群系统中，由于现有的并行编程运行环境 1 5 上海大学硕上学位论文 负载平衡机制通常十分简单，同时各个节点的体系结构和资源状况互不相同， 如何充分利用资源和调度负载就主要成为程序员的责任。但并行程序运行时系 统资源状况在动态改变，程序员很难做出准确的并行任务静态调度。因此，必 须动态监视系统的资源状况，做出准确的分配决策。 ( 2 ) 集群系统是多用户系统，同时可能有几个用户运行各自的作业。这就 要保证前台用户对工作站的优先使用权。而现有并行环境对此考虑不多。在 p v m 中，采用r o u n dr o b i n 任务分配策略，并行任务依次派生到各个节点上， 不管该节点是否被前台用户使用。因此，必须在某前台用户频繁操作时尽量减 少分配给该节点的任务。这样做既能使前台用户不会因后台任务太多而无法忍 受过长的响应时间，又能充分利用空闲节点的资源。 ( 3 ) 负载迁移与通信成本。当系统处于不平衡状态时，必须启动负载平衡 算法来实现系统的负载平衡，这必然要进行负载迁移。而负载迁移的粒度太大， 就会造成不必要的颠簸；如果迁移的粒度太小，还抵不上迁移负载的额外开销， 又不划算。所以在进行负载迁移时必须要考虑负载迁移的代价与通信成本之间 的关系，这样才能提高系统的吞吐量，优化系统。 3 2 分布树的负载均衡模型 树型结构是一类非常重要的非线型数据结构，其是以分支关系定义的层次 结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构 都可以用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中， 用树来表示源程序的语法结构。在许多程序中，我们采用树作为基本的数据结 构，但是当求解问题规模越来越大时，我们考虑如何划分这棵树为并行环境下 的分布树【1 3 1 5 1 ，而且各个处理器的负载相对均衡。当然，还必须满足一个条件 就是，处理器之间的通信也相对较少。 本节主要研究基于分布树的负载均衡模型，即如何将一棵树划分为p 个分 布树，p 个分布树属于p 个处理器( 计算节点) ，使每个分布树的负载量基本相 等，且处理器之间的通信量也要降到最低。分布树的建立是个复杂的问题，有 太多的因素需要考虑，比如树的每层都有多个结点且每个结点负载可能不同； 1 6 上海大学硕士学位论文 有些树的层数比较多；还有些树并不是每个结点都存在，即有一些空结点。在 分布式并行环境下，负载均衡的分布树，可以加快程序的运行，提高程序的并 行效率。负载不均衡的分布树，可能导致程序的执行速度变慢，甚至体现不出 并行算法的优点。 3 2 1 基于最细层的分配模型 最简单的一种分配方案7 8 1 ：将树最细( 底) 层的所有的结点平均分为p ( 处 理器总数) 份分给各个处理器，其中m ( p ) 为分配给处理器p 的结点，而在其上 面各层，则将m ( p ) 的所有父结点及祖先结点都分配给处理器p ，如图3 1 所示。 图中所示为二叉树，在实际应用中可能是r l 叉树，但由于n 叉树的图比较复杂， 所以本文的图都是基于二叉树的。本文中所提到的树的最细层就是树的底层， 图3 1 基于最细层的分配模型 1 7 上海大学硕士学位论文 在图3 1 中也就是由上往下数的第五层。在树结构中，除最细层之外的其它层， 称为粗层，如上图中的第一层到第四层都为粗层。 在树结构中，随着层数的逐渐增加，每一层的结点数也越来越多，并且一 般在最细层，结点数达到一个最大值。例如：满二叉树共有m 层，最细层也就 是第m 层的结点数为2 ”1 ，除最细层外的其它各层结点数之和为2 ”1 1 ，则最 细层结点的个数占树所有结点数的一半左右。同样，具有m 层的满三叉树，最 细层的结点数为3 m 。1 ，除最细层外的其它各层结点数之和为3 ”一以，则最细层 ，厶 结点数占树所有结点数的比例大于二分之一。随着满n 叉树中n 的增大，最细 层的结点数所占树的所有结点数的比例将越来越大。 由于本划分方案是基于最细层的划分，而且最细层上的结点数是树中结点 最多的一层，如果此层的负载均衡良好，那么整棵树的负载均衡也会比较好。 当n 越来越大时，此划分方法的负载均衡效果越来越好。 在前面的介绍中，我们只是笼统地说将树最细层的所有的结点平均分为p 份分给各个处理器。实际上，在最细层的分配上也存在很多方法，随着树最细 层结点数m 和处理器数p 增多时，最细层的划分方法的不同将严重影响树的负 载均衡。 第一种方法：将树中最细层的所有结点个