（计算机应用技术专业论文）loggp模型的同步通信性能分析与评测.pdf

摘要 摘要 论文以l o g g p 并行计算模型的长消息通信机制为核心展开研究。 并行计算模型为并行算法和并行计算机系统结构的分析与设计提供 了具有指导意义的理论界面和模型框架，它是并行计算研究的重要领 域。l o g p 模型能够评测并行计算机的实际性能，其四个参数l 、o 、g 、 p 准确地表示了并行计算机的最重要的性能参数。l o g g p 模型是l o g p 模型的扩展，在通信模型中引入了线性长消息机制，提高了通信带宽， 既更好地发挥了并行机的效率，又使得实际结果接近设计期望。 在集群环境中，主要使用消息传递方式进行并行计算，m p i 作为 最流行的消息传递平台，得到广泛应用。对于集群计算机上的m p i 平 台的异步执行机制，l o 耵p 模型也是异步的，所以l o g g p 模型能够有 效地指导集群计算杌下船i 平台上的并行计算。在发送长消息时，影 响l o g g p 模型的通信性能的重要一点是没有考虑到同步。通过对长消 息加一个长度界限值的方法对1 0 9 g p 模型进行改进，使得集群环境下 的m p i 程序实现更加精确，效率更高。论文提出了根据m p i 下的通信 模式来评估l o g g p 模型的参数的方法，设计了并行测试程序，对改进 前后1 0 9 g p 模型的参数在曙光1 7 0 0 集群计算机上进行了实际测量。 实验结果显示发送额外开销是l o g g p 模型线性长消息的通信瓶颈，改 进前后模型的参数的对比分析结果和性能对比结果表明改进后l o g g p 模型的性能优于l o g g p 模型。 关键字：并行计算模型，l o g p 模型，l o g g p 模型，杼i ，长消息 a b s t r a c t 1 1 l ek 咖e l0 ft h i st h e s i si ss y n c h r o n o u sc o m m u n i c 撕o no fl o n g m e s s a g e0 fl 0 9 g pm o d d 虹勰i m p o n a n tr e s e 砌a r e ao fp 缸a l l e l c o m p u t i n 吕p a 瑚1 e lc o m p u t i n g 脚蹦p r o v i d ea nd j 删i v e t h e o r e t i c a l i n t e r f a c ea n dm o d e l 丘锄郫嘟kf b ra n a l y s i sa n dd e s i g l i i n go fb o t hp 啦l l e l a l g o r i t h m s 衄ds y s t e m s 删t e c t u r l o 驴m o d e lc a ne s t i m a t et h er c a l p c r f b 城她c eo fp a r a l l dc o m p u t c r ，a n dr e a lp a r 柚e t e r0 fp 盯a 1 1 e lc o m p u t e r c a nb ee x a c n ye x p r e s s e db y 五d l l rp 舢e t 盯k o ，g ，p 1 kl o g g p m o d e l i s a i ie x t e n s i o no ft h e 她pm o d e lb y 跏p p o r t i n gl o n gm c s s a g e ，w h j c h p m v i d ea 舢c hh i g h e fb 柚d w i d t l l ，n o to n l ye x p l o i t st h ep e r f o m 粕c eo f p a r a l l e lc o m p u t e r ，b u ta l s om a l 【e st h ep i e d i c t i o nb ed o s et ot h en l 玎t 洳e e f f c d p m n c lc o m p u t i n gj nc l u s t e r s 迅i m p l e m e n t e db ym a s s a g e - p 舔s i i l g a st h em o s p o p u l 盯m 越s a g c _ p a s s j n gp l a t f b r ，m p ii su s e dw i d e l y - m p i p r o g 姗i m p l e m e n t a t i o ni n c l u s t e 璐i s a s y n c h r o n o u sa n db ) g g pi s 觞y l l c h r o n o u s ，s ol o g g pc a n a d m i t st h em p lp a r a l l e l a s y n c h i o n o u s p i o j 卿m i n gs t y l ei nc l u s t c 墙t h en e e do fs y n c h 瑚i z a t i o nw h 蚰s e n d i n g al 叫gm 鹤s a g ei so u to f n s i d c r a t i o nu n d e rt h e 螂pm o d c l ，w h i c h 栅e c t st h e 如鼢d v 卸t a g eo f 咖m 蛐i t i o np 髓f 0 玎彻c c t h e 螂p m o d e lw a se x t e n d e db ya d d i n gat h 戚o i df o rl 帅gm c s s 噌el e n g t h w l l i c h m a k c sm p ip m g 姗m o ma c c u r a t ea n de m c i e n ti nc i u 咖r s t h em e t h o d o fe v a l u a t i n gt h ep a r a m e t e i s0 ft h el o g g p sb 鹤c do no o m m u n i 龃t i o n m o d eo fm p i i s 垂v i n n l ep a p e ia n d p 缸a l l e lt e s t h gp f 0 替a mi sd e s i 印e d 摘要 1 1 1 ep a r 锄c t e r so fl o g g p 孤di t sc x t c n d e dm o d e li st e s t c di nm a c l i i n e ： d a w n i n gt c l 7 0 0s u p e rs e “e lb y 粕a i y z et i l ed a t ao ft e s t ，t h er c s u n i n d u d e ( 1 ) s e n 曲1 9 o v e r h e a di st l l eb o m e _ n e c ko f l o n gm 骼s a g e c o m m u n i c a t i o nu n d e rl o g g pm o d e l ，( 2 ) t h ep e r f o m l 柚c eo fe x t e n d e d l o g g p m o d e li sb e t t e rt h a nt i i el d g g pm o d e k i e y w o r d s ：p a m l l e lc o m p u t i n gm o d e l ，l d g pm o d e l ，l d g g pm o d e l ，m p l ， b m gm e s s a g e y8 7 9 8 2 9 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：蕉壁笙 日期：蒯年弓月f o 日 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保留论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名虚鲻 日期：州年7 月c 。日 北京交通大学硕士学位论文 1 绪论 1 。1 研究背景 人类对计算机性能的要求永无止境，在众多领域中对计算提出了 极高的具有挑战性的要求。面对这种挑战，在一般的计算机上用传统 的计算方法往往是无能为力的，而并行计算正是实现高性能计算、解 决挑战性计算问题的有效手段。在对并行计算的广泛需求中，归纳起 来主要有三种类型的应用： ( 1 ) 计算密集( c o m p u t e i n t e n s i v e ) 型应用，如大型科学工 程计算与数值模拟； ( 2 ) 数据密集( d a t a _ i n t e n s i v e ) 型应用，如数字图书馆、数 据仓库、数据开采和计算可视化等； ( 3 ) 网络密集( n e t w o r k i n t e n s i v e ) 型应用，如协同工作、 遥控和远程医疗诊断等。 从另一方面讲，也正是这些重大的应用需求推动了当代并行计算 技术的迅速发展。 并行计算的出现源于实际应用程序存在内在并行度这一个基本 事实。同时性和并行性是物质世界的一种普遍属性，具有实际物理背 景的的计算问题在许多情况下都可以划分为能够并行计算的多个子 任务。针对某一具体应用问题，可以利用它们的内在并行度，设计并 行算法，将其分解成相互独立、但彼此又有一定联系的若干个子问题， 分别交给各台处理机，而所有处理机按照并行算法完成初始应用问题 1 绪论 的求解。 可以看到，应用程序中是否存在可挖掘并行度是并行计算机应用 的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应 用中具有举足轻重的地位。 在使用并行计算机解决一个实际问题时，并行算法的设计是很重 要的，而且最终它要成为一个由程序实现的结构依赖性的算法。这就 需要有一个抽象的并行计算机结构来作为研究高效的结构依赖性的 算法的基础，以保证所设计的并行算法适应广泛的并行计算机结构， 并能依照抽象的结构来分析并行算法的效率，从而指导与并行结构相 匹配的并行算法设计。 从并行算法的设计和分析出发，从各种具体的并行机中抽象出 来，在一定程度上反映出具体并行机的属性，可以使算法研究不再局 限于某一具体的并行机的模型，称之为并行计算模型( 或抽象机器模 型) 。“。从更广阔的意义来说，并行计算模型为并行计算提供了硬件 与软件的界面。在该界面的约定下，并行系统的硬件设计者和软件设 计者可以开发对并行性的支持机制，从而提高系统的性能。 并行计算模型的主要作用如下： ( 1 ) 并行计算模型是并行算法实现的基础。并行算法设计与分 析依赖于并行计算模型，通常人们针对统一问题可以设计出多种不同 算法以适应在不同模型上对该问题的求解，并分析和评价并行算法的 优劣。 ( 2 ) 并行计算模型给并行计算设计与分析提供了一个简单方便 北京交通大学硕士学位论文 的框架。由于并行计算模型抽象了一类并行计算机的基本特征，避开 了硬件结构过多的繁琐细节的限制，从而保证了它在相当范围内的通 用性，同时又能反映出不同算法的主要特征，为算法设计提供启发、 指导和评价的依据。 ( 3 ) 并行计算模型使并行算法设计具有一定的生命力。算法设 计者避开了多种多样的具体的并行计算机结构，依据并行计算模型来 设计算法。这样，一方面可以使算法研究者集中精力在开发应用问题 本身固有的并行性，分析算法性能；另一方面设计出的算法具有通用 性，从而使并行算法的研究成为一项相对独立的活动。 因此，研究并行计算模型具有重大意义。 1 2 并行计算模型研究现状 目前，并行计算模型已经不再是仅仅受到算法研究者的密切关 注，它也受到越来越多的软件设计者和硬件设计者的关注。这是因为 在诸如设计问题的解决方案、软件编码、将算法转换为高效的机器指 令执行序列、设计高效的执行硬件等一系列过程中，人们都对建造计 算模型提出了自己的要求。 冯诺伊曼模型已经成为统一通用的串行计算模型在顺序计算中 取得了巨大的成功。由并行计算机系统的公共模式，是可以探索一个 通用的并行计算模型的。如图卜1 ，并行计算机系统通常都是由网络 连接多台计算机构成的，而每台计算机都是由微处理器、高速缓存、 d r a m 和网络接口组成。从理论上分析，跟据这种机制仍然可以寻求 一个统一的并行计算模型“。 l 绪论 图卜1 并行计算机系统的公共模式 现存的众多并行计算模型中，基本上它们都是将某一类并行计算 机的某些基本特征抽象出来而形成的。如：p r a m ( p a r a l l e lr a n d 锄 a c c e s sm a c h i n e ) 模型“”是对一类共享存储的并行机的特征抽取，它 抛开通信干扰，可用于直接开发原始算法内在细粒度并行。l o g p 模型 “”是对一类分布式并行计算机的特征抽取，是基于点对点通信的一种 计算模型，集中分析处理机与网络之间的瓶颈。c 3 ( c o m p u t a t i o n ， c o 衄u n i c a t i o n ，c o n g e s t i o n ) 模型“2 1 是对一类基于消息传递的分布 式粗粒度系统的特征抽取，集中反映的是网络拥挤和路由影响。b 嗍 ( b 1 0 c kd i s t r i b u t e dm e m o r y ) 模型“”则是共享存储编程模式与消息 传递的分布式存储系统之间的一个桥梁模型，反映的是存储系统中流 水线预取等方面影响。 但是，它们缺乏通用性。模型使用者迫切需要一个通用并行计算 模型，在该模型上，硬件设计者可以设计多种结构的并行计算机而无 须虑及被执行的软件，软件设计者能够编写各种可在此模型上有效执 行的程序而无须考虑所使用的硬件。l o g p 模型“的提出正是为了解决 这一问题。尽管l o g p 模型并不完美，但是与其它模型相比较却显示 4 北京交通大学硕士学位论文 出了优点。与此同时，针对1 0 9 p 模型的弱点，模型研究者相继提出 了一些改进的l o g p 模型n 4 呻1 ，从而能够更好地利用模型解决问 题。 l o g p 是一个能很好地符合并行计算机系统公共模式的并行计算 模型。它与p r a m 模型和b s p 模型的最大不同之处就在于它没有显式 同步操作。根据技术发展的趋势，未来的并行计算机发展的主流之一 是大规模并行计算机( m a s s i v e l yp a r a l l e lp r o c e s s o r ，简单记为m p p ) 啪1 ，它是由上千个功能强大的处理器存储器节点，通过受限带宽和 可观延迟的互联网络构成。所以建立并行计算模型应该充分考虑此情 况，这样基于此模型的并行算法才能够在现有的和未来的并行计算机 上有效运行。 相对于p r a m 模型和b s p 模型而言，l o g p 是最具有实际意义的并 行计算模型。过去对l o 驴模型的研究，主要是从理论分析的角度， 对其参数进行分析研究，通过增加或者减少其参数个数来优化并行程 序设计，提高通信带宽。至今为止，最好的一种扩展是l o g g p 模型“， 它是通过在l o g p 引入一个长消息的的线性机制扩展而来，该模型充 分抽取了并行机最重要的方面处理器之间的通信，迫使算法设计 者关注数据布局和消息分组的问题。最近的一些研究可以参考文献 2 3 6 7 ，由于l o g p 模型微观通信所涉及参数较多，基于l o g p 模型微观通信涉及的算法分析比较复杂，所以这种研究是顺应应用要 求的。 1 3 论文研究内容 本文将结合m p i 的通信模式以l o g g p 并行计算模型的长消息通信 5 l 绪论 机制为核心展开研究，通过分析l o g g p 模型的长消息传递机制，对 l o g g p 模型进行改进，对模型改进前后的参数和通信开销进行评估。 并根据m p i 程序设计的特点，制定通信时间测量规范和通信时间测量 方法，然后在曙光t c l 7 0 0 集群服务器进行实际测量，根据测试数据 对l o g g p 模型改进前后的长消息通信性能进行分析。 1 4 论文的组织结构 论文的组织结构如下： 第一章简要介绍了论文的研究背景，并行计算模型研究现状和 研究内容。 第二章主要介绍了1 0 9 p 模型和l o 酊p 模型，对两个模型的参数 进行了分析和讨论，通过与p r a m 模型和b s p 模型的对比、分析，总 结了l o g p 模型的特点。通过比较l o g p 模型和l o g g p 模型的长消息通 信机制，总结了l o g g p 模型的长消息通信的优点和性质。 第三章提出了l o g g p 模型改进的目标，给出了改进模型的方法， 并分析了改进后模型的通信开销。 第四章分析了l o g g p 模型在集群环境中指导m p i 编程时同步通 信的不一致性，结合押i 的四种典型的通信模式，给出了集群环境中 l o g g p 模型的通信开销评估方法。 第五章设计了并行测试程序，制定了通信时间测量规范和通信 时间测量方法，在曙光t c l 7 0 0 集群服务器上对改进前后l o g g p 模型 的参数进行了实际的测量，对测量结果进行了详细的分析，得到了结 论。 6 北京交通大学硕士学位论文 第六章是论文的总结和所得出的结论。 2l o g p 模型概述 2l o g p 模型概述 并行技术发展使并行机正趋向于这样一个系统：由简单独立的计 算机集合组成，每个计算机包括一个微处理器、c a c h e 高速缓冲存储 器和一定规模的动态随机访问存储器( d r a m ) ，由一个高性能的通信网 络连接。并且这种趋势随着小规模计算机日益占领更多的市场而加速 发展。在这样一个系统中，通过网络接口的通讯带宽远远滞后于处理 机与存储器内部带宽，虽然接口技术正在改进，但处理机速度却发展 得更快，所以必须把延迟和通讯以及有限的带宽仍然作为并行计算机 的瓶颈。 并行机的发展趋势和算法设计要求导致l o g p 模型的提出。l o g p 模型摒弃了机器的特殊问题而通过四个参数来描述和强调并行计算 机的共性问题：通信延迟( l ) 、通信开销( o ) 、通信带宽( g ) 和处理机 数目( p ) 。在l o g p 模型提倡的方法中，一个好的算法就是按照这些参 数使一种策略具体化以适应不同的机器。 2 1 l o g p 模型 2 1 1 l o g p 模型的定义 l o g p 模型由d c u l l e r 等人提出”3 ，与p r a m 模型和b s p 模型的最 大不同之处就在于它没有显式同步操作。根据技术发展的趋势，2 0 世 纪9 0 年代末和未来的并行计算机发展的主流之一是大规模并行计算 机( m a s s i v e l yp 8 r a l l e lp r o c e s s o r ，简单记为m p p ) 口町，它是由上 千个功能强大的处理器存储器节点，通过受限带宽和可观延迟的互 北京交通大学硕士学位论文 联网络构成。所以建立并行计算模型应该充分考虑此情况，这样基于 此模型的并行算法才能够在现有的和未来的弗行计算机上有效运行。 在此情况下，一个以m p p 为背景的计算模型l o g p 模型被提出来。 l o 驴模型由以下四个参数描述： l ( l a t e n c y ) 表示在网络中源处理器与目的处理器进行消息通信 所需要等待或延迟时间的上限： o ( o v e r h e a d ) 表示处理器发送或者接收一条消息所需要的额外 开销( 包含操作系统核心开销和网络软件开销) ，在此期间处理器不 能执行其它操作； g ( g a p ) 表示一个处理器连续两次进行发送或者接收消息的最小 时间间隔； p ( p r o c e s s o r ) 表示处理器存储器模块对数。 g 的倒数为处理器的通信带宽，l 和g 反映了通信网络的容量。l 、 o 和g 都可以表示成处理器周期的整数倍。( 假定一个周期完成一次局 部操作，并定义为一个时间单位) 。 可以看出，l o g p 模型是一种分布存储的点到点通信的多处理器模 型。它使用l 、o 、g 三个参数刻画了通信网络的特性，但是却屏蔽了 网络拓扑、选路算法和通信协议等具体细节。 本质上讲，通信网络可以看作是一个启动率为g 、延迟为l 、端 点处理器开销为。的流水线部件；网络的容量假定是有限的，在任何 时刻至多只能有玩条消息从一个处理器到另外一个处理器，且任何 消息均可以在有限但非确定的时间内到达目的地；在网络容限范围 9 2l o g p 模型概述 内，点到点传输一条消息的时间为历也。 l o g p 模型在计算通信时间时屏蔽了拓扑结构对网络性能的影响。 这是因为通过对具有上千个节点的网络( 如超立方、蝶形网、网孑l 、 胖树等) 的平均距离分析，发现它们的差别相对于整个消息传输时间 的影响是很小的。 在网络空载或轻载时，通信接口部件对于系统性能的影响更大， 在网络超载时，则会出现竞争资源的现象，使得等待时间迅速增加， 所以l o g p 模型对网络的容量加以限制。同时l o g p 模型使用了无竞争 的通信模式，因为这种模式重复传输时可以利用整个带宽，而其它的 通信模式往往依赖于选路算法、路由器缓存器数量和互联拓扑结构。 另外作为推广，针对特定的通信模式可以采用适当的参数g 进行算法 分析。 l o g p 模型鼓励编程人员采用一些好的策略，如作业分配，计算与 通信的重叠以及平衡的通信方式等等，但是这在另一方面，却增加了 编程者的负担。编程人员需要很强的技巧性，要对每个处理器的局部 计算进行仔细安排，以在网络通信能力的限制范围内将通信操作和计 算操作尽可能重叠起来，此外还需要妥善分配处理器，以减少对通信 带宽的要求和降低远程访问的频率。 综上所述，l o g p 模型将现在和将来的并行计算机的特性进行了精 确的综合，以少量的参数刻画了并行计算机的主要瓶颈，其详尽程度 足以反映并行算法设计时的主要问题，而其简捷性也足以支持详细的 算法分析。 1 0 北京交通大学硕士学位论文 2 _ 1 。2l o g p 通信机制分析 1 0 9 p 模型的消息传递机制如图2 1 所示。 1 卜q 发送 、 发送 、b li 接收 图2 一ll o g p 模型中的消息传递机制。2 1 并行程序的执行时问t 。由两部分组成，一个计算部分t 。和一个 通信部分t 即有： t 。2 t 。+ t 。一 其中计算时间可使用类似于顺序算法的方法加以推算，而通信时 间依赖于许多因素，包括网络延迟和网络竞争，因而无法用一个简单 的方程来表示。作为最基本的近似，我们将使用下列公式： t 一2t 。t ”t + n t h t 。 其中t 。是表示发送一个数据字所需要的传送时间。t 。为启动 时间，也成为消息时延，l o g p 模型中就是参数。就是t 。，它是发 送不包含数据的消息所需的时间，包括在源进程处将消息打包以及在 2l o g p 模型概述 目的进程除将消息解包所需的时间，t 。的值由所使用的网络协议所 决定。发送处理器发送一个消息后到发送下一个消息之间的g o 空闲 时间是网络竞争形成的。 2 1 2 参数讨论 一个实际的并行机有其具体的执行特征，同时又必须为算法设计 和分析提供一个合理框架。一个参数过少的模型不可能完整地描述所 有的并行机，而用一个很大的参数集对感兴趣的算法进行分析也很困 难且无必要，l o g p 模型对参数的特殊选择表示了二者之间的一种折 衷，参数取舍刚好为二者间的一个适中点。 l o g p 模型的4 个参数l 、o 、g 、p ，其中，l 、g 反映了互连网络传 送消息的平均固有性能，o 反映了处理机对网络协议的处理能力，p 为 处理机数。 实际上，因为并不是任何情况下这些参数都同等重要，所以并不 是只要采用l o g p 模型都必须全部用上这四个参数。与现实的并行系统 相结合时，经常可以忽略一、二个甚至三个参数，获得一个更简单的模 型。例如，在一个数据传输量很少的算法中，就可以忽略网络的带宽 和容量限制，从而可以忽略l 、o 、g 三个参数。另外，在有些系统中， 采用网络信息管道来发送很长的字节流，这样，信息传输时间中，信 息之问的时间间隔占主要地位，而延迟时间可以忽略，所以，l 可以 略去。在某些并行机中，处理机的通信开销对于通信间隔起了支配作 用，因此g 可以忽略。一种简单的近似技术是增加。使其与g 一样大， 从而可以忽略g ，而用至多为2 倍的。来计算。 北京交通大学硕士学位论文 但是，从另一方面来说，去掉某些参数来简化模型会产生漏洞， 算法设计者使用简化模型时，可能会导致错误的性能估计。 2 2l o g p 模型与p r 删模型、b s p 模型的比较 2 2 1l 昭p 模型v sp r a 哺模型 p r a m 模型。”是从顺序计算的冯诺伊曼( 随机存取机器r a n d o m a c c e s sm a c h i n e ，简记为r a m ) 模型直接类比得到的。作为一种理想 化的并行计算模型，它假定存在着一个容量无限大的共享存储器和有 限或者无限个功能相同的处理器，每台处理器均具有简单的算术运算 和逻辑判断功能，任何时刻各个处理器都可以通过共享存储单元相互 交换数据。 在p r a m 模型里，所有处理器是蕴式同步的，同步开销假设为零。 通过读写共享变量进行通信，通信开销忽略不计。另外，并行性开销 也不考虑。因此p r a m 模型唯一考虑的开销是负载不平衡开销。 可见，p r a m 模型保持了简单性，它被广泛用来分析并行算法复杂性， 特别适用于并行算法的表达、分析与比较。它使用简单，很多并行机 的低级细节如处理器间通信、存储管理和进程同步等都隐含于模型 中；算法设计者可以容易地设计算法，并且稍加修改就可以运行在不 同的并行计算机上。根据实际需要，有可能在p r a m 模型中加入一些 诸如同步和通信等需要考虑的问题。 与p r m 蟆型相比，l o g p 模型要复杂得多。可以说，l o g p 和p r a m 模 型是并行计算模型的两个极端。l o g p 模型面向消息传递和分布式存 储，并利用l 、o 、g 、p 四个参数较好的反映了现实世界中并行计算 2l o g p 模型概述 机的体系结构。如果使l o g p 模型的参数g = o ，l = o ，o = o ，那么它就可 以等同于p r a m 模型。p r a m 模型是一个理想化的模型，完全忽略了通 信和同步开销。在p r a m 模型里，所有处理器是蕴式同步的，同步开销 假设为零。通过读写共享变量进行通信，通信开销忽略不计，并行性 开销也不考虑。 p r a m 模型是同步的，意味着所有的指令都按照锁步方式操作，这种 方法比较费时，不能反映现实系统的异步性；它假定共享单一存储器， 不适合分布存储的异步的m i m d 机器；它假定每个处理器都可以在单 位时间内访问任何存储单元而忽略了存取竞争和有限带宽是不现实 的；它假设处理器有限或无限，对并行任务的增大不加限制，也是不 现实的。因为p r a m 模型对零通信开销和指令级同步的不现实假设， 所以它并不能够真实反映实际的并行计算机，至今它未被用于实际的 并行计算机。 相比之下，l o g p 模型过于复杂，缺乏有效的分析和性能预测的 模型，而p r a m 则过于简单，无法真实地描述物理机器。另一方面， 并行计算模型作为对现实世界的抽象，必须能便于我们进行理论分 析和算法设计，因此它应该尽量简单。p r a m 模型由于其简单性，它 被广泛用来分析并行算法复杂性，特别适用于并行算法的表达、分析 与比较，很多并行机的低级细节如处理器间通信、存储管理和进程同 步等都隐含于模型中；算法设计者可以容易地设计算法，并且稍加修 改就可以运行在不同的并行计算机上。根据实际需要，有可能在p r a m 模型中加入一些诸如同步和通信等需要考虑的问题。 但是，l o g p 模型并非因为其复杂性而不能使用。l o 妒模型将现 1 4 北京交通大学硕士学位论文 在和将来的并行计算机的特性进行了精确的综合，以少量的参数刻画 了并行计算机的主要瓶颈，其详尽程度足以反映并行算法设计时的主 要问题，而其简捷性也足以支持详细的算法分析。l o g p 模型的可用性 已经由诸如播送、求和、f f t 、排序、图的连通性等算法得以证实， 它已经打开了研究模型的新途径，不仅为算法设计者提供了设计适合 于近代并行计算机的巨量并行算法的手段，而且对设计并行计算机的 体系结构也提供了指导性意见。 2 2 2l o g p 模型v s 盼p 模型 b s p ( 块同步并行) 模型“”定义一个并行结构由以下三个部分组 成： 一组处理器存储器模块对： 实现处理器存储器模块对之间点到点传递信息的选路器； 执行同步所有处理器存储器模块对的全局通信机制。 根据上述情况，b s p 计算模型设定了三个定量参数： p 表示处理器数量； g 表示选路器吞吐率，也称带宽因子； l 表示全局路障同步之间的时间间隔。 一个基于b s p 模型的算法由若干个超步( s u p e r s t e p ) 组成，在 各个超步之间用一个同步划分。 1 5 2l o g p 模型概述 务 门口门口” 全局通信 路障同步 图2 _ 2 超步示意图 如图2 2 所示，每个超步分成有序的三个阶段： ( 1 ) 局部计算：若干个处理器并行地完成分配给自身的计算任 ( 2 ) 全局通信：处理器之间相互通信，交换数据，协调动作； ( 3 )障碍同步：确保通信过程中交换的信息被传送到目的处理 器上，并使所有处理器达到一种可知的、一致的状态。 b s p 计算模型的一个超步里，每个计算操作只使用它自身局部存 储器中的数据。这些数据或在程序启动时，或由以前超步中的通信操 作将其存放到局部存储器中。所以一个进程的计算操作与其它进程无 关。通信总是以点对点方式进行，因此不允许多个进程在同一周期对 同一存储单元进行读写。 因为采用路障同步，在一个超步中，所有存储器和通信操作必须 1 6 北京交通大学硕士学位论文 全部完成后，才能开始下一超步中的任何操作。所有这些意味着b s p 计算模型具有顺序一致性存储器模型。 b s p 模型是个分布存储的m i m d 计算模型。它不需要任何特殊的交 互机制，可以是共享变量或是消息传递。它有一个单地址空间，一个 处理器不但能够访问它的局部存储器，而且能够访问在任何节点上的 任何远程存储器。 l o g p 模型采用的参数最多，也是现有的并行计算模型中最复杂 的。b s p 模型引入了路障同步机制，并且忽略了发送和接收消息的额 外开销d ，它在某种程度上可以看成l o g p 模型的简化。如果在l o g p 计算模型中加上路障( b a r r i e r ) 同步而去除个体通信所造成的开销 ( 0 v e r h e a d ) 就变成了b s p 计算模型“，即： l o g p + b a r i i e r o v e r h e a d = b s p 因此在本质上来讲，b s p 与l o g p 是等效的，而且二者可以互相模 拟伽。用b s p 去模拟l o g p 所进行的计算时，通常会慢常数倍；而用 l o 驴去模拟b s p 所进行的计算时，通常会慢对数倍。 l o 妒模型和b s p 模型的区别并不仅限于此。l o g p 模型侧重于用 局部的观点来描述并行计算机，模型中的许多参数都和各处理机的具 体情况有关。相比之下，b s p 模型是基于大块同步的，它用更加全局 的观点来看待并行计算机。b s p 模型中参数l ，g 都重在描述和整个 并行计算机有关的行为。 与b s p 模型相比，l o g p 算法的设计技巧性很强，要对每个处理器 的局部计算步进行仔细安排，以在网络通信能力的限制范围内将通信 2l o g p 模型概述 操作和计算操作尽可能重叠起来；要妥善分配处理器，以减少对通信 带宽的要求和降低远程访问的频率。不同的l o g p 算法其设计技巧亦 不同，基本上无章可循。 2 3 l o g g p 模型 2 3 1l o g p 模型的不足之处 l o g p 模型充分考虑了网络性能和通信带宽，能够有效地指导并行 程序设计，有着独到的优越性。通过试验数据的验证“。，在只发送短 消息的情况下，l o g p 模型可以准确预测通信性能。然而，许多并行机 对长消息提供了特殊的支持，相对于短消息来说，长消息可以获得更 高的通信带宽。为了支持长消息，加利福尼亚大学的a 1 b e r t 博士通 过引入一个长消息的线性模型将l o 妒扩展为l o g g p 模型“，该模型 充分抽取了并行机最重要的方面处理器之间的通信，迫使算法设 计者关注数据布局和消息分组的问题。 2 3 2l o g g p 模型 l o g g p 模型不仅对长消息可以建模，而且对短消息也可以建模。 其通信性能用下面的参数进行刻画： l ( l a t e n c y ) ：延迟的上界，表示从源处理器发送一个消息到目的 处理器的时间。 o ( 0 v e r h e a d ) ：表示处理器在发送或接收一条消息所需的额外开 销，在此期间它不能进行其他的操作。 g ( g a p ) ：消息之问的间隔，表示处理器可以连续进行消息发送或 1 8 北京交通大学硕士学位论文 接收的最小时间间隔。 g ：长消息中每个字节的间隔，表示长消息中每个字节所需的时 问。 p ：处理器存储器模块的数目。 g 的倒数对应于长消息的通信带宽，g 的倒数对应于短消息的通 信带宽。l o g g p 模型的五个参数都可以用处理器周期的整数倍来表示， 该模型隐含了另一个参数，每个消息的大小w 。在描述并行机的特性时， 把g 定义成每个字节的时间是最自然的。然而，有时候更容易的把g 表示成每个大小为w 字节的项的间隔。 在l o g g p 模型中，认为接收消息的处理器只在整条消息到达之后 才对消息进行访问，同时假设一个单端口模型，在任意给定的时间， 一个处理器只能发送或接收一条单独的消息。 l o g g p 模型克服了l o g p 模型的仅支持短消息的不足之处，能够同 时支持短消息和长消息，刻画具体机器更为实际，使得并行程序设计 者能够高效地设计和分析算法。 2 3 3 两个模型的比较 l o g g p 模型扩展了l o 驴模型，继承了l o g p 模型的基本特征，两 者之间在通信模型、基本参数上是一致的。l o g g p 模型和l o g p 模型的 通信模型都是某个固定大小的点到点通信。与l o g p 模型一样，l o g g p 也可能经常使用其中一部分参数，获得一个更简单的模型。 由于l o g g p 长消息机制的引入，两者之间在消息传递机制方面具 2l o g p 模型概述 有不同之处。 l o g p 模型仅支持短消息传递j 其消息传递机制见节2 1 _ 2 图2 1 。 在两个处理器之间发送一条短消息需要d 吐幻个周期。其中发送处理 器中用d 个周期，传输延迟使用个周飙在接收处理器中使用另外d 个周期。 r 只 b i o c i g i g i g i g i gl i o 1 6 ig i g l s d 驾羹慕、矧、毽蕊蕊沁：。 沁一r e c e i v e i 。j r e c e i v es 肌d p 0 ，p l ，p 2 表不处理器 图2 3l o g g p 模型中的消息传递机制“” l o g g p 模型的消息传递机制如图2 2 所示。发送一条七字节的长 消息需要d 十倍一觎切个周期。发送处理器使用了d 个周期，接着 的送出的每个字节都需要g 个周期。最后一个字节在d 手伍叫占时刻 送出。传输延迟使用了个周期。最后，接收处理器需要d 个周期的 开销。发送处理器和接收处理器只有在d 个周期的额外开销中才是忙 碌的，剩下的时间内计算和通信重叠。 至今为止，l o g g p 模型是扩展l o g p 模型的最好的一种方式“。 增加的带宽参数引吏得该模型处理长消息更为实际，参数d 、占和口抽 北京交通大学硕士学位论文 取了不同形式的通信瓶颈：d 抽取了处理器在发送和接收消息中使用 的时间，占反映了长消息通信网络对每个处理器的带宽，而g 抽取了网 络的启动瓶颈。 可见，l o g p 模型仅支持短消息，而l o g g p 模型不仅支持短消息， 也支持长消息，可以用l g 和l g 分别刻画短消息通信带宽和长消息 通信带宽：对于消息长度t ，当七；1 时，l o g g p 模型就变成了l o g p 模 型，所以l o 蜘p 模型比l o 驴模型具有更好的通用性。 研究表明，影响l o g g p 模型通信性能的重要一点是发送长消息时 没有考虑到同步。为了提高l o g g p 模型的通信性能，可以对l o g g p 模 型进行改进，将在第三章详细论述改进的方法。 2 4 本章小结 本章首先介绍了l o g p 模型，通过对l o g p 模型的通信机制分析， 剖析了参数l ，o ，g 的网络开销的内涵，并对l o g p 模型参数进行了 讨论，并将l o g p 模型与p r a m 模型和b s p 模型进行对比分析，总结了 三种模型的特点：然后介绍了1 0 9 g p 模型，对比分析了l o g p 模型和 1 0 9 g p 模型的消息通信机制，总结了两个模型之间的异同点和长消息 通信的性能优点；最后，由于1 0 9 g p 模型长消息通信没有考虑到同步， 提出可以对1 0 9 g p 模型再进行改进。 2 l 3 改进的l o g g p 模型 3 改进的l o g g p 模型 3 1 模型改进的目标 集群系统的诞生源于美国国家航空和宇航局的b e o w o l f 项目和 b e r k e l e y 人学的n 0 w 项日。它足利用高速网络把一组工作站或p c 机 按照某种结构连接起来，并存并行系统软件的支持下实现高效并行处 理的系统。集群的诞生被誉为并行计算机工业后次革命性事件，改变 了人们对超级计算机的认识，为人类计算能力的提高开拓了一个巨大 的发展空间。 集群计算机具有下面的特点： ( 1 ) 使用方便，可利用原有资源。集群中每个单独的节点都是 传统的平台，用户可以在熟悉的环境下开发和运行他们的应用程序。 传统的平台提供了在工作站上运行的功能很强的程序设计环境工具， 并且有成下上万种现成的为串行执行所开发的应用程序可供使用，这 些软件可以不加修改地在集群上运行。因而可以把集群看作是一个比 多个工作站吞吐量大得多、响应时问短得多的、可供多个串行用户作 业使用的巨大的工作站。 ( 2 ) 可靠性高。集群中有多个存储器、处理机和磁盘部件，有 一个部件出现故障，其它部件仍能使用，从而保证集群能继续工作。 集群中每个节点都有自己的操作系统，一个操作系统崩溃了，其它节 点仍能工作。 ( 3 ) 可扩展性好。集群的计算能力能随节点的增加而增加。集 群中处理机、存储器、磁盘、甚至输入输出设备都可增减。由于节点 群中处理机、存储器、磁盘、甚至输入输出设备都可增减。由于节点 2 2 北京交通大学硕士学位论文 间是松耦合的，集群的节点数有可能增加到几百个甚至更多。 ( 4 ) 性能价格比高。集群的节点和互连网络等都用已商品化的 计算机产品做成，能大批量生产，使成本降低。 正是具备这些特点，集群系统已成为国内外学术界和工业界竞相 研究开发的热点。 集群计算机作为全体计算机节点的集合，这些节点由高速网络物 理地互连。典型情况下，它的每个计算节点都有自己的处理器、存储 设备，这与l o g p 并行计算模型对并行计算机结构的抽象是完全一致 的。 目前在集群计算机上，主要使用消息传递的方式进行并行计算， 而最流行的消息传递平台无疑是消息传递界面( m e s s a g ep a s s i n g i n t e r f a c e ，简记为m p i ) 平台“。与其它平台相比，m p i 平台具有很 多优点： ( 1 ) 具有很好的可移植性，几乎被所有的并行环境所支持； ( 2 ) 具有很好的可扩展性，是目前高效率的大规模并行计算( 数 百个处理器) 最可信赖的平台； ( 3 )比其它消息传递系统好用，具有很好的可开发性； ( 4 ) 具有完备的异步通信功能，为使用者提供了强大帮助； ( 5 ) 有精确的定义，为并行软件产业的发展提供了必要条件。 目前，1 6 p i 平台得到并行计算机供应商、库编写者及应用专家的 联盟的广泛支持，已经成为业界标准。 3 改进的l o g g p 模型 在m p i 平台上进行l o g g p 程序设计时，存在的一个问题就是长消 息通信时必须考虑到同步，有必要对l o g g p 模型的长消息通信机制进 行分析，获得影响l o g g p 长消息通信性能的因素，对l o g g p 模型进行 改进，以使其更有效地指导集群计算机下m p i 平台上的并行计算。 3 2 模型改进的方法 研究表明，影响l o g g p 模型通信性能的重要一点是发送长消息时 没有考虑到同步。文献 1 ，4 ，1 4 ，1 7 使用1 0 9 g p 模型来分析m p i 程 序的性能。文献 1 ，1 4 讨论了在发送长消息时的同步通信，文中假 设发送处理器在最短的时间内和接收处理器进行同步通信，把同步通 信开销归入到额外开销。中，并且对于任意长度的消息都设为一个常 量值，但是，由于发送者并不总是和接收者在最短的时间内同步通信， 且对于不同长度的消息其开销也是