（计算机软件与理论专业论文）相关分析在mpijava群组通信优化的应用.pdf

硕士学位论文 论文题目：相关分析在p i j a v a 群组通信优化的应用 专业：计算机软件与理论 硕士生：王景浩 指导教师：张治国副教授 摘要 论文主要讨论了m p a v a 系统在进行群组间通信时所存在的网络使用效率不高 的问题，指出该问题的主要原因是系统通信接口的调度策略未经优化，并在总结了 p 锄d a ，j a v a 并行库( g m i ) ，基于i p 多播( i p m u h i c a s t ) 的m p i 群通信管理模式，j a v a 组 间消息通信库p m a c t i v e ，m p j a v a 和p j m p i 等模型的共同点之后，提出了改进m p a v a 群组通信接口的相关分析模型。 该模型主要通过对单位时间内系统中消息的传递数量与节点的等待时耗进行统 计，并计算其相关系数，通过相关系数的值来对系统消息的优先级进行划分，以解 决增加单位时间内系统中消息传递数量与缩短节点的等待时耗之间的矛盾，从而达 到增加单位时间内传递消息的总数进而提高网络使用效率的目的。 本文主要采用了数学分析与实验溯试的方法对模型进行检查。抽样误差率，消 息冗余度指标，网络利用率提高系数，平均延迟度等指标被用来衡量模型的有效性。 实验测试主要用到的方法包括p h l 咖n g ( 一个在群组内各节点之间来回传递空消息 的基准测试，空消息的内容为空，但长度大于零) 郴p ( a 1 1 p a 镌s h o n c s tp a l l l 譬一 求解带权有向图中任意两点问最短路径的集合) ，p o n 一个模拟高分子蛋白与水相 互渗透时晶格的演变过程的应用程序) 等常用的m p i 系统测试程序。p i n g p o l l g 程序负 责测试系统在改进后，通信功能的正确性和抽样的准确性；a s p 负责测试系统改进 前后集群的m p i 接口的消息的正确性和消息冗余度，发送接收延迟等性能；p 0 n s 程 序用于测试应用程序在皿| p 弧v a 改动前后的执行效率的改变。为了能够计算测试指 标，在测试程序中添加了测试模块。 实验结果表明该模型在节点数量较多，应用程序传递群组消息频繁( 例如经常发 送广播消息) 的条件下能比较有效地减少消息的延迟，提高呷a v a 对网络的利用率。 关键字：m p i j a v a ，相关分析，群组通信，通信接口，集群计算 硕士学位论文棍差分薪理j ， 一 w z 群缘遵詹防磁触硅用 c o r 件l a t i v e a 皿a l y s l sm o d df o i c o i l e c h v ec 哪m u n j 龃6 帆i n t e 凼o f m p i j a v a m a j o r ：c o m p u t e r s o f t w 盯c 姐dt h e o r y n a 雠： w a n gj 啦h a o s u p e n ，i s o r ：z l l a n gz h i0 u o a b s t r a c t i nt h j sm e s i s ，w ea n a l y s i st h cp r o b l e mo f1 0 w e m c i e c yi l lu s i i l gn c t w o r kb y m p i i a v a ；a n ds u 衄缸i z et h cc o m 瑚ng r o u do f m ei d e l s ：p a n d a j a v ag m i ，g m u p m a n a g e m e ms c h c m c sf o fi m p l e m e m 吨m p ic 0 e d i v ec 0 m 砌n j c a t i o no v c r i p - m u n i c a s t ，g r o u pc o m 珊m i ( 斌i o n sl n e s s a g cl i b r a r yi nj a v a ，m p j a v aa n dp j m p i ；t h e n g i v eac o n e j a t i v ea n a i y s i sm d d e l 旬rc 0 e c t i v cc 0 衄u n i c a t i o ni n t e 嘞c co fm p i j a v a t 扯n 船d e li st l l l u g ht l l cs t 砒i c 幻fl h ct o t a lc x e c i l t c dc 0 衄u n i 龃t i 0 p r i m i t i v c so f t h es y s t e m 删t h ew a i t i n gt h e0 fe v 盯y d ej l lu n i tt i l n c ，t h e ns c tp r i v i l e g eo ft h e s y 砒啪m e s s a 窖皓a c c o f d i n gt o h c l a t 蠡o nv a l u c s ot h a tw cc a n 伽咀q u c rt h ec o n t r a d i c t i o n o fi n c f c a s i n gt h ct o t a le 驰c i l t e d 啪u n i c a t i o np r i m i t i v c so f t h es y s t e ma n dd e c f c 璃i n g t h c 、姐i t i n gt 劬co f c v c r yi m d ej nl l i tt 妯 a n c r l v i n gt h 砖p m b l c m ，w cc a nt h c i n c r 随曲喀t h cm e s 鞠g ea 瑚u mo fs y s t c mi nu n tt j 玎a n de n h a n c et h ee 瓶c i c c yo fu s i i l g n e t w o f k w b 惦em a t h c m a t i 髓l 锄l y s i s 勰dt e 髓i n gp f o g 舳t 0c h e c ：kt h e 脚d c ls a 唧ke o f r a t i 0 ，m c s s a g e d 蚰d a n c yd c g 弦e ，i m 豁a g ct r a n s p o ne 任i c i c n c yi c r e 笛i n gr a t i o ，a v c m g c h t e 噼yd c g 障et 0c h kt h ev a l i d a t i d o ft h cm d d c l p r o 簪a m si nc o m m o nu t 0 c s tm p i ， s u c h 勰p i n g p 0 n g ( ab c 舵h m a r kw h i c h n d 抽g 姗um e 鹋a 萨t h cl c n g l hi sn o t n u l l b e 呐c c nt l l en o d c s ) ，a s p 渊1 p a 砌s h o n c 或p a t h s ) a n dp 0 t t 啦p r o g r a mt h a t s j m l a t ct l 砖j n 矗l t t a t eb c t w e m a 口o m o l e c u kp r o t e 缸a n dw a t c i ) h a db e 哺u s e dt ot c s t t h ci d i f i e d 】p a v as y s t e mu n d 盱t h ed 慨t i 【mo ft h c 啪d c ln e p i g p o n gp m g r a i l l ，i s t 0d l c c kc o m c t 】睇踮o fs a n l p l 妯g ，a n da c c i i 豫c yo fs a m p l i n ga f t c rl n p i j a s y s t e mh 嬲 b e e n 脚d i f e d ；t h ea s pp r o g 舳i st oc h c c kt h em e s 鞠g e 硎u n d a n c yd c g 弦e ，c o 删n c s s m 硕士学位论文 o fm e s s a g e ss e q u e n c e ，m e s s a g et r a n s p o i tc m c i c n c yi c i e a s i n gi a t i oa n d 也ea v e r a g e l a t e n c yd e g r e eb c f o r ea n da f t e r l p i j a v as y s t e mm o d i f i e d ；a n dp o t t s i sb c i l l gu s e dt ot e s t t h ee m c i e n c yo fa p p c a t i o np r o g r a m0 nm p i j a v ab e f o r ea n da f c e r b e i n gm o d m e d t h cr e s u l to f t h ct e s ts h o w st h a t ，w h c nc l u s t c rl l a si 0 r cn o d e sa n dt h ca p p h c a t i o n t r a n s p o r tm e s s a g e 丘e q u e n t l y ，t h em o d c lc a nd e c r e a t h ch t e n c yo fm e s s a g ea n da p p m v e t h cu s a g eo ft h en e t w o r k k e yw o r d s ：m p a v a ，c o l l e c t i v ec 0 m 舢n j c a t 沁1 1 g r o u pc o m m u n i c a t i o n ，c o r r e l a t i v e a n a l y s i s ，c o i n i i l u n i c a t i 0 i m e r f a ，c l u s t e fc 0 m p u t i l l g l 、， 硕士学位论文 第1 章问题背景及陈述 1 1 问题的背景 群组间通信( c o l l e c t i 、r c g m u pc o m m u n i c a t j o ) 是高性能计算( 集群计算网格计算) 的一个重要的特性，它是指集群或者网格的多个主机节点( 这里假设每个主机节点 只有1 个处理器，下同) 由于某种计算或者任务的需要丽通过网络进行数据的分发与 交换，消息的广播与传递等活动【1 】。群组之间的通信功能主要通过各种平台的消息 传递接口来实现。 m p i 模型作为并行程序的一种平台模型在集群上应用十分广泛，它具有消息传 递速度快，效率高，支持点对点通信和群组通信等优点，适合于具有紧偶合特性的 基于巨型机或者集群的高性能计算。可是由于受当时历史条件的限制，原来的m p i 模型不支持面向对象的开发机制，虽然在后期加入了对c + + 语言的支持，但由于保 留了原先的代码，仍然不能充分发挥c + + 在面向对象方面的优势，从而制约了并行 程序代码的编写效率与质量【2 】。 后来人们利用j a v a 语言对m p i 模型重新编码，出现了j m p i ，i n p i i a v a ，m p u 等新 的编程模型，以达到让碉睢模型能够充分支持面向对象技术的目的。 p i j a v a 是一个面向对象的标准m p i 的j a v a 接口，它是开放源代码的h pj a v a 语言 的一部分，但是m p i j 啪本身并没有对j a v a 语言进行任何扩展，它在各种平台上都能 提供一致的j m 开发功能及本地m p i 环境【3 】。n l p i j a v a l 2 提供了，1 2 的所有功能， 它是作为一套本地m p i 的j n i ( j a v an a l i v ei n t c r f h c c ) 包实现的，支持的平台包括： 装有m p l c h 、u w 或s u n 磁c o 伫i 的s o l a r i s ，装有m i c h 或u 蛳的w i n d o 啪或l i l i u x ， 以及i b m 的s p 机。2 0 0 3 年1 月h p 发布了m p i j a v a l 2 5 版本，此版本吸收了s 吼j 2 s e ( j a v a2p h t 如r n l s t a n d a r de d i t i o n ) 1 4 的特色，避免了早期版本中存在的一些问题。 它可以运行在更多的平台上，比早期的任何版本更可靠1 3 】。在m p i 的三种实现 中，m p i j 啪采用j n i 机制( ，a v a t i v el c c f 缸c ) ，比采用纯j a v a 的实现更好地兼容了原 有的m h 程序库。 1 2 问题概述 m p i 的实现大多是针对高可靠的网络环境的，而m p i 2 标准在实际制定的过程 硕士学位论文 中，对在多个节点相互之间进行消息传递的群组间通信，仍然只是按下标序号的某 种特定排列( 如由，号节点传到，号节点) 进行，并没有采用任 何调度策略对其进行优化【4 】。虽然许多学者对m p i 的组间消息传递的实现提出了许 多改进方案，但是由于这些改进方案都没有在这方面进行过多的考虑，因此该问题 实际上并没有受到关注。图1 1 为m p i j a v a 广播一个消息的过程： 厂_ = = i = = = i i i = = = ；i _ 臣型墅蟹压墅墅堑回臣受量爱圈 卜一i ，臣! 塑妻里匣司 匣复垄妻塑 l 一一1 r 、= ! i l 口f i 右目 i 匣墅壅叁网 k 一一f 广一一一一一一一一一一一一一一一一一一一一一一一一一一 l 一一一一一一一一一一一一一一一一一一一一一一一一一一 j 图l - 1 从图1 1 可以看出进行消息广播时，由于m p i j a v a 的群组通信采用m p i 标准四种通 信模式中的同步通信模式，后面的接收进程必须等待前面的接收进程完成消息接收 的过程后才能开始接收消息f 3 l 。由于在m p i ，8 v a 中这种顺序是从进程号小到大的顺序 固定进行的，因此每次广播时进程号大的节点都要等待前面进程号小的节点完成消 息的接收才能开始接收消息，可能造成计算能力较强但进程号大的节点每次都要等 待相当长的时间。同样的问题存在于m p l 的其它j a v a 实现( 如j m p i 和m p m 中，故它 们都难以发挥高速网络的优势，最后造成应用程序执行效率的降低【5 】。其结果是当 前各种用j a v a 程序按照m p i 2 标准所实现的m p l 模型上应用程序的执行效率都比不 上用传统语言( c 托+ 枷f b r t r 蹰) 所实现的m p l 模型( p i 血c 犯+ 删心i 如rf 0 r t 啪) ，在 某些情况下甚至比在单机上运行的效率还要低【6 】。 根据【7 】的研究结果，m p i 程序在m p i 的j a v a 实现上运行所需的时间大概是单机运 行的1 0 倍，比m p li nc c + 卅f o 砌限a n 要慢2 0 倍以上。 造成这种情况的原因有许多，如j a v a 程序的解析执行速度比较慢，系统负载不均 2 f基r 彗| 一 塑璧 去 硕士学位论文 衡等等。但是其中一个很重要的原因则是许多分布式应用程序的各个节点之间的通 信流量不均匀，可能在某一段时间内突发性地产生大量通信消息，在其它时间叉可 能没有任何交互信息需要传递，容易造成发送消息时，接收节点处于等待消息的空 闲状态。而m 闻a v a 采用的】n l 机制则大大增加了这种空闲状态的可能性( 因为j n l 需要调用本地代码，延缓了系统的启动速度和系统加速度) ，因此这个问题在m 口i j a v a 中更加突出【8 】。 这个问题中，消息传递的数量往往与节点执行消息传递的持续时间成正比，同 时用于传递消息的通信原语具有互斥的特性( 即正在执行通信原语的节点在某一段 时间内只能与一个节点进行通信，以保证消息的顺序性、正确性和完整性，该特性 根据不同的应用程序而具有不同的影响) 【9 】。而要提高网络的使用效率，则要增加 单位时间内系统中通信原语的执行总数或者缩短各个节点的等待时间。但是由于消 息的顺序性，节点的等待时耗又受到所等待的对话节点执行通信原语的持续时间之 影响，因此也受到单位时间内通信原语的执行数量之影响【1 0 】。因此研究他们之问 的关系，在确保消息的顺序性、正确性和完整性的前提下，解决增加单位时间内系 统中消息发送总数与缩短节点等待时耗之间的矛盾就成为人们研究的重点【1 1 1 。 1 3 本文的框架 本文的第2 章主要介绍了几种关于群组通信研究的模型：它们分别是p a n d a j a v a g m i ，m p lo v c r 秘m u n i c a s t ，j a 姐p r o a d i v e ，m p j a v a j f 口p j m p i 。第3 章在总结了前面 四个模型的三个共同点倮用了已有的系统或者策略为基础，都对节点进行了类型划 分：建立或者改进原有系统库文件中的通信接口，提出了各自的调度策略) 的基础上， 提出了使用相关分析改进群组通信调度策略的模型，模型主要使用抽样取值，计算 相关系数，改变优先级设置的方法。在第3 章还提出了衡量模型的指标：抽样误差率， 消息冗余度指标，网络利用率提高系数，平均延迟度。第4 章则给出了相关分析模型 在m p i i a v a 群组通信接口中的实现方法，包括群组通信接口组成的描述和改进策略各 个模块的功能和实现。第5 和第6 章分别描述了实验环境的建立，实验的原则，实验 的步骤，实验的结果及其分析，实验采用了p i l l g p o n g 程序a s p 程序和p o t t s 程序作为 检查模型有效性的基准测试。第7 章在数据分析的基础上进行了建模思想的总结，并 指出模型在一定条件下能够提高m p i j a v a 的网络使用效率，降低消息冗余度的优点。 硕士学位论文 第2 章群组通信研究的现状 2 1 问题研究的历史 起初，由于网络硬件的发展缓慢，人们对群组间消息传递的研究主要在网络底 层方面，因此研究进展也比较缓慢。p 锄d a 模型是早期这方面研究的代表之一。 近年来，由于网络技术的飞跃性突破，网络速度和带宽都有了很大的提高，因 此多节点的分布式应用( 如集群、网格) 激增，从而使得对多个节点之间的通信机 制的研究也逐渐广泛起来。由于许多研究都在同时进行，相互间的关系错综复杂， 因此很难对它们进行一个系统的描述，下面仅以一些例子来说明这些研究所取得的 成果。 2 2 各种模型举例 2 2 1p a n d a 模型 1 9 9 3 年，在解决组间通信问题方面，p 柚d a 系统提供了一个模型【1 2 】。p a n d a 用 一个专门设计的进程( 称为q u c n o 盱) 负责维护进程顺序号( s c q u c n c c 姗n l b e r ) ，为 组间通信提供了三种解决方法：p b 硫- t o - p o i n tf o l l o wb yab m a d c 雒t ) ，b b ( b f o a d c 船t f o 】帖wb yab r o a d c a s to f t h e q u c n c cn 岫b c r ) 和g s b ( g c ts e q u e n 曲m b h e r 柚d b r o a d c 弱t ) ( 如下图) ： 鼬i i dc t 鹫a 宣pb c o & d o t i t k l t o w l e d 曩e r n e 胍 图2 1 4 硕士学位论文 在b b 方法中，发送消息的进程先添加一个带标识的关键词和顺序号到消息中， 然后自行对消息进行广播。对于后续进程来说，它们只需要广播一个带有该关键词 及新的顺序号的消息就可以了。每个收到该消息的进程都要检查其顺序号，以确认 以前是否收到过。 在p b 方法中，发送消息的进程把带标识的关键词和顺序号添加到消息后，发送 给守护进程( s c q u c n c c r ) 。守护进程( s e q u e n c c r ) 用新的顺序号替换原来的顺序号之后， 发送给系统的每个进程。每个收到该消息的进程都要检查其顺序号，以确认以前是 否收到过。 在g s b 方法中，发送消息的进程发送一个只带顺序号的消息给守护进程 ( q u e n c e r ) 。守护进程( s e q u 衄c c r ) 用新的顺序号替换原来的顺序号之后，返回给发送 进程。发送进程再把带标识的关键词和新的顺序号添加到消息后，发送给系统的每 个进程。每个收到该消息的进程都要检查其顺序号，以确认以前是否收到过。 p a n d a 模型对比较有效地提高了消息在进程间传递的效率，但是由于它采用了分 情况处理的方式，而每种处理方法都有自己的缺点：髓方法只需要广播一次带数据 的消息，但接收进程则会收到该( 带数据的) 消息两次以上。p b 方法由于要通过守 护进程进行广播，每条消息的数据都多传递一次( 从发送进程到守护进程的传递) ， 冗余消息高达1 0 0 ，对传递数据量大的消息十分不利。而g s b 方法虽然广播和接收 数据消息都只有一次，但它需要先获得新的顺序号，结果它与收护进程的交互带来 了延迟和额外的开销，只能适用于低延迟的网络。 由于p 柚d a 模型的三种方法中b b 和p b 方法都有大量的额外( 冗余) 消息，而g s b 方法只能适用于低延迟的网络，因此p a n d a 模型不能有效解决群组间进程传递消息效 率不高的问题。 2 2 2j a v a 蹦i 并行库( g m i ) 2 0 0 1 年，荷兰科学技术大学数学与计算科学系的j a s o nm a a s s e n ，t h i l o k i e l m a n n ，h e n r ie b a l 三个人指出了j a v a 刚i 技术的群组间消息传递机制不适合 并行程序计算的缺点，并提供了一个g m i ( g r o u pm e t h o di n v o c a t i o n ) 模型以实现有 效的群组问通信 1 3 。g m i 模型在脚i 原有的基础上改写了跚i 的库，使得r m i 不仅支 持本地对象( 1 0 c a lo b j e c t ) 和远程对象( r e m o t eo b j e c t ) 及其方法的调用，还支持组 5 硕士学位论文 对象( g r o u po b j e c t ) 及其方法的调用，如图2 2 和图2 3 。 图2 2 图2 2 描述了r 原有的通信机制，即由台服务器上的s t u b 接口通过对两台或 者多台客户机上的s k c l c t o n 接口控制各台客户机的对象实例。但是各个客户机的 s k e l e t o n 接口相互之间不能进行消息传递。 图2 3 图2 _ 3 则描述了g 虹模型的通信机制，g 把各台服务器上的对象实体看作对象 群( o b j c c tg r o u p ) ，然后提供了消息前送机制( f o 聊甜d 矗培s c h e m e s ) 、应答处理机制 ( r 印l yh a n d l i n gs c h e m ) 、交叉处理机制( 0 n l m 9 0 n a lc o m b i a t 孟0 no f t h c f o n a r d 矗i ga n dr c p i yh a n d i 缸嗜s c h e m e s ) 和群同步机制( s y n c h m n i z a t i o no f g f o u p i n v o c a t i 0 粥) 。消息前送机制修改了s k c l c t o n 接口，在其中添加了群组问公众调用方 6 硕士学位论文 法( g r o u pi n v o c a t i 0 ) 和群组问私人调用方法( p e r s o n a l i z c dg f o u pj l l v o c a t i o n ) 。g m u p i l l v o c a t i o n 方法把消息传递到群中的每个对象实例并使之接收：p e r s o m l i z c dg m u p i n v o c a t i o n 方法也把消息传递到群中的每个对象实例，但是由于被调用方法所传递的 参数不同，只有某些特定的目标节点才会收到这些消息。应答处理机制包括结果丢 弃( d i s c a r dr e 辄l t ) 、返回一个结果( f e t 啪o n cr e s u n ) 和结果综合( c o m b i l l er e s u n ) 三种处理方式。结果丢弃是指s k e l c t o n 不返回任何处理结果给s t u b 也不处理任何异常， 直接把结果丢弃；返回一个结果是指不管有多少个节点得到该调用方法的处理结果， s t u b 都只返回一个，如果得到多个结果，则返回其中符合特定条件的某一个；结果 综合是指当该调用方法在多个节点的得到多个结果，则由一个用户指定的方法来对 结果进行综合，并返回综合之后的结果。交叉处理机制把l o c a l 、r e m o t e 、g r o u p 、 p e r 衄l i z c d 四种情况按照d i a f dr e 辄l t 、r e t 哪。船r e 辄n 和啪b 缸er e 辄n 三种处理方 式分别调用n o m a l 如v o c a t i o n ，勰y i l c h r 0 0 u si n v o c a t i o n ，懿y n c l l r o n o u sr m i 等方法， 其机制如图2 4 。 t i l t i m m c a t - o n d 妊c a r df 嘲t 刖_ f o 辩)c o n l b i m k 他l a 甜j 咖m sm 越 h m lj n b m m p l - s i ，kc o m b i m 幢e a s y i 埘w o u sr m i r m l m p l s i ，1 ec m l 畦m ，e g 呻 s y 咐拇哪啪s 尊岬h 。c 鲥蚺g l m 驴m v o 翻l i o n 鲫u pc o m b i 烈f 树 蒯粥妒曲蝌m t s 脚n 吣i 删g m u pi 雕 非l 啦d 鲫l m 艄洒婶w n a i i 蒯伊pc b i 图2 - 4 其中勰y n c h r o 肿u sj n v o b o n 和篮”c h u si m 采用j g 垤r 原有的机制， 硒y n c h r o 肿璐g r o u p 胁6 d n 采用广播同步消息并且所有都接收该消息的方式进 行，而够y n c h m u sp c r 瑚觑dg 删叩i n v o c j o n 则采用发送消息到特定地址并且只 有该地址的节点接收同步消息的方式进行。 6 m i 模型较好的解决了r 群中各个节点之间由于不能进行交互而需要服务器 进行所有调度处理从而使服务器( 前置机) 负载过重的缺点，从而在系统启动的加 速度方面比r ，甚至在某些方面超过了舶p i l a v a 。图2 5 、图2 6 和图2 - 7 分别是g m i 、 i 洲i 租唧i j a v a 分别运行解决a s p ( 胁p a i l ss h o r t e 醴p a i 埘，i 量q ( l i n e 盯e q u a t i o n s o l v c r ) 和q r ( q r 自c t o r i z a t i c 时等问题的应用程序的结果( 使用m a n t a 编译器) 【1 3 】。 硕士学位论文 a s p i_ m a n t a ，g m i l m a n t 划r m l - 日 m d i j a v a 一 。 尹一 矛” 01 02 03 04 05 0 6 0 c d u s 图2 5 l e o m a n 协7 g m l ； m a n i a | f r m i - 鲁 m p l j 啪- 一一 ，。+ + ， j 一；：r 叫= 二 一臣一 一i 千 01 02 03 04 05 0 c p l l s 图2 6 8 6 0 仲 o a丁口oo已田 ； 竹 o d 3 口o q 硕士学位论文 o r m a m a a g m i ； m a n t 甜r m i 一目- m p i a v a ， j 。， ，+ ， ，一 ：。一一。 c ： ：盎：二一。 。， 兰二_ 一一 一 01 0 2 03 04 05 0 c p u s 6 0 图2 - 7 但是g m i 模型仍然在效率方面存在不足，例如调用p c r s o n a e dg r o u pi l l v o c 砒i o n 方法传送消息到某些节点时，该消息还是要发送到各个节点，冗余度还是接近1 0 0 ， 因此当每个节点的广播消息数量都增加时( 如l e q 问题) 系统速度反而会下降，如 图2 - 6 ，丽其应答处理机制则存在丢弃结果的可能性，因此作者承认其程序的可伸缩 性和健壮性都存在问题 1 3 。 2 2 3 通过i p 多点传送( i p 一叫1 t i c a s t ) 的肝i 群通信管理模式 2 0 0 3 年，美国佛罗里达州立大学计算机科学系的x i ny u a l i ，s c o nd a n i c l s ，a h m a d f a r a j ，a m i t 哪a n d e 四个人在研究m p i 通过多点传送原语进行群组间通信时，发现 通过m p i 库与i p 协议相结合，可以形成多点传送原语( 砸删h 妇s tp r i i l l i t i v e s ) ，从 而提高集群中各节点间相互通信的性能又不牺牲m p i 库的简便性( 即无需对硬件或 者操作系统进行任何改动) 1 4 】。于是他们提出了三种实现m p i 群管理的模式：静 态管理模式( s t a t i c 蓼。叩删啪g c m c n ts d 托m c ) ，动态管理模式( d y n a m i cg r o u p m n a g c m c n ts c h e m e ) 和编译器辅助模式( c o m p i l c r - _ a s s 酞c dg 【o _ 婶础衄q 吕c r m s c h c m e ) 。静态管理模式在m p l 的每个m 蹦l n i c a t o r 实体中对所参与的进程作静态 划分( s t a t i ci d c n i i f y ) ，从而使多点传送消息( 多点对多点的相互通信) 只在划分好的 某个组内进行传递；动态管理模式负责动态地创建或取消多点传送组( i 肌l t 妇t g r o u p s ) ，并只允许多点传送消息在某个组内的节点中被传递，该模式更为灵活但 9 伸 o d n g a 硕士学位论文 会产生大量的群管理活动( 挚o u p 蚴g e m e n to v e r h e a d s ) ；编译器辅助模式则通过大 量的通信活动来分摊( a m o n i z c ) 群管理活动的功能 1 4 。 图2 8 为该模型的示意图，群中同一个级别的节点用同一个交换机相连，不同级 别的节点通过两个交换机相互连接。 图2 8 图2 - 9 为m p id v c fj p - n m n i c 枷与l 弧们幢p i 在一个2 9 个节点的集群上执行 m p i s c a t t e f 方法所得到的结果 1 4 】。 p 翻救羽m 棚w eo f 劓驴，j 酝耐衄ro na2 m d e 科啦咖 图2 9 该模型比较简便地实施了对m p i 通信接口的修改，使之较好地与l p 协议融合， 因此能够从底层对网络利用提供高效地支持，特别是在编译器辅助模式下能够达到 非常高的执行效率。但该模型的静态管理模式不能有效地支持一对多的通信方式( 虽 然原文作者称经过评估，一对多的通信方式并不经常发生，而系统对小规模的一对 一鬯一_i口ca瓦蓦_兽j 硕士学位论文 多通信已经给予足够的支持) ，从图2 9 可以看出当消息长度小于1 0 0 b 时，模型所实 现的所耗费的通信时问小于l 地l ，m p l 系统，而通信消息的长度逐渐增大时，所耗费 的通信时间将会急剧增大，故该模型更适合于短消息数量多的应用：另外该模型依 赖于特定的编译器，因此实际上影响了原来m p i 库豹健壮性并降低了程序的可移植 性 1 4 。 2 2 4j a v a 组间消息通信库p r o a c t i v e 2 0 0 4 年，法国国家信息与自动化研究院( 】艮e n c hi 删的l a u f e n tb a d u e l f r a n c o j s eb a u d e 。d e n i sc a m 眦l 三个人共同提出了j a v ap m 觚i v eg r o u p 方案 1 5 。该 方案提供一个名为p m a c t i v e 的j a v a 库( h t t p ：伽n w i n r i a 丘佃勰耐p m a c t i v c ) ，该库基于 r m l 方式，把每个j a 伯虚拟帆看作一个节点( d e ) 类的对象实体，而把节点进程看作 活动对象，进程迁移则看作活动对象被动态地绑定到一个n 0 d e 对象上。因此除了远 程方法调用不需要p r 州妇i y e 以外，p m a 砸 库负责传递活动对象，进行底层异步通 信和高层同步，对“请求”与“应答”进行自动定位 1 5 。图2 1 0 是p m m i v e 的工 作示意图。 僻日删h 口 o ) 账6 球襄删q瞳 ，、 蛊等蜊。 以_ = = = ：= 。一 ( ) e - o _ m _ “n -l 唧岬 邑 图2 一1 0 该系统的重点在于活动对象的迁移和异步、同步机制，其实现的原则是对活动 对象进行类型划分，建立类型群( t y p cg 咖叩) ，在一段特定时间内，某一类的对象被启 动，并由s t u b 接口进行传递。系统提供一个m i g r a t e t o 原语使得活动对象可以从任何 l l 硕士学位论文 j a v a 虚拟机迁移到其它任何虚拟机上。每个活动对象都有一个根元素作为唯一入口， 也作为区别标志；活动对象除了可以被自己调用以外还可以被其它对象通过公有方 法所调用；每个活动对象都由自己的控制线程来决定是否接受远程方法调用的请求， 这些请求被自动地存放在一个队列中。通常这些请求都是异步的，如果一个活动对 象同时被多个调用所请求，则一个“按需等待”( w a i t - b y n e c e s s i t y ) 机制将会处理 这些请求的同步：给每个异步的远程调用设立一个集合点，在上下文环境未符合条件 之前，进程被阻塞于该点( 在图2 1 0 中步骤l 被阻塞直到步骤2 执行完) 。 该模型的好处是对并行通信处理进行了屏蔽，实现了底层透明，不需要像m p l 那样需要有特殊的并行程序风格，可以很好的与j a v a r m i 程序兼容。但是与m p i 相 比，其功能有限，例如它不支持阻塞同步( b a r r i e rs y n c h r o n i z a t i o n ) ，而与r m i 相比，其层次结构又比较复杂，工作量也比较大( 作者声称该系统还在完善中) ，因 此妨碍了该模型的推广 1 5 。 2 2 5m p j a v a 牙弭p j m p i 2 0 0 3 年w i l l i a mp u g h 和j a i m cs p a c c o 在j m p i 基础上使用j a v an 孟0 对通信接口进行 改写直接操作缓存，得到了m p i 的一种新的j a v a 实现m p h v a ( m e s s a g cp a 踞i g j a v a l ，以避免原有j a v a1 0 流的低效率，缩短消息内容的读写时间。但是由于需要直 接对缓存进行操作，因此其缺点是编程方式复杂，代码安全性差。【1 6 】 删( 1 l l 北j a v am p i ) 则是以j w ar 为基础对m p l 标准的纯j a v a 语言实现，使 用路由表方式为m p l 通信( 包括点对点通信和群组通信) 自动选择消息的路由，消息发 送不再只由一个节点负责，所有的节点都可能参与消息的传递。由于其层次比较多， 工作量较大，因此许多功能仍未实现。【1 7 】 硕士学位论文 第3 章组间消息传递的相关分析模型 3 1 建模的原则 3 1 1 上述各种模型的启发 上述各种对群组间通信进行改进的模型中，主要的焦点都集中在通信接口的改 进与调度策略的实现等方面，包括如何使消息能够分类发送，使节点的等待时耗能 够减少，故此可以认为它们是这些模型的共同点。这些模型在具体的改进方法上也 有相同之处，它们是：一、采用了已有的系统或者策略为基础，如g m i 模型和p r o a d i v e 模型都是以j a v ar m l 为基础的，i 9 i n u l t i c a s t 模型则以m p i 标准和l p 协议为基础；二、 都对节点进行了类型划分；三、建立或者改进原有系统库文件中的通信接口，其中 g 模型改进r m i 的s t u b 和s k c l 曲o n 接口，而i p m u n i c 髂t 模型采用了修改m p i 库使之与 i p 协议相结合的方式，j a v ap m m i v e 模型则直接采用了在r m i ，并在其基础上建立 自己的群通信接口的方式；四、提出了各自的调度策略，包括消息传递方式，同步 方式等等。 其中第一点使要解决的问题能够简化，实现改进策略的工作量大大减轻；第二 点则使得系统可以对不同的节点或者进程赋予一定的优先级，以方便对不同级别的 消息进行处理；第三点则说明这些改进策略并不是凭空得来，而是在前人工作的基 础上进行研究的；第四点则是各种模型在提出改进策略之后都必须面对的问题，因 为采用的策略不同，所需的处理方式也不同。 3 1 2 建立模型的原则 模型的建立主要是解决原系统在群组阃通信时效率不高的闯题，所以结合上面 各种模型所具有的共同点，笔者把下列几点作为建立模型的基本原则： 采用修改系统库文件的通信接口( 特别是与群组通信相关的接口) 的方式， 一方面可以对改进工作进行集中控制，另一方面可以减少工作量。 用某种划分方法通信参与者进行等级划分，并且根据不同的等级赋予不同的 优先级。 充分利用已有的模型或者策略并以之作为新模型的基础。 对系统的改动尽量不影响系统原来的功能。 硕士学位论文 3 2 使用相关分析的原因 从前面的叙述，我们可以看出群组间通信所存在的问题已经越来越受到重视。 人们从不同的角度和方向对这些问题进行了深入的研究，其中也包括对m p i 模型在这 个方面所存在问题的研究。这其中，在通信调度策略中使用统计方法( 包括提取特 征函数，相关分析，回归分析等等) 也是人们的研究方向之一 1 8 。 3 2 1 相关分析简介 相关分析是指由一个或者一组随机变量来估计或者预测另外一个随机变量的问 题。根据参与计算的已知随机变量的个数，相关分析可以分为二元相关分析( 已知 一个随机变量) 和多元相关分析。相关系数：设有两组样本鱼，z 一，z n 及 孰拍，- 弧，其样本平均数分别为i ，盱，样本标准差分别为品，s ，且两组样本 之协方差( c o v a r i a n c e ) 摹呵定义为 ，2 击吾汹一弧_ - ) 。( 3 _ 1 ) 则相关系数r 定义为 ( 3 2 ) r 表示两组样本之间的相关程度，其值介于1 与1 之间( 1 r 1 ) 。当r = o 时， 表示两组样本之间不相关；当o l r l o 时称z - ，匈如与讥- 伽。一正相关，即x 与y 具有相同的升降趋势；当r 0 时称。t ，z t - - 。- 与扭- 铀t ，弧负相关，即x 与y 具有相反的升降趋势。相关系数的绝对值越大，关联强度越大。相关系数可以给出 两个随机变量的相关关系的度量1 1 9 】。 3 2 2 使用相关分析的优点 使用相关分析建立群组间通信模型，一方面能够对原来增加单位时间内系统中 消息传递的总数与缩短节点的等待时耗之间不确定的关系进行相关估计，从而可以 有效地对消息的优先级划分进行量化；另一方面可以使得系统能够动态地根据其运 1 4 硕士学位论文 行状态进行调整。另外由于待估计关系的相关变量只有两个，因此其计算量并不大， 可以有效地减少消息的冗余度，因此不会大量占用系统资源。 而且使用相关分析模型对通信接口进行优化，其改动量可以受到控制，并且不 会影响系统原来的功能和原有程序的兼容性。 3 2 3 可能出现的问题 使用相关分析进行计算时，通常会出现以下问题： 精确度的控制( 主要依赖于计算的误差) ，精确度根据不同的应用会对结果产 生很大的影响，而这些影响事前难以