（计算机应用技术专业论文）离子传输模拟并行计算平台中动态负载均衡模型研究.pdf

硕f 学位论文 摘要 随着信息技术的迅猛发展，越来越多的领域需要在极短的时间内处理大量的 数据。而传统的单机模式往往无能为力，并行计算被认为是解决此类问题的可行 途径之一。其中集群有投资少、易实现、见效快等优点，是并行计算发展的趋势。 本课题源自中科院近代物理研究所强流加速器中空间电荷效应及稳定性的理 论与实验研究项目。本文通过并行集群技术，实现多个计算节点协同完成离子传 输模拟的数值计算任务。本文针对异构集群平台，提出了一种基于负载状态反馈 的动态负载均衡模型。本文主要工作包括： 首先，应用并行设计的p c a m 方法和分治算法对加速器离子传输模拟问题建 立并行求解模型，并通过m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 接口与c 语言完成并行 程序的设计和实现。 其次，提出了一种基于状态反馈的动态负载均衡模型d l b m s f ( d y n a m i cl o a d b a l a n c i n gm o d e lb a s e do ns t a t u sf e e d b a c k ) ，该模型提出用可用资源综合权值作为 作业调度的指标，用改进的加权轮询调度算法一i w r r s 算法( i m p r o v e dw e i g h t e d r o u n d r o b i ns c h e d u l i n g ) 进行作业分配；提出了一种基于负载状态改变触发的作 业迁移算法一t t a l s c 算法( t a s k st r a n s f e ra l g o r i t h mb a s e do nl o a ds t a t u s c h a n g i n g ) ，该算法大大提高了异构集群的并行效率；应用周期心跳检测机制保障 集群系统的稳定性与可靠性。 最后，通过对实验结果分析，验证了通过p c 集群实现并行计算的优越性和有 效性，验证了本文提出的d l b m s f 模型相对于m p i c h 提供的轮转调度具有较高 的负载均衡效率。 关键词：m p i ；集群；并行计算；负载均衡：离子加速器 u 离子传输模拟并行计算甲台中动态负找均衡模型研究 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o ns o c i e t y ，al a r g ea m o u n to fd a t an e e dt o b ep r o c e s s e di nas h o r tt i m e i ti sh a r df o rs i n g l em a c h i n es e r i e sm o d ei nt r a d i t i o n a l w a y ，b u tp a r a l l e lc o m p u t i n gt e c h n o l o g yi so n eo ft h ee f f e c t i v em e t h o d st os o l v es u c h p r o b l e m s c l u s t e ri s ak i n d o fp a r a l l e l c o m p u t i n gt e c h n o l o g y ，w h i c hh a ss o m e a d v a n t a g e s ，s u c ha sl o wi n v e s t m e n t ，e a s yt oi n s t a l l ，q u i c kt og a i ne f f e c t ，e t e b e c a u s e o ft h e s ea d v a n t a g e s ，c l u s t e rw i l lb et h em a s t e ri nt h ep a r a l l e lc o m p u t i n ga r e a t h i st h e s i ss t e m e df r o mt h et h e o r e t i c a la n de x p e r i m e n t a lr e s e a r c hi nt h es p a c e c h a r g ee f f e c ta n dt h es t a b i l i t yo fh i g h c u r r e n ta c c e l e r a t o r s ，w h i c hb e l o n g e dt ot h e i n s t i t u t eo fm o d e r np h y s i c s ，c h i n e s ea c a d e m yo fs c i e n c e s i nt h i s p a p e r , p a r a l l e l c l u s t e rt e c h n o l o g yw a su s e dt oa c c o m p l i s ht h el a r g en u m e r i c a lc a l c u l a t i o no fi o n t r a n s m i s s i o nb yp cc l u s t e rn o d e sw h i c hc o o p e r a t e dw i t he a c ho t h e r w ea l s op r o p o s e d ad y n a m i c ，l o a db a l a n c i n gm o d e lf o rh e t e r o g e n e o u sc l u s t e r , w h i c hw a sb a s e do nt h e f e e d b a c ko ft h el o a ds t a t ec h a n g i n g ，a tt h es a m et i m ei nr e a l i z i n gt h ep a r a l l e lp r o g r a m o fi o nm o t i o ns i m u l a t i o n t h em a i nc o n t r i b u t i o n so ft h i sp a p e rw e r ea sf o l l o w s ： f i r s t l y , c o n s i d e r i n gt h ep r o c e s s e so fi o nt r a n s p o r t ，t h ew r i t e rd e s i g n e dam o d e li n r e s p o n s et ot h es i m u l a t i o np r o b l e mo ft h ei o nt r a n s m i s s i o n ，u s i n gd i v i d e a n d c o n q u e r a l g o r i t h ma n dam e t h o dn a m e dp c a m ( p a r t i t i o n i n g ，c o m m u n i c a t i o n ，a g g l o m e r a t i o n ， m a p p i n g ) f o rd e s i g n i n gp a r a l l e ls o f t w a r e t h ew r i t e rd e s i g n e da n di m p l e m e n t e da p a r a l l e lp r o g r a mb ym p ii n t e r f a c ea n dcp r o g r a m m i n gl a n g u a g ea c c o r d i n gt ot h e m o d e l s e c o n d l y ，t h ew r i t e rp r e s e n t e dad l b m s f ( d y n a m i cl o a db a l a n c i n gm o d e l b a s e do ns t a t u sf e e d b a c k ) m o d e lb a s e do nt h es t a t u sf e e d b a c k ，a n dr e a l i z e dt h em o d e l b yt a k i n ga d v a n t a g eo ft h em p im e s s a g e - p a s s i n gm e c h a n i s m i nt h i sm o d e l ，a n i n t e g r a t e dw e i g h to fa v a i l a b l er e s o u r c ew a st h ei n d i c a t o rf o rt a s kd i s p a t c h i n g ，a n da n i m p r o v e dw e i g h t e dr o u n d - r o b i ns c h e d u l i n ga l g o r i t h mc a l l e di w r r sw e r eu s e df o r t a s kd i s t r i b u t i o n t h em o d e la d o p t e dd y n a m i cl o a db a l a n c i n ga l g o r i t h mt r i g g e r e db y s l a v en o d e sl o a ds t a t u sc h a n g i n g ，w h i c hi m p r o v e dt h ep a r a l l e l e f f i c i e n c yo fc l u s t e r g r e a t l y i no r d e rt og u a r a n t e et h es t a b i l i t ya n dr e l i a b i l i t yo fc l u s t e rs y s t e m s ，t h em o d e l a l s oa d d e dp e r i o d i ch e a r t b e a td e t e c t i o nm e c h a n i s m l a s t l y ，h o wt h er a t i oo fc o m p u t i n gt i m et oc o m m u n i c a t i o nt i m ei m p a c t so n p a r a ll e ls p e e d u pi sa l s ot a l k e da b o ui nt h i s p a p e r t h ew r i t e rc o m b i n e dt h ei o n s i m u l a t i o np a r a l l e lp r o g r a mw i t ht h ed l b m s fm o d e l ，e x p e r i m e n ta l s ot e s t e dt h a tt h e i i i 硕 ：学付论文 d l b m s fc a n b r i n g a g r e a tl o a db a l a n c i n ge f f i c i e n c y ，c o m p a r i n gw i t h t h e r o u n d - r o b i ns c h e d u l i n gp r o v i d e db ym p i c h k e yw o r d s ：m p i ；c l u s t e r ；p a r a l l e lc o m p u t i n g ；l o a db a l a n c e ；i o na c c e l e r a t o r i v 离子传输模拟并行计算平台中动态负载均衡模帮研究 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图3 1 图3 2 图3 - 3 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 l 图5 1 图5 2 图5 3 图5 4 图5 5 插图索引 p c 集群的网络结构：6 p c 集群的体系结构7 p c a m 算法设计过程1 l 两种区域分解策略1 3 求兀近似值示意图1 4 主从模式并行程序设计1 6 对等模式并行程序设计1 6 主从模式m p i 程序的执行过程1 8 加速器串行离子模拟流程图一2 2 问题的并行求解过程2 2 并行算法数据流程图2 4 集中式调度3 0 分布式调度3 0 d l b m s f 模型全局结构3 8 主节点内两模块关系图一3 9 主节点执行流程图4 0 从节点两模块一4 3 从节点资源收集模块流程图一4 4 主从节点作业调度4 5 m p i 消息传递机制4 5 m p i 非阻塞通信4 6 作业列表状态变化图4 8 并行化性能分析图5 6 三种模拟方式计算时间对比一5 9 负载均衡效率6 0 集群正常工作结果输出6 0 节点出错验证结果输出6 l v 硕f 学位论文 附表索引 表4 1 节点初始权值一：一3 3 表4 2 负载状态变化触发作业负载均衡机制一3 6 表5 1 硬件配置表5 4 表5 2 离子数( 1 0 4 ) 圈数( 1 0 0 ) 一5 5 表5 3 离子数( 1 0 4 ) 圈数( 1 0 0 0 ) 。5 6 表5 4 离子数( 1 0 6 ) 圈数( 1 0 0 ) 5 6 表5 5 资源权值定义表5 7 表5 6 作业复制下离子模拟( 离子数( 1 0 6 ) 圈数( 1 0 0 ) ) 5 8 表5 7 作业发送与作业复制时问对比一5 9 i l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：召昂彦。惫日期：加矽年否月厂日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 日期： 日期： 易窍 6 月 日 z - 日 卜 硕f ：学位论文 1 1 研究背景 第1 章绪论 随着信息社会的迅猛发展。越来越多的领域都涉及到要处理海量的数据。从 飞机设计的风洞实验，天气气象预报到能源勘探、医学、军事以及基础理论研究 等领域中都对计算提出了极高的具有挑战性的要求。有一些实验必须要在实验室 进行，例如核武器数值模拟，航空航天高速飞行器的设计，原子物理过程微观世 界的模拟，材料科学中的计算，环境资源以及生物计算等。这些重大的计算问题， 涉及到非规则的复杂结构、非均匀的复合材料、非线性的动力学系统以及奇性区 域、活动边界、带约束条件等各种复杂的数学物理问题。其实验需要的计算平台 没有每秒t f l o p s 级的计算性能是万万不行的【1 1 。在一般的计算机上用传统的计 算方法往往无能为力。 随着计算机和计算方法的飞速发展，几乎所有的学科都走向了定量化和精确 化，逐渐产生了一系列诸如计算物理、计算化学等的计算类科学，从而形成了一 门计算性的学科分支，即计算科学。如今，计算科学己经成为继理论科学及实验 科学之后的第三门科学。通常，对于计算科学中的复杂问题，并且问题本身就具 有并行的自然属性，传统的单机模式往往无能为力，而并行计算则被认为是解决 此类问题的可行途径之一【2 j 。 利用并行计算，具有如下优点： l 、它可以加快速度，即在更短的时间内解决相同的问题或在相i - j 的时间内解 决更多更复杂的问题特别是新出现的挑战问题。 2 、节省投入，并行计算可以以较低的投入完成串行计算的任务。 3 、物理极限的约束，如光速是不可逾越的速度极限设备，设备和材料不可能 做的无限小，通过并行能够很好的提高处理速度，所以说并行技术是实现高性能 计算的核心。 高性能并行计算机是目前能满足大规模计算需求的支撑平台之一，因此，正 是这些重大的应用需求推动了当代并行计算技术的迅速发展【3 】。计算机网络技术 的迅猛发展，以及集群这一体系结构的出现使得高性能计算能力不再只能被少数 几个大公司，大企业拥有，各个实验室都可以根据自身条件利用廉价的p c 和l i n u x 操作系统搭建自己的集群，这样不但可以充分利用每个p c 的计算资源，同时也 能获得很高的计算性能。 在集群技术领域中，核心的难题是通过设计较好的负载均衡系统来提高集群 的高性能性【4 】，使计算资源得到充分的利用。 离了f 输模拟并行计算平台中动态负载均衡模型研究 1 2 课题来源及意义 本该课题来源于中国科学院近代物理研究所重离子加速器h i r f l ( h e a v yi o n r e s e a r c hf a c i l i t yi nl a n z h o u ) ，属于国家大科学工程项目。为了得到高质量的束流， 必须经过严格的束流调试和模拟。其具体物理问题所需要的数值计算，如果用单 个计算机来完成，完成模拟的离子规模小，模拟精度低，耗费时间长。据实验统 计，使用单台p c ( 5 1 2 m 内存，p e n t i u m42 0 gc p u ) 计算1 0 4 个离子，模拟运行1 0 0 圈数所需要的平均时间是2 6 5 0 7 3 0 5 6 秒，随着离子规模的变大和模型圈数的增 多，所需要计算时间会更长，也就是说加速器束流调束人员在对中间参数调整的 过程中，设置好调整电磁元器件的参数之后要等1 0 几分钟的时间等待下一次的器 件设置，工作效率低。用1 0 4 个离子的数量来模拟真实管道内比1 0 1 0 还要多的数 量，其选取的离子代表性较差，造成实际结果本身与理论结果的误差就会很大。 为了帮助研究人员调试的精度和缩短时间，必须使用较多的初始离子参与模拟计 算，并且要设置离子在加速器内部运行的圈数尽可能的多，整个模拟过程所需要 的计算量是巨大，可以说只有高性能计算机器才可以胜任。 通过高性能集群计算来模拟离子在加速器中的传输，以此来提高工程的进度 和效率。由于简单的并行程序开发平台提供的都是单一的负载均衡机制，作业调 度算法简单，在异构集群下容易造成负载失衡、并行效率低等弊端，不能够满足 具体应用的需求，在并行集群计算领域，核心的问题在于负载均衡和对重载节点 作业的荐分配【5 】。所以本文根据具体的工程需要，在实现并行程序编写的同时， 结合并行开发平台提出了一种基于异构集群的一种基于从节点负载状态反馈的动 态负载均衡模型。 该课题是一个计算机当前研究的热点领域( 高性能p c 集群并行计算) 在具体 物理问题( 重离子加速器离子运动模拟) 中的应用。具有很高的理论和实际意义。 该解决方案是以集群系统为平台，结合目前并行编程标准接口m p i ( m e s s a g e p r o c e s si n t e r f a c e ) ，应用分而治之并行化算法实现模拟程序的并行化，同时由于一 般的集群系统要么没有提供负载均衡机制，要么提供的机制都很简单，例如轮转 调度，最小链接调度等算法实现的负载均衡。作者在该并行程序中加入了本文提 出的一种针对于异构集群的负载均衡模型，该模型有效地进行作业调度和作业迁 移，弥补异构性带来的系统整体系统差异，达到计算资源的充分利用，进而缩短 整体作业的模拟计算时间，该模型还具有好很的容错性和高扩展性。 课题的实现具有f 艮强的实际意义： ( 1 ) 我国并行技术在粒子加速器应用方面所开展的研究还较少，尽管很多部 门和单位已有不少联网的计算机资源，如工作站、p c 机、服务器和各种并行机等， 但通常这些用户单位都不知道如何应用这些闲置资源从事并行计算及开展并行应 2 硕十学位论文 用。通过目前的计算机网络技术以及基于b e o w u l f 的集群架构，每个科研机构都 可以根据自身条件利用廉价的p c 和l i n u x 操作系统搭建自己的集群，本文通过 构建基于w i n d o w s 的p c 集群来实现多个计算节点协同完成离子传输模拟的数值 计算任务。该课题的实现可以很大程度上给其他科学计算领域应用高性能p c 集 群完成计算任务，做一个很好的参考。 ( 2 ) 该课题是根据研究所内部已有资源，通过合理的拓扑结构来构建高性能 的p c 集群；根据具体离子数目的多少和矩阵相乘规模大小设计并行算法：针对 异构集群的节点性能差异，解决集群作业调度、作业迁移问题。可以从具体的实 际问题中提出适合解决相似问题的模型，开拓高性能集群计算在其他领域有的应 用。 ( 3 ) 该项目的成功，可以在很大程度上缩短模拟时间，提高束流测束专家调 束的效率，对整个兰州重离子加速器工程成功进入应用阶段起到关键作用。例如 通过精确控制束流的流强和方向、位置来提高重离子实验环境的准确度，对重离 子在治癌，探照生物育种等应用领域提供良好的离子源。整个工程的成功建设将 为我国二十一世纪一二十年代在核物理学科国际前言领域的激烈竞争中继续占有 一席之地提供先进的实验条件。 ( 4 ) 在本文提出的集群负载均衡模型中，提出了服务从节点负载状态改变触 发作业再分配策略，基于可用计算资源综合权值作为负载指标作为调度策略等具 有较高的实用性和创新性。虽然这些算法的提出是偏向于p c 集群在本工程的应 用，但是，p c 集群负载调度本身就很具有研究意义，而这些算法只要按照其思想 对具体的一些条件稍作变化就可以应用于一般集群和其他领域的应用，所以具有 普遍性。 1 3 本文主要工作 作者参与中国科学院近代物理研究所蓬离子加速器离子传输模拟并行程序开 发的相关工作，在w i n d o w s 环境下组建大型的局域网p c 集群，编写离子模拟并 行应用程序，提出了一种基于状态反馈的动态负载均衡模型一d l b m s f 模型，有 效的提高资源利用率和缩短全局作业计算时间，使所组建的面向异构p c 集群的 性能得到提高。本文将对以下具体问题进行讨论和研究，主要包括： ( 1 ) 以并行计算技术为核心，介绍了p c 集群系统的关键技术，分析几种典型 的并行算法设计方法以及对目前应用较多的并行编程模式进行讨论。然后介绍负 载均衡技术的概念与常见的几种负载均衡算法，并对比分析了其优缺点。 ( 2 ) 应用并行算法设计的p c a m ( 划分、通信分析、作业组合和处理器映射) 方法对加速器内离子传输模拟问题进行分析，建力主从关系并行程序模型，用分 而治之作业划分方法对问题按数据进行分割，实现多个集群节点协同完成大型数 3 离子传输模拟并行计算平台中动态负载均衡模型研究 值计算作业。在w i n d o w s 系统下，构建基于m p i 的b e o w u l f 架构的p c 机群，实 例模拟和结果分析验证了通过p c 集群实现并行计算的优越性和有效性，并对计 算时间和通信时间的比值对并行效率和加速比的影响进行了讨论。 ( 3 ) 由于m p i c h 缺乏统一的负载调度系统，应用的是集群系统提供的简单的 轮转负载均衡机制。对异构集群来说，运行作业带来的并行效率差，针对异构集 群，本文提出了一种基于负载状态改变的动态反馈负载均衡模型( d l b m s f ) ，并 利用m p i 的消息传递机制对该模型进行了实现。模型采用本文提出的可用计算资 源综合权值作为负载调度的指标，按照本文提出的改进加权轮选调度算法一 i w r r s 算法进行作业分配；模型采取本文提出的一种基于服务从节点负载状态改 变触发的作业迁移算法一t t a l s c 算法，该算法大大提高了异构集群的并行效率； 模型引入周期心跳检测机制来保障集群系统的稳定可靠性。 以上述工作为基础，作者撰写本文，各章节内容安排如下： 第一章是绪论。主要介绍论文的立题背景，介绍了课题的来源、研究意义。 接着简要叙述了研究内容和作者所完成的工作。 第二章是并行计算和集群系统相关背景知识的介绍。首先介绍了并行计算机 概念和构建p c 集群系统的关键技术，接着介绍了并行算法设计一般过程和基本 原则，最后介绍了并行程序设计相关的分类和基于m p i 的并行编程模型。 第三章是根据兰州重离子加速器离子模拟计算需求，采取主从关系模型，用 分而治之作业划分方法对问题按数据进行分割，根据串行程序的数据流程，实现 了离子传输模拟的并行化。 第四章是基于m p i 的集群系统的负载均衡机制不能满足异构集群的需求，本 文提出了一种基于状态反馈的动态负载均衡模型，并应用c 语言与m p i 消息传递 机制对模型进行了设计与实现。 第五章是在集群系统下进行串并行对比实验；分析了不同计算时间和通信时 间比例的计算作业带来的加速比差异；对加入负载均衡模型之后的并行程序进行 实验，并对模型带来的负载均衡效率进行分析；通过对集群的节点进行关机，检 测集群系统的稳定性和可靠性。 最后是结论，主要对本文所完成的工作和主要创新点进行了总结，并对下一 步的研究工作进行了展望。 4 硕十学传论文 第2 章并行计算与集群系统 所谓并行计算，从学科意义上讲，并行计算实际上包括并行计算的硬件平台 ( 并行计算机) 和并行计算的理论基础( 并行算法) 以及并行计算的软件支撑( 并行程 序设计) 三大部分内容b 1 ，其中并行算法是核心和瓶颈。 2 1 并行计算机 并行计算机即能在同一时间内执行多条指令或处理多个数据的计算机，并行 计算机是并行计算的物理载体。 经过近2 0 年的努力，高性能并行机开发技术有了很大的突破，其中高性能并 行计算机系统模型主要包括以下五种方式【6 】【 。 ( 1 ) 单指令多数据流s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) ：它用一个控制器 来控制多个处理器，同时对一组数据中的每一个分别执行相同的操作来实现空间 上的并行性 ( 2 ) 并行向量处理机p v p 模型( p a r a l l e lv e c t o rp r o c e s s o r ) ；系统中包含少量高 性能专门设计定制的向量处理器，同时使用专门设计的高带宽交叉开关网络进行 连接，主要采用共享存储模块。 ( 3 ) 对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) ：每个处理器可以以同等代 价访问各个共享存储器。优点是并行度很高，但是由于系统总线的带宽是有限的， 故处理器的数目也是受限的。 ( 4 ) 大规模并行处理机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 ) ：每一个节点由微处 理器，分布式存储器及网络接口电路构成；节点间以定制的高速网络互联。 ( 5 ) 工作站或p c 集群( c l u s t e ro f w o r k s t a t i o no rc l u s t e rp e r s o n a lc o m p u t e r ) 。 由于目前工作站和p c 差距越来越小，加上本文研究平台为p c 集群，以下该 类并行机统称为p c 集群。 前四类由于受系统结构的限制或研制费用及成本较高等诸多因素，其市场受 到一定的限制，近些年不如p c 发展迅速。目前基于b e o w u l f 架构的p c 集群价格 低廉，有着很好的异构性和可扩展性，是并行计算机未来发展的趋势。 2 2 集群 p c 集群系统是指将多台p c 机通过高速通讯网络把高性能工作站或高档p c 机连接起相互连接起来，配备一定的并行支撑软件8 1 ；形成一个松耦合的网络并 行计算环境，协同地并行求解同一问题。可以利用本局域网内的p c 机资源，在 5 离子传输模拟并行计算甲台中动态负载均衡模犁研究 用户普遍使用的w i n d o w s ，l i n u x 各个版本的系统平台上，动态地构造并行虚拟 机，其能提供几百亿或几千亿次的计算性能，完全可以满足一般科研计算需要。 p c 集群的网络拓扑结构参见图2 1 。 n 图2 1p c 集群的网络结构 p c 集群系统具有以下优点： 1 ) 投资风险小：集群系统不存在资金浪费问题，在一个局域网或者单位的 i n t r a n e t 中，机器在大部分时间都处于低利用率的状态据b e r k e l e y 实验显示， 每天即使在下午最忙的时间，也有6 0 的工作站处于空闲可利用状态，可以利 用空闲时间来进行需要的计算【9 】【l0 1 。 2 ) 易于编程开发：用户不需要学习新的并行程序设计语言，只要利用所提供 的并行程序设计环境加入并行库接口，就可使程序并行运行在集群上。 3 ) 系统结构灵活：用户将不同性能的p c 机用不同的体系结构和各种互联网 络构成同构或异构的p c 集群系统，从而弥补单一体系结构应用面狭窄的弱点。 4 ) 性能价格比高：p c 集群系统可以用少量资金实现部分大型并行计算机的 计算性能。能充分利用分散的计算资源，p c 集群可以给空闲的p c 机加载并行计 算作业，从而p c 计算资源得以充分利用。 5 ) 可扩展性好：用户可以根据需要增加集群中节点数量，进而提高集群的计 算能力。 p c 集群由于具有以上等突出优点，从众多并行机系统模型中种脱颖而出。目 前己成为高性能并行计算的主流，在中小企业、大专院校和要求不是太高的科研 6 硕十学位论文 机构在经济方面完全有能力支付的起，系统计算性能完全可以满足需要，受到普 遍欢迎。p c 集群在未来的科学计算领域将起到越来越重要的作用1 1 1 1 。 按照p c 并行集群的工作环境和工作方式分析，它是多计算机多进程并行工作 的，所以属于m p m d 结构。然而在并行计算进程中，必然有部分进程必须等待某 些进程的中问结果，进程才能往下继续执行，这种结构属于s p m d i l2 。，即同时多 路的并行运算进程及不同时的多路并行进程的多种的数据运算互相混合运算体 制。对b e o w u l f 的结构研究表明，s p m d 的以太网交换机互联集群是最适合我国 国情的建造方式【l 】，p c 集群系统的体系结构如图2 2 所示。 串行应用 集群中日j 件( 单一系统映像和可崩性基础) 并行应用 并行编程环境 p c j 二作环境p c j = 作环境llp c 工作环境lp c 工作环境 普通软件 网络硬件 普通软件 网络硬件 普通软件 网络硬件 普通软件 网络硬件 高速网络 图2 2p c 集群的体系结构 2 2 1 集群系统的关键技术 构造和使用集群系统的关键技术主要有以下四个川【1 3 】： ( 1 ) 高可用性支持 可用性是指如何充分地利用集群中的冗余资源，使系统在尽可能长的时间内 为用户服务。集群系统通过大量冗余的处理器、存储器、磁盘、i o 设备、网络 及操作系统映象等，提供了有效的高可用性。对于集群系统来说，由于整个系统 由多个节点构成，因此整个系统中出现硬件故障的概率要比单个节点构成的系统 要高，为了进一步挖掘这些多余资源的潜力，需要使用一些可用性技术。 ( 2 ) 单一系统映象 如果一群互联的计算机被设计成看起来好像统一的资源，我们就说他实现了 单一系统映像s s i ( s i n g l es y s t e mi m a g e ) ，一组由快速网络连接起来的工作站或p c 机不一定就是一个集群，一个集群应该是一个单一映像的系统，它表现为一个单 一的系统。 ( 3 ) 负载均衡 7 离子传输模拟并行计算平台中动态负载均衡模型研究 从集群系统的定义我们知道集群系统是多台完整的计算节点通过网络互连而 构成的一个系统，它之所以可以提供强大的数据计算和数据处理的能力，在于它 拥有足够多的处理器以及存储单元。我们要充分发挥集群系统的能力，就需要充 分利用集群系统中的资源。然而当系统中的作业数目比较多，或者单个作业比较 复杂的时候，各个节点上的负载就会出现不均衡的现象，系统的利用率就会大大 下降。因此如何充分的利用集群系统中的资源，也是高性能集群系统设计中的一 个重要问题。在考虑了传统的并行计算环境缺少强大的负载均衡系统下，本文对 此做了重点研究。 一个好的负载均衡系统可以在保证对正在运行的作业产生最小影响的条件 下，动态地对集群进行重新配置。负载均衡系统主要包括： ( 1 ) 用户服务器 该服务器允许用户向一个或多个队列提交作业，指出每个作业的资源需求， 从队列中删除一个作业，询问一个作业或一个队列的状态信息。它可以驻留在每 个主机节点上。 ( 2 ) 作业调度器 该调度器根据作业类型、资源需求、资源可用性以及调度策略来执行作业调 度和排队。 ( 3 ) 资源管理器 监视和分配资源，执行调度策略，并收集记账信息。 ( 4 ) 并行文件系统 集群上的许多并行应用要处理大量数据，需进行大量的i o 操作，这些海量数 据存放在单节点上很困难，而数据又必须快速的存取，为了集群获得高性能，就 必须要有一个高性能的并行文件系统支持。 ( 5 ) 高效通信 如果网络通信延迟很长，再加上用于通信的开销就可能很大程度地限制集群 技术对某些问题的适应性。随着网络技术迅速发展，有很多高速通信技术为集群 技术提供了通信支持，比如高速以太网技术、a t m 技术和m y r i n e t 等等。拥有高 速处理能力和高带宽的网络交换设备在p c 集群系统网络通信中使用，对解决通 信瓶颈问题很有益处。 2 2 2 集群系统的研究现状 群系统以其规模可伸缩性和可编程性以及相对低的价格；使得国内外的许多 大学、研究机构和商业公司竞相投入对它的研究、开发与应用。 ( 1 ) 国外集群并行系统的研究现状 早在19 9 4 年，第一个p c 集群就诞生于美国n a s a 戈达德空间飞行中心。n a s a 8 硕i 。学位论文 用一种廉价的方案，解决地球和太空科学领域里有关计算的一些非常棘手的问题。 该系统总共用1 6 个p c 组成，每个p c 包含有一个i n t e l 4 8 6 处理器，使用的操作 系统是l i n u x ，连接设备也是普通的网卡。这个p c 集群达到7 0m f l o p s 的运算 能力，这种计算系统被称为b e o w u l f ，其具有投资费用不多，又能实现原来只能 在中型机和大型机上才能够进行的大型计算的优点，从而在某些情况下取代一部 分大型并行机【1 4 】。目前，这种构建方案组成的计算系统己成为高性能集群计算领 域研究的一个重点方向。从此，集群计算( c l u s t e rc o m p u t i n g ) 概念被广为关注，集 群技术成为一个新的研究热点。 直至2 0 0 7 年，美国的蓝色基因集群系统通过升级，仍然占据t o p s 0 0 排名第 一的的位置，其l i n k p a c k 性能为4 7 8 2 t f l o p s ，是2 0 0 6 年2 8 0 6 t f l o p s 的1 8 0 倍。 随着对机群系统研究工作的开展，国外许多大学和实验室都建立了实验集群 系统，并进行了许多应用测试，结果表明大量的并行应用程序都能在集群系统上 获得很好的效率。据统计，美国l i v e m o r e 国家实验室的9 0 的应用问题都能在集 群上解决。目前，国外己经推出多种商品化的集群系统。2 0 0 1 年i b m 在美国表 示将为美国国家超级计算应用中心制作两套i b ml i n u x 集群计算机系统，它每秒 钟可执行2 万亿次浮点运算。在h p c ( h i g hp e r f o m a n c ec o m p u t i n g ) 领域，软件帝 国的巨头m i c r o s o f t 也加入进来，自从n t 开始就已经开始涉足集群。2 0 0 8 年 w i n d o w ss e r v e r2 0 0 8 的正是发布，通过集成v i s u a ls t u d i o2 0 0 8 迅速实现h p c 应 用部署，提供综合性平行编程环境。 ( 2 ) 国内集群系统的研究现状 在我国，对并行计算机的研究主要集中在m p p 体系结构的高性能并行计算机 系统，推出了许多实用化的科研成果，比较有名的产品有：曙光系列超级服务器、 神威超级计算机、银河巨型机等。 联想公司在1 9 9 9 年9 月推出了用于分布式高性能计算的n s l 0 0 0 0 高性能集群 服务器，该系统是个四节点的系统，主要基于联想万全4 5 0 0 r 服务器，以总体 成本相对较低的设备组合，足以替代传统r i s c 小型机和中型机的工作。 中国自主开发研制的集群式高性能计算机集群系统“自强2 0 0 0 一s u h p c s ”于 2 0 0 0 年9 月在上海大学问世。这一系统的峰值速度达到每秒3 0 0 0 亿次浮点操作。 直至目前，曙光5 0 0 0 高性能计算机是国家8 6 3 计划高性能计算机及其核心软 件重大专项支持的研究项目，是面向网格的高性能计算机，同时也是面向信息服 务的超级服务器，可以提供多目标的系统服务。曙光5 0 0 0 a 的第一套超大型系统 于2 0 0 8 年1 1 月份落户“上海超级计算中心 ，该系统的计算节点机采用四路四核 a m db a r c e l o n a ( 主频2 0 g h z ) 处理器，每个节点6 4 g b 内存，整个系统由1 6 5 0 个 节点组成庞大集群，共有6 0 0 0 颗c p u 与1 0 0 t 海量内存，其理论浮点峰值为每 秒2 3 0 万亿次，采用2 0 g b ，延迟小于1 3 u s 的i n f i n i b a n d 高速网络进行互联，采 9 离子传输模拟并行计算甲台中动态负载均衡模犁研究 用了w c c s + s u s el i n u x 双操作系统 我国的并行和分布计算技术研究，在大型机研制方面缺少竞争力，在高性能 计算领域，尤其是p c 集群技术给我们提供了一个与国外赶齐的机会，对于集群 系统而言，主要是一些大学和科研机构在进行研究和应用，研究的目的主要是为 本部门提供一个性能较好的并行计算环境，或者是为了开发相关并行软件【3 】。 2 3 并行算法 2 3 1 并行算法设计基本原则 并行算法是适合在并行机上实现的算法，一个好的并行算法应该具备充分发 挥并行机潜在性能的能力。并行计算机的出现来源于实际应用程序中存在的内在 并行度这一基本事实，因此，应用问题中是否存在可挖掘的并行度是并行计算机 应用的关键，而并行算法作为应用程序开发的基础，在并行计算机应用中具有举 足轻重的地位。 并行算法是并行计算的基础，与实现技术相结合，为高效率使用并行计算机 提供决方案。其基本原则简述如下【1 5 】【1 6 1 ： ( 1 ) 与体系结构相结合。 ( 2 ) 具有可扩展性。并行算法是否是随处理机个数增加而能够线性或近似线性 的加速，这是评价一个并行算法是否有效的重要标志之一。 ( 3 ) 粗粒度。通常情况下，粒度越大越好。因为在每个处理机中有很多需要计 算的工作作业，大粒度可以充分发挥多处理机的作用。并行加速比对细粒度问题 一般情况下是不会很高的，这也是为什么应用并行计算完成求解大规模问题的原 因所在。 ( 4 ) 减少通信。一个高效率的并行算法，通信是至关重要的。提高性能的关键 是减少通信量和通信次数，其中通信次数通常情况下是决定因素。设法加大计算 时间相对于通信时间的比重，减少通信次数甚至以计算换通信，这是因为对于集 群系统一次通信的开销要远远大于一次计算的开销，因此要尽可能降低通信的次 数，如果能够实现计算和通信的重叠，那将会更大地提高整个程序的执行效纠。 ( 5 ) 优化性