（计算机系统结构专业论文）基于pvm的并行程序开发平台研究.pdf

摘要 网络并行计算在高性能计算的需求推动下迅速发展起来，在工程科学 领域的应用已经非常广泛。伴随着网络并行计算的发展出现了一些并行 支撑平台，如p v m ，m p i 等。这些平台本身都具备一系列的a p i 接口，提 供给开发人员调用，开发人员通过调用这些平台提供的函数进行并行程 序设计。然而这些平台的共同特点是开发效率低、质量难以保证，而且 对开发人员的要求比较高，开发难度大。 并行程序的开发与串行程序开发相比，具有一定的特殊性和复杂性。 并行程序的分析和设计需要考虑如任务分配，进程间的通信和同步等细 节，而且并行程序需要调用并行平台中复杂的函数来完成数据传输和处 理。因此并行程序设计比串行程序要复杂，它比串行程序更需要开发工 具的支持。 当前国内外对并行计算的研究主要在实际的工程应用上，并行开发工 具的研究相对较少，目前还没有一个较好的并行开发工具。并行开发工 具发展的相对滞后，在很大程度上影响了网络并行计算的发展。因此， 针对这种情况，本文提出了一个基于p v m 的并行程序开发平台。平台 包括一个并行程序库、并行程序框架生成向导和一个嵌入到v i s u a lc + + 开发环境中的并行类管理器。 并行程序库是一个面向数值计算领域的、具有面向对象特征的并行算 法库。我们把一些典型数值并行算法进行了封装，为开发人员提供高层 次的应用程序接口，开发人员只需调用库中的类和函数就可以轻松进行 并行程序设计。 并行程序框架生成向导集成了一些常用的并行程序模板，开发人员通 过向导可以生成并行程序框架。 并行类管理器是借鉴v i s u a lc + + 开发环境中的类向导设计出来的。通 过管理器开发人员可以在工程中创建新类，并且能够管理在工程中已经 创建的类。 广东t 业大学t 学硕十学位论文 通过本平台进行并行程序开发将会更加容易，开发效率也会更高。这 不仅能加快网络并行计算的发展，而且能推动其他相关工程科学的发展。 关键字：网络并行计算；p v m ；面向对象；并行程序库 n 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 si nr a p i dd e v e l o p m e n td r i v e nb yt h e d e m a n do fh i g h - p e r f o r m a n c ec o m p u t i n g ，a n di ti sw i d e l yu s e di nt h ef i e l do f e n g i n e e r i n g a n d s c i e n c e a l o n g w i t hn e t w o r kp a r a l l e l c o m p u t i n g s d e v e l o p m e n t ，s o m ep a r a l l e lp l a t f o r m sa p p e a r ，s u c ha sp v ma n dm p i ，e t c t h e s ep l a t f o r m sh a v eas e r i e so fa v a i l a b l ea p ii n t e r f a c e s i th a ss o m es p e c i f i c i t ya n dc o m p l e x i t yo np a r a l l e lp r o g r a mc o m p a r e dt o s e r i a lp r o g r a m t h ea n a l y s i sa n dd e s i g no np a r a l l e lp r o g r a mh a st oc o n s i d e r m o r et h i n g sa n dc o n d i t i o n s ，s u c ha st a s kd i s t r i b u t i o n ，c o m m u n i c a t i o n ， s y n c h r o n i z a t i o na n do t h e rm u n d a n ed e t a i l s p a r a l l e lp r o g r a mn e e d st oc a l l t h ec o m p l e xf u n c t i o n st oh a n d l et h ec o m m u n i c a t i o na n dd a t ap r o c e s s i n g t h e r e f o r e ，p a r a l l e lp r o g r a m i sm o r ec o m p l i c a t e dt h a nt h es e r i a lp r o g r a m i t n e e d ss o m eg o o dp r o g r a m m i n gp l a t f o r ma n dt o o l st os u p p o r t n o w a d a y st h er e s e a r c ho nt h ep a r a l l e lc o m p u t i n gd o m e s t i ca n df o r e i g n f o c u s e so nt h e a p p l i c a t i o n ，w h i l et h e r e s e a r c ho nt h ep l a t f o r ma n d e n v i r o n m e n ti sf e w e r t h e r ei sn o tag o o dp a r a l l e l p l a t f o r mn o w t h e d e v e l o p m e n to fn e t w o r kp a r a l l e lc o m p u t i n g i sa f f e c t e d b y t h e p o o r d e v e l o p m e n to ft h ep a r a l l e lp l a t f o r m t h e r e f o r e ，w eb u i l dap a r a l l e l p r o g r a mp l a t f o r mb a s e do np v m t h ep l a t f o r mi n c l u d e sap a r a l l e ll i b r a r y ，a p a r a l l e lp r o g r a mf r a m e w o r ka p p w i z a r da n dac l a s sm a n a g e re m b e d d e di n t h ev i s u a lc + + e n v i r o n m e n t p a r a l l e l l i b r a r yf o c u s e st ot h ea r e a so fn u m e r i c a lc o m p u t a t i o n t h e l i b r a r yp a c k a g e ss o m et y p i c a lp a r a l l e la l g o r i t h m s ，p r o v i d i n gah i g h - l e v e l a p p l i c a t i o ni n t e r f a c et ot h ep r o g r a m m e r s p r o g r a m m e rc a nw r i t ep a r a l l e l p r o g r a mb yc a l l i n gt h ef u n c t i o n si nt h el i b r a r y p a r a l l e lp r o g r a ma p p w i z a r di saw i z a r df o rp r o g r a m m e rt oc r e a t ean e w p r o j e c t w ew r i t es o m ep a r a l l e lp r o g r a mt e m p l a t ea n dp a c k a g ei n t ot h e 1 1 1 童三些奎耋三兰至圭兰丝丝圣 w i z a r d p r o g r a m m e r c a ne a s i l y g e n e r a t ep a r a l l e lp r o g r a mf r a m e w o r k t h r o u g ht h ew i z a r d p a r a l l e lc l a s sm a n a g e ri sac l a s sw i z a r df o rp r o g r a m m e r t h ed e s i g no f t h em a n a g e ri sa c c o r d i n gt ot h ec l a s sw i z a r di nv i s u a lc + + e n v i r o n m e n t p r o g r a m m e rc a ne a s i l yc r e a t en e wc l a s s ，a n dt om a n a g et h ec l a s s e sh a v e b e e nc r e a t e di nt h ep r o j e c tt h r o u g ht h ec l a s sm a n a g e r i tw i l lb ee a s i e ra n dm o r ee f f i c i e n tf o rp r o g r a m m e rt op r o g r a mt h r o u g h t h ep l a t f o r m t h i sw i l ln o to n l ys p e e du pt h ed e v e l o p m e n to ft h en e t w o r k p a r a l l e lc o m p u t i n g ，b u ta l s ot h ed e v e l o p m e n to fr e l a t ee n g i n e e r i n ga n d s c i e n c ea r e a s k e y w o r d s ：n e t w o r kp a r a l l e lc o m p u t i n g ；p v m ；0 b j e e t - o r i e n t e d ；p a r a l l e la l g o r i t h m s l i b r a r y i v 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所里交的论文是 我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经发表 或撰写过的研究成果，不包含本人或其他用途使用过得成果。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的声明，并 表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取 得的，论文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此 声明。 2 0 0 7 年r 月1 8 日 第一章绪论 第一章绪论弟一早珀t 匕 1 1 课题的研究背景和意义 随着计算机科学技术的发展，其应用领域也越来越广泛。虽然近几十 年来硬件技术的发展导致计算机的处理速度得到了迅速的提高，但在许 多高级应用领域内，对处理速度的要求仍不能得到满足。许多领域如能 源、气象、军事、医学、人工智能以及一些基础研究等，都需要快速而 有效的并行计算机来实现大规模的科学计算和数据处理。对并行处理的 需求极大地促进了并行技术的发展。网络并行计算就是在这种需求的 促进下出现和发展起来的。 网络并行计算系统是由多台同构或异构的计算机组成，通过网络互连 方式组合成的一个综合计算环境，系统结点可以是台式机、工作站、小 型机，还可以包括各种类型的大型机、巨型机，其规模可以小到几台计 算机、一个局域网，大可以到广域网。 网络并行计算具有广泛的应用前景，其主要优势在于：可以利用现有 的网络资源和计算机资源，构建简单，计算成本低；并且可以通过合理 的任务分配和负载平衡策略获得很好的性能效果；系统规模易于扩展， 能够满足计算性能和规模需求的增长。 网络并行计算迅速发展伴随着出现了一些支撑并行计算运行的系统 平台，其中具有代表性的、应用最广的是p v m 和m p i 。p v m 由于其源代码 可以免费得到，应用和研究都更广泛一些。 随着计算机软件的发展，程序开发工具的进步也日新月异，如一些可 视化开发环境v i s u a ls t u d i o 和函数库s t l 等。这些开发工具的发展在 很大程度上减轻了开发人员的负担，促进了软件技术的发展。开发人员 利用这些工具可以简便地开发出功能完善的应用程序。但是在并行程序 开发工具方面却相对落后，目前还没有较理想的开发工具。而并行程序 的开发与串行程序开发相比，具有一定的特殊性和复杂性。并行程序的 广东工业大学t 学硕十学位论文 分析与设计需要考虑各并行任务的协同和通信。并行程序的编写模式与 串行程序也有很大的差异，并且并行程序开发需要相应的并行平台的支 撑，需要调用平台提供的函数来完成数据的传送和处理。开发并行程序 比开发串行程序相对要难很多。 并行程序设计在开发平台方面发展的相对落后，已经影响到并行技 术的发展。因此，并行程序开发平台的研究和开发对网络并行计算的发 展是很有价值的。现在大部分的并行程序开发人员都是利用常用的串行 程序开发工具( 如v i s u ms t u d i o 等) 来进行并行程序的开发，由于这 些开发工具并没有专门针对并行程序开发的工具包，所以并行程序开发 的效率不高，难度也比较大。开发人员都希望有一个智能化高的、功能 强大的并行程序开发平台，可以简化并行程序的开发。这不仅能加快网 络并行计算的发展，而且能推动其他工程科学的发展。 1 2 国内外研究现状 国外在网络并行计算方面的研究要比国内先起步，北美和欧洲的在并 行环境和平台的研究走在最前面。美国伊万诺大学m u r a t e 教授领导的科 研小组一直从事机群工作环境方面的研究。美国田纳西大学和橡树岭国 家实验室进行了一个名为p v m p i 的研究项目，研究的目的是是否可以将 p v m 和m p i 的功能结合起来形成一个统一的编程环境p v m p i 。而德国的研 究机构则将今后的研究重点转向并行应用、并行编程环境、优化技术和 开发工具等方面”】。 美国麻省理工大学的l i n c o l n 实验室研究和开发了一个并行向量库 ( p a r a l l e lv e c t o rl i b r a r y ，p v l ) 。p v l 是具有面向对象特征的程序库， 为应用程序员提供一个高层次的、具有高性能、高可移植和高效性的应 用程序接口0 3 。 国内随着网络并行计算的发展，并行计算已经成为研究的热点。清华 大学的陆嘉和温冬婵等人对基于机群系统的面向对象并行程序开发环境 进行了研究，在可扩展机群系统上实现了面向对象的并行程序开发环境 p a r a o b j e c t 川。 2 第一章绪论 国家高性能计算中心的李庆华等人研究了面向对象的并行程序设计 环境框架，构建了一个基于p v m 的面向对象程序框架环境o o p v m 强1 。 信息工程大学的黄永忠等人也研究基于m p i 的并行开发环境，提出并 实现了一个可视化的并行开发环境p o v p e ，并且设计了一个面向对象的 并行程序设计原因s p c + + ”1 。 中南大学的胡志刚等人也在研究p v m 的开发环境，他们在p v m 平台的 基础上提出和开发了一个可视化的并行开发工具”1 。 中国科学技术大学的陈国良院士多年来一直从事并行计算的研究，从 并行体系结构、机群系统再到并行算法的研究，涉及并行计算的多个领 域，对并行数值算法的进行了深入研究。 华中科技大学的张建中等人也一直从事p v m 并行计算研究，他们提出 了一个基于负载信息收集和预测的动态负载平衡系统，系统通过b p 神经 网络进行负载信息的预测并根据预测来进行负载平衡。1 。 广东工业大学已经开发出应用于勘探地球物理的电法勘探数据网络 并行处理系统，并且已经构建了一个可视化的网络并行计算平台“”。 1 3 论文的研究目标、研究内容 网络并行计算的研究已经相当普遍，技术也比较成熟。目前并行计算 的研究很多都只是在应用上的研究，将网络并行计算应用到某个领域中。 这些在各个领域上的应用研究都是有较强的专业背景，各应用研究上的 联系很少。目前国内外对网络并行计算开发环境的研究相对较少，没有 出现过较理想的开发工具。并行算法的研究经过了很多年，特别是数值 并行算法的研究，已经很成熟。本文提出了一个网络并行计算的开发环 境，构造一个并行程序的开发平台，并且编写了一个面向对象的数值并 行算法库。通过平台能够简化并行程序开发的复杂性，降低并行程序开 发的难度，使并行程序的开发变得简单高效。这不仅有利于网络并行计 算的推广与普遍应用，而且还能推动其他工程学科的发展。 本课题研究的主要目标是提出并初步实现一个并行程序开发平台。开 发人员通过平台可以生成一些常用的并行程序基本框架，以及可以通过 广东1 = 业大学1 = 学硕士学位论文 平台进行面向对象和可视化的并行程序设计。 平台的主要功能有以下几点： 1 ) 初始化构建一个并行计算环境； 2 ) 通过并行程序生成向导生成并行程序基本框架； 3 ) 通过调用并行程序库进行面向对象的并行程序设计； 4 ) 用户可以通过开发环境中的并行类管理器进行可视化编程。 本文研究的是基于p v m 的并行程序开发平台，这涉及到计算机领域多 方面的知识，包括计算机网络，数据库，软件工程，并行数值算法，程 序设计理论等，要完成整个研究目标，主要的研究内容包括下面几个方 面： 1 ) 学习和研究p v m 开发环境及其编程模式 深入学习和研究p v m 开发环境的结构、原理，以及基于p v m 的并行程 序开发模式。分析各种模式的特点和差异，选择合适的编程模式，并分 析研究在该模式上进行并行程序开发的一般流程和方法。 2 ) 分析研究并行数值算法 分析研究常用的并行数值算法，如定积分计算、矩阵运算、线性方程 组求解等。分析算法在p v m 编程模式上的具体实现。分析研究将这些算 法封装到并行库中的具体实现方案。 3 ) 任务分配和负载平衡 分析当前常用的任务分配方法，包括静态任务分配方法和动态任务分 配方法。分析这两种方法的特点和具体实现。 4 ) 研究流行的开发环境 分析当前流行的开发环境，如v i s u a ls t u d i o ，c + + b u i i d e r 等。分 析研究当前并行开发人员常用的开发环境，选择合适的开发环境作为平 台的开发基础。 1 4 论文结构 本文一共分为五章。第一章为绪论，主要介绍课题的研究背景和意义， 以及国内外的研究现状；第二章对网络并行计算的体系结构和特点进行 4 第一章绪论 概述，并详细论述了网络并行计算的支撑平台p v m ；第三章讨论了基于 p v m 的并行程序设计，分析了基于p v m 的并行程序开发方法，讨论了两 种任务分配方法，并用两种方法分别做了实验，最后论述了面向对象的 并行程序设计，提出了三个基本对象；第四章给出了一个基于p v m 的并 行程序库，分析了一些常用并行算法，以及并行库的结构和特点；第五 章描述了一个可视化的并行程序开发平台，具体讨论了平台的设计与实 现。 广东t 业大学工学硕+ 学位论文 第二章网络并行计算及开发环境 2 1 网络并行计算概述 2 1 1 高性能计算的需求 自从世界上第一台电子计算机问世以来，计算机高速发展已经持续 了半个多世纪，计算速度已经提高了亿倍以上，它对科学技术以至整个 人类社会都产生了巨大的影响。根据著名的摩尔定律，平均每隔1 8 个月， 同样体积的集成电路中的晶体管数量就会增长一倍，性能也会提升一倍。 计算机和计算方法的进步极大地提高了人类的计算能力，从而引起了科 学方法论的巨大变革。近年来，在各种科学与工程领域中都逐步形成了 计算性学科的分支，如计算力学、计算物理、计算化学、计算生物学、 计算地震学，等等。计算在生命科学、天文学、医学、系统科学、经济 学、社会科学以及其他软科学中所起的作用也日益增大。在气象、核科 技、石油勘探、航空航天、金融、交通运输、密码学等国民经济与国防 建设的许多重要领域中，高性能计算已经成必不可少的手段。 推动高性能计算机发展的第一动力是科学技术发展对于高性能计算 不断增长的需求。高性能计算的需求领域包括科学和工程问题的大型科 学计算问题，这样的问题常需要对大量数据进行很多次重复计算以得到 有效结果。而且计算必须在合理时间内完成。在制造业领域，工程计算 和模拟如果可能的话必须在几秒或几分钟内完成。在设计环境中，如果 进行一次模拟需要两个星期才能得到结果，这通常是不可接受的。因为 只有模拟完成时间足够短时，设计者方可高效地工作。当系统变得更复 杂时，就需要增加更多的时间对系统进行模拟。有一些应用问题的计算 对时间由特定的期限，如气象预报，花两天时间来获取当地第二天精确 的天气预报将使得这种预报毫无疑义。某些研究领域，如对大型d n a 结 6 第二章阿络并行计算及开发环境 构建模以及进行全球天气预报均具有巨大挑战性问题。所谓巨大挑战性 闯题是指无法用当今计算机在合理的时间内完成求解的那些问题。显然， 解决这一类问题用l o 年的执行时间是不合理的。 高性能计算的应用水平已经成为衡量一个国家科技、经济和国防综 合实力的重要标志。早在1 9 9 1 年美国就提出了高性能计算与通信( h p c c ， h i g hp e r f o r m a n c ec o m p u t i n ga n dc o m m u n i c a t i o n ) 计划，其主要内容 是研制万亿次超级计算机、建设计算机高速通信网络和培养开发中的能 力和提高工业生产率，确保美国在高科技的优势地位和竞争能力。美国 提出h p c c 计划后，日本相继提出了真实世界计算计划，欧洲提出了万亿 次机计划。我国“8 6 3 ”高科技计划也将并行计算列为关键技术，高性 能计算国际问的竞争将愈演愈烈。 2 1 2 并行计算的提出 提高计算速度的种方法使用多个处理器协同求解一个问题，这种 方法实际上好多年来直在进行研究。在这种方法中，整个求解问题被 分为若干部分，然后每个部分各由一个处理器并行计算。编写这种形式 的程序被称为是并行编程。计算平台，即一台并行计算机，可以是专门 设计的、含有多个处理器的计算机或是以某种方式互连的若干台独立的 计算机。这种方法将显著地提高性能。基本的想法是，n 台计算机应能 提高n 倍的单机速度，不论当前计算机的速度为多少，可以期待求解问 题将以1 n 时间完成。当然这是一个理想情况，实际上很难达到。这是 因为求解问题经常不能完全分解为各个独立的部分，同时各部分之间必 须进行交互，包括计算中的数据传送和同步。尽管如此，仍可达到实质 性的改进，这取决于求解问题的并行度。对并行计算的要求永远不会终 止，这一方面是因为单处理器执行速度不断升级使并行计算机速度越来 越快，另一方面总是有一些具有巨大挑战性的问题，这些问题在当前计 算机上求解不可能在合理的时间被完成。 除了可使对现有的求解问题得到加速之外。多计算机多处理机的使 用常常可使一个更大的求解问题或更精确的求解问题能在合理的时间被 广东工业大学工学硕十学位论文 完成。例如，许多物理现象的计算涉及带将求解问题分成为离散的求解 点，电法勘探的电算技术包含着将电流场分为三维的求解格点。二维和 三维的求解格点出现在许多其他应用中。用多处理机求解时，常允许在 给定的时间内计算更多的求解点，从而获得更精确的解。一个相关的因 素是多计算机比单机有更大的总主存储器容量，从而使需要较大主存储 器容量的求解问题得到解决。 并行计算的发展基于人们在两方面的认识。第一，单机性能不满足大 规模科学与工程问题的计算需求，而并行计算机是实现高性能计算、解 决挑战性计算问题的唯一途径；第二，同时性和并行性是物质世界的一 种普遍属性，具有实际物理背景的计算问题在许多情况下都可划分为能 够并行计算的多个子任务。 现在的超级计算机和高性能计算机必定是并行机，虽然它们可能采 用了不同的并行处理技术。这是因为串行计算机受到了主频、集成电路、 组装工艺、冷却等方面的限制，计算速度难以得到令人满意的提高。也 是因为人们对计算能力的需求是无止境的，尽管单机速度也一直在提高， 将它们构成多机并行系统就能获得更快的速度。 2 1 3 网络并行计算的出现 在各个工程领域提出的高效的计算方法中，都有一个共同特点，那就 是计算空间大。但是将这些优秀高效的计算方法真正应用于解决实际问 题并行之有效的并多见。究其原因，其主要因素是这类问题需要解决大 型代数方程组，需要大型并行机来进行计算，但是除了少数计算机大户 ( 石油、天气预报) 外，许多用户由于工业资金的不足和不经常使用并 行计算机，因此就不具备昂贵的并行计算机，无法构造一个并行计算的 环境；同时，这些优秀的算法在应用领域中借助于串行计算机实现的时 候又不能将其优越性充分反映出来。 网络并行计算就可以为广大用户解决这一窘迫的问题。网络并行实质 上就是利用互联网上的计算机资源实现大问题的并行计算。它由计算机 机群系统组成，也就是由高性能网络或局域网物理地互连的全体计算机 第二章网络并行计算及开发环境 结点的集合。典型情况下，每个计算机结点是一台s m p 服务器、一台工 作站或是一台p c 计算机，结点可以是同构的，也可以是异构的。计算机 数目一般为几个至几十个，支持控制并行或数据并行的开发。每个结点 上都有完整的操作系统、网络和用户界面，都可作控制结点或运算结点， 网络并行计算的优点是投资少、见效快、灵活性强等。随着计算机网 络的发展，许多单位都具备了局域网，故不需要在计算机的硬件和软件 方面再投资，就可以搭建起可媲荚一台并行计算机的计算环境，从而满 足科学计算的需要。网络并行计算最近几年的表现引人注目，由于具有 出色的性价比、灵活性和良好的并行处理能力，除了广泛作为研究课题 外，在各个行业的应用发展也很快。 2 2 网络并行计算的体系结构 网络并行计算系统是由多台同构或异构的计算机组成，通过网络互连 方式组合成的一个综合计算环境，系统结点可以是台式机、工作站、小 型机，还可以包括各种类型的大型机、巨型机，其规模可以小到几台计 算机、一个局域网，大可以到广域网。 网络并行计算系统从结构和结点的通信方式来看，它属于分布式系 统，主要利用消息传递方式实现各主机之间的通信，通过建立在现有操 作系统之上构建虚拟环境，并通过特定的并行编程环境利用消息传递方 式实现各主机之间的通信。由建立在一般操作之上的并行编程环境完成 系统的资源管理及相互协作，同时也屏蔽工作站及网络的异构性，对程 序员和用户来说，网络并行系统是一个整体的并行系统。网络技术和并 行编程环境的发展使得网络并行系统这一并行处理系统形式成为当前研 究的热点。目前已实现和正在研究中的网络并行系统大多采用现有工作 站和通用l a n 网络，这样既可以减少设备硬件的投入又可以缩短开发周 期。大多数网络并行系统的并行编程环境是建立在u n i x 或w i n d o w s 操作 系统之上，尽量利用现有的支持系统，减少整个并行系统的开发和维护 费用。图2 - 1 是当前常用的网络并行的体系结构。 9 广东工业大学工学硕士学位论文 臣圃 匪圃匝圃 结点机 结点机 网络设备网络设备 高速网络( 以太网，a t m 等： 图2 - 1网络并行系统的体系结构 2 3p v m 开发环境 2 3 1p v m 的特点 p v m 支持用户采用消息传递方式编写并行程序，计算以任务为单位， 一个任务就是一个系统进程，每个任务都有一个任务标识符。p v m 支持 在虚拟机中自动加载任务运行，任务间可以相互通信以及同步。在p v m 系统中，一个任务被加载到哪个结点上去运行一般来说对用户是透明的 ( p v m 允许用户指定任务被加载的结点) ，这样就方便了用户编写并行程 序。归纳起来p v m 有如下特点阳1 ： ( 1 ) p v m 系统支持多用户及多任务，多个用户可将系统配置成相互重叠 的虚拟机，每个用户可同时执行多个应用程序。 ( 2 ) 易于编程。p v m 支持多种并行计算模型，用户使用p v m 提供的函数 库可以进行并行程序或分布式程序的设计工作，使用传统的c c + + 语言。 ( 3 ) 系统提供了一组便于使用的通信原语，可实现一个任务向另外一个 或者多个任务发送消息，以及阻塞和无阻塞收发消息等功能。系统还实 现了消息缓冲区的动态管理机制，每个消息所需要的缓冲区由p v m 运行 时动态申请，消息长度只受结点上可用存储空间的限制。 1 0 第二章网络并行计算及开发环境 ( 4 ) p v m 提出了任务组的概念，可以把一些任务组成一个任务组，一个 任务可以属于多个任务组，而且可以在运行时动态改变。 ( 5 ) 支持异构计算机联网构成并行虚拟计算机系统，且易于安装、配髯。 ( 6 ) 具有容错功能，当发现一个结点出现故障时，p v m 会自动将它从虚 拟机中删除。 2 3 2p y m 的组成 p v m 系统环境由两个部分组成，其中一个部分是p v m 后台守护进 程p v m d ，它通过t c p i p 协议控制各进程之间的通信。在p v m 中，主 p v m d 需要在本结点启动一个独立的h o s t e r 进程，并由h o s t e r 进程负责 启动其它结点上的从p v m d 。另一部分为用户可调用的p v m 函数库 l i b 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 d 的工作。监控台可以建立 p v m 的环境，启动、检查或杀死本地任务，收集任务的输出，打印到屏 幕上，并接收任务事件消息。它可以连接到任意的p v m d 上，而且可以 同时存在多个监控台。如果监控台启动时，没有p v m d 在运行，则监控 台自动启动一个p v m d ，并且与它联接。实际上，监控台本身就是一个 普通p v m 任务，通过与p v m d 通信获得虚拟机中其它任务的运行、通 信状态以及虚拟机的配置信息。现在，用户可以使用x p v m 或者w p v m 。 这两个都是p v m 监控台的图形化界面应用程序，它借助于窗口界面以 图形的方式进行实时显示p v m 信息。 2 3 3p v m 虚拟机结构 从软件的角度看，一个完整的p v m 虚拟机由三部分组成：p v m 守护进 程p v m d ，p v m 接口库和p v m 控制台。p v m d 是整个p v m 的核心，驻留在构 成虚拟机的每台实际计算机上，完成整个虚拟机的维护、任务的控制、 广东工业大学1 ：学硕七学位论文 消息的传递等工作。p v m 接口库则包含了用户可调用的p v m 库函数，如 消息传递、任务创建、任务间协作同步及虚拟机的动态配置等，所有p v m 应用程序都必须和该库链接。p v m 控制台则作为一个特殊的p v m 任务为 用户提供了用于虚拟机管理、任务管理等功能的交互式界面。它们一起 为用户提供了在松散耦合的网络上进行并行计算的能力。 p v m 虚拟机通过p v m d 来实现，每个p v m d 负责管理p v m 并行应用中的 部分任务，各个p v m d 之问进行通信以协同管理整个虚拟机，并协同完成 任务之间的消息传递。 每个p v m 虚拟机都有一个主p v m d ，也就是p v m 虚拟机构建过程中的 第一个p v m d ，其他的p v m d 由主p v m d 依次启动，并称为从p v m d 。相应的， 主p v m d 所在的主机叫主结点，从p v m d 所在的主机称为从结点。主结点 和从结点一起构成了p v m 虚拟机1 。图2 2 给出了一个p v m 虚拟机的结 构示意图。 图2 - 2 p v m 虚拟机结构示意图 f i g u r e2 - 2t h ea r c h i t e e l u r eo fp v m 2 3 4p v m 通信机制 p v m 任务之间可以利用p v m 提供的通信函数进行消息传递，包括点对 点通信和群集通信。p v m 通信基本上都采用了基于消息缓冲区的方式来 实现。p v m 缓冲区分为系统消息缓冲区和用户消息缓冲区。一个p v m 任 1 2 第二章网络并行计算及开发环境 务可以有多个用户消息缓冲区，但只能有一个系统消息缓冲区。 为了实现任务之间的数据发送与接收，如图2 3 所示，需要进行以 下步骤： 1 ) 发送方把数据放入到发送缓冲区，并打包成指定格式的消息； 2 ) 发送方调用p v m 函数库中的通信函数，把该消息发送到接收方的接 收缓冲区： 3 ) 接收方调用p v m 函数库中的通信函数，从自己的接收缓冲区接收 消息，并解包出数据。 甲 q p 、p v m 通信函数 ( 接收缓冲区) 【发送缓冲区) 发送方接收方 图2 3p v m 点对点通信 f i g u r e2 - 3p 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 系统环境中，结点机器的p v m 守护进程( p v m d ) 之间通过用户数 据报协议( u d p ) 的s o c k e t 进行通信，守护进程和它的用户任务间的以及 两个用户任务间的通信是用t c p 协议实现的。示意图如图2 4 所示。 用户任务是调用p v m 库函数请求p v m d 提供某种服务。而对于系统设 计者和管理员来说，了解系统的底层通信机制有助于设计和分析系统的 性能以及找到如何改善系统性能的途径。 广东t 业大学下学硕十学位论文 p v m 系统环境 $ u d p 厅函高 t c p l 用户任务 结点机 图2 - 4p v m 通信机制 结点机 2 3 5w 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 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 ，设置为l i s t e n ； ( 3 ) 在m a s t e r 主控机上的h o s t 框中填入要加入虚拟机系统的计算机名 1 4 茎三耋堡垒兰堑兰塞垒垩茎堑丝 称，再填入用户名和密码，点击a d dh o s t 按钮，就可把这台主机加入 p v m 系统里来。如图2 5 所示。 闰2 - 5w p v b l 控制台界面 f i g u r e2 - 5 t h ec o n s o l eo fw p v m 广东t 业大学t 学硕士学位论文 第三章基于p v m 的并行程序设计 3 ，1 并行编程模式分析 3 1 1p v m 的编程模式 p v m 是属于基于消息传递的并行开发环境，它提供了两种编程模式。 一种是主从( m a s t e r s 1 a v e ) 模式，另一种是s p m d ( s i n g l ep r o g r a m m u l t i p l ed a t a ) 模式。 主从模式：其基本思想是将一个待求解的任务分成一个主任务( 主进 程) 和一些子任务( 从进程) 。主进程负责将一个任务分解成一些子任务； 然后负责收集各子任务的求解结果；最后汇总得到问题的最终解。各子 任务( 从进程) 接收主任务发来的消息数据；并行进行各自计算；向主任 务发回各自的计算结果。 s p m d 模式：所有进程都执行一个程序，只是计算的数据不同。其中， 有一个进程在完成自己的计算任务的同时负责非计算的功能，如收集、 显示结果等，这个进程通常是应用程序初始时手工启动的。 当p v m 的工作模式是主从模式的时候，第一台启动p v m 的机器成为 主机，其他的由监控程序或用户自己启动的机器成为从机。它们共同形 成一台并行虚拟机。在并行虚拟机上，用户运行一个p v m 应用程序由分 布于各个结点机上的多个进程构成，每个进程称作一个任务( t a s k ) ，分 配一个唯一的任务标识符t i d ( t a s ki d ) 。t i d 形成了p v m 统一的、虚拟 的、清晰的任务管理空间，多个任务通过互相识别t i d ，在网络上发送、 接受消息，协作完成计算任务。主从模式的结构图如图3 - 1 所示。 第二章基fp v m 的并行程序设计 图3 - 1i h a s t e r s 1 a v e 模式结构图 3 1 2 主从结构的编程模式 m a s t e r s l a v e 是一种p v m 应用程序最常用编写模式。在这种模式中， 一个并行应用软件有两个程序组成，一个是m a s t e r 程序，运行在主结点 上，一个是s l a v e 程序，运行在所有的计算结点上“”。 m a s t e r 程序的功能是： ( 1 ) 申请和释放结点机；启动s l a v e 程序； ( 2 ) 处理用户界面和i o ； ( 3 ) 进行数据划分和任务分配； ( 4 ) 广播计算数据到各个结点机，并从各个结点机接收部分结果； ( 5 ) 整合各结点机返回的结果，输出最终结果。 s l a v e 程序的功能是： ( 1 ) 从m a s t e r 程序接收计算数据； ( 2 ) 计算和识别出本机的计算任务； ( 3 ) 完成计算任务； ( 3 ) 将计算结果返回m a s t e r 程序： 下面将详细介绍m a s t e r s l a v e 的编程模式，并列出需要使用的主要 函数的功能和用法啼1 。 m a s t e r 程序的一般编写步骤 广东工业大学工学硕十学位论文 ( i ) 获取本进程的任务标识符； m y t i d = p v m m y t i d ( ) ： 函数在程序开始的时候调用，返回调用进程的任务标识符。任务标识 符是由本地p v m d 赋予的一个3 2 位正整数，这个整数的3 2 位分为几个域， 分别存放调用进程的不同信息。当值小于零的时候表示出错。 ( 2 ) 启动从结点上的s l a v e 进程； n u m t = p v m s p a w n ( c h a r * t a s k ，c h a r * * a r g v ，i n tf l a g ，c h a r 宰w h e r e ， i n tn t a s k ，i n t 宰t i d s ) ： 函数启动若干个从结点机上的p v m 进程，每个结点机上都执行t a s k 可执行文件( t a s k 是s l a v e 程序的文件名) 。函数返回多个参数，启动 的进程数量n u m t 、任务标识数组t i d s 等。 ( 3 ) 将任务分割成若干个子任务 任务分配的方法主要有两种：静态任务分配和动态任务分配方法。开 发人员可以根据需要选择合适的分配方法。 ( 4 ) 将一些必要的数据传输给各台结点机。 我们需要在具体计算开始的时候将一些虚拟机的基本消息广播到网 络上的其他计算机，主要包括：虚拟机的结点机数量，结点机的任务标 识数组，以及各台结点机的计算任务数组。 在发送数据前我们需要对发送缓冲区进行初始化， p v m _ i n i t s e n d ( i n te n c o d i n g ) ： 参数e n c o d i n g 指定打包数据时采用的格式转换方法，主要包括三种： p v m d a t a d e f a u l t ，p v m d a t a r a w ，p v m d a t a i n p l a c e 。一般我们会采用第一 种p v m d a t a d e f a u l t 。 打包使用封装数据函数p v m p k 0 ，用于把发送数据迸行打包送入 发送缓冲区中。 对于打包不同的数据类型，p v m 提供了不同的封装函数， i n ti n f o = p v m p k b y t e ( c h a r * x p ，i n tn i t e m ，i n ts t r i d e ) i n ti n f o = p v m p k f l o a t ( f l o a t * f p ，i n tn i t e m ，i