（计算机应用技术专业论文）基于pvm的任务分配及调度策略研究.pdf

摘要 摘要 网络并行计算是一种分布式处理系统，它利用现有高速网络互联的处 理机、工作站的软硬件资源，实现以前只有专用且昂贵的大规模并行计 算机系统才能完成的高性能计算。与专用的大型机、超级并行计算机相 比，网络并行计算具有投资小，灵活性强，应用软件开发速度快和可移 植性好的优点。正是由于其简洁、高效以及广泛的适用性和易用性，网 络并行计算成为当今并行处理技术研究的热点。 任务的分配与调度是网络并行计算中最基本、最关键，也是最具挑战 性的问题之一，是影响并行计算执行效率的一个关键因素。任务分配与 调度是计算机研究领域的一个经典问题，其许多子问题尚未彻底解决， 对它们进行研究具有重要的理论和实际价值。 论文详细分析了p v m 网络并行计算平台的系统结构和通信机制，对 网络并行计算的模型和实现进行了深入的探讨，研究了各种任务分配及 调度的相关策略。针对网络并行计算的任务分配与调度存在的问题，通 过对p v m 网络并行环境的特点及各种任务分配策略进行详细的对比研 究，综合考虑任务执行时间，任务间的通信时间以及处理机的计算能力 等因素，本文提出了任务预分配与动态调度相结合的任务分配与调度策 略。 基于p v m 网络并行计算平台的并行程序比较适合一些中、大粒度的 任务，任务间的通信时间和通信延迟开销都比较大，本文提出的任务分 配与调度策略能较好地解决了该问题。根据任务之间的通信关系，在任 务的预分配中，对任务模型进行了并行簇的划分，并把处理机按并行簇 进行分组。每个处理机组有一个组调度主机，对并行簇进行任务的动态 调度，避免了使用单一调度主机产生的瓶颈问题。使用的任务预分配策 略比一般的静态任务分配大大减小了任务分配的时间，又避免了完全依 靠动态分配策略进行任务调度而带来的抖动现象的发生；每个处理机组 采用动态任务调度又能根据系统的信息负载情况进行合理地调度，减小 任务分配的开销和任务间的通信开销，从而使并行计算的效率得到提高。 通过详细地分析与研究，本文设计了一个基于w i n d o w s 环境下p v m 广东t 业大学t 学硕 ：学位论文 平台的任务分配与调度模型。该任务模型包括系统负载的获取、任务的 预分配与动态任务调度。最后总结了本文的研究工作，指出了下一步的 研究方向。 关键字：并行计算p v m 并行簇任务预分配动态任务调度 a b s t r a c t n e t w o r kp a r a l l e lc o m p u t i n gi sad i s t r i b u t e dp r o c e s s i n gs y s t e m ，i tm a k e f u l lu s eo ft h eh i g h s p e e dn e t w o r kw o r k s t a t i o no rc l u s t e ro fh a r d w a r ea n d s o f t w a r er e s o u r c e st oc o m p l e t e di nh i g h p e r f o r m a n c ec o m p u t i n g ，w i t c ho n l y h a v eb e e nd o n eb yt h es p e c i a la n de x p e n s i v ed e d i c a t e dl a r g e s c a l ep a r a l l e l c o m p u t e rs y s t e mc a nb e c o m p a r i n gw i t ht h em a i n f r a m ea n ds u p e rp a r a l l e l ， n e t w o r kp a r a l l e lc o m p u t i n gi sa d v a n t a g eo fl i t t l ei n v e s t m e n t ，f l e x i b l e ，h i g h s p e e di nd e v e l o p m e n to fa p p l i c a t i o ns o f t w a r ea n dt r a n s p l a n t e df e a s i b l e b a s eo ni t ss u c c i n c t ，h i g h - e f f i c i e n ta n de x t e n s i v es u i t a b i l i t ya n de a s yu s i n g ， n e t w o r kp a r a l l e lc o m p u t i n gs y s t e mh a sb e c o m et h eh o tp a r ti nt h ep a r a l l e l p r o c e s s i n gt e c h n o l o g yr e s e a r c h a so n eo ft h em o s t f u n d m e n t a l ，c r i t i c a la n dc h a l e n g a b l ep r o b l e m si n n e t w o r kp a r a l l e lc o m p u t i n g ，t a s ks c h e d u l i n gi st h ek e yp o i n ti nt h ee f f i c i e n t e x e c u t i o no fn e t w o r kp a r a l l e lc o m p u t i n g t a s ka l l o c a t i o ni sac l a s s i c a l p r o b l e mi nc o m p u t e rs c i e n c e ，w h o s em a n ys u b - p r o b l e m sh a v en o tb e e n r e s o l v e dt h o r o u g h l y r e s e a r c ho nt h e s ep r o b l e m si sv e r yv a l u a b l ei nb o t h t h e o r ya n dp r a c t i c e t h i sp a p e rh a sb e e na n a l y z e di nd e t a i lt h es y s t e ms t r u c t u r eo fp v m c o m p u t i n gp l a t f o r ma r c h i t e c t u r e ，c o m m u n i c a t i o nm e c h a n i s m s ，t h em o d e l o f p a r a l l e lc o m p u t i n ga n ds o m es t r a t e g i e so ft a s ka l l o c a t i o na n ds c h e d u l i n g t ob ea i m e da tt h ep r o b l e m so ft a s ka l l o c a t i o na n d s c h e d u l i n gi nt h e n e t w o r kp a r a l l e lc o m p u t i n g ，t h i sp a p e rp r o v i d e ss o m es t r a t e g i e so ft h et a s k a l l o c a t i o na n ds c h e d u l i n gc o m b i n e dp r e - a s s i g n e dt a s k sw i t hd y n a m i ct a s k a l l o c a t i o nb a s e do nt h er e s e a r c ho fc h a r a c t e ro fp v mn e t w o r kp a r a l l e l c a l c u l a t i o na n ds t r a t e g i e so fa l lk i n d so ft a s ka l l o c a t i o n ，t a s kr u n n i n gt i m e ， c o m m u n i c a t i o nt i m ea n dc a p a b i l i t yo fp r o c e s s i n gu n i t t h ep a r a l l e lp r o g r a m sw h i t c hr u no np v ma r em o r es u i t a b l ef o rm e d i u m a n dt o u g ht a s k d u r i n gt h et a s k ，i ti st o oe x p e n s ef o rc o m m u n i c a t i o nt i m e a n dd e l a y t os o l v et h i sp r o b l e m ，t h i sp a p e rp r e s e n t st a s ka l l o c a t i o na n d h i 广东t 业大学t 学硕士学位论文 s c h e d u l i n gs t r a t e g y a c c o r d i n gt o t h ec o m m u n i c a t i o nb e t w e e nt a s k s ，i t d i v i d e st h et a s km o d e lb yp a r a l l e lc l u s t e rd u r i n gt h ep r e a s s i g n e dt a s k h a v e d i s p a t c h e r 。sh o s tc o m p u t e ro fag r o u pt od e a lw i t ht h ea i r e r e we a c ho n e ， f o r mac l u s t e ri n r u n n i n gs i d eb y s i d ea n dc a r r yo nt h e m a n a g i n g d y n a m i c a l l yo ft h et a s k ，h a sa v o i d e du s i n gt h eb o t t l e n e c kq u e s t i o nw h i c h t h es i n g l ed i s p a t c h e r sh o s tc o m p u t e rp r o d u c e s a s s i g nt h et a c t i c st or e d u c e t h et i m ef o rt a s ka l l o c a t i o ng r e a t l ym o r et h a ng e n e r a ls t a t i ct a s ka l l o c a t i o n i na d v a n c ei nt a s ku s e d ，i ti sa s s i g nt a c t i c sc a r r yo nt a s ks c h e d u l i n gb u t s h a k ye m e r g e n c eo fp h e n o m e n o nt h a tb r i n gd y n a m i c a l l yt or e l yo nt o t a l l yt o p r e v e n tf r o m ；d y n a m i c t a s k s c h e d u l i n g c a nb em a n a g e d r a t i o n a l l y a c c o r d i n g t ot h e s y s t e m a t i c i n f o r m a t i o nl o a ds i t u a t i o n ，r e d u c et h e c o m m u n i c a t i o ne x p e n s e sa m o n gt h ee x p e n s e sa n dt a s ko ft a s ka l l o c a t i o n ， t h u sm a k et h ee f f i c i e n c yo fp a r a l l e lc o m p u t a t i o ni m p r o v e d t h r o u g hd e t a i l e da n a l y s i sa n dr e s e a r c h ，t h i sp a p e rd e s c r i b e st h ed e s i g n o fap v mt a s ka l l o c a t i o na n ds c h e d u l i n gm o d e lb a s eo nw i n d o w s t h em o d e l i n c l u d es y s t e ml o a dm o d e lf o rt h ea c q u i s i t i o n ，t h ep r e - a l l o c a t i o no ft a s k s a n dt a s ks c h e d u l i n ga n dd y n a m i c f i n a l l y ，t h i sp a p e rp r e s e n t st h en e x tp h a s e o fr e s e a r c h k e y w o r d s ： n e t w o r kp a r a l l e l c o m p u t i n g ，p v m ，p a r a l l e l c l u s t e r ， p r e a s s i g n e dt a s k s ，d y n a m i ct a s ks c h e d u l i n g i v 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是 我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经发表 或撰写过的研究成果，不包含本人或其他用途使用过得成果。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的声明，并 表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取 得的，论文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此 声明。 指导教师签字： 论文作者签字： 2 0 0 7 丐月弓佣 第一章绪论 1 1 课题的研究意义与研究现状 1 1 1 研究意义 网络并行计算是一种分布式处理系统，它利用现有的通过高速网络 互联的处理机、工作站的软硬件资源，实现以前只有专用的昂贵的大规 模并行计算机系统才能完成的高性能计算。它与大型机、超级并行计算 机相比具有投资小，灵活性强、应用软件开发速度快，并且可移植性好 的优点。正是由于其简洁、高效及广泛的适用性和易用性，网络并行计 算环境成为当今并行处理技术研究的热点。 网络并行计算环境可以是由多种不同结构的计算机构成，通过多种 互连方式组合的一个综合计算环境，可以包括p c 、工作站、小型机、特 种计算机，还可以包括各种类型的大型机、巨型机，其规模可以小到几 个计算机、局域网，大到广域网，甚至i n t e r n e t 。 网络并行计算环境具有广泛的应用前景，其主要优势有： 1 可以利用现有的网络计算资源，计算成本低； 2 通过合理的任务调度，可以获得最佳性能； 3 网络规模易于扩展，可以满足不断增长的计算需求： 4 开发人员可以利用他们熟悉的环境开发并行程序 其中基于消息传递的p v m ，m p i 等就是应用比较广泛的网络并行计 算平台。p v m 是一个免费的、公开源码的、被广泛接受的并行编程环境， 提供资源管理、进程管理、消息传递以及协同操作等支持。它可以把多 个异构的计算机组织起来成为一个并行计算系统。这些异构的计算结点 可以通过多种网络互联成为一个网络计算虚拟机。 使用工作站和个人计算机进行分布式并行处理、以低成本完成大型 科学计算的一个非常具有发展前景的途径，但同时也提出了大量富有挑 战性的课题，任务分配与调度就是其中一个很重要的问题。任务分配和 调度的根本问题是：经过初始分配，并行程序实现一组任务后，需要将 它们合理或优化地分配到分布系统中的各个处理单元。如果这一问题处 广东t 业大学1 = 学硕七学位论文 理得不好。就有可能导致分布效率低下，甚至效率还不如单个计算机计 算。 任务分配问题是个n p 完全问题，人们不会盲目地去寻求解决这类 问题的最优解，但对于具体的分布式系统，在适当的假设条件下寻找不 一定是最优解但在实际中可行且效果较满意的方法，仍是现今十分活跃 的研究课题。 调度问题的最大挑战还在与如何处理任务系统的动态性，动态调度 出现的巨大复杂性使得动态调度算法产生很高的计算成本而降低了实用 性，许多调度问题还远远没有得到很好的解决，调度算法的研究仍然是 一个长期而艰巨的任务，在现阶段，我们只能针对某一领域的问题设定 约束条件，寻求更有效的方案。 p v m 系统在分配任务时，在机群中采用循环轮转的平均分配的算法， 主要原因是：算法实现简单，且运行的代价小。它可使任务最大限度地 广为分布，以追求高并行性目标，缩短作业运行时间。但该算法没有考 虑并行计算系统中各处理机存在的运行速度的差异，使得系统的负载分 布不平衡，慢速的处理机成为系统的瓶颈，在快速的结点上运行的结点 必须阻塞等待，浪费了宝贵的计算资源，若处理机间的运行速度差异很 大的话，这种浪费由为严重。 如何在异构计算环境中研究并行计算的任务分配与调度问题已经成 为了该领域目前和未来研究的一个主要方向 1 2 1o 在异构计算环境中，各 个处理机的处理能力并不完全相同，处理机的互联网络存在不同的带宽 和网络延时，以及处理处理上的操作系统与数据结构的差异及网络通信 协议的多样性。因此，异构计算环境中的并行任务分配与调度问题较之 同构系统复杂得多。建立适于异构环境的并行应用模型以及设计更优化 的基于异构模型的任务分配与调度算法是具有挑战性的工作。 1 1 。2 课题研究的现状 任务的分配与调度作为并行计算的核心问题之一，对其的研究工作 在国内外都一直十分活跃，许多大学和科研机构在并行分布式计算和任 务的分配与调度方面进行了卓有成效的研究。 2 第一章绪论 在对任务分配与调度的算法的研究当中，尤其是早期的研究中，基 于表的任务调度算法的研究较多，如文献 3 提出的e t f ( e a r l i e s tt i m e f i r s t ) 算法和文献 4 提出的m h ( m a p p i n gh e u r i s t i c ) 算法都是比较 有影响的表调度算法。由于表调度算法在实现上相对简单，也比较成熟， 其思想在任务调度的研究中一直占有比较重要的地位，很多算法都是在 它的基础上的延伸。 在并行计算系统中，处理机之间的通信是必不可少的，通信是并行 系统中一种消耗比较大的开销，尤其是在基于消息传递的并行计算系统， 如基于p v m 或m p i 平台的并行计算系统。为了减少系统中各处理机之问通 信开销的，一些学者提出了基于任务复制的调度算法，该算法通过在处 理机上冗余地映射任务图中的一些任务，以达到减少处理机之间通信开 销的目的。与其他的调度技术相比，该类算法有比较高的时间复杂度， 但复制任务或数据也需要很大的开销。文献 5 3 提出的c p f d ( c r i t i c a l p a t hf a s td u p l i c a t i o n ) 算法和文献 6 提出的p y 算法都是比较有代表 性的居于复制的任务调度算法。 以上的任务分配及调度算法，系统中都有一个调度机负责任务的分配 与调度，文献 7 3 介绍了一种结点自适应的调度算法，该算法不用专门的 调度机负责任务的分配与调度。虽然说用调度机的集中调度方式看似浪 费了一个处理机的计算能力，但却是必要的，这样能增加整个计算的效 率。而结点自适应的调度算法实现起来难度相对较大。 近年来各种基于状态空间的搜索技术曾用来寻找最优的子任务分配 与调度策略。但限于所针对问题的特殊性而缺乏通用性，有时甚至导致 指数级的时间复杂度。因此，多项式时间复杂度的启发式搜索算法一度 曾用来求解任务分配与调度策略问题，但因为所有启发式搜索算法都是 以牺牲解的全局最优性来降低算法的时间复杂度，同样不能确保得到最 优的任务分配与调度策略：其次因为启发式搜索算法中采用确定性的贪 婪策略往往导致算法对任务调度参数( 处理机数量与输入任务结构图) 十 分敏感，从而使得启发式搜索算法在大型复杂任务分配与调度策略的求 解中不具有时间与求解质量上的可伸缩性。文献【8 】介绍了基于遗传算法 和模拟退火算法的并行计算任务分配策略。该文献还提出了一种“合一 3 广东工业大学工学硕士学位论文 一阈值”启发式分配算法，它是一种分阶段进行任务分配的算法。第一 阶段为“合一”阶段，对用户提交的一组任务进行合一处理，“合一”是 指根据一定条件，将两个任务分配到同一处理机上。第二阶段为“调整” 阶段，在第一阶段的基础上，根据各处理机上规定的阈值，对各处理机 上的实际负载作必要的调整，文献【9 】【1 0 】中也介绍了一些启发式任务分 配算法。 如前所述，任务分配问题是个n p 完全问题，人们都是在适当的假设 条件下或某些特定领域中研究其最优解。前述的各种算法也都是在特定 的假设条件约束下或在特定的领域的分配算法。相对与其他并行系统， 对支持异构系统的p v m 系统的并行计算的任务分配的研究不是太多。 吉林大学的鞠九滨较早进行了p v m 任务的调度1 1 1 1 ，对p v m 环境下 的进程迁移问题进行了深入的研究，通过对p v m 系统的修改研制了支 持任务调度的p v m 系统一d p v m 系统【1 2 j 。文献 1 3 3 采用对结点负载实测 和利用人工神经网络进行预测下相结合的策略并利用检查点技术和进程 迁移技术，来改进p v m 的任务调度机制，以达到动态的负载平衡，文 献【1 4 】介绍了一种p v m 任务调度中的消息处理方法。 1 2 研究内容 论文利用目前在并行领域广泛应用的基于消息传递模型的典型代表 p v m 作为并行计算平台，研究在该平台下的任务分配与调度策略，在已 有的并行计算理论和方法研究的基础上主要开展一下几个方面的工作： 1 研究p v m 并行计算环境的系统体系结构及其通信机制。 2 研究并行计算的模型，任务分配与调度的模型。主要是p v m 的并 行程序模式，以及p v m 并行环境下的任务分配与调度的模型的分析与构 建。 3 研究了网络并行计算的任务分配与调度的相关问题，包括一些常 用的任务分配技术，归纳总结现有的一些任务分配策略及其实现的算法。 4 归纳总结影响任务分配与调度性能的因素，以及提高任务分配与 调度性能的途径。 5 针对网络并行计算的任务分配与调度存在的问题，研究适合于 4 第一章结论 p v m 并行计算程序的任务分配与调度策略，以减小了任务分配与调度的 开销和任务间的通信开销，提高并行计算的效率。 1 3 论文的组织 第一章介绍论文的研究意义，目前网络劳行计算任务分配及调度的 研究现状，以及本文的组织结构。 第二章详细分析了基于消息传递机制的p v m 网络并行计算平台，研 究了其系统结构及通信机制，以及相关的并行程序模型。 第三章分析了网络并行计算中的任务调度的理论，介绍任务分配及 调度的基本概念，归纳总结基本的任务调度技术，对任务分配模型及任 务调度性能进行了进一步研究。 第四章研究基于p v m 并行计算环境的任务分配方法及其存在的问 题，通过对比分析各种任务分配及调度的优劣，提出了任务预分配与根 据系统负载变化进行动态任务分配的任务分配策略，并建立了任务分配 模型。 第五章对任务分配及调度模型的进行分析及设计。 总结与展望不分是论文研究结果的总结以及后续研究的展望。 广东t 业大学1 二学硕士学位论文 第二章p v m 并行计算平台的分析 2 1 网络并行计算 并行计算的发展主要基于人们在两方面的认识1 1 1 o 第一，单机性能 不能满足大规模科学与工程问题的计算需求，而并行计算机是实现高性 能计算、解决挑战性计算问题的重要途径；第二，同时性和并行性是物 质世界的一种普遍属性，具有实际物理背景的计算问题在许多情况下都 可划分为能够并行计算的多个子任务。 并行计算能显著地提高性能，其基本想法是，i 台计算机应能提高糟 倍的单机速度，不论当前计算机的速度为多少，可以期待求解问题以i n 时间完成。当然这是一个理想的情况，在实际应用中是很难达到的，具 体还要取决于欲求解的问题及其并行性程度。对并行计算的要求永远不 会终止，因为总是有一些具有巨大挑战性的问题，这些问题在当前计算 机上求解不可能在合理的时间内完成。 所谓并行计算即将某一任务分解成更小的子任务集合，将这些子任 务分别分配给网络中的计算资源，使之能同时进行，各子任务之间通过 消息传递或内存共享等模式进行同步或数据交换，等待子任务完成后将 结果汇总融合得出与串行计算相同的结果。 网络并行计算除了可使对现有的求解问题得到加速之外，多处理机 的使用常常可使一个更大的求解问题或要求更精确的求解问题能在合理 的时间内完成。例如，许多物理现象的计算涉及到将求解问题分成为离 散的求解点，电法勘探的计算技术包含着将电流场分为三维的求解格点。 二维和三维的求解格点出现在许多其他应用中。用多处理机求解时，可 以许在给定的时间内计算更多的求解点，从而获得更精确的解。一个相 关的因素是多计算机比单机有更大的总主存储器容量，从而使需要较大 主存储器容量的求解问题得到解决。 工作站集群系统( c o w ，c l u s t e ro fw o r ks t a r i o n s ) 作为网络并行 计算的一个重要方向，锝到了广泛的研究和应用“”。集群是一种并行或 者分布式处理系统，它由很多连接在一起的独立工作作站组成，像一个 6 第二章p v m 并行平台的分析 单独集成的计算资源一样协同工作“”。处理机结点可以是一个单处理机 或者多处理机的系统，如p c 机工作站或者s m p 拥有内存i 0 设备和操作 系统。计算机集群对于用户和应用程序来说就像一个单一的系统这样的 系统可以提供一种价格合理的，并可获得所需性能和优势的解决方法。 它提供快速而可靠的服务，这在以往只能通过更昂贵的专用共享内存系 统来达到。 p v m 和m p i 是能简单快速地构建网络虚拟并行计算环境的典型代 表。其中p v m 是一种基于l a n 的异构并行计算环境，可以把多个异构的 计算机组织起来形成一个易于管理、可扩展的、可编程使用的并行计算 资源，这些异构的处理机结点能够通过多种网络( 如e t h e r n e t 、a t m 、 f d d i 等) 互连，成为一台网络虚拟机，用户的计算任务被分配到各个处 理机结点上并行计算，从而为实现利用已有的l a n 资源进行并行程序的 开发提供了一种有效的解决方案。 由于p v m 源代码公开，可以从网上自由得到，已经成为目前很流行 的大型科学计算的并行软件，它提供基于消息传递的并行程序设计接口， 使网上的用户能够集中地使用众多的机器来求解大规模计算问题。p v m 作为消息传递分布并行编程的事实标准，已被广泛移植到多种平台( u n i x 类、w i n d o w s ) 多种网络和多种体系结构( i n t e p c ，s m p ，m p p 和p v p ) 。 目前正在标准化和商业化。在技术上，p v m 正在向面向对象方面发展。 2 2p v m 概述 p v m 的开发始于1 9 8 9 年，最初由美国椽树岭国家实验室( o r n l ) 开 始研制，后来e m o r y 大学，田纳西大学，卡耐基梅隆大学及p i t t s b u r g h 超级计算机中心参与共同研制的一种网络并行计算平台。它得到美国能 源部、美国国家科学基金会的资助。由于系统具有较好的适应性、可扩 展性、可移植性和易使用性等特点，已经成为并行处理中非常流行的软 件。p v m 已经在w i n d o w sn t 和w i n d o w sx p 等非u n i x 平台上得到实现， 支持c 、c + + 、f o r t r a n 和j a v a 等多种程序设计语言。 2 2 1p v m 系统的特点 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 即并行虚拟机，它将由通用网络连接 7 广东t 业大学1 = 学硕十学位论文 起来的多台计算机模拟成一台分布式存储的并行计算机，是基于消息传 递模型的网络并行计算系统。p v m 系统中，各处理机问的通信基于t c p i p 协议，它同时也支持直接利用多处理机本身提供的通信函数。p v m 是一 个自包含，通用的纯软件系统，它可以较好地支持粗粒度、混合并行任 务的执行，包括图形显示、数据处理、大规模的浮定点计算等。 p v m 的并行程序以任务为单位，每个任务有一个任务标识符。p v m 支持在虚拟机中自动加载任务运行。任务被加载到哪个节点上运行对用 户来说是透明的，大大的方便了用户编写并行程序。p v m 具有以下特点“”： 1 p v y 系统支持多用户及多任务运行。多个用户可将系统配置成相 互重叠的虚拟机，每个用户可同时执行多个应用程序。 2 p v m 提出了进程组的概念。可以把一些进程组成一个迸程组，一 个进程可属于多个进程组，而且可以在执行时动态改变。 3 系统提供了一组便于使用的通信原语。可实现一个任务向其它任 务发消息，向多个任务发消息，以及阻塞和无阻塞收发消息等功能。系 统还实现了通信缓冲区的动态管理机制。 4 易于编程。p v m 支持多种并行计算模型，用户可以使用p v m 提供 的函数库来进行并行计算程序的设计。 5 支持异构计算机联网构成并行虚拟计算机系统，且易于安装、配 置。p v m 在机器层、应用层和网络层这三个层次上支持的异构性。也就 是说，p v m 允许应用任务充分利用网络中适于求解问题的硬件结构；p v m 处理所有需要的数据转换任务；p v m 允许虚拟机内的多个机器用不同的 网络( f d d i ，t o k e nr i n g 和e t h e r n e t 等) 相连。 6 具有容错功能。当发现一个处理机出故障时，p v m 会自动将之从 虚拟机中删除。 除此之外，p v m 还具有其他的特性，如用户可定义主机群、对硬件 半透明访问、基于进程的计算、利用进程传递机制等。 p v m 在高性能科学计算中已经获得了广泛的应用，包括分子动学模 拟、超导研究、分维计算、矩阵计算、地下水、材料科学和气象科学等， 并受到了一致好评。 2 2 2w p v m 3 第二章p v m 并行平台的分析 w p v m 是p v m 的f o rw i n d o w s 的版本，可以运行在w i n d o w sn t 、2 0 0 0 和x p 的平台上。w p v m 是本论文研究的并行计算平台。系统版本是w p v m 3 4 版，它包括一个控制台程序p v m ，一个p v md a e m o n 程序p v m d 和几个程 序库。程序员通过在其应用软件中调用p v m 库子程序来进行并行程序设 计。p v m 库子程序提供了进程控制、动态进程组、多消息缓冲区、消息 传递等手段，支持c 、c + + 、f o r t r a n 语言。一旦系统中安装了w p v m 软件， 则启动一项常驻内存的服务，与其对应进程表中有一开机后自启动的进 程一一w p v m d s e r v e x e 。 。 w p v m 3 4 提供一个可视化的控制台，让我们很方便的就可以构造一 个并行计算的环境。由于p v m 是由一组通过网络连接起来的计算机构成 的虚拟机。如果我们要运行基于p v m 的并行程序，须在这些机器上启动 p v m 程序，并予以配置。配置方法如下： 1 在m a s t e r 主控机上启动控制台程序p v m ，设置为m a s t e r ： 2 在各s l a v e 从控机上也启动控制台程序p v m ，设置为1 i s t e n ： 3 在m a s t e r 主控机上的h o s t 框中填入要加入虚拟机系统的计算机 名称，再填入用户名和密码，点击a d dh o s t 按钮，就可把这台主机加入 p v m 系统里来。如图2 一l 所示。 图2 - 1w p v m 的控制台界面 f i g u r e2 - 1t h ec o n s o l eo fw p v m w p v m 的可视化控制台界面与w p v m 的后台的联系是通过对同一个文 件的存取实现的，用户在控制台界面所做出的修改会写入到w p v m 的记录 文件一一p v m h o s t s c f g 中去，w p v m 读取p v m h o s t s c f g 文件中的内容， 在后台构建并行平台。控制台界面、p v m h o s t s c f g 记录文件与w p v m 后 台之间的关系如图2 2 所示。 9 广东t 业大学t 学硕士学位论文 图2 - 2w p v m 前后台连接 f i g u r e2 - 8t h el i n k i n go f p v m si n t e r f a c ea n dd a e m o n 可以看出，要构造一个并行计算的环境，使用者首先必须了解整个 网络中结点的相关信息，包括处理机是否可用、机器的名称等，然后要 在各台处理机中进行设置。 2 3p v m 系统的组成与结构 2 3 1p v m 系统的组成 p v m 系统环境由三个部分组成：p v m 后台守护进程( p v m d ，p v m d a e m o n ) ，p v m 函数库( l i b p v m ) 和p v m 控制台( c o n s o l e ) 。 p v m d 后台守护进程是整个p v m 的核心，驻留在构成p v m 系统环境的 每台处理机上，负责整个系统环境的维护、任务的控制、消息传递等工 作。它通过t c p i p 通信协议控制进程之间的通信。 p v m 函数库与用户应用程序相连，负责消息传递、任务创建、任务 间协作同步以及虚拟机的动态配置等。用户任务( 应用程序) 通过调用 l i b p v m 库函数请求p v m d 的服务以进行并行计算，l i b p v m 的顶层为用户 编程接口，底层保持独立，以便移植。 p v m 控制台作为一个特殊的p v m 任务，通过与p v m d 通信获得虚拟机 中其它任务的运行、通信状态以及虚拟机的配置信息。p v m 控制台可以 建立p v m 的环境，启动、检查或杀死( k i l l ) 本地任务，收集任务的输 出，打印到屏幕上，并接收任务事件消息。它可以连接到任意的p v m d 上( 主p v m d 或从p v m d ) ，而且可以同时存在多个控制台。如果控制台启 动时，没有p v m d 在运行，则控制台自动启动一个p v m d ，并且与它联接。 现在，已经出现了x p v m 、w p v m 等p v m 控制台的图形化界面应用程序，它 兽舌 薹三兰些竺苎堑圣垒墼坌堑 们可以以图形的方式进行实时显示p v m 信息。 在运行p v m 应用程序之前，用户要在每台处理机上启动p v m 后台守 护进程，p v m 应用程序要同p v m 函数库进行链接，然后应用程序就可以 从任意处理机的控制台上启动运行，这三者一起为用户提供了在松散耦 合的网络上进行并行计算的能力。 2 3 2p v m 系统结构 p v m d 是整个p v m 的核心，每台处理机通过自己的p v m d 负责并行应 用中的部分任务，消息传递通过各处理机上的p v m d 的通信之间。每个 p v m 系统环境中第一个启动的p v m d 为主p v m d ( m a s t e rp v m d ) ，对应的启 动该主p v m d 的处理桃叫做主控机( m a s t e r ) 。此外，在p v m 中，主p v m d 需要在本处理机启动一个独立的m a s t e r 进程，并由m a s t e r 进程负责启 动其它处理机上的从p v m d ( s l a v ep v m d ) ，其它p v m d 所在的处理机叫做 从控机( s l a v e ) ，主控机和从控机一起构成了p v m 虚拟机的环境，其结 构示意图如图2 - 3 。 主控机m a 鼬玎 从控机s l a 2 图2 - 3p v m 虚拟机环境结构图 f i g u r e2 - 3t h ea r c h i t e c t u r eo fp v m ：奎二些查茎三兰堡圭兰堡鎏奎 2 4p v m 通信机制 p v m e p ，计算任务集合通过互相显式地发送和接收消息协同操作， 所以消息是其中的核心概念。一般每个消息都带有消息类型，p v m 中的 消息是有数据类型的，消息大小仅受可用存储器容量的限制。p v m 系统 支持异构系统，允许含有多种数据类型的消息在具有不同数据表示法的 机器之间交换，由p v m 自动处理不同处理机之间数据表示的转换。p v m 是以用户调用子程序库的方式实现任务间的通信。在p v m 中每个任务都 由唯一的t i d 来标识。 在p v m 系统环境中，处理机的p v m 守护进程( p v m d ) 之间通过用户 数据报协议( u d p ) 的s o c k e t 进行通信；守护进程和它的用户任务间的 以及两个用户任务间的通信是用t c p 协议实现的。p v m 通信机制示意图 如图2 - 4 所示。 p v l 系统环境 靖点机括扁机 图2 - 4p v m 通信机制 f i g u r e2 - 4c o m m u n i c a t i o nm e c h a n i s mo fp v m 正如图2 - 4 所示，用户任务是调用p v m 库函数请求p v m d 提供某种服 务。而对于系统设计者和管理员来说，了解系统的底层通信机制有助于 设计和分析系统性能以及找到如何改善系统性能的途径。 2 4 1 p v m 的通信方式 p v m 任务之间可以利用p v m 提供的通信函数进行消息传递，包括点 对点与群集通信。p v m 通信基本上都采用了基于消息缓冲区的方式来实 现点对点通信。p v m 缓冲区分为系统消息缓冲区和用户消息缓冲区。一 个p v m 任务可以有多个用户消息缓冲区，但只能有一个系统消息缓冲区。 p v m 点对点通信步骤如下： 1 2 第二章p v m 并行平台的分析 1 发送方把数据放入到发送缓冲区，并打包成指定格式的消息； 2 发送方调用p v m 函数库中的通信函数，把该消息发送到接收方的 接收缓冲区； 3 接收方调用p v m 函数库中的通信函数，从自己的接收缓冲区接收 消息，并解包出数据。 p v m 点对点通信如图2 - 5 所示： 回回 i 使用通信函教 i 发送缓冲区1 发送消息 ，f 接收缓冲区1 、jl， 发送方接收方 图2 5p v m 点对点通信 f i g u r e2 - 5p o i n tt op o i n tc o m m u n i c a t i o no fp v m p v m 使用了一个叫做1 i b g p v m3 a 的分离函数库来支持群集通信， 群集通信包括广播和组播，用于对任务组发送消息。在p v m 的群集通信 函数中，有些必须是同一任务组内的所有任务执行；有些则只需部分任 务参与；甚至还有些可以由非组内的任务执行。图2 6 为p v m 的群集通 信示意图。 图2 6p v m 群集通信 f i g u r e2 - 6g r o u pc o m m u n i c a t i o no fp v m 2 4 2p v m 的通信函数 p v m 网络并行计算中的任务问的通信是通过p v m 系统提供的通信函 数来进行的。这些函数主要分为4 类：消息缓冲区的创建管理、消息打 包与解包、点对点通信以及群集通信。表2 - 1 列出了这4 类最常用的通 信函数。 表2 - 1p v m 的部分通信函数 t a b l e2 1p v m sc o m m u n i c a t i o nf u n c t i o n s 类型p v m 函数含义 p v m i n i s t e n d 初始化一个消息发送缓冲区，其中为空 p y r e m k b u f 创建一个消息缓冲区 消息缓冲区管理 p v m f r e e b u f 释放某个消息缓冲区 p v m _ g e t s b u f 获取当前发送缓冲区的标识 p v m g e t r b u f 获取当前发送缓冲区的标识 p v m p k 用于把指定类型的数据打包成消息 消息打包与解包 p v m u p k 用于把指定类型的数据解包成消息 p v m s e n d 以阻塞方式发送一个消息 p v m _ r e c v 以阻塞方式接收一个消息 点对点通信 p v m _ n r e c v 以非阻塞方式接收一个消息 p v m t r e c v 接收一个消息，若超时返回 p v m m c a s t 组播消息，但目标参数具体到每个任务 群集通信 p v m b c a s t 组播消息，目标参数是一个任务组 p v m b