（计算机软件与理论专业论文）pvm环境下动态负载平衡策略的研究.pdf

摘要 摘要 科技的发展对计算能力提出了更高更新的要求，传统的高性能计算机在性价 比上、对程序员的要求上以及适应性上很难满足各行各业、各个层次的需求。随 着网络技术的迅速发展以及p c 机、小型机、工作站的普及，网络并行系统应运 而生，由多台计算机所组成的网络并行计算环境，其运算能力甚至可以超越一台 高性能计算机。 网络并行系统是由专用或通用网络上一组互联的计算单元及相关资源组成， 可被用户视为单一的计算环境来使用。网络并行系统以其相对低廉的价格、较短 的开发周期、小的用户投资风险、节约系统资源、良好的系统扩展性以及单一系 统映象等优势吸引着众多的研究人员。 其出现以来，许多院校和科研单位都投入大量的人力和物力进行网络并行计 算的研究工作，作为并行系统关键技术之一的负载平衡技术也吸引着越来越多科 研人员的关注，国内的吉林大学和清华大学在负载平衡的研究方面取得了很多成 果。负载平衡机制分为静态负载平衡机制及动态负载平衡机制，其中静态负载平 衡方法应用的比较广的是二次均分法，有关动态负载平衡技术的研究在不断深 入。 本文提出一个基于模拟退火法进行预测的接收者启动的c a 适应动态负载平 衡策略，借助于并行计算平台p 、m ( p a r a l l e lv i r t u a lm a c h i n e ，并行虚拟机) ， 在v c 下编写并行程序。课题具体的研究内容如下： ( 1 ) 查找和分析国内外研究人员所提出的负载平衡机制的优缺点以及适用范 围： ( 2 ) 网络并行计算环境的构建，深入研究p v m 对负载平衡的支持； ( 3 ) 提出一个综合负载指数，衡量各结点机负载，采用神经网络技术进行负 载信息的预测； ( 4 ) 设计一个基于p v m 的支持异构环境的动态负载平衡系统，主要采用自适 应和接收者启动相结合的方法； ( 5 ) 负载平衡系统的性能测试：以求解线性方程组为例，分别在无负载平衡 广东丁业大学工学硕七学位论文 系统以及有负载平衡系统的环境下进行测试。 关键宇：并行计算；动态负载平衡系统；模拟退火法；神经网络 i i a b s t r a c t w i t ht h ep r o g r e s so fs c i e n c ea n dt e c h n o l o g y 。p e o p l eb r i n g sf o r w a r d h i g h e rr e q u e s t st oc o m p u t i n ga b i l i t y t h et r a d i t i o n a lh i g hp e r f o r m a n c e c o m p u t e rc o u l d n ts a t i s f yt h er e q u i r e m e n to fe v e r yw a l ko f1 i f ea n d e v e r yh i e r a r c h yi np r i c ep e r f o r m a n c er a t i o ，a p p l i c a b i l i t ya n dt h e r e q u i r e m e n tt op r o g r a m m e r n e t w o r kp a r a l l e ls y s t e ma p p e a r e dw i t ht h e r a p i dp r o g r e s so f n e t w o r kt e c h n o l o g y ，t h ep o p u l a r i z a t i o no f p e r s o n a l c o m p u t e r ，m i n ia n dw o r k s t a t i o n t h ec o m p u t i n ga b i l i t yo ft h en e t w o r k p a r a l l e lc o m p u t i n gc i r c u m s t a n c ec o m b i n e db ym u l t i c o m p u t e r sm a y b e e x c e e d so n eh i g hp e r f o r m a n c ec o m p u t e r n e t w o r kp a r a l l e ls y s t e mc a nb eu s e da so n es i n g l e c o m p u t i n g c i r c u m s t a n c e ，i t i sm a d eu po fas e to fi n t e r l i n k e dc o m p u t i n gu n i t sa n d c o r r e l a t i v er e s o u r c e so nt h es p e c i a lo rt h eu n i v e r s a ln e t w o r k d e p e n d i n g o ni t sl o wp r i c e ，s h o r td e v e l o p i n gp e r i o d ，s m a l li n v e s t m e n tr i s k ， r e d u c e ds y s t e mr e s o u r c e s ，g o o ds y s t e me x p a n s i b i l i t ya n ds i n g l es y s t e m i m a g e ，m o r ea n dm o r er e s e a r c h e r sj o i nt h er e s e a r c ho fn e t w o r kp a r a l l e l s y s t e m m a n y a c a d e m i e sa n ds c i e n t i f i cr e s e a r c hd e p a r t m e n t si n v e s tm u c h m a n p o w e ra n dm a t e r i a lr e s o u r c e si nt h er e s e a r c hw o r k so fn e t w o r kp a r a l l e l c o m p u t i n gs i n c ei t sa p p e a r a n c e a so n eo fi t sk e yt e c h n o l o g i e s ，l o a d b a l a n c i n gt e c h n o l o g yh a sg o tm o r er e s e a r c h e r s sa t t e n t i o n ， j i l i n u n i v e r s i t ya n dt s i n g h u au n i v e r s i t yh a dg o tm a n yf r u i t s l 0 a db a l a n c i n g s t r a t e g i e si n c l u d es t a t i ca n dd y n a m i cl o a db a l a n c i n gs t r a t e g i e s ，t h e a l l p e r v a d i n gm e t h o du s e di ns t a t i cl o a db a l a n c i n gi sd i c h o t o m y ，t h e r e s e a r c hs t i l ls h o u l db ed e e p e n e df o rd y n a m i cl o a db a l a n c i n g t h i sp a p e rp u t sf o r w a r do n ek i n do f s e l f - a d a p t i v ed y n a m i cl o a d b a l a n c i n gs t r a t e g i e s s t a r t e db yr e c e i v e ra n d t h el o a di n f o r m a t i o n i i i 厂东r 业大学t 学硕七学位论文 p r e d i c t i o nm e t h o d o ft h i ss t r a t e g i e si sb a s e do ns i m u l a t e da n n e a l i n g a l g o r i t h m w ew i l lw r i t ep a r a l l e lp r o g r a m si nv cd e p e n d i n go np v m t h e d e t a il e dr e s e a r c hc o n t e n t sa r eb e l o w ： ( 1 ) f i n d i n ga n da n a l y z i n gt h em e r i t sa n df a u l t so ft h ee x i s t i n gl o a d b a l a n c i n gs t r a t e g i e s ，d i s c u s s i n gt h e i ra p p l i c a t i o na r e a ； ( 2 ) t h eb u i i d i n go fn e t w o r kp a r a l l e lc o m p u t i n ge n v i r o n m e n ta n dk n o w i n g t h es u p p o r to fp v mt ol o a db a l a n c i n gd e e p l y ； ( 3 ) p u tf o r w a r do n ei n t e g r a t e dl o a di n d e xt om e a s u r et h el o a do fe v e r y p ca n dp r e d i c t i o nt h el o a di n f o r m a t i o nb y a p p l y i n gn e u r a ln e t w o r k s t e c h n o l o g y ； ( 4 ) d e s i g n i n go n ed l b ss u p p o r t i n gh e t e r o g e n e o u s e n v i r o n m e n tb a s e d o np v m ，a d o p t i n gt h ec o m b i n e dm e t h o d o fs e l f - a d a p t i v ea n dr e c e i v e r s t a r t e d ； ( 5 ) s y s t e mp e r f o r m a n c et e s ti nt w od i f f e r e n tt e s tc i r c u m s t a n c e s k e yw o r d s ：p a r a l l e lc o m p u t i n g ；d y n a m i cl o a db a l a n c i n gs y s t e m ( d l b s ) ： s i m u l a t e da n n e a l i n ga l g o r i t h m ；n e u r a ln e t w o r k 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的既明，并表示 了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 论文作者签字： 2 0 0 7 年j 月可日 第一章绪论 1 1 研究背景 第一章绪论 1 1 1 研究背景 随着计算机技术的发展，其应用领域也越来越广泛。尽管硬件技术 不断发展。但在诸多高级应用领域内，c p u 处理速度仍不能满足高性能 计算的要求。传统的高性能计算机在性价比上、对程序员的要求上以及 适应性上很难满足各行各业、各个层次的需求。许多领域，如气象、能 源、军事、医学、人工智能及一些基础研究等。都需要快速而有效的并 行计算机来实现大规模的科学计算和数据处理，对并行处理的需求极大 地促进了并行技术的发展“，。随着p c 机、小型机、工作站的普及以及网 络技术的发展，网络并行系统应运而生，其运行能力甚至可以超越一台 高性能计算机。 网络并行系统是由专用或通用网络上一组互连的计算单元及相关资 源组成，可被用户视为单一的计算环境来使用。网络并行系统以低价格、 短的开发周期、用户投资风险小、节约系统资源、良好的系统扩展性以 及单一系统映象等优势吸引着众多的研究人员。 p v m 是并行虚拟机( p a r a l l e lv i r t u a lm a c h i n e ) 的简称，最早起始 于1 9 8 9 年，目前己发展到3 4 7 版。p v m 允许用户在联网的异构计算机 上开发和运行p v m 并行程序，可以将整个网络中的异构计算机虚拟成一 台大型并行机来使用，是一种公共的并行程序开发环境，支持的程序设 计语言包括c 、c + + 和f o r t r a n ，使得大型计算在花费较少的情况下得以 实现。p v b i 是一个免费软件包，它提供开放的源代码，可以在u n i x 和 w i n d o w s 操作系统上编译，可移植性好，应用范围非常广泛。p v m 作为消 息传递分布、并行编程的事实标准，已被广泛移植到多种平台( u n i x 类、 w i n d o w s ) 、多种网络和多种体系结构( i n t e lp c 、s m p 、m p p 和p v p ) 上 在技术上。p v m 正在向面向对象方砸发展，并进一步向m p i 方向变化 p v m 的另一个主要发展方向是能够进行动态负载均衡的d p v m ，它的主要 广东工业大学t 学硕士学位论文 特征是p v m 任务可以透明的迁移。 网络并行系统出现至今，许多院校和科研单位都投入大量的人力和 物力进行网络并行计算的研究工作。作为并行系统的关键技术之一的负 载平衡技术也得到了许多科研人员的关注，国内的著名高校吉林大学和 清华大学在这方面的研究有了很大的进展，提出了一些有效的负载平衡 方法。负载平衡机制分为静态负载平衡机制和动态负载平衡机制，其中 静态负载平衡方法应用的比较广的是二次均分法，动态负载平衡技术并 没有许多实际应用，有待于进一步研究。 国防科技大学的肖侬对基于网络并行计算环境的动态负载分配算法 做了研究，他对稳定的发送者启动自适应算法进行了分析和改进。文献 2 提出了接收者驱动方法的动态负载平衡系统设计( r i l b s ) ，r i l b s 克 服了周期性查询在负载较重的情况下可能带来的系统瓶颈以及负载保持 稳定情况下的不必要的浪费，设计了用全局调度和局部调度相结合的方 法来取代周期性的负载查询。全局调度是当服务器接收到一组任务时立 即开始的调度，而局部调度是作为由忙变闲的接收方主动发起的调度， 即接收者驱动方法的调度。文献 3 提出了进程迁移支持下的动态抢先式 负载平衡实现机制。该机制综合考虑了c p u 利用率，内存和队列长度对 进程迁移的影响，负载指标能够全面地反映出系统的负载情况，信息收 集方式采用集中式，控制方式采用集中式和分布式协商机制进行负载平 衡激发和控制执行。华中科技大学的张建中博士等人也进行了这方面的 研究，他提出了一种l i n u x 下的具有动态负载平衡功能的改进的p v m ”1 。 对于并行系统中负载平衡的研究很多，但是真正适用于异构环境以 及w i n d o w s 操作系统的策略很少，本课题旨在研究基于w i n d o w s 的w p v m 异构网络并行环境下的动态负载平衡，以期获得更好的效率。 1 1 2 研究意义 有人说，并行处理机是计算机设计的未来。科技的发展，网络的普 及，高性能计算的需求对计算环境提出了新的要求，网络并行计算环境 以其较高的性价比，对开发人员的低要求，良好的扩展性等优势赢得更 加广泛的关注。负载平衡技术是提高并行加速比和运行效率的网络并行 2 第一章绪论 计算环境中的一项关键技术。本文提出基于模拟退火法进行预测的接收 者启动的自适应动态负载平衡策略，该策略的应用，对于提高p v m 并行 计算效率会取得比较好的效果。 1 2 负载平衡研究现状 文献 5 提出的动态负载平衡分配算法是对稳定的发送者启动自适 应算法的改进。他所提出的分配算法具有以下特点：具有分布特性，算 法采用分散分配方式；采用负载共享，重负载的结点机可以将新任务转 移到轻负载的结点机上；具有稳定性，探询次数和任务转移次数均有上 限，以防止系统崩溃，采用非抢先式方式转移任务，只转移新产生的任 务，不转移已执行任务。 文献 6 提出了一种同构系统的动态迁移协议，独立于网络结构。在 这篇目文章中提出了投标算法和征募算法的概念。投标算法与征募算法 与发送者驱动算法和接收者驱动算法的概念是相同的。 也有人提出了进程迁移支持下的动态抢先式负载平衡实现机制。信 息收集方式采用集中式，控制方式采用集中式和分布式协商机制进行负 载平衡激发和控制执行。具体方法是：可设定或通过选举产生一个主机， 主机上守护进程c o l l e c t e d 负责收集各主机实时信息。各处理机守护进 程负责收集本地负载信息，周期性送c o l l e c t e d 。控制方式采用集中式 和分布式结合的方式，既可以由m a s t e r e d 激发负载平衡，也可以由各处 理机守护进程p n d 激发，m a s t e r d 从c o l l e c t e d 中获得各处理机信息， 包括各处理机状态和工作负载等。由m a s t e r d 根据定位策略和当前信息 负载目标p m 的定位，和p n d 协商进行任务迁移，更新系统信息表，重复 这个过程直到系统负载基本平衡”- 。 文献 7 提出基于预测的动态负载均衡算法包括两部分：预测算法和 调度算法。预测算法采用线性时间模型进行预测。调度算法采用的是改 进的接收者驱动策略：设定l m i l 3 及l m a x ，当l p = l m a x 时，启动发送者处理过程。 文献 2 所提出的集中控制与接收者驱动相结合的方法，该方法避免 了周期性的负载信息查询，从而减少了通信开销，使系统获得较理想并 广东t 业大学工学硕l ：学位论文 行性能。 一个有效的动态负载平衡方法这篇文章中提出的算法解决了以 下问题：通过减少移动负载次数而减少了额外开销；采用益处估计，根 据益处估计结果来决定是否进行负载平衡：通过将最重载任务和最轻载 任务重新分配负载来解决移动负载的粒度问题“1 。 一种基于多种资源的负载平衡算法的设计与模拟的文章中所提 出的负载平衡算法有效的解决了陈旧信息问题，所采用的方法是改进的 k 子集算法“，。 文献 4 提出了通过b p 神经网络进行负载信息预测的动态负载平衡 的设计，这是将神经网络技术应用到异构系统中进行负载信息预测的一 次重要突破。 1 3 本文的主要工作 1 3 1 研究目标 本课题研究的主要目标是提出一种p v m 环境下的动态负载平衡策 略。该策略适用予局域网下的异构环境，用户定位为并行计算的歼发人 员，通过采用该策略所实现的并行计算模型进行程序开发可以获得较高 的加速比和运行效率。 1 3 2 研究内容 为了实现预定的研究目标，本课题具体的研究内容如下： i 查找和分析国内外研究人员所提出的负载平衡机制的优缺点以及 适用范围； 2 网络并行计算环境的构建：在异构的p c 机群上，基于p v m 搭建网 络并行计算平台； 3 深入研究p v m 对负载平衡的支持； 4 提出一个综合负载指数，衡量各结点机负载； 5 采用神经网络技术进行负载信息的预测： 6 设计一个基于p v m 的支持异构环境的动态负载平衡系统，主要采 用自适应和接收者启动相结合的方法； 4 第一章结论 7 负载平衡系统的性能测试：以线性方程组为例，分别在无负载平 衡系统以及有负载平衡系统( 分丽治之的并行思想) 的环境下进行测试， 运行结果进行比较。 1 4 本文的结构 本文对w i n d o w s 平台下动态负载平衡策略作了全面的研究和分析， 在此基础上完成p v m 环境下动态负载平衡策略的设计。论文结构如下： 第一章，绪论。本章首先介绍了课题的研究背景以及所研究课题的 国内外发展现状，从而引出本文的主要工作。 第二章，相关技术。介绍本论文所用到的相关技术，网络并行计算， 并行虚拟机( p v m ) ，动态负载平衡技术及模拟退火算法。 第三章，几种典型的负载平衡方法分析比较。对目前比较成熟的动 态负载平衡策略进行详细的分析。 第四章，动态负载平衡系统的设计。介绍了本课题的实验环境，研 究方案及动态负载平衡系统的设计。 第五章，g a u s s j o r d a n 消元法的并行实现。给出了g a u s s j o r d a n 消元法的串、并行算法，并对结果进行分析。 最后是总结。 ， 广东工业大学t 学硕一f ：学位论文 第二章相关技术 2 。1 并行计算与消息传递的并行计算平台 2 1 1 并行计算 1 并行计算 通常网络并行处理系统是利用高速e t h e r n e t 网将多台计算机连起 来，利用并行软件构成处理平台来实现。由于各工作站自j 没有共享内存， 各处理机之间通过消息传递机制来实现进程和数据通讯，各个处理机可 以执行不同进程。因此，网络并行处理系统可归属于分布式存储m i m d 类的开发环境并行处理系统，基于消息传递的并行处理平台是网络并行 程序开发和运行的基础1 。 作为并行计算物质基础的计算机硬件在不断的更新换代。并行性从 指令级向程序级、任务级发展，并行粒度在加大，并行性也加强。最初 的并行性是指令级的，通过在单处理机内部增设流水线处理部件、多功 能单元及关联存储器等来开发指令级并行性。指令级并行性远远不能满 足高性能计算的需求，为了进一步提高并行度，计算机系统向开发程序 级和任务级的并行性的多计算机系统发展。把多台计算机连起来，互相 配合，各尽其能，利用功能专门化、多机群和网络化这三种基本技术向 同构型多处理机系统、异构型多处理机系统和分布式处理系统发展。 世界上第一台真正的并行机系统是1 9 7 2 年研制成功的1 1 1 i a cn ， 它是由美国投资3 0 0 0 万美元研制的8 x 8 = 6 4 的阵列机。此后的十几年一 直是以向量化结构为主的计算机占统治地位，它的代表是1 9 7 6 年诞生的 c r a y - i 。8 0 年代末，以c r a y 序列为代表的向量并行机为主向量计算 机的特点是利用流水线的概念，把一个计算部件拆成几段，每一段操作 一个子功能，通过时间重叠来实现并行加速，但是它的加速比还是不能 满足求解超大规模计算问题的要求，因此9 0 年代，开始研究大规模并行 机与网络并行机s p 。是1 9 9 4 年i b m 推出的i 叫s p x 序列中第二个产品， 它的一个机柜可以安装1 6 个处理器，一个大系统可由1 6 个机柜组成， 6 第二章相关技术 这样，每个系统最多可以有2 5 6 个结点机，结点机是1 2 8 位内存寻址， 定点与浮点运算可以同时进行，操作系统是a d c ，并行环境有p v m 和m p i 等。我国研制的曙光1 0 0 0 是分布式存储的大规模并行多处理机，结点机 3 6 个，每个结点机为i 8 6 0 芯片，时钟主频4 0 m h z ，整个并行机运行在基 于u n i x 的并行分布式操作系统上，并行环境有n x 库，p v m 和e x p r e s s 。 任务划分、数据分布、任务调度，任务同步、任务通讯这几个概念 是并行计算中研究的热点，这几个概念是相互影响的，采用不同的方式 对应不同的并行计算模型。 2 并行计算的应用 并行计算研究的主要目标是解决具有重大意义的科学工程计算问 题，包括气象、能源、医学、工程、军事等众多领域。要求计算机系统 能进行高速、有效的并行处理，计算性能达到很高的水平。并行计算应 用如下： 用于天气、环境等的预测和模拟； 超级并行计算机用来进行能源勘探，建立油田的三维模型，识别 可能提供原油的地层形状； 在超级并行机上可以模拟生物医学系统和进行遗传工程的研究， 如研究蛋白质结构分子合成的分子生物学，也可以用计算机辅助 结晶学研究： 在军事机构中，已经用大型并行机c r a y l ，c y b e r 一2 0 5 模拟自 动武器的效果，用p e p e 并行机进行反弹道导弹的雷达信号处理， 用s - i 多处理机来进行反潜水艇战斗的海面监视等。 此外，并行计算还用于与许多应用领域有关的基础研究，例如，计 算物理学家分析质点轨迹和流体动力学、量子场理论、分子动力学的研 究，计算化学家求解量子力学、统计力学、聚合化学、晶格生长等问题， 电子工程师使用多级牛顿算法求解大规模的电路方程、v l s i 芯片设计等 总之，在这些领域的研究中，单处理器的计算速度受到顺序执行的 限制，已满足不了大规模计算的需求，因此，开发高速的超级计算机， 运用高度并行处理技术已成为一个重要而有效的途径。 7 广东t 业犬学t 学硕_ j 学位论文 3 并行系统的性能度量 ( 1 ) 执行时问 程序串行运行时间是指在串行计算机上，程序从开始到运行结束所 用的时间。 并行运行时间是从并行计算开始时间到最后的处理桃完成运算所经 过的时间。我们用t s 表示串行运行时间，用t p 表示并行运行时间。 ( 2 ) 总并行开销 求解一个问题，所有处理机所用总时间是p t p 。这个时间的t s 部分 是完成有用工作所花费的时间，剩余部分即是开销。用t o 表示并行系统 的开销函数。 t o = p t p t s ( 1 1 ) ( 3 ) 加速比 加速比是指在单个处理机上求解问题所花的时问与用p 个相同处理 机所组成的并行计算机求解同一问题所花时间之比。 s ：t s t p ( 1 2 ) a m d a h l 定律： a m d a h l 给出了一个加速比的通用模型如下： s p ：t 1 + ( 1 一；) p t 1 ) ( 1 3 ) = i + ( 1 一) p e 是一个百分比，是程序或代码中不能被并行化的百分比，( 1 一) 是可以完全并行化的百分比。不考虑如内存争用等通信延迟因素 1 3 。 ( 4 ) 效率 包含p 个处理机的理想并行系统应能提供加速比p 。但实际上，理 想性能是不可能实现的。当执行一个算法时，结点机不可能投入1 0 0 的 时间以及1 0 0 的资源来进行算法的计算。 效率定义为加速比与结点机数目的比率，它依赖于结点机被利用的 程度。用符号e 表示效率。 e = s p ( 1 4 ) 4 并行算法的一般设计方法 1 ) 直接将串行算法改为并行算法； 3 第二章相关技术 发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行 算法。 2 ) 直接设计并行算法； 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并 行算法。 3 ) 借用已有算法求解新问题。 找出求解问题和某个已解决问题之问的联系，改造或利用已知算法， 将其应用到求解问题上。 5p c a m 设计方法学一设计并行算法的四个阶段 1 ) 划分：将大任务分解成若干个小任务，开拓并发性； 2 ) 通讯：确定各任务间的数据交换，监测划分的合理性： 3 ) 组合：依据任务的局部性，组合成更大的任务； 4 ) 映射：将每个任务分配到处理器上，提高算法的性能。 2 1 2 网络并行计算 i 网络并行计算的定义 利用一组由网络互连的计算机同时解决一个大闻题的过程就是网络 并行计算。 网络并行计算机是由高性能网络或局域网连接的全体结点机的集 合。一个结点机可以是一台服务器、一个工作站或是一台p c 机，结点机 可以是同构的，也可以是异构的。结点机数目一般为几个至几十个，支 持控制并行或数据并行的开发。每个结点机都有完整的操作系统、网络 和用户界面，既可作控制结点，又可做运算结点，即各结点机是平等的。 2 网络并行计算优点 第一，资源利用率高 通常用户结点机的工作负载并不重，或是空闲的，如将这些结点机 组成一个机群系统，就可以有效的利用它们进行并行计算。 第二，结构灵活 在网络并行计算环境下，构成的并行虚拟机的机器可以改变，可以 将空闲的机器加入到虚拟机中，也可以把某台机器从当前的虚拟机中移 9 广东工业丈学t 学硕士学位论文 出。 第三，投资少、风险小 用户购置传统巨型机或大规模并行处理系统( m p p ) 很昂贵，会担心是 否适合使用以及使用效率的问题，一旦不适合，等于浪费了大笔资金。 而网络并行系统的投资相对少很多，不仅可以用来进行网络并行计算， 还可以单机使用。 第四，编程方便 网络并行编程环境支持原有的传统语言，如c ，c + + ，f o r t r a n 。 由于网络并行计算具有以上的优势，因此网络并行计算能够从理论 技术发展到实际应用，成为解决大型问题的计算机系统的发展方向。 3 网络并行系统适用的计算类型 从应用问题的角度来看，有一类应用程序非常适合于在网络并行系 统上运行，这类应用程序的特点是各个子任务是相对独立的应用程序， 子任务之间无需通信，只存在子任务和父任务之间的通信。对于存在数 据交换的多个子任务，只有它们同时被网络并行系统的各个结点执行的 情况下才能获得较好的性能。而对于不存在数据通信的任务，在进行调 度时不受执行次序或同步的限制，因而可以最好的发挥网络并行系统的 优势n ”。 2 1 3 基于消息传递的并行计算平台 消息传递的特点：多线程、异步并行性、分开的地址空间、显式相 互作用、显式数据映射和负载分配，支持消息传递的并行计算平台有 m p i 、p v m 、e x p r e s s 和l i n d a 等。“ 1m p i 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 标准制定的人员来自欧美4 0 多个组织，包 括大部分主要的并行计算机制造商、大学研究所、政府实验室及工业组 织等。有了统一的并行编程语言标准，并行计算环境下的应用软件及软 件工具就能够实现透明的移植，各个厂商就可以依据标准来提供具有自 身特色和优势的软件实现和软件支持，从而提高并行处理的能力。 m p i 是一种基于消息传递模型的并行编程接口，已经发展成为消息 传递模型的代表和事实上的工业标准，它不是一门具体的语言。迄今为 止，所有的并行计算机制造商都提供对m p i 的支持，所以，理论上任何 一个正确的m p i 程序都可以不加修改地在所有并行计算机上运行。 m p l 只是一个并行编程语言标准，要编写基于m p i 的并行程序，还 必须借助某一m p i 具体实现。m p i c h 是l i n u x 平台下最重要的一种m p i 实现，是一个与m p i 规范同步发展的版本。每当m p i 标准推出新的版本 时，m p i c h 就会有相应的实现版本。l a m ( l o c a la r e am u l t i c o m p u t e r ) 是l i n u x 平台下另一免费的m p i 实现，它由o h i o 州立大学开发，主要用 于异构的网格计算并行系统。 2p v i p v m 是一种基于局域网的并行计算平台，通过将多个异构的计算机 有机地组织起来，形成一个易于管理、易于编程、并且具有很好的可扩 展性的并行计算环境。 p v m 支持c 和f o r t r a n 语言。程序员首先参照消息传递模型编写好 并行程序，然后将编译后的程序以任务为单位在网络并行系统的结点机 上运行。p v m 能够在虚拟机中自动加载任务并运行，并且提供了任务间 相互通信和同步的手段。由于所有的计算任务都被分配到合适的结点机 上，多个结点并行运算，从而实现了任务一级的并行。 p v m 为利用现有计算资源进行并行程序的开发与研究提供了一种有 效的解决方案。由于p v m 免费、开放和易用的特性，使得它成为一个被 广泛接受的并行程序开发环境，目前几乎所有的并行计算系统都支持 p v m 。 3e x p r e s s e x p r e s s 系统最初是由加州理工大学c a l t e c hc 。f o x 领导开发 的，在一批并行机上优化实现后，成为p a r a s o f t 公司的一个商业消息 传递库。它强调并行程序设计的高层问题，目的在于进一步地为用户提 供并行程序设计环境，支持c 与f o r t r a n 两种程序设计语言。 e x p r e s s 是由一个或多个主机或由有多个c p u 的并行处理机构成， 广东工业大学1 = 学硕l ：学位论文 一般不需要特殊的硬件支持，能运行在分布存储和共享存储的硬件系统 上。当前，e x p r e s s 主要适用于分布存储的多机系统，这些相同或不同 类型的机器可由不同的拓扑结构进行连接。 e x p r e s s 提供c u b i x 和h o s t - n o d e 两种工作方式，它们分别对应于 不同的并行程序库。对于c u b i x 方式，分配工作完全是系统自动完成的， 而h o s t n o d e 方式，既可以由用户指定要分配的结点数，也可以完全交 给系统自动完成。在任何时刻，消息可从e x p r e s s 系统中一个结点传送 到另一个结点。e x p r e s s 核心负责消息的中间转存及路由，不仅提供了 点对点通信，还提供了广播通信原语，这些方式同时也适用于i o n 务 4l i n d a l i n d a 是美国y a l e 大学d a v i dg e l e r n t e r 开发的用于实现与机器 无关的并行设计环境，是一个关联的、虚拟的共享存储系统，既可以用 于共享存储的计算机系统，又可用于分布式存储的计算机系统。是通过 对传统程序设计语言进行扩充来实现的，使其具备并行程序设计的能力。 目前有c - l i n d a 和f o r t r a n l i n d a 两个版本。 l i n d a 中关联存储部分称为t u p l e 空间，其中每个元素称作t u p l e 。 t u p l e 的标识与选择是通过对其值域的匹配完成的，l i n d a 以t u p l e 空 间为核心进行进程间的同步和通信。l i n d a 适合应用于单一结点上具有 多个处理进程且进程间同步点较多以及全局通信较为频繁的场合。 2 2p v m 并行虚拟机 2 2 1p v _ 简介 p v m 是一种常用的基于消息传递的并行编程环境，它把工作站网络 构建成一个虚拟的并行机系统，为并行应用提供了运行平台。 p v m 是美国o a kr i d g e 国家实验室推出的一个分布并行计算平台 它不仅适合于m p p 大型并行系统，也支持网络计算机。p v m 第一版由美 国o a kr i d g e 国家实验室的v a i d ys u n d e r a m 和a ig e i s t 在1 9 8 9 年设计 实现，它只是最初的实验版本，用在研究异构的分布式计算过程中时发 现它的移植性差、编程接口不完善。- ，1 9 9 1 年2 月推出的p v m 2 0 版对 1 2 第二章相关技术 原有代码进行了优化，简化了编程接口并开始开发图形接口，研究监控、 容错和性能分析。1 9 9 3 年推出p v m 3 0 版，作了很多改动，包括用户界 面、进程控制、容错和任务组，相继研制的p v m 3 1 版( 1 9 9 3 年4 月) 、 p v m 3 2 ( 1 9 9 3 年8 月) 、p v m 3 3 ( 1 9 9 4 年6 月) 、p v m 3 4 版( 1 9 9 6 年) 研究 了负载平衡、多处理机集成等问题。p v m 引起许多科研部门的兴趣，目 前，o a kr i d g e 国家实验室、e m o r y 大学、t e n n e s s e e 大学、卡内基梅隆 大学、p i t t s b u r g h 超级计算机中心等都加入到p v m 的研究项目中。p v m 以及与其配套的异构计算机网络环境( h e n c e ) 、可视化工具x p v m 已经被 广泛应用。一批标准的软件，如l i n p a c k ，e i s p a c k ，l a p a c k 等正在移 植到p v m 平台，所有的并行机公司宣布支持p v m 。p v m 3 1 建立在以u n i x 为操作系统的、基于t c p i p 协议的网络环境中在p v m 的控制下，能将 多台网络计算机( 可以是并行机或是单处理机，每台计算机称为一台结点 机) 看成是一台单一的分布式存储并行计算机，即并行虚拟机。用户可以 把它作为一台大的并行机使用， 2 2 2p v m 的通信机制 p v 鲥的通信机制： p v m d p v m d 通信：p v md a e m o n 间通过用户数据报协议( u d p ) 的s o c k e t 进行通信，由于u d p 限制包的长度，所以p v m 把长的包分成多片发送。“7 1 本机p v m d t a s k 与t a s k t a s k 通信：t a s k 与本机的p v m d 或本机的 其他t a s k 间使用t c p 协议进行通信； 远程t a s k t a s k 通信：t a s k 使用t c p 协议与远程t a s k 进行通信。 p v m 的m a s t e r s l a v e 运行模式： 由主( m a s t e r ) 程序激活一组从( s l a v e ) 进程，并调度这些进程， 各从进程之间允许通信。第一台启动p v m 的机器称为主机，其他的由监 控进程或用户自己启动的机器称为从机。它们共同形成一台并行虚拟机。 在并行虚拟机上，用户运行的一个p v m 应用程序由分布于各个结点机上 的多个进程构成，每个进程叫做一个任务( t a s k ) ，分配一个任务标志 t i d 。t i d 形成了p v m 统一的、虚拟的、清晰的任务管理空间。多个任务 通过互相识别t i d ，在网络上发送、接收消息，协作完成计算任务。 ：耋王垩奎耋：茎至! ：耋竺鎏兰 各结点机之间通信可以有两种方式：消息传递方式和远程过程调用 方式。远程过程调用方式具有“请求、调用、返回”的语义，一台机器 发出请求，调用应用程序，应用程序在另一台机器上执行完毕，将结果 返回到调用它的那台机器上。消息传递方式提供数据发送、接收、同步 等原语，各结点机通过互相传递消息来协同完成任务。p v m 采用消息传 递的通信模型，利用t c p i p 网络进行消息收发。 目前，有科研人员分析出p v m 支持客户机服务器( c l i e n t s e r v e r ) 分布计算的不足，设计和实现了一个在p v m 虚拟并行机环境下的、基于 t i d 的远程过程调用通信模型。 2 2 3p v m 的组成 p v m 由三部分组成： 第一部分是p v m 监控进程( p v m d ) ，它是整个p v m 的核心。每台结点 机都运行一个p v m d 。通过t c p 协议实现本机任务与p v m d 的交互，及通 过u d p 协议实现结点机之间p v m d 与p v m d 的交互。 第二部分是p v m 接口库p v m1 i b ，它向p v m 任务提供一个采用消息 传递方式的a p i 接口，支持c 语言、f o r t r a n 语言。 第三部分是p v m 控制台进程，相当于并行虚拟机的操作平台，可以 与用户交互式地工作。用户在此可以增加、删除结点机以及执行一些其 他的控制命令，如启动、终止一个p v m 任务，显示某任务的状态等。 2 2 4p v m 的工作模式 p v m 的工作模式是主从结构( m a s t e r s l a v e 模式) ，它属于群型计算 模式。第一台启动p v m 的机器称为主机，其他的由监控进程或用户自己 启动的机器称为从机，它们共同形成一台并行虚拟机。在并行虚拟机上， 用户运行p v m 应用程序由分布于各个结点机上的多个进程构成，每个进程 叫做一个任务( t a s k ) ，分配一个唯一的标志一任务标识符( t i d ) ，形成 了p v m 统一的、虚拟的、清晰的任务管理空间，多个任务通过识别t i d 在网络上发送、接收消息，协作完成计算任务。“7 1 在使用m a s t e r s l a v e 模型时，需要确保m a s t e r 进程不成为瓶颈， 当任务太小或s l a v e 相对太快时可能会产生这种情况。选择任务粒度时， 要保证进行任务迁移所节省的开销要大于通信和同步等所产生的开销。 t l s 2 2 5p y i i 的特点 异构性 异构性表现在两方面：一是组成并行虚拟机的计算机的体系结构可 以不同，p v m 支持p c 机、工作站、并行计算机、向量机及多处理机； 二是p v m 允许虚拟机内的多个结点机使用不同的网络进行相连，如 t o k e nr i n g ，f d d i ，e t h e r n e t 等。 通用性强 既适于网络并行计算，又适用于m p p 大规模