（计算机软件与理论专业论文）cabsp模型及其性能评测.pdf

摘要 摘要 本文以并行计算模型为核心展开研究。一个准确的、完善的并行 计算模型能够在很大程度上指导与简化软件和硬件的设计工作。论文 通过有选择地考察目前常用的五种并行计算模型，就一些候选的机器 特征进行深入分析，总结出一个通用并行计算模型应该遵循的原则： 简单而又实际，概括性强而又描述精确，在模型上编写的程序具备时 间的可预测性并易于实现。根据这个原则，论文通过分析块同步并行 ( b s p ) 模型的特点，与其它模型进行对比、分析，认为：b s p 模型可 以作为一个通用并行计算模型的基础模型加以研究发展。 论文分析了b s p 模型、a b s p 模型和c s a b s p 模型在并行程序任 务的分配上存在的不足之处，在计算负载不均衡时会影响并行程序的 执行效率，进而提出了c a b s p 模型。它与以往的b s p 及其相关模型 相比，引入了一个新的向量参数计算因子c ，用于衡量集群中各个节 点的计算处理能力，并根据节点的实际计算能力分配并行任务，使得 c a b s p 模型在保留了b s p 模型优点的基础上，能够保证并行任务以最 优的方式分配到每一个节点。论文提出了引入计算因子c 后并行程序 执行时间的测试方案，对b s p 模型、a b s p 模型、c s a b s p 模型和c a - b s p 模型循环乘积并行程序的执行时间在曙光t c l 7 0 0 集群系统m p i 环境 下进行了测试，并作了对比分析。结果表明，考虑到计算因子后，在 负载不均衡的情况下，c a _ b s p 模型能够简单有效的提高并行程序的执 行效率，与此同时，论文也指出了c 卜b s p 模型在应用上的适应性以 及在参数量化方面尚需继续深入研究。c a b s p 模型对于以b s p 模型 为基础的其他并行计算模型向着异构化、实用化发展具有指导意义。 关键字：并行计算模型，c a - b s p ，计算因子，m p i ，性能评测 北京交通大学硕士学位论文 1 1 i ek e m e lo ft h i sp 印e ri st l l ep a m l l e lc o m p u t i i l gm o d e l s ap a r a 玎e l c o m p u t i l l gm o d e lw h i c hi s e x a c t柚dc o n s u m m a t ec a nd i r e c ta n d p r e d i g e s tt h ed e s i g no ft h es o f t w a r ea n d t h eh a r c l w a r eg r e a t l y tt 1 l i sp a p e r s h o w sas t u d yw h i c hp r e s e n t sf i v e r e p t c n t a t i v em o d e l so fp a m l l e l c o m p u t a t i o ni l lc o m m o nu s ea n dt h ed i f l e r e n tm k st l l e ys e r v ei i it h e i r 印p l i c a t i o nf i e l d ，a n dt h e na n a l y z e sw h i c hm o d e lc h a r a c t e r i s t i c sa r e i m p o r t a n tt oe a c hd e s i g n m m u n i t y a sar e s u l t ，t l l i st h e s i sc o n c l u d e sb y s u g g e s t i n gau n i f y i n ga n d u n i v e r s a lm o d c lo fp a 确l l e lc o m p u t a t i o nw h i c h i sc o n s i s t e n tw i t ham o d e ld e s i g np h i l o s o p h yw h i c hb a l a n c e ss i m p l i c i t y a n dp r a c t i c a l ，s t m n g l yg e n c m l i z e da n da c c u m t e l yd e s c r i b e d ，e a s yt ow r i t e ap r o g r a mo nm em o d e l 柚dt l l en i n t i m ec a nb ed o p e do u t a c c o i d i i l gt o t h ep h i l o s o p h ya b o v e ，t h ep a p e rc o m p a r e sb s p w i mo t l l e rp a m l l e lm o d d a n da n a l y z e sb s pm o d e li nd e t a i l 柚dt h i n k sb s pm o d e lc a nb e r e s e a r c h e da n dd e v e l 叩e da sab a s em o d e lo ft h eu n i 母i n ga n du n i v e r s a l m o d e lo fp a r a l k l m p u t a t i o n t h e 他s e a r c h e rf i n d st l l a tt h eb s pm o d e l a - b s pm o d e l 柚dt h e c s a b s pm o d e ia ”a l ls h o n c d 伽t l l ed i s t i i b u t i o no ft h ep a m l l e lt a s k ，t h e p a r a l l e lp r o 班m se 伍c i e n c ym a y b ei n 丑u 蛐c e dw h e nt l l ec a l c l l l a t el o a di s n o te q u n i 嘶u m ，w ep r o p 0 c a b s pm o d e l ，m p a f ew i mn l eo t h e r p a r a l l e lm o d e l ，t h ec a - b s pm o d e li l p o nt h ec a k u l a t eg e n ec a san e w v e c t o rp a 删e t c rt ow e i g ht h ec a l c u l a t ca b m t yo f t h ep r o c e s s o 硌i l lt h e c l u s t e i st l l e nd i s t r i b u t et l l et a s kb a s eo nt l l ea b i l i t v 1 1 l ec a b s pm o d e li s n o to n i yr e s e r v e dt l i es h d n g p o i n to ft h eb s pm d d e la l i da l m a k et l l e d i s 喇b u t i o no ft h ep a m l l e lt a s kw 曲山eb e s tm o d e t h ep 印e ra d v 卸c e sa t e s tc a f o rt h em n t i m eo ft h ep a m l l c lp i o g r a mw i i ht l l ec a l c u l a t eg e n ec ， t h e nt e s t s 柚d 柚a l y s i st h em 岫eo f t l l ec y c l ep i o d u c tp a m n e lp m 铲a m o nt l i eb s pm o d e l ，a - b s pm o d e l ，c s a - b s pm o d e la n dt h ec a - b s p m o d e lu n d e ft l l em p le n v i m m e n ti nt h cd a w n 玳gt c l 7 0 0c l u s t e lt 1 i e i c s u l tp m v e st l i a tt i l ec a - b s pm o d e lc 强i m p r o v et i i ep r o g m m ，s 摘要 e f f i c i e n c ys i m p l ya n de f 诧c t u a l l y ，a tt h es a m et i m e ，w ea l s op o i n to u tt h a t t h ec a b s pm o d e lh a ss o m el o c a l i z a t i o nw h e na p p l i e da n dn e e d l u c u b r a t et oe s t i m a t et h ep a r a m e t e l t l l ec a - b s pm o d e lc a nd i t e c tt h e d e v e l o p m e n to ft h ep a r a l l e lm o d e lw h i c hb a s eo nt h eb s pm o d e lt ob e h e t e m g e n e o u sa n dm o r eu t i l i t y k e y w o r d s ：p a r a l l e lm o d e l ，c a - b s p ，c a l c u l a t eg e n e ，m p l ，p e r f o 啪a n c e e v a l u a t i i l g 独创性声明 y 8 7 9 8 二2 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的材 料。与我一起工作的同志对本研究所做的任何贡献已在 论文中作了明确的说明并表示了谢意。 本人签名： 寸蜘 一、7 日期：羔出年立月日 | 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技术 学院所有。未经许可，任何单位和个人不得拷贝。版权 所有，违者必究。 本人躲主照 日期：王年三月日 绪论 第一章绪论 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 ) 型应用，如协同工作、 遥控和远程医疗诊断等。 从另一方面讲，也正是这些重大的应用需求推动了当代并行计算 技术的迅速发展。 并行计算的出现源于实际应用程序存在内在并行度这一个基本 事实。同时性和并行性是物质世界的一种普遍属性，具有实际物理背 景的计算问题在许多情况下都可以划分为能够并行计算的多个子任 北京交通大学硕士学位论文 务。针对某一具体应用问题，可以利用它们的内在并行度，设计并行 算法，将其分解成相互独立、但彼此又有一定联系的若干个子问题， 分别交给各台处理机，而所有处理机按照并行算法完成初始应用问题 的求解。 可以看到，应用程序中是否存在可挖掘并行度是并行计算机应用 的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应 用中具有举足轻重的地位。 在使用并行计算机解决个实际问题时，并行算法的设计是很重 要的，而且最终它要成为一个由程序实现的结构依赖性的算法。这就 需要有一个抽象的并行计算机结构作为研究高效的结构依赖性算法 的基础，以保证所设计的并行算法适应广泛的并行计算机结构，并能 依照抽象的结构来分析并行算法的效率，从而指导与并行结构相匹配 的并行算法设计。 从并行算法的设计和分析出发，从各种具体的并行机中抽象出 来，并在一定程度上反映出具体并行机的属性，可以使算法的研究不 再局限于某一具体的并行机的模型，称之为并行计算模型( 或抽象机 器模型) “”。从更广阔的意义来说，并行计算模型为并行计算提供了 硬件与软件的界面。在该界面的约定下，并行系统的硬件设计者和软 件设计者可以开发对并行性的支持机制，从而提高系统的性能。 并行计算模型的主要作用如下： 2 绪论 ( 1 ) 并行计算模型是并行算法实现的基础。并行算法设计与分 析依赖于并行计算模型，通常人们针对统一问题可以设计出多种不同 算法以适应在不同模型上对该问题的求解，并分析和评价并行算法的 优劣。 ( 2 ) 并行计算模型给并行计算设计与分析提供了一个简单方便 的框架。由于并行计算模型抽象了一类并行计算机的基本特征，避开 了硬件结构过多的繁琐细节的限制，从而保证了它在相当范围内的通 用性，同时又能反映出不同算法的主要特征，为算法设计提供启发、 指导和评价的依据。 ( 3 ) 并行计算模型使并行算法设计具有一定的生命力。算法设 计者避开了多种多样的具体的并行计算机结构，依据并行计算模型来 设计算法。这样，一方面可以使算法研究者集中精力在开发应用问题 本身固有的并行性，分析算法性能上i 另一方面设计出的算法具有通 用性，从而使并行算法的研究成为一项相对独立的活动。 因此，研究并行计算模型具有重大意义。 1 2 研究现状 目前，并行计算模型已经不再仅仅受到算法研究者的密切关注， 也受到越来越多的软件设计者和硬件设计者的关注。这是因为在诸如 设计问题的解决方案、软件编码、将算法转换为高效的机器指令执行 序列、设计高效的执行硬件等一系列过程中，人们都对建造计算模型 3 北京交通大学硕士学位论文 提出了自己的要求。 现存的众多并行计算模型中，基本上它们都是将某一类并行计算 机的某些基本特征抽象出来而形成的。如：p r a m ( p a r a l l e lr a n d o m a c c e s sm a c h i n e ) 模型是对一类共享存储的并行机的特征抽取，它抛 开通信干扰，可用于直接开发原始算法内在细粒度并行。l o 驴模型“3 3 是对一类分布式并行计算机的特征抽取，是基于点对点通信的一种计 算模型，集中分析处理机与网络之间的瓶颈。c 3 ( c o m p u t a t i o n ， c o m u n i c a t i o n ，c o n g e s t i o n ) 模型是对一类基于消息传递的分布 式粗粒度系统的特征抽取，集中反映的是网络拥挤和路由影响。b d m ( b 1 0 c kd i s t r i b u t e dm e m o r y ) 模型1 则是共享存储编程模式与消息 传递的分布式存储系统之问的一个桥梁模型，反映的是存储系统中流 水线预取等方面的影响。 但是，它们缺乏通用性。模型使用者迫切需要一个通用并行计算 模型，在该模型上，硬件设计者可以设计多种结构的并行计算机而无 须虑及被执行的软件，软件设计者能够编写各种可在此模型上有效执 行的程序而无须考虑所使用的硬件。b s p ( b u l ks y n c h r o n o u s p a r a l l e l i s m ) 模型“”的提出正是为了解决这一问题。尽管b s p 模型 并不完美，但是与其它模型相比较却显示出了优点。与此同时，针对 b s p 模型的弱点，模型研究者相继提出了一些改进的b s p 模型嘲嘲u ”， 从而能够更好地利用模型解决问题。 过去对b s p 模型的研究，主要是从理论分析的角度，来研究它之 4 绪论 上的一些典型的并行算法的分析与设计，而近期的研究热点却从模型 上的算法研究转向模型的编程研究，即从理论研究转向实际应用，最 近的一些研究可以参考文献 1 2 3 4 5 ，因为任何并行算法的 应用最终都要落实到具体的编程上面，所以这种转变是符合应用要求 的。 1 3 论文的组织结构 论文的组织结构如下： 第二章详细介绍了目前常用的五种并行计算模型的性质、特点及 其各自的应用情况； 第三章分析了构造一个通用并行计算模型的困难性和必要性，总 结出发展一个通用并行计算模型应该遵循的原则。分析了一些构造并 行计算模型的主要特征，通过与其它模型进行对比、分析，指出b s p 模型可以作为一个通用并行计算模型的基础模型加以研究发展。 第四章分析了目前基于b s p 模型的两种并行计算模型：a b s p 模 型和c s a b s p 模型，指出三种模型的在并行任务分配上的缺点，介绍 了一种改进的b s p 模型c a b s p 模型。 第五章给出了集群环境中c a b s p 模型的参数的评估规则与方 案，在曙光集群计算机上进行了实际的测景。通过循环乘积的并行化 方法说明了c a b s p 模型与b s p 模型、a b s p 模型和c s a b s p 模型在不 5 北京交通大学硕士学位论文 同的负载情况下程序执行效率方面的差异。 第六章是论文的总结和所得出的结论。 6 并行计算模型 第二章并行计算模型 在目前多种多样的并行计算模型中，作者有选择地抽取五种常用 的模型进行考察。除了最基本的p r a m 模型之外，其余四种分别是b s p 模型、l o g p 模型、c 3 模型和b d m 模型。与p r a m 模型有所不同，后四 种模型为了弥补p r a m 模型的不精确性，均通过将某些机器特征抽象 成一些常数因子的方法来刻画并行计算模型，并且考虑到同步、通信 等因素，能够较为真实地反映并行计算机的性能，这些改变代表了并 行计算模型研究的趋势。以上五种模型在并行计算各个阶段的研究和 发展方面起到了重要作用。 2 1p 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 h i 模型唯一考虑的开销是负载不平衡开销。 7 北京交通大学硕士学位论文 可见，p r a m 模型保持了简单性，它被广泛用来分析并行算法复 杂性，特别适用于并行算法的表达、分析与比较。它使用简单，很多 并行机的低级细节，如处理器间通信、存储管理和进程同步等都隐含 于模型中；算法设计者可以容易地设计算法，并且稍加修改就可以运 行在不同的并行计算机上。根据实际需要，有可能在p r a m 模型中加 入一些诸如同步和通信等需要考虑的问题。 但是p r a m 模型的缺点显而易见。p r a m 模型是同步的，意味着所 有的指令都按照锁步方式操作，这种方法比较费时，不能反映现实系 统的异步性；它假定共享单一存储器，不适合分布存储的异步的m i m d 机器；它假定每个处理器都可以在单位时间内访问任何存储单元而忽 略了存取竞争和有限带宽，是不现实的；它假设处理器有限或无限， 对并行任务的增大不加限制，也是不现实的。因为p r _ a m 模型对零通 信开销和指令级同步的不现实假设，所以它并不能够真实反映实际的 并行计算机，至今它未被用于实际的并行计算机。 p r a m 模型研究者根据处理器实现同步的不同特点，将p r a m 模型 划分为s i 肋一p r a i l 模型和m i m d - p r a m 模型”1 。前者是通过总结阵列式 结构的并行计算机和流水线结构的向量机的特点而抽象出来的，而后 者是在总结共享存储器多处理机结构特点的基础上抽象出来的。二者 的区别可以从图2 1 直观地对比得出。 8 并行计算模型 图2 一ls i 肋一p r 栅和m i 如呻r 枷计算模型 ( 左侧是s i m d p r a m 计算模型，右侧是m i m d p r a m 计算模型， p i 表示第i 个处理器，u 表示局部存储器) 为了解决处理器之间的读、写冲突，根据处理器对共享存储单元 存取访问的不同约束条件，s i m d p r a m 模型又可以分为：不允许同时 读和同时写( e x c l u s i v e r e a da n de x c l u s i v e w r i t e ) 的p r a m 模型， 简单记为e r e w p r a m ；允许同时读但不允许同时写( c o n c u r r e n t r e a d a n de x c l u s i v e w r i t e ) 的p r a m 模型，简单记为c r e w - p r a m ；允许同 时读和同时写( c o n c u r r e n t r e a da n dc o n c u r r e n t w r i t e ) 的p r a m 模型，简单记为c r c w p r a m 。 而按照不同的互联网结构m i 肛p r a m 又可以分为：通过总线访问 全局变量的m i m d 模型，简单记为m i 胁一b u sp r a m ；通过交叉开关访问 全局变量的m i 佃模型，简单记为m i 一c bp r a m ；通过多级互联网络 访问全局变量的m i h i d 模型，简单记为m i 胁m i np r a m 。 9 北京交通大学硕士学位论文 作为一种基本的计算模型，研究者对p r a m 模型的认识不断深化， 在它的使用过程中不断对它做出了若干推广，主要有： ( 1 ) 存储竞争模型，它将存储器分为一些模块，每个模块一次 可以处理一个访问，从而可以在模块级来处理存储器的竞争； ( 2 ) 延迟模型，它考虑了信息的产生和能够使用之间的通信延 迟： ( 3 ) 局部p r a m 模型，此模型考虑了通信带宽，它假定每个处 理器都有无限的本地存储器，而访问全局存储器的时间开销是比较昂 贵的； ( 4 ) 分层存储模型( h p r a h i ) ，它将存储器视为分层的存储模块， 每个模块由大小和传送时间表征，多处理器由模块树表示，叶子为处 理器： ( 5 ) 异步p r a m ( a p r a m ) 模型，它更接近于实际的并行机，使 用同步路障控制程序，并且考虑了成本参数的定量化。 综上所述，尽管p r a m 模型与实际机器差别较大，还未被用于实 际并行计算机的机器模型，但是它仍然能够提供有价值的设计信息。 p r a m 模型忽略了实现并行性所需要的代价，目的是让设计者揭示给定 问题的可能的最大并行度，并且给出了理想的并行时间复杂度的度量 标准。由于p r a m 模型抽象了很多细节，使得它异常简单，所以它是 开发高级并行算法的很好的模型。许多用p r a m 模型开发的并行算法 1 0 并行计算模型 实际上是好算法，甚至有时一个不实际的基于p r a m 模型的算法能够 改进成一个实用的并行算法。在算法界，p r a m 模型被广泛采用，并普 遍接受下来，特别是算法理论研究者非常喜欢使用它。 2 2b s p 模型 b s p ( 块同步并行) 模型“”定义一个并行结构由以下三个部分组 成： ( 1 ) 一组处理器存储器模块对； ( 2 ) 实现处理器存储器模块对之间点到点传递信息的选路器； ( 3 ) 执行同步所有处理器存储器模块对的全局通信机制。 根据上述情况，b s p 计算模型设定了三个定量参数： p 表示处理器数量； g 表示选路器吞吐率，也称带宽因子； l 表示全局路障同步之间的时间间隔。 一个基于b s p 模型的算法由若干个超步( s u p e r s t e p ) 组成，使 用一个同步划分各个超步。 1 1 北京交通大学硕士学位论文 务 h 口门门 算 全局通信 路障同步 图2 2 超步示意图 如图2 2 所示，每个超步分成有序的三个阶段： ( 1 ) 局部计算：若干个处理器并行地完成分配给自身的计算任 ( 2 ) 全局通信：处理器之问相互通信，交换数据，协调动作； ( 3 ) 障碍同步：确保通信过程中交换的信息被传送到目的处理 器上，并使所有处理器达到一种可知的、一致的状态。 在b s p 计算模型的一个超步中，每个计算操作只使用它自身局部 存储器中的数据。这些数据或在程序启动时，或由以前超步中的通信 操作将其存放到局部存储器中。所以一个进程的计算操作与其它进程 无关。通信总是以点对点方式进行，因此不允许多个进程在同一周期 对同一存储单元进行读写。 并行计算模型 因为采用路障同步，在一个超步中，所有存储器和通信操作必须 全部完成后，才能开始下一超步中的任何操作。所有这些意味着b s p 计算模型具有顺序一致性存储器模型。 b s p 模型是个分布存储的m i m d 计算模型。它不需要任何特殊的 交互机制，可以是共享变量或是消息传递。它有一个单地址空间，一 个处理器不但能够访问它的局部存储器，而且能够访问在任何节点上 的任何远程存储器。 在一个实际并行计算机中，存在着许多部件之间的通信，它们要 求不同的通信模式。为了简单起见，b s p 计算模型在超步中将这些通 信操作抽象为h 关系“”概念。 定义2 1 一个h 关系是任何通信操作的抽象，在其中，如果每 个节点最多发出o u t 个字到各个节点，并且每个节点最多接收i n 个 字；那么h = o u t i n ，其中 代表某种二元操作符，通常可以取最 大值( m a x ) 或者求和( + ) 。 在一个具体的全局通信阶段中，每个处理器可以向其它处理器发 送一组消息，也可以接收来自于其它处理器的消息。一个处理器发送 或接收的消息个数构成的集合可以用h 关系来描述，h 关系的发送时 间可以用参数g 来表示。直观而言，如果所有消息的长度为一个字长， 那么h 关系的发送时间为h g 。 按照超步结构的设计和h 关系假设，可以很容易地根据b s p 计算 1 3 北京交通大学硕士学位论文 模型的参数抽象出b s p 计算模型的成本模型“，如公式( 2 1 ) 所示： 第n 个超步的成本 丁。；m “，w j ，+ 叫 ，g ，+ l o t7 ，一1 o i ，一1 ( 2 1 ) 其中w ；是进程i 的局部计算所花费的时间， h ，是进程i 所进行的h 关系， p 、g 、l 是上面已经设定的b s p 计算模型的参数。 b s p 计算模型允许在一个超步内重叠计算、通信和同步操作。如 果三种操作完全重叠，则超步所需时间为m a ) 【( w ，卧，1 ) 。而通常只 是使用公式( 2 1 ) 的保守时间值。如果整个计算包括s 个超步，则 总的运行时间可以表示为公式( 2 2 ) ： 丁一。荟z 一2 磊嘿薯，+ g 荟侧+ 吐 ( 。一。) 应用h 关系假设和成本代价分析公式，可以方便地进行性能预测 和算法复杂度分析。根据成本代价公式，要充分开发出基于b s p 模型 的性能优越的并行算法，至少要考虑如下两个原则： ( 1 ) 均衡地分配任务：每个超步完成局部计算的时间取决于计 算时间最长的节点。因此，算法设计时要尽可能保证每个超步分配给 每个计算节点的计算任务相同； ( 2 ) 减少通信代价：由于通信的速度相对较慢，过多的通信将 大大增加计算代价，这就决定了程序设计时必须尽量减少各节点之间 1 4 并行计算模型 的通信。 综上所述，b s p 模型在保留了p r 从模型简单性的同时，引入了 附加的参数表示通信、同步等所带来的开销，以克服p r a m 模型的缺 点。除了负载不平衡开销( p r a m 模型也考虑) 以外，b s p 模型设定了 同步开销，其下限为通信网络延时( 即通过物理网络传递单字节所需 要的时间) ，并且总是大于零；设定通信开销，是一个与平台有关的 常数带宽因子，它和与特定的通信模式相关。可见，与p r a m 模 型相比，b s p 模型更为现实。 在b s p 模型上，已经实现了大量重要的并行算法“7 “”3 ，最近的算 法研究成果可以参考文献 1 2 3 。而且，一些b s p 模型研究者已 经为b s p 模型构造了一些函数库”。利用这些b s p 库，程序员可以 直接编写b s p 应用程序，解决实际应用问题。目前，b s p 模型已经在 诸多并行计算应用中取得成功“2 “”旧”1 。由于它能适应多种并行计算 结构，在s g ip 佣e rc h a l l e n g e 、c r a yt 3 d 、i b ms p 2 、s u n 多处理机 系统、d i g i t a la l p h a 等并行系统中得到应用。 2 3l o g p 模型 l o g p 模型由d c u l l e r 等人提出“”，与p r a m 模型和b s p 模型的 最大不同之处就在于它没有显式的同步操作。根据技术发展的趋势， 2 0 世纪9 0 年代末和未来的并行计算机发展的主流之一是大规模并行 计算机( 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 ，它是 北京交通大学硕士学位论文 由上千个功能强大的处理器存储器节点，通过受限带宽和可观延迟 的互联网络构成。所以建立并行计算模型应该充分考虑此情况，这样 基于此模型的并行算法才能够在现有的和未来的并行计算机上有效 运行。在此情况下，一个以m p p 为背景的计算模型l o g p 模型被提 了出来。 l o g p 模型由以下四个参数描述： 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 、端 点处理器开销为。的流水线部件；网络的容量假定是有限的，在任何 时刻至多只能有l g 条消息从一个处理器到另外一个处理器，且任何 消息均可以在有限但非确定的时间内到达目的地：在网络容量的限制 范围内，点到点传输一条消息的时间为2 0 + l 。 l o g p 模型在计算通信时间时屏蔽了拓扑结构对网络性能的影响。 这是因为通过对具有上千个节点的网络的平均距离分析，发现它们的 差别相对于整个消息传输时间的影响是很小的。 在网络空载或轻载时，通信接口部件对于系统性能的影响更大， 在网络超载时，则会出现竞争资源的现象，使得等待时间迅速增加， 所以l o 驴模型对网络的容量加以限制。同时l o g p 模型使用了无竞争 的通信模式，因为这种模式重复传输时可以利用整个带宽，而其它的 通信模式往往依赖于选路算法、路由器、缓存器的数量和互联拓扑结 构。另外作为推广，针对特定的通信模式可以采用适当的参数g 进行 算法分析。 l o g p 模型鼓励编程人员采用一些好的策略，如作业分配，计算 与通信的重叠以及平衡的通信方式等等，但是这在另一方面，却增加 了编程者的负担。编程人员需要很强的技巧性，要对每个处理器的局 部计算进行仔细安排，以在网络通信能力的限制范围内将通信操作和 1 7 北京交通大学硕士学位论文 计算操作尽可能重叠起来，此外还需要妥善分配处理器，以减少对通 信带宽的要求和降低远程访问的频率。 与p r a m 模型相比，l o g p 模型要复杂得多。如果使l o 妒模型的 参数g = o ，l = o ，o = o ，那么它就可以等同于p i t a m 模型。同时l o g p 模型是b s p 模型的改进与细化。例如：在一个超步中并非所有的处理 器都发送或接收h 条消息；在一个超步中消息一旦到达处理器就可以 立即使用，而不必像b s p 模型一样必须等到下一个超步。可以说，l o g p 模型和b s p 模型各有千秋。 l o g p 模型没有考虑消息的大小。l o g g p 模型对它进行扩展，增加 了一个参数g ，用以描述发送长消息时的网络带宽。与l o g p 模型相比， l o g g p 模型指导的算法的执行速度和性能有较大提高，但随着模型的 进一步复杂化，算法的设计与分析也更为复杂。 综上所述，l o g p 模型将现在和将来的并行计算机的特性进行了 精确的综合，以少量的参数刻画了并行计算机的主要瓶颈，其详尽程 度足以反映并行算法设计时的主要问题，而其简捷性也足以支持详细 的算法分析。对于某些算法，用这种比较复杂的模型来分析仍可操作， 因为这些参数的重要程度在不同环境下是不同的，往往可以略去其中 的一个或几个参数来使模型简单一些。l o g p 模型的可用性已经由诸如 播送、求和、f f t 、排序、图的连通性等算法得以证实，它已经打开 了研究模型的新途径，不仅为算法设计者提供了设计适合于近代并行 计算机的并行算法的手段，而且对设计并行计算机的体系结构也提供 并行计算模型 了指导性意见。 2 4 c 3 模型 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 ) 模型是通过分 析高性能可扩展的网络计算机系统特点得到的”。它是一个与体系结 构无关的粗粒度的并行计算模型，其目的在于反映计算复杂度、通信 模式和通信期间潜在的拥挤因素对粗粒度网络算法的影响。 在粗粒度机器上，并行算法对通信模式非常敏感。前面所述的 b s p 模型和l o g p 模型将复杂的通信操作交由编程人员实现，这无疑加 重了人们的负担。而c 3 模型却强调使用公用的通信操作来开发粗粒度 的并行算法。另外，前面的模型均未反映通信操作中潜在拥挤的影响， c 3 模型却考虑了网络链路拥挤和处理器拥挤对并行算法性能的影响。 c 3 模型主要由以下五个参数加以描述： p 表示处理器的个数； h 表示网络延迟； b 表示网络的对分宽度，即将网络等分为两个子网络时所需断开 的处理器连接的个数； s 表示启动时间，即建立一个消息的开销； l 表示消息包的长度，即消息包所含的字节个数。 北京交通大学硕士学位论文 c 3 模型与b s p 模型相似，计算可以划分为一系列的超步；同步出 现在两个超步之间且用路障同步机构实现；在每个超步内实现局部计 算，然后再发送接收消息。 一个超步的时间由所完成的计算单位数和通信单位数来度量，其 中计算单位数取决于所做的局部计算量，而通信单位数取决于处理器 所发送的数据量、处理器所接收的数据量、消息的传输延迟和处理器 间超过容量限制的通信所引起的拥挤。在分析算法复杂度时，必须累 加每一个超步中的计算和通信单位数，所有超步中的总计算单位数与 通信单位数之比可以指示算法的性能。 c 3 模型假定处理器不能同时发送和接收消息。在无拥挤时的通信 单位数与不同的选路方案和不同的发送接收原语有关。c 3 模型考虑 了最常用的选路方案：存储转发( s t o r e a n d f o r w a r d ) 路由和虫蚀 ( w o r m h 0 1 e ) 寻径路由以及两种发送接收原语：阻塞方式和非阻塞 方式对通信单元的影响。c 3 模型中，拥挤作为一种全局现象，与体系 结构、选路策略和处理器间的传送数据量有关。度量拥挤是在所有消 息都同时选路的假定下进行的。 c 3 模型特别适用于粗粒度算法的开发与分析，模型特别强调了通 信瓶颈的作用。在这个方面，它比b s p 模型和l o g p 模型都要准确和 详尽，不过这在一定程度上增加了模型的复杂度。 综上所述，c 3 模型是对一类基于消息传递的分布式粗粒度系统的 2 0 并行计算模型 特征抽取，它集中反映的是网络拥挤和路由影响。粗粒度并行计算机 上的算法的性能非常敏感于通信模式，容易拥挤的通信模式很容易造 成通信瓶颈，并行计算机参数之问的关系以及这些参数与通信数据量 之间的关系对如何执行选路操作有着至关重要的影响，同时在准备消 息包与建立选路路径过程中所招致的大的软件开销也起着重要的作 用。此外，粗粒度算法通常是将串行和并行解题方法结合在一起，决 定哪些子问题以及多大的子问题应该串行解，哪些应该并行解，这对 算法的总体性能也是一个非常关键的问题。 目前，c 3 模型作为开发敏感于并行计算机参数的粗粒度算法的平 台，已经研究了诸如矩阵相乘、确定二元图像的连通性等并行算法， 并且在d e l t a 和p a r a g o n 等并行系统上验证了c 3 模型的有效性。“。 2 5 b d _ 模型 b d m ( b l o c kd i s t r i b u t e dm e 啪r y ) 模型m 1 是一种块分布模型， 它可以作为共享存储编程模式与基于消息传递的分布式存储系统之 间的桥梁模型。 b d m 模型主要使用四个参数描述： p 表示处理器个数： m 表示局部存储器中连续的m 个字： t 表示处理器从发出访问请求到得到远程数据的最大延迟时间， 北京交通大学硕士学位论文 它包含了准备请求的时间、请求包在网络中路由的时问、目的处理器 接受请求的时间以及将包中m 个连续字返回给源处理器的时间： o 表示处理器发送数据到网络或从网络接收数据的时间。 由上述可知，处理器远程连续访问m 个字需要t + mo 时间，k 个 处理器访问同一主存段所需k ( t + m o ) 时间。b d m 模型认可流水线 预取技术，即某个处理器的k 次预取操作所需时间为t + l ( mo ，通过 数据访问进行消息传递处理。参数m 反映了空间局部性特点，提供了 一种评价共享主存的算法性能的方法，度量了由于远程访问引起的处 理器之间的通信。 b d m 模型考虑了共享主存中的存储竞争问题，并且提供方法用来 分析网络的路由情况。不过，b d m 模型认为初始数据置于局部内存中， 对于共享主存程序的编程者来说，需要增加额外的数据移动操作。b d m 模型没有考虑网络中影响延迟的因素，例如处理器的本地性、网络的 拥挤状况，同时也未考虑系统开销。 综上所述，b d m 模型是共享存储编程模式与消息传递的分布式存 储系统之间的一个桥梁模型，反映的是存储系统中流水线预取等方面 的影响。b d m 模型的研究者已经在该模型上实现了诸如负载平衡、排 序、f f t 、矩阵相乘等并行算法，并且算法复杂度可以达到最优或近 似最优。 并行计算模型 2 6 本章小结 本章详细介绍了目前常用的五种并行计算模型一p r a m 模型、b s p 模型、l o 驴模型、c 3 模型和叻m 模型，详细分析了它们的性质、参数 的构成及含义、模型的特点及其应用方向，同时对这五种模型在描述 并行计算方面的优点和不足之处进行了解释说明。 北京交通大学硕士学位论文 第三章并行计算模型通用性分析 顺序计算之所以取得巨大的成功，关键在于顺序计算存在一个统 一通用的计算模型ra l 模型，这个模型提供了一个简单清晰的框 架来通用地支持所有的软件和硬件。可以说，r 枷模型在顺序计算的 软什与硬件之间架起了一座桥梁。与顺序计算相比，并行计算尚未找 到一个通用有效的计算模型。因此，通过有关分析，本文总结出一个 通用并行计算模型需要遵循的原则。根据这个原则，从第二章中考察 的并行计算模型中遴选出若t 机器特征进行分析，指出b s p 模型可以 作为一个通用并行计算模型的基础模型加以研究发展。 3 1 通用模型遵循的原则 并行计算模型研究者为了设计出一个通用有效的并行计算模型 已经做了大量的工作。起初，研究人员比照顺序计算的r a m 模型，设 计出p r a m 模型。该模型遵循了简单的标准，但是却不十分精确。 如果将r a m 模型用于渐近性能的测量，那么测量结果将是足够精 确的。这是因为它在某些未模型化的机器特征如存取访问和算术指令 的开销之间作出了适当的平衡。然而在并行计算机上，却缺乏这种平 衡。同时某些未模型化的特征，特别是对非本地内存引用的开销对性 能将施加重大影响，由此导致并行计算的渐近分析结果有失精确。不 过，根据r 川模型所设定的渐近分析标准为研究人员提供了有益的借 过，根据r 川模型所设定的渐近分析标准为研究人员提供了有益的借 并行计算模型通用性分析 鉴，促使人们引入一些常数因子来描述并行计算模型，这种设计方法 已经被广泛接受，并且不断得到推广。 在当今的大规模并行计算领域里