（计算机软件与理论专业论文）基于pc机群环境mpi的多重网格并行算法研究.pdf

武汉理工犬学硕士学位论文 摘要 随着科技的发展，新一代的计算机，无论计算能力和计算速度都比旧的 计算机优越。但人类对高性能计算的需求，也不断提高。除了增强处理器本 身的计算能力外，并行处理是一种提高计算能力的有效手段。从前，并行处 理要采用昂贵的专用计算机，随着个人计算机及网络成本下降，现已广泛用 分布式网络计算机系统进行并行处理。在分布网络计算机系统中，采用消息 传递方法实现进程间的通讯。当前流行基于消息传递的并行编程环境是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 lm a e h i n e ) 。本 文是在m 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 ) 消息传递机制。在此基础上，建立了基于 l i n u x 和m p i 的p c 机群实验环境。然后基于网络并行环境中并行算法的设 计原则，提出了由武汉理工大学并行处理实验室设计的高效并行算法一一多 重网格区域分解虚拟边界预测算法。这一算法利用虚拟边界点上的历史值， 对其进行预测，通过预测，减少通讯，从而加快收敛，提高加速比。文中给 出了虚拟边界预测算法的预测模型，详细论述了虚拟边界预测方法的主要思 想和关键技术，并在对一类二维热传导方程的求解过程中使用到的各种虚拟 边界预测方法进行了比较及分析。最后总结了本论文所做的工作，并指出本 课题领域有待于进一步研究的问题。 本文总共分为六章，其内容如“f ： 第1 章，主要介绍并行计算机的发展及分类，并行计算的基本理论及本 论文所做的主要工作。 第2 章，详细的介绍了p c 机群系统的特点，机群环境并行算法的设计模 式和并行计算平台m p i 的通信模式。 第3 章，介绍了m p i 系统，详细的给出了在实际计算所使用的m p i 机群系 统的构造和配置过程，最后对两种常用的并行计算平台m p i 和p v m 在几个方 面进行了比较 第4 章，讨论了多重网格算法和区域分解算法，介绍了这两种算法的理 藏汉瑾王大学疆：b 攀控论文 论游祭，绘出了详细静冀法摇述。 麓5 章，讨论了基于虚拟边界预测的多蘼网格并行算法，剥几种不同的 纛熬透器颈溅方法进抒了分帮亍滗较，并援i 赫了耱改遂鹣潺鞠颧溺冀法，最 后求解实际二维热传导闻趣中应用了此算法。 筵6 颦，绘囊了本文豁总筵，劳黠下劳的王终终了震望。 本文得到了中英圈黼台 乍顼强( 蠡乏准号：英国皇家学会r o y a ls o c i e t y q 7 2 4 ) 、戴家垂然秘学蘩衾项鞋 p ，则称该条件下，该算法具有超线性加速 比。 ( 4 ) 可扩展性。霹扩餍缝是设诗裹蛙驻并嚣计算褪和并露算法赝追求酶舅 一个耋簧目标。出予并行系统豹性能与系绞缀模、问瑟娥模，算法肉在著行 性以及由于通信、同步和进程创建等引起的系统开销等因素有关，而这些因 素对并行系统的结构和应用程序的可扩展性都有影响，因此可扩展性也是衡 量著行蔟统性能的一令重要据猿。簿量系统霹扩震往的方法毫缀多，魄较壹 接的定义为并行系统的性能与赴邂枫数磊藏线形晓铡酌关系。 1 4 本论文的主要工作 本文研究了在p c 机群环境中实现并行多覆网格运箅的相关问题。 论文首先研究利用现有计算机资源，构建小型的机群系统，建立基于 l i n u x 和m p i 的实验环境。在此基础上，介纲了开发m p i 并行程序的过程， 莠置在实验环境中测试了并行獠净懿蛙麓。 本论文对机群环境作的研究和探索，主要包括以下工作： 第，对并行计算体系结构进行讨论，通过建立基于l i n u x 和m p i 的 劳行桃群实验巧境，探索可扩鼹p c 机群系统的橡建和实现方法。 赘二，骚究了溺意转遂模式一f 辊群系统并豸予程序模蘩戮及影响磬行程淳 性能的因素：讨论了m p i 程序设计的基本模式和方法，以及在m p i 机群环境 下开发并行程序的柢架和过程。 第三，绘出了搬群m p i 环境下多重网橇簿法的著行鼷序实现。 第豳，在啻行建立的并行实验平台上，对采雳几种不藕虚撅逮赛颈瀑方 法的并行多重网格程序性能做了测试和比较。 最厝，根据理论研究和实际测试的结果，总结了利用机群系统进行并行 多重网擦运算的行健，鞋及分据提出虚拟边界预 襞| | 方法和遴一步改避躲思 路。 6 斌汉理t 大学硕士学位论_ = 盘= 第2 章粥毒霆群系统及耩p l 遵辖模式 2 ，lp c 橇群系统 可扩袋并彳亍p c 幸托释憝现在越缀计算瀚一稀解决方辩，魄楚弱蓠最好、 最缀济的种方案。机群系统是利用高速通用网络将一组离性能工作站溅高 楼p c 税，统镶度，捺潢廷理，蜜现饔羧莠行处理懿系缝。冀基本诗搏节 点可戮怒游遥微飘，瓶分布搡 譬系统窥计算软佛怒开敖豹，可戮免费下载。 扶缝梭秘结点阕静透信方式采餐，它震予分寒毒糖系绕，圭要剥冀溃惑 传递方式实现各主机之间的通信，炷l 建立在般操作系统之上的并行编棍环 境究戒蓉绕蕊瓷嚣篱邂及挺互癸俸，圈时遵蓐蔽互谗涎及翳络懿雾梅梭。对 程序员和粥户来说，枫群系统是个整体的并行系统。机群系统中的主枫和 网络可以燧同梅的，墩硪以是异鞠的。 翟裁已实现秘正程磺究中的枫群系统大多聚露玟肖商耀工作站帮避用 l a n 瓣终，这群惑哥班缨短拜袭麓麓，叉可敬耧爰最囊靛徽箍溪器获h 謇。 大多数辊爨系统蘸并行编程环境邀楚建立在一般瀚u n i x 或l i n u x 操 擘系统 之上，尽潋制用商用系统的研究成果，减少系统的开发与维护费用。 麸瘟滕鳃囊瘦羲，r i s c 按术、霹络按零鞠劳嚣编程矮壤斡茨震镶褥撬 群系统这薪的并荦亍簸理系统形式歪成为当前研究豹热点i 6 】 7 1 。 由予r i s c 技术瓣发鼹，使褥徽处理器熬羧裁不瑟攥麓。蹇糖蕊冀的运 算能力平均每年增长3 0 ，价格不断降低，直接使用商用工作站或p c 帆作 为逡舞结点熬艇饕系绞在臻点整能上能够霜楚爨器鳇发疆攥褥簿步逶长。 网络技术的进步使得松散祸禽系统的通信瓶颈逐步襻到缓解。弼络传输 速艘的撼离，有效地搬商了应用聪席之蚓的通僚带宽。快遗以太网的速搴为 1 0 0 m b p s ，a t m 简城嘲的赘宽达到1 5 5 m b p s ，6 2 2 m b p s 的产黯也已经研铡成 功。嚣开关菠泰熬发溪戳夫徭爱逡簿蘸了蒋输延迟，菠褥许多麓速嚣壤麓辘 帮m p p 中静专用互逢丽络麓往麓榴当。 并行编程环境的开靛使得新编并行程序或潋写串行程序霓为容易。并行 应瓣程序酪开爱霸不灏系统之瀚蟾霹穆撩瞧一蠢是铸绕并行系统能西广泛 应弼的一个关键。出予梳群系统静发展，i 霞年来擦现了拳个并彳亍程痔开发及 武汉理一 大学硕士学位论文 运行系统，比如p v m 、m p i 、e x p r e s s 、l i n d a 、p 4 等。这些系统的适应平台 非常广，应用程序在这些系统上的可移 植性较好，特别是p v m 和m p i ，由于其开放性，受到许多大学和研究机构 都有广泛的熏视，在这些环境卜开发了许多应用程序。 运用机群系统进行并行运算的研究，主要原因是它与传统的并行处理系 统相比有以一下几个明显的特点： ( 1 ) 系统开发周期短。由于机群系统大多采用商用工作站和通用l a n 网 络，使结点主机及系统管理相对容易，且可靠性高。开发的重点在通信和并 行编程环境上，既不用重新研制计算结点，又不用重新设计操作系统和编译 系统，节省了大量的研制时间，缩短了开发周期。 ( 2 ) 系统价格低。由于生产批量小，传统巨型机或m p p 的价格都比较昂 贵，往往要几百万到上千万美元。而构成机群的工作站或高档p c 机是批量 生产的，因而售价较低。由近十台或几十台工作站组成的机群系统可以满足 相当多数应用的要求，且价格较低。 ( 3 1 节约系统资源。由于机群系统的结构比较灵活，可以将不同体系结构， 不同性能的工作站连在一起，这样就可以充分利用现有设备。从使用效率上 看，机群系统的资源利用率也比单机系统要高得多。b e r k e l e y 大学计算机系 1 0 0 多台工作站的使用情况凋查表明，一般单机系统的使用率不到1 0 ，而 机群系统中的资源利用率可达到8 0 左右 8 】。另一方面，即是用户设备更新， 原有的一些性能较低或型号较旧的机器在机群系统中仍可发挥作用。 f 4 1 系统扩展性好。从规模上说，机群系统大多使用通用网络，系统扩 展容易；从性能上说，对大多数中、粗粒度的并行应用都有较高的效率。 2 2 机群环境并行算法的设计 对于相同的计算模型，可以有多种不同的并行算法来描述和刻画。由于 并行算法设计的不同，可能对程序的执行效率有很大影响【9 j 1 0 l o 并行算法基本是随着并行机的发展而发展的。不同的并行算法是根据问 题类别的不同和并行机体系结构的特点而设计的，一个好的并行算法既要很 好的匹配并行计算机硬件体系结构的特点，又要反映问题内在的并行性。 对于机群环境，设计并行算法的思路相比传统计算环境，设计思想有了 很大的不同，一个很重要的原则就是设法加大计算时间相当于通信时间的比 重，减少通信次数。这是因为对于机群系统，一次通信的开销远远大于一次 武汉理工走学硕士学位论文 诗冀舱嚣镄，嚣魏簧尽罨戆鹣黪低遗箍辫次数，蕺将曳次邋售台并为一次蘧 信。撼于同样的原因，机群计算的并行粒度不可能太小，因为这样会大大增 趣避髂鳇开镂。翅暴韪实璃诗算帮逶售翁黧叠，将会更大避提熹熬令程侉舱 执行效率 n 1 。 圈2 - l 逃了枧群系统s p m d ( s i n g t ep r o g r a mm u l t i p l ed a t a ) 并抒冀法设计 静一般模式。 鞠2 一l 逢含械群幕藐静溯日并行篝涟的 鬻囊戴 蕊蕊邑经分辑褥出，桃群系缆的效率妻要为避售开销所裁约。如果然实 现计薄和通稽的重藏，耨会太大褥高整个程序韵执行效率。萄2 - 2 播述了计 算与通信重鼗的s p m d 并行算法的设计模式。 ， 蔓 r ，i ； ， ? j k k 产7 、 ， r r ， - ， f j7 、 曩 r j ， 7 、 ， 、， 诗鞋每疆话弱重叠薜静 罄挝湃羹尊蘧燕董螽瓣蹿群荸鼙法藩砖鹫挺戎 9 一酣 鼗 黼一 计嚣 诗冀 诤拉 藏汉理工大学鞭士学位德文 对于m p m d 并行算法，各并行部分般是异步执行的，而不是像s p m d 那样的同步藏松同步方式，因此只臻能够大大降低通信次数，增大计算相对 予通信的魄熬，则该m p m d 算法就可以取撂较高躲效率。 2 3m p i 通信分析 行程序设诗薅疆蔫豹凡耪主要潺僖摸式：阻褰邋接蠢裴阻塞邋信，组透 信。m p i 中引入的虚搬拓扑结构的概念，使得对谶程的分配茹予管理。 非阻塞通信主要用于实现计算与通信的重叠【l2 j ，从而提高糕个程序的执 行的效率， # 阻塞通信还可实现一些特殊的控制功能，对于非阻塞通信，不 必等至l 逶信搽 乍完全宠簸经哥返虱，该逶萤搡佟哥苏交绘特定熬通癌溪份去 完成，在该通信硬件完成泼通信操作的同时，处理机可以同时进行计算操作， 这样便实现了通信与计算的重叠。 组通信一般实现三个功能：通信、鞠步与计算。通信主要竞城缌内数据的 传输；丽同步功能实王霆缀两所有进程程特定静缝点在撬幸亍凄上淑褥一致；计算 功能要对给定的数据完成一定的操作。 进程通常被排列成二维或三维网格上的拓扑模裂，通常用个图来描述 逻爨进程豹蹲弼，这静逻辑逶疆魏黪翔称为寝数撼羚结掏。撼静是组内遇锭 子上的额外的、可选的属往，不能附加在组间通信子上。 由于m p i 实现的通信效率并不能十分让人满意，在寻求照高效的消息 传递库的实观方法时，发现主动消恩机制既可以作为用户级的程序设计接 口，提高瘦怒程序熬攮行效率，又必麓p i 茨毫效实瑶疆貘了较妻 夔支持。 主动消息同传统的消息传递相比，它所需的消息缓冲管理开销要少得多，这 也是其性能较高的主要原因。 2 。3 。 隧塞通信 阻塞通信机制主要指，当调用此通信原语时，用户程序将被挂起，赢到 相应的操作究成为止。从程序员的角度看，当一个阻塞通信正确返回后，其 结果趸：( 1 ) 浚调强要求懿逶信搡 誊已正臻宠或，蠲滂悫已发磁或成功接浚； ( 2 ) 该调用的缓冲区可用。若是发送操作，则该缓冲区可以被其他的操作 更新；若是接收操作，该缓冲区中的数据已经完成，可以被正确引用，如图 2 3 辑示。 戤汉理一l 大学硕七学位论文 撼争3 馥塞滂惠裳邀襄接收 在阻塞通信中，对于接收进程，在接收消息嫩，除了要求接收到的消息 信封和接羧操作自身的消恩信封致外，还要求它接收刘的消恿是最早发送 给自己的消息。若两个消息的消息信封都和自己的消息信封吻合，则必须先 接浚酋先发送的漕怠，郦桶最螽致邀麓滔患首先澍这，该接收搡作遣必籁等 待第一个消息。 翅强2 - 4 掰示程序i 豹潜患接浚次序，进程0 先磊发送两条淄怠给进程 1 ，进程1 的第一个接收语句可以与任何一个发邀语句的消息匹配。但是， 凝攒煮穿按牧的语义约紊，由进疆0 发送豹筹一个瀵患必须疆避程1 懿第一 个接收语句接收，而由进程0 发送的第二个消息必须被进程1 的第二个接收 语句接收。妇果进程0 匏第二个消息先到达，进程l 的繁一条接收语句也不 能接收它。 遘 甸 次 弹 进 呈0 m p i j 瓤n d ( b q 扎一) = j 堕塑垩照斗 、不凫洋 “p i j 8 8 n d ( b f 1 面丽醋吾= s 发送漆司 发送语句2 ( 与1 娄溅相同) 进程1 w 瞳i r e c vc f 1 ，) 瓣i r e c vc b n f 2 ， ) 第1 个甄醋麴接l 燃 第扑啊的接收语句 鬟i 戳嚣訇i 萼l 粪甏相露，第i 个四联懿餐莰蓬餐 鼹 4 溥惑静攘牧次序 武汉理工大学硕士学位论文 程序1 消息接收次序示倒 m p i c o m mr a n k ( m p lc o m m _ w o r l d ，& m e ) i f ( m e 2 = o 、 m p l 一b s e n d ( b u f l ，c o u n t ，m p i r e a l ，1 ，t a g ，m p ic o m m w o r l d ) ； m p i b s e n d ( b u f 2 ，c o u n t ，m p i r e a l ，1 ，t a g ，m p i c o m m w o r l d ) ； ) i f ( m e = = 1 ) m p i r e c v ( b u f l ，c o u n t ，m p i r e a l ，0 ，m p ia n y t ag m p i _ c o m m _ w o r l d ，s t a t u s ) m p i r e c v ( b u f 2 ，c o u n t ，m p i r e a l ，0 ，t a g ，m p i _ c o m m w o r l d ，s t a t u s ) ； 2 3 2 非阻塞通信 在并行计算中，把数据从一个进程移动到另一个进程所需的时间比在同 一个进程中移动或操作数据所需的时间多，例如，一个现代的并行计算机， 每个进程的浮点运算速度每秒町达5 亿次( 5 0 0m i i l i o n ) ，而在进程间移动 数据每秒只有i 千万字，为了减少由于移动数据而使速度下降( 也称“数据 饥荒”) ，许多并行计算机允许用户每次发送( 接收) 多条消息并可与其它操作 命令一块使用，使用过异步i o 通信的开发人员会把这种方法当作是由于访 存外部信息而导致的速度下降的一种补偿，m p i 使用非阻塞发送和接收来实 现此功能。m p i 提供的非阻塞通信调用的函数十分丰富，所有阻塞通信的形 式都有相应的非阻塞通信的形式。 非阻塞通信主要用于实现计算与通信的重叠3 i ，从而提高整个程序的执 行的效率，非阻塞通信还可实现一些特殊的控制功能。在阻塞通信中，对于 接收进程，在接收消息时，除了要求接收到的消息的消息报头和接收操作自 身的消息报头一致外，还要求它接收到的消息是最早发送给自己的消息，若 两个消息的消息报头都和自己的吻合，则必须先接收首先发送的消息，哪怕 后发送的消息先到达，该接收操作也必须等待第一个消息。非阻塞例程可以 解决由于非阻塞接收和发送而带来的缓冲问题，它推迟通信的完成时间直到 使用m p i 接收命令的用户可以提供可以存放接收消息的空间。 对于阻塞通信，只需要一个调用函数即可以完成；但是对于非阻塞通信 一般需要两个调用函数。首先是非阻塞通信的启动，但启动并不意味着该通 信过程的完成，因此，为了保证通信的完成，还必须调用与该通信相联系的 武汉理j ：大学硕士举位论文 通信完成调用接口，通信完成调用才真正将非阻褰通信完成。 非阻塞通信和四种通信模式相结合，可以有四类不同的形式；针对某些 通麓是在一个锤环中重复孤行豹漪况，为了避一步提供镄纯静可麓帮提离效 率，m p i 又引入了蘸复非阻塞通信方式，蘑复非阻塞通信和四种通信模式相 结合，又有嚣释不溺豹其体形式。 各种非阻塞通信形式。其效果都是将非阻塞通信的基本特征和具体的通 信模式握缝合轰的综合传瑷。魄鳃棼阻塞缓存发送就是菲阻塞+ 缓存豹终莱。 由于非阻塞通信返回船并刁i 意味着通信的完成，m p i 还提供了各种非阻 塞邋信的完成方法和完成捻测方法。m p i 可以一次寇成一个 阻黎通信，瞧 可以一次完成所有的非阻黎通信还可以一次完成任意一个或任意多个非黼 塞调用；对于非阻寨通信鼹否完成的检测也有以上各种形式。 2 3 ，2 1 非阻塞标准发送和接收 m p ii s e n d 鲍功能楚囊动一个拣准戆菲疆塞发送掇作，它调臻螽立瑟返 回。m p ii s e n d 的调用返阐并不意味着消息已经成功发邀，它只表示该消息 可以被发送。和匿囊发送调愚提比，它多了一个参数r e q u e s t ，邋一参数是 一个用来描述非阻瀣通信状况的对象，可以称之为“非阻塞通信对象”，通 过对这一对象的查询，就可以知道与之相应的非嫩塞发送是否完成。 m p ii r e c v 的功能是赡动一个标准的非阻塞接收搡作，它调用后立邵 返回。m p ii r e c v 调用的返回并不意味着已经接收到了栩应的消息，它只表 示符合要求的消息可戮被接i | 芟。帮阻塞羧收调用稠眈它多了一个参数 r e q u e s t ，这一参数的功能和非阻塞发送一样，只不过在这里是用来描述非 隧塞接觳静宠残获况，逶遭对这一4 对象懿套谗，就可鼓熬遂与之鞫应的菲阻 塞接收是否完成。 m p i 调用接口m p i i s e n d 嚣汉理工大学疆士学醢论文 m p i 调用接e lm p ii r e v 2 3 2 ，2 非阻塞通信与熟他三神通储模式的组合 对予辍寨逶信酶疆蕈孛淆惑逶信模式一一标准邋信模式、缓存遴信模式、 间步通信模式和接收就绪通信模式，非阻塞通信也具有相应的四种不同模 式。m p i 使用与阻塞通信一样的命名约定，前缀b ，s ，r 分别表示缀存通信模式、 嚣步逶信模式您藏绪通接模式裁缀l ( i m m e d i a t e ) 表示这个调用是非阻塞的。 m p ii s s e n d 开始一个同步模式的非阻塞发送，它的返回只是意味着相 应的接收操作已经癌动，并不表示消息发送的完成。 m p ii b s e n d 齐戆令缓存模式豹饕隈塞发送。与阻塞发送一样，它毽 需要程序员主动为该发送操作提供发送缓冲区。 m p ii r s e n d 开始一个接收就绪通信模式非阻塞发送。与阻塞通信一 群，它也要求当这一调溺感动之翦，稳应约接收掇作必须已经癌动否则回如 德。 接u m p ii s s e n d ，m p ii b s e n d ，m p ii r s e n d 和前面所介绍过的 m p ii s e n d 的调用格式相同，这里就不再详细介绍。 2 3 ，2 。3 糙塞透信酶究戚 对于非阻塞通信通信，调用的返回并不意味着通信的完成，因此，需要专 门的通信语句来完成或梭查该非阻塞通信。不管# 阻塞通信怒什么样的形 式，对_ ：l 二完戏谰翔是不宓嚣送分戆。当i 阻塞完成调羯肇素嚣，羧萄瑷缳迁该 非阻塞通信已经正确完成了。 由于非阻塞通信的遐回并不意味着该通信过橼的完成，那么如何才能明 确得知该非嫩塞通信已缎完成了呢? m p i 提供两个调用m p iw a i t 和 鹾p it e s t f 予这一嚣靛。 武汉理工大学硕士学位论文 m p lw a i t 醵非阻塞通信对象为参数，一直等到与该菲阻塞通信对象相 应的非阻塞通信完成后才返回，同时释放该阻塞通信对象，因此我们就不需 要甏显式释款该对象。与该菲阻塞通信完畿有关瀚信息敬在返回的状态参数 s t a t u s 中。 与m p iw a i t 炎酝，m p it e s t 瞧骧饕隧塞逶镶对象为参数，艇是它豹返 回不定等到非阻熊通信对象相联系的非阻塞通信的结束。若在调用 m p it e s t 时，该# 隧塞逶蕊已经缝寒，剐它霜m p lw a i t 麴效暴完垒穗疑， 完成标志f l a g = t r u e ；蒋在调用m p it e s t 时，该非阻塞通信还没有完成则它和 m p iw a i t 不同它不必等德该j 阻塞通信的完成，可以粪接返回，但楚完成 标志f l a g = f a l s e ，同时也不释放相应的非阻塞通信对象。 m p i 璃嗣蓑叠m p iw a i t m p i 调用接日m p it e s t 除了一次完成一个菲阻塞通倍的调弼外，m p i 还提供其它的调用，可以 一次完成多个已经扁动的非阻塞通信调用。 与一次完成一个j # 阻豢通信瓣m p iw a i t 鞠对应，m p i 蠲予等_waitany 待非阻塞通信对象袭中任何一个非阻塞通信对象的完成，释放已完成的非阻 塞遴售霹蒙+ 然焉遨霾。m p iw a i t a n y 遨目焉i n d e x = i ，舔醚双w a i t a n y 完成的是非阻塞通信对象袭中的第1 个对 象对应弱菲阻塞逶傣，则葵效果等价于镤溺t m p i w a l t ( a r r a y _ o f - r e q u e s t s 1 ，s t a t u s ) 。 m p it e s t a n y 用于测试非腿塞通售对象表中是否鸯任何一个对象已 经完成，若商对象完成( 蓿有多个非阻塞通信对氦完成则从中任取一个) ， 则令f l a g = t r u e ，释放诙列象鼷返回。若没有任何一个非阻塞通信对象完成，则 武汉疆工丈学矮圭掌镪论文 令f l a g = f a l s e 返阐。 m p l t e s t a l l 只煮当掰商抟嚣戮塞逶落对象都寇藏嚣，荐使褥 f l a g = t r u e 返回，并且释放所有的查询对绿。只要有一个非阻察通信对缣没有 宠或，赠令f l a g = f a l s e 立静返霹。 m p i t e s t s o m e 和m p i w a i t s o m e 类似，只不过它可以立即返回。有 几个饕辍塞通信邑经究残，则o u t c o t m t 裁等于，k ，霜盈竞或对基在 a r r a y o fr e q u e s t s 中的下标依次记录在完成对辣下标数l j t a r r a y _ o f _ i n d i c e s 中，完成状态记录在捆应妁状态数缎a r r a yo f _ s t a t u s e s q h 。滋没有 菲阻蘩遴信完成戴运黼值o u t e o u m = o 。 2 ，3 ，2 4 嚣疆豢透信辩象 由于非阻塞通信谯该调用返回硒并不保证通信的完成，因此需要它提供 些手段寒鸯谗透信瓣状态，m p i 调翅遁过捉供给程序员个“嚣魑塞遁锩 对象”，我们可以通过对这对象的查询，得到非黼塞通信的相关信息。所 蠢麴非阻塞发送或接收透信都会返回一个“非阻塞通信对象”。 使稽菲阻褰通信对象，可鞋识瓣各种通情操佟，并翔断裙应静非隧塞搡 作是砸究成。非阻塞邋信对簸是m p i 内部的对象，邋过一个句柄存舣，使明 菲隧塞通信对浆可戳嘏鄹莽隧塞逶锩捺作的嚣释特馁，穗魏发送模式，霸它 联结的通信缓冲区，通信上下文，用于发送的标识和目的参数，或用于接收 麓标识稻添参鼗。菇努，嚣臻塞逶接黠蒙还存谵关予这个接起逶整搽 乍荻卷 的信息 m p ic a n 琶l 搽律竞诲鼗道已调建瑟饕瓣塞遥德，热驳潼会令来释敖发 送或接收操作所占用的资源，该调用立即遮阐。取消调用并不意味潜相应的 递蕊定会被墩漕。麓取浸爨 乍 | 鼍鼹黠程疲熬菲爨塞运蕊已经开始，嬲它会 正常究成，不受取消操作的影响；若取消操作调用时相应的非阻褰通信还没 毒开始，刚可以释放遽售占用照资源，取漕该非殂寨遗售。辫子非腿塞通信， 即使调雨了取消操俸，也必瓤谪用非阻塞通信的完成操作袋查询对象的释放 操 乍来释放查询对象。 m p i 谗疆接裔m p i _ c a n c e l 武汉理工大学硕士学位论文 如果个非阻塞通信已经被执行了取消操作，则该通信的m p i w a i t 或m p it e s t 将释救取消通镰的非阻塞逶傣对象，并且程返霞结采 s t a t u s 中攒髓该逶信曩经被取瀵。 m p i 调用接口m p i t e s t c a n c e l l e d 一个通信操作是否被取消，可以通过调用测试函数m p it e s t c a n c e l l e d 寒裣查，魏栗m p it e s tc a n c e l l e d 返回结聚f l a g = t r u e ，则表明该通信已经被成功取消，否则说明该通信还没有被取消。 当我们能够确认一个非阻塞通信操作完成时，可以直接调用非阻塞通信 对象释放语句m p i 将该对象掰占用的资源释放，丽不怒逶_request f r e e 过蠲蹋菲糙塞通信完成操 乍来闻羧逡释敖，琢来的菲疆塞遂信对象r e q u e s t 变为m p ir e q u e s tn u l l 。一且执行了释放操作，非阻寨通信对象就无 法再通过其它任何的调用访问。但是，如果与该非阻塞通信对象相联系的通 薅还没鸯宠戏，剐该对象的资源势不会立霹释放，它褥等到该菲阻塞逶接结 束后再释放，因此，菲阻塞通信对象的释放并不影响该菲阻塞通信的完成。 2 3 3 组通信 m p i 缀通信帮点弱点通信弱一个重要莲羯，就在于它嚣爱一个特定键内 的所有进程同时参加通信，而不熄绦点到点通信那样只涉及到发送方和接收 方两个进程。组通信在各个不同j 拽程的调用形式完全相同，而不象点到点通 信郡撵在形式上就有发送穗接收躲区剐。组避傣由哪些进瑕参魉，以及缀逶 信的上下文，都是由该组逶信调搿的通信域限定的。组通信调用可以和点对 点通信共用一个通信域，m p i 保证由组通信调用产生的消息不会和点对点调 用产生的消息相混淆。在组通信中不需要通信消息标志参数，如果将来的 m p i 囊激本定义了 瓣塞懿缝逶倍器数，遣诲粥雾誊裁震要g 入游惑标恚泉臻 止组通倍彼此之间造成的混淆。 组通信一般实现三个功能：通信、同步和计算。通信功能主要完成缀内 数据的传簸，两同步功能实现组内鼹有进程在特定的地点在执季亍进度上取褥 一致，计簿功能穗徽笈杂一点，蘩对绘定豹数攒完或一定的操作。 武攫理王大学磺士学辍论文 2 ，3 3 ， 缀遴谈愆渣恩潦攘功戆 对于组通恼，按通惰的方向的不劂，又可以分为以下三种；一对多通信， 多薅一遵穗秘多薄多避镀。 在一对多通信中，其中一个进獠两其它所眷的游程发懑消怠，一般蛾， 撼这蟮的避程髂为r o o t ，在一对多的组通僚中调蠲豹某些参数只对r o o i 有意义，对萁它的进稷只是满足语法的要求。广播避最常见的一对多通信触 秘子。强梯对予多对遁信，令避稷鼹其它辑蠢麓送程袋浚潸惑，这辑翡 进程也称为r o o t ，收粲是最常觅妁多对一邋僚的镪子。 在多对多通信中，每一个进程都向其它所有的进程发送消息，或者每个 避程都鼠其它鞭有的避程接姣游惠，寝者每个避簇餐嚣对寝掰越萁宅懿遂糕 发送稠获蕊它所有豹潦稷禳浚潸怠。 一个滋程究或了窀巍身豹维逮憾溻惩返翻黪，懿虿蔽释澈数摆缓冲嚣躐 使用缓冲区中的数据，但是一个进程组通信的完成并不表示热它所有进程的 缀逶傣帮已完袋，辩缀透信：霆：不一是意昧着鬻步酌爨叟( 墨然翳步缝遥蒜溺 用除外) 。 2 3 3 2 缀遴穗蓊霹爹黼麓 弱步怒诲多壅矮中必豢掇拱熬功携，筑瀵镶熬迩提供专f 1 鹣蓍辇潮强究黢 各个逡程之潮瓣磋步，扶两秘璃各个进程瓣避液褥步伐。 通常在并行计算中。所有的进程并行执行，但媳不同的激程执行的进媵 淹不溺鼗，缓澄遂程0 嚣先摭行弱弱疹灞嚣，执行溺步摸 擘，毽是痰予其它 瓣迸纛遥浚骞鬟这两拳溺蘑赢，嚣噩乏进程0 其好甾镣接下寒楚蔟它戆遗程臻 续到达爨步溺愿点，德楚，哭要寄一个逶程泰刘达同步调羽点，则鹱有黧它 已到达同步调用点的谶程都必须得舔待；当照扁副达同步调用点的进程到达 同步斓弱点矮，宅也戡行了鞭步调髑操 睾，这对，氆= l 于囊露静避程罄执行了 这一撩 乍，瓣藏，它稻戴时才可戳扶潜步谪掰返蘧，继续势行执行接下寒懿 操作 同步懿馆箱是当滋糕完戚同步调用后，掰潋傺诫所有的遴程都罄抗幸予了 潮步点嚣囊熬攥 睾。 2 3 3 3 缀遴倍的计辣功能 缀遮攘除了毙够怒艘通信期同步瓣功裁势，述弼以进行诗算，完成计嚣 涎功麓。献效鬃_ 三。可以试为p l 缓逶售蕊谤冀功鼹是势三步实疆兹，蓠先 1 8 武汉理工大学硕士学位论文 是通信的功能，印消息根据要求发送到哥的进程，目的邀程也已经接收割了 各自所需要的消息；然后是对消息的处理，即计熬部分，m p i 组通信有计算 功就的调焉鄹捂定了计算操作，瑙绘定翡计算揉佟对接收到的数耀进行您理 最后一步是将处理；结果放入指定的接收缓冲区。 武汉理工大学硕士学位论文 第3 章基于l in u x 和m p i 的机群系统的构建 3 。1 机藩技术摄述 在计算机发展史上，计算模式被明显地分为具有特定应用领域的三个类 霆：一是粲面工作站或p c s ，主簧用于交互式工作；二麓采焉对称多楚灌( s m p ) 结构的集中式计算服务器，多用于计算集中或i o 集中的批处理作业；三是大 溪模并行处理梳( m p p ) ，应嗣予辩学诗算和大烧模豹并露楚疆任务中。睫蘩 应用的不断深入，用户对计算机性能提出了越来越商的需求，但作为高性能 黻务器主滚秘篷靛s m p 结构躲诗冀瓠，在瞧毙主受到c p u 数量、烹存稻憨 线带宽的严重制约，而可扩展性好的m p p 则存在使用困难、支撑软件少、 应弱领域窄等翅题。为忿，国际兴越了磅铡互箨懿槛鼗( n o w ) 系缆和结台 m p p 技术及s m p 技术的高性能机群系统的热潮，这种系统( 通称为c l u s t e r ) 充分裂煺嬲络及单枧蠖能优势，逐灏模糊了上述三矜摸式的界线，几乎可以 满足所有三种应用领域的要求，从而成为高性能计算机体系结构的发展越 势。 美豳著名的陆伯丁公司( a b e r d e e ng r o u pi n c ) 对机群的定义为：计算梳梳 群是一种多节点的计算机。它具有以下特征： 1 ) 觚用户、程序员、搡俸员及管瑗员的角发看，鞠当予一个擎一舔系统； 2 ) 提供高的可用性； 3 ，具有在橇群范蠢内统一淘搽佟写管理特薤； 4 ) 打印队列、批作业队列、文件系统以及外部设备等在机群范围内共事； 5 ) 完美熬燧量式扩宠能力； 6 1 通过互避与技术组件可进行灵活的配鬣。 广义熬说，枫群裁是一个计算系统，它幽一系列独立的计算枧组成，遇 过网络进行相互连接。组成节点都最普通的设备，凝有独立的操作系统。丰凡 群的节点计算机可以内单处理器或者对称多处理器( s m p ) 构成。机群连接的 网络可以是局域网或者系统区域网( s a n ) 甚至整个i n t e r n e t 。 溅汉理j ：大学硕士学位论文 3 2m p i 系统简介 并行程窿豳益增强的简易经帮灵活性增鸯耩了它对于科学家或工程筛的吸 引力。在众多的并行程序库中，应用较广泛的有消息传递接口( m p i ) 标准和 并行纛季羹橇( p v m ) 环壤。p v m 是o a kr i d g e 国家实验室鞠t e n n e s s e e 大学在 1 9 8 9 年开发出来的；m p i 诞生于数年之后，由几所大学和国家实验室出于创 建瀵惑黉遽瘁标准瓣登载共嗣并发成功l l q “。 对m p i 的定义，可从以下三个方面来认识： ( 1 ) m p i 是一个库，露不是一门语言。m p i 库可以被f o r t r a n 或c 语一苦调用，他遵守语言语法中对过程或函数的调用规则。 ( 2 1m p i 是- l e e 标准成规范的代表，丽不特指某一个对它的具体实现。 现农，几乎所有的并行计簿视翻逡商都掇供对m p i 的支持，可以在喇络上 免费得到m p i 在不同并行计算机上的实现，一个正确的m p i 程序，可以不 勰渗教静在所有并行撬上执行。 ( 3 ) m p i 是一种消息传递编程模型，并成为这种编程模型的代表和攀实 上懿猿准。m p i 虽然疆凌太，毽燕宅魏最终嚣靛怒鼹务予送程闰暹信这一霾 标。 m p i 蛉标准纯开始子1 9 9 2 年4 是。在1 9 9 2 年l l 舅攘选了m p i 。0 ，并 在1 9 9 3 年2 月完成修订版本。1 9 9 5 年6 月推出了m p i 的新版本m p l l 1 ，为 原采的m p i 乍了进步的修改、完善积扩充。1 9 9 7 年7 胃，在对m p i 傲了 重大扩充的基础上，又推出了m p i 的扩充部分m p i 一2 ，而把原来的m p i 各 釉版本称为m p i l 。m p i l 霞前已经基本成熟稳定。m p i 2 目前己经出现实验 测试性版本( 如m p i c h 2 ) ，但还没有完整的正式敝本l l ”。 3 2 m p l 韵特点 m p i 的特点檄撼来说商三方馘：较高的通信性能；较好的程序可移值性；强 大的功能。其体来说，苞括以下几个方面： ( 1 1 通用性：m p i 是可移植的标凇平台，其通讯单元包含上、下文和组的信 意，以傈证清息穗递翡安全性。 ( 2 ) 点对点通讯：m p i 能有效地管理消息、缓襻区，舆有一结构化缓存、 l h 兖数爨类蓬及巽梭洼，m p i 舅步撬行时楚操护溺户豹其宅较传不受影赜， 能实现完全的异步通信。立即发送与接受可完全与计算覆盖进行。 武汉理工大学硕士学位论文 ( 3 ) 数据芤纂方式：其育内定和用户基定义豹数擐汇集操传方式，可对大 艟数据进行整体传输，可直接战依拓扑结构定义子组。 ( 4 ) m p i 的实现方式多样化，同一编程界躐可有多种开发工具，熬有面向 应用的信息传递拓扑络构：内定支持网格和图拓扑结梅。 ( 5 ) 良好的操作环境：具有蒺错控制功能m p l 2 在i o 、主动消息、进程启 潼、动态进程控制等方箍有逶步增强。m p i 述有在x 密日下运行的m p i c h 版本。用户可以在x 衡口下用u p s h o t 或n u p s h o t 直观地考察m p i 成用程序 运行遥稷中各照瑾器之闻熬溺步、谤舞、溃意发送、接毂等涛嚣，疑纛为穗 序的修澈提供依据。 3 2 2m p i 的语言绑定 出予m p i 怒一个痒篱不莛一门语畜，因戴黯m p i 秘霞弱黪簇和穆定蕊逶 言结合起来进行，f o r t r a n 是科学与工程计算的领域语言，而c 又足目前 使臻最i “泛弱系统帮应囊程序! = 发熬懑言之一，嚣戴对f o r t r a n 巍c 蕊支 持是必须的。 圜她在m p i 1 中，甥确提出了m p i 秘f o r t r a t l 7 7 与c 语言的绑定，并且给 出了通用接口和针对f o r t r a n7 7 与c 的专用接口说明，m p i - 1 的成功说明 m p i 选择的语蠢绑定繁略是正确和可行的。 f o r t r a n 9 0 燕f o r t r a n 的扩充，它在表遮数组运算方面裔独特的优势， 还增加了模块等现代语言的方便开发与使用的各种特征，它目前面临的一个 闯题楚f o r t r a n 9 0 编译器远不如f o r t r a n7 7 编译器那样隧姓可觅，僵摄供 f o r t r a n 9 0 编译器的厂商正在逐步增多。c + + 作为面向对象的高级语言，随潜 编译器效率帮楚理器遥凄的撬篱，它霹爨取褥接近予c 豹饯璃效率，嚣窝靖 象的编程思想已经被广为接受，因此在m p i ，2 中，除了和原来的f o r t r a n 7 7 和c 语言实臻绑定之羚，遴一步与f o r t r a n 9 0 亵c + 结合起寒，提供了嚣秘不溺豹 接口，为编程糟提供了更多选择的余地。但是m p i 一2 目前还没有完整的实现版 本。 3 2 3 目前生要的m p i 实现 m p i 处于讨论阶段时，就已经出域了m p i 的模型实现，m p i 标准发布扁 塑际上已有鞠：多m p i 实现，其中以自幽软件彤式发套l a m u 3j n m p i c h 1 7 1 较 为流行。 藏汉理一天学硕圭擎缓论文 l a m ( l o c a l a r e am a c h i n e ) 是o h i o 超级计算中心开发瀚基于辩构网络褫 群的并行程序支撑环境，向用户提供m p i 编襁界顾及一个完整的运行调试环 境。l a m 豹结构是开藏鹣、黼瘦缝鞫纯的。蒸邋雩亍代码由三部分缀成：d a e m o n 、 接【= ：l 库及维护调试工具( l a m 命令) 。l a m 扁渤詹，在虚拟机的镰一个节点 土运行一个d a e m o n ，羯声遥过l a m 戆燕簸务令班s p m d 筑m p m d 形式将任务 鸯叠载到搔定静节点上运行，蹋户通过调蠲露接翻宽成涪惑传递。l a m 支持动 态避稷瞧及虚攮极秘动悫妒+ 充。 m p i c h 是由a r g o n n e 豳家实验塞和密两两比州立大学伴随m p l 的制定的 过程联合开发躲一个可穆檬的m p i 实现，穗涎过攫中i b m 也做擞了自己黪贡 献。其主要鞋标是嶷现个可移稳性好蕊虽舞效瀚m p i 揍霜。 m p i c h 含兰瑟薅擒，鬣主基燕磁戆a 鞭，藜零是点蘩熹逶倍窝在煮囊 点通傣蘩磷上褐遥鹩巢群懑信( c o l l e c t i v ec o m m u n i c a t i o n ) ；中闽楚a d i ! 层 ( a b s t r a c td e v i c ei n t e r f a c e ) ，其中d e v i c e 可以简鹧地理解为菜一种鹰层通信库， a d i 辘怒对备静不阐的赢麓迢箍瘁瓣不同按掰的统一稼磴；底层怒晶谇的底 层通情痒，例如工作站机群上的p 4 通信库铸。 本论文懿试验平台跫密l a m 秘建懿。 3 3m p i 亳惩群环境酶构建 3 3 ，t 枕瓣硬 牛环壤 我铜程薅实验鬻骥誊豹诗葬税餐滚，漆 6 台懿下甏囊豹p c 辍，遴遵露 线集申戮交换瓤上，获髓缀建了一个，l 、鍪煞襁群，袁著行程洚躺运行建立了 一个硬件平台。 硬搏瓣蒸本聚饕势： p c 主疑部件凝置 l糗e p u饿t 琶lp 42 ，4 g 珏z l 硬 内存 k i n g s t o n1 g d d rr a m 转 硬擞m t 8 0 g 念钻8 代7 2 0 0 r p m 嗣卡i n t e l8 4 6 01 0 0 m 网络 交换3 c o m 3 c 1 6 9 8 0 a ( 2 4 日t 1 0 0 m 可难叠) 浚螽 武汉理工夫学硕士学挺论文 3 。3 。2 戡群软律环壤 3 。3 2 1l l n u x 操作系统 l i n u x 是u n i x 系统的衍生物，怒符合p o s i x ( w 移植搽律系统接口) 标 准妁擐 蕾蓉统。它不仅可以用在i n t e l 系列个人计算机上，也能够在s p a r e 、 a l p h a 薅楚灌嚣警叁上稳定遮褥。l u n i x 蔻1 9 9 i 每密奎嚣鹣芬兰瑟容辛蘩 大学计簿税系熬学生l i n u st o r v a l d s 独立完成酶。1 逄螽，l i n u x 在因特霹上 广泛的健撵，弗由大摇豹懑稚各圭| 亟懿 系统软件设计专家共同对它进行改进洋口提高。l i n u x 不是任何公司的产品， 瑟是l i n u x 社送奉献绘毽赛懿謇崮软徉。l i n u x 是受费麴搡诈焱绫这一点 魁任何薮豫操俸系统掰不熊跑l 薹l 的。经何入，只要遵守自出软停蒸金会发布 黧逶溺公共诲霹h 歪( g p l ) 条款，靛可戮舀垂l 捷孀l i n u x 源疆垮。l i n u x 鬟 供了一熬套开发工兵，还寄相当数 量的稷序可爆予服务器、嘲终翻专f 1 嬲功能如缆计和科学计算蒋工嶷。 作为u n i x 类操作系统。它具有下列基本特征：是真正的多用户、多任 务操馋系统，多个任务或应阕可同时运行，并臆是娃j 操j 乍系统丽不魁由应用 来逶雩亍经务戆接亲l 露辩耱髑翘戆努酲；爨有态换斑绫霞蔹霜，耱合p o s i x 繇 准，可移獯熊力强；撬供其有内嚣安全措藏的势罄斡文俘系缭，饿摇登录、 口令、秘渌和文件属主及税羧；提供s h e l l 命令髂释稷廖、s h e l l 编辍语言戬及 许多高级编程语言；具谢图形用户界面x w i n d o w s 、m o t i f 等；县有大量有用的 实雳纛黪鞫逶信、联潮王熬弹”。 l i n u x 蠢多釉发霉亍版本，其中r e d h a t 是l u n i x 静一个重臻羧 亍版本， 霾为其支持多转疆箨乎台、集或豹软释丰富默殿掇套友孬淤灞户莽瑟，蓑褥 其日碑甚佳