（计算机应用技术专业论文）一种改进的bsp模型分析及其性能评测.pdf

摘要 论文以并行计算模型为核心展开研究。并行计算模型为并行算法和 并行计算机系统结构的分析与设计提供了 具有指导意义的理论界 面和模 型框架，它是并行计算研究的重要领域。目 前在并行计算中，尚未有一 个如冯“ 诺伊曼模型般在顺序计算中 取得成功的 真正统一通用的 并行计 算模型， 来保证硬件设计者设计多种计算机结构而无须考虑被执行的软 件，软件设计者编写各种有效执行的程序而无须考虑所使用的硬件。论 文通过有选择地考察日 前常用的五种并行计算模型，就一些候选的 机器 特征进 行深入 分析， 总 结出 一 个通用并行 计算模型应该 遵循的 原 则: 简 单而又实际， 概括性强而又描述精确。 根据这个原则，论文通过分析块 同步并行 ( b s p )模型的特点，与其它模型进行对比、分析，认为:b s p 模型可以 作为一个通用并行计算模型。 论文指出， 当 在集群环境下利用b s p 模型指导m p i 程序实现时， b s p 模型刻画的同步执行机制并不适合于m p 工 程序的异步执行特点。 通过利 用一个局部子集同步代替全局障碍同 步和将超步概念一般化为消息步的 方法对原有的b s p 模型进行改进， 可以使之更好地指导集群环境下的m p i 程序实现。论文论述了根据h 关系假设来评估改进的b s p 模型的参数的 方法，并在曙光集群计算机上进行了实际测量。实验结果显示参数的所 有变化范围被限定到某一区间里， 而且h 关系的 通信时间对通信模式的 依赖性要比 对处理器数量的依赖性大。 另外通过快速傅里叶变换的并行 化，演示了 如何利用改进的b s p 模型指导m p 工 程序的实现和代价分析， 在曙光集群计算机上的实验结果证明了改进 b s p模型的正确性和有效 性。 关键字:并行计算模型，b s p 模型， h 关系，消息步 来然作努、 耳吓厂 万 熟 勿 全r 公 石 t h e k e rne l o f t h i s t h e s i s i s p a r a l l e l c o m p u t i n g mo d e l s , a s a n im p o r t a n t re s e a r c h a r e a o f p a r a l l e l c o m p u t i n g , w h i c h p r o v i d e a n d i r e c t i v e t h e o r e t i c a l i n t e r f a c e a n d m o d e l fr a m e w o r k f o r a n a l y s i s a n d d e s i g n i n g o f b o t h p a r a l l e l a l g o r it h m s a n d s y s t e m s a r c h i t e c t u r e s . i n t h e r e a l m o f s e q u e n t i a l c o m p u t i n g v o n n e u m a n n m a c h in e h a s s u c c e s s f u l l y p r o v i d e d 。画勿 吨 a n d u n i v e r s a l m o d e l o f c o m p u t a t i o n玩t h e r e a l m o f p a r a l l e l c o m p u t i n g , h o w e v e r , t h e r e h a s b e e n n o s i m i l a r s u c c e s s . s o t h i s t h e s i s s h o w s a s t u d y w h i c h p re s e n t s fi v e r e p r e s e n t a t i v e m o d e l s o f p a r a l l e l c o m p u t a t i o n in c o m m o n u s e , a n d t h e n a n a l y z e s w h i c h m o d e l c h a r a c t e r i s t i c s二 i m p o r t a n t t o e a c h d e s i g n c o m m u n i t y . a s a re s u l t , t h i s t h e s i s c o n c l u d e s b y s u g g e s t i n g a u n i f y i n g a n d u n i v e r s a l m o d e l o f p a r a ll e l c o m p u t a t i o n w h i c h i s c o n s i s t e n t w i t h a m o d e l d e s i g n p h i l o s o p h y w h i c h b a l a n c e s s i m p l i c i t y a n d d e s c r i p t i v i t y w it h p re s c r i p t i v i t y . a c c o r d i n g t o t h e p h i l o s o p h y a b o v e , t h e t h e s i s c o m p a r e s it w it h o t h e r m o d e l a n d a n a b rz e s b s p m o d e l i n d e t a il a n d t h i n k s b s p m o d e l c a n b e re g a r d e d a s a u n i f y i n g a n d u n i v e r s a l m o d e l o f p a r a l l e l c o m p u t a t i o n . wh e n u s i n g b s p m o d e l t o 厕d e mp i p r o g r a m s i n c l u s t e r s , r e s e a r c h e r s fi n d t h a t t h e a s y n c h r o n o u s n a t u r e o f m a n y mp i p r o g r a m s d o e s n o t fi t t h e b s p m o d e l . t h e b a r r i e r s y n c h r o n i z a ti o n i m p o s e d b y t h e b s p m o d e l re s tr i c t s t h e r a n g e o f a v a i l a b l e a l g o r i t h m s a n d t h e i r p e r f o r m a n c e . t h r o u g h t h e s u p p r e s s i o n o f b a r r i e r s a n d t h e g e n e r a l i z a t i o n o f t h e c o n c e p t o # s u p e r s t e p s t h e o n 乡 n a l b s p m o d e l h a s b e e n im p r o v e d . t h e n e w b s p m o d e l a d m i t s t h e m p i p a r a ll e l a s y n c h r o n o u s p r o g r a m m i n g s ty l e i n c lu s t e r s . t h e p a r a m e t e r s o f t h e m o d e l s a n d t h e i r q u a l i t i e s a r e e v a lu a t e d 勿 h - r e l a t i o n s h y p o t h e s i s a n d m e a s u r e d i n p r a c t i c e o n a c l u s t e r m a c h i n e : d a w n i n g t c i 7 0 0 s u p e r s e r v e r . t h e r e s u l t p r o v e s t h a t t h e d e p e n d e n c e o f t h e t i m e s p e n t i n a n h - re l a t i o n i s s t r o n g e r i n t h e c o m m u n i c a t i o n p a t t e r n t h a n i n t h e n u m b e r o f p r o c e s s o r s a n d t h a t t h e t o t a l v a r i a t i o n o f t h e h - r e l a t i o n t im e i n b o t h t h e p a t t e rn s a n d p r o c e s s o r n u m b e r s i s r e s t r i c t e d w i t h i n n a r r o w l i m i t s . t o i l l u s t r a t e h o w t o u s e t h e n e w b s p m o d e l t o g u i d e im p l e m e n t i n g a n d c o s t a n a l y s i s o f mp i , a f a s t f o u r i e r t r a n s f o r m a l g o r i t h m i s c o n s i d e r e d . t h e c o m p u t a t i o n a l re s u l t s p r o v e t h a t t h e i m p r o v e d b s p m o d e l i s o f a c c u r a c y a n d v a l i d i t y . k e y wo r d s : p a r a l l e l c o m p u t i n g mo d e l , b s p mo d e l , h - r e l a t i o n s , me s s a g e - s t e p . 工 r 北京交通大学硕士研究生学位论文 第一章 绪论 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 ) 型应用， 如协同工作、 遥控 和远程医疗诊断等。 从另一方面讲，也正是这些重大的应用需求推动了当代并行计算技 术的迅速发展。 并行计算的出现源于实际应用程序存在内在并行度这一个基本事 实。同时性和并行性是物质世界的一种普遍属性，具有实际物理背景的 的计算问题在许多情况下都可以 划分为能够并行计算的多个子任务。 针 对某一具体应用问题，可以利用它们的内在并行度，设计并行算法，将 其分解成相互独立、但彼此又有一定联系的若干个子问题，分别交给各 台处理机，而所有处理机按照并行算法完成初始应用问题的求解。 可以 看到，应用程序中是否存在可挖掘并行度是并行计算机应用的 关键，而并行算法作为应用程序开发的基础，自 然在并行计算机应用中 具有举足轻重的地位。 在使用并行计算机解决一个实际问题时，并行算法的设计是很重要 北京交通大学硕士研究生学位论文 的，而且最终它要成为一个由 程序实现的结构依赖性的算法。 这就需要 有一个抽象的并行计算机结构来作为研究高效的结构依赖性的算法的基 础，以 保证所设计的并行算法适应广泛的并行计算机结构，并能依照抽 象的结构来分析并行算法的效率，从而指导与并行结构相匹配的并行算 法设计。 从并行算法的 设计和分析出 发， 从各种具体的并行机中 抽象出 来， 在一定程度上反映出具体并行机的属性， 可以 使算法研究不再局限于某 一具体的并行机的 模型， 称之为并行计算模型 ( 或抽象机器模型)3 1 从更广阔的意义来说，并行计算模型为并行计算提供了硬件与软件的界 面。在该界面的约定下，并行系统的硬件设计者和软件设计者可以开发 对并行性的支持机制，从而提高系统的性能。 并行计算模型的主要作用如下: ( 1 ) 并行计算模型是并行算法实现的基础。并行算法设计与分析 依赖于并行计算模型，通常人们针对统一问题可以设计出多种不同算法 以 适应在不同模型上对该问 题的求解，并分析和评价并行算法的 优劣。 ( 2 ) 并行计算模型给并行计算设计与分析提供了一个简单方便的 框架。由 于并行计算模型抽象了一类并行计算机的基本特征，避开了硬 件结构过多的繁琐细节的限制，从而保证了它在相当范围内的通用性， 同时又能反映出不同算法的主要特征，为算法设计提供启发、指导和评 价的依据。 ( 3 ) 并行计算模型使并行算法设计具有一定的生命力。算法设计 者避开了多种多样的具体的并行计算机结构，依据并行计算模型来设计 算法。这样，一方面可以使算法研究者集中精力在开发应用问 题本身固 有的并行性，分析算法性能;另一方面设计出的算法具有通用性，从而 使并行算法的研究成为一项相对独立的活动。 因此，研究并行计算模型具有重大意义。 北京交通大学硕士研究生学位论文 1 . 2 研究现状 目 前，并行计算模型已经不再是仅仅受到算法研究者的密切关注， 它也受到越来越多的软件设计者和硬件设计者的关注。这是因为在诸如 设计问 题的解决方案、软件编码、将算法转换为高效的机器指令执行序 列、设计高效的执行硬件等一系列过程中，人们都对建造计算模型提出 了自己的要求。 现存的众多并行计算模型中，基本上它们都是将某一类并行计算机 的 某些基本特征 抽象出 来而形成的。 如: p r a m ( p a r a l l e l r a n d o m a c c e s s m a c h i n e ) 模型124 1 是对一类共享存储的并行机的特征抽取， 它抛开通信干 扰， 可 用 子 直 接开 发 原 始 算 法内 在 细 粒 度并 行。 l o g p 模型 77 是 对 一 类 分 布式并行计算机的特征抽取，是基于点对点通信的一种计算模型，集中 分析处理机与网 络之间的 瓶颈。 c 3 ( c o m p u t a t i o n , c o m m u n i c a t i o n , c o n g e s t i o n ) 模型2 ” 是对一类基于消息传递的分布式粗粒度系统的特征 抽取，集中反映的是网络拥挤和路由影响。b d m ( b l o c k d i s t r i b u t e d m e m o r y ) 模型9 1 则是共享存储编程模式与消息传递的分布式存储系统之 间的一个桥梁模型，反映的是存储系统中流水线预取等方面影响。 但是，它们缺乏通用性。模型使用者迫切需要一个通用并行计算模 型，在该模型上，硬件设计者可以设计多种结构的并行计算机而无须虑 及被执行的软件，软件设计者能够编写各种可在此模型上有效执行的程 序 而 无 须 考 虑 所 使 用的 硬 件。 b s p ( b u l k s y n c h r o n o u s p a r a l l e l i s m ) 模 型 16 1 的提出正是为了解决这一问 题。 尽管b s p 模型并不完美， 但是与其 它模型相比较却显示出了优点。与此同时，针对 b s p 模型的弱点，模型 研究者相继提出了一些改进的b s p 模型【13 1 115 ) 2 1 ) 2 6 1 ， 从而能 够更好地利用 模型解决问题。 过去对 b s p 模型的研究，主要是从理论分析的角度，来研究它之上 的一些典型的并行算法的分析与设计，而近期的研究热点却从在模型上 的算法研究转向模型的编程研究，即从理论研究转向实际应用，最近的 一些研究可以参考文献 1 4 1 7 2 2 2 5 ，因为任何并行算法的应用最 北京交通大学硕士研究生学位论文 终都要落实到具体的编程上面，所以这种转变是顺应应用要求的。 1 . 3 论文的组织结构 论文的组织结构如下: 第二章详细介绍了目 前常用的五种并行计算模型的性质、特点及其 各自的应用情况: 第三章分析了构造一个通用并行计算模型的困难性和必要性，总结 出发展一个通用并行计算模型应该遵循的原则。分析了一些构造并行计 算模型的主要特征，通过与 其它模型进行对比、分析， 指出b s p 模型可 以作为一个通用并行计算模型。 第四章分析了b s p 模型在集群环境中指导m p i 编程的弱点，介绍了 一种改进的b s p 模型。 第五章给出了集群环境中改进的b s p 模型的参数的评估方法，在曙 光集群计算机上进行了实际的测量。通过一个快速傅里叶变换算法演示 了利用改进的b s p 模型分析和设计m p 工 程序的方法，并在曙光集群上进 行了实际测试。 第六章是论文的总结和得到的结论。 北京交通大学硕士研究生学位论文 第二章 并行计算模型概述 在目 前形形色色的并行计算模型中，作者有选择地抽取五种常用的 模型进行考察。 除了最基本的p r a m 模型之外， 其余四 种分别是b s p 模型、 l o g p 模型、 d 模型、 b d m 模型。 与p r a ” 模型有所不同， 后四 种模型为了 弥补p r a m 模型的不精确性， 均通过将某些机器特征抽象成一些常数因子 的方法来刻画并行计算模型，并且考虑到同步、通信等因素，能够较为 真实地反映并行计算机的 性能， 这些改变代表了 并行计算模型研究的 趋 势。以 上五种模型在并行计算各个阶段的研究和发展方面起到了重要作 用。 2 . 1 p r a m模型 p r a m模型i% ) 是从顺序计算的冯 诺伊曼 ( 随机存取机器， r a n d o m a c c e s s m 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 a m模型的缺点显而易见。p r a m 模型是同步的，意味着所有 的指令都按照锁步方式操作，这种方法比较费时，不能反映现实系统的 北京交通大学硕士研究生学位论文 异步性;它假定 共享单一存储器，不适合分布存储的异步的m i m d 机器; 它假定每个处理器都可以 在单位时间内访问 任何存储单元而忽略了存取 竟争和有限带宽是不现实的;它假设处理器有限或无限，对井行任务的 增大不加限制， 也是不现实的。 因为p r a m 模型对零通信开销和指令级同 步的不现实假设， 所以它并不能够真实反映实际的并行计算机，至今它 未被用于实际的并行计算机。 p r a m 模型研究者根据处理器实 现同 步的 不同 特点， 将p r a m 模型划 分为s 工 m d - p r a m 模 型 和m i m d - p r a m 模 型8 l前 者是 通 过总 结阵 列 式 结 构 的并行计算机和流水线结构的向量机的特点而抽象出来的，而后者是在 总结共享存储器多处理机结构特点的基础上抽象出来的。二者的区别可 以从图2 - 1 直观地对比得出。 图2 - 1 s i m i r p r a m 和m u 7 .1 i 计算模型 ( 左侧是s i m d - p r a b ! 计算模型， 右侧是m i m d - p r a m 计算模型， p表示第 i 个处理器，l m 表示局部存储器) 为了解决处理器之间的读、写冲突，根据处理器对共享存储单元存 取访问的的不同约束条件，s i m d - p r a m模型又可以分为:不允许同时读 和同时写 ( e x c l u s i v e - r e a d a n d e 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 d 北京交通大学硕士研究生学位论文 e 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 d a n d c 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 工 m d - p r a m 又可以分为:通过总线访问全 局变量的m i m d 模型，简单记为m 工 m d - b u s p r a m ;通过交叉开关访问 全局 变量的m 工 m d 模型，简单记为m 工 m d - c b p r a m ; 通过多级互联网络访问 全 局变量的m a d 模型，简单记为m i m d - m i n p r a m . 作为一种基本的 计算模型， 研究者对p r a m 模型的认识不断深化， 在 它的使用过程中不断对它做出了若干推广，主要的有: ( 1 )存储竞争模型， 它将存储器分为 一些模块， 每个模块一次均 可以处理一个访问，从而可以在模块级处理存储器的竞争; c 2 )延迟模型， 他考虑了 信息的产生和能够使用之间的通信延迟; ( 3 )局部p r a m 模型， 此模型考虑了通信带宽， 它假定每个处理器 都有无限的本地存储器，而访问全局存储器是比较昂贵的; ( 4 ) 分层存储模型 ( h p r a m )，它将存储器视为分层的 存储模块， 每个模块由大小和传送时间表征，多处理器由 模块树表示，叶子为处理 器; ( 5 )异步 p r a m c a p r a m ) 模型，它更 接近于实际的 并行机， 使用 同 步障控制程序，并且考虑了成本参数的定量化。 综上所述， 尽管p r a m 模型与实际机器差别较大， 还未被用于实际并 行计算机的机器模型， 但是它仍然能够提供有价值的设计信息。 p r a m 模 型忽略了实现并行性所需要的代价，目 的是让设计者揭示给定问题的可 能的最大并行度， 并且给出了理想的并行时间复杂度的度量标准。由于 p r a m 模型抽象掉很多细节， 使得它异常简单， 所以它是开发高级并行算 法的很好的模型。 许多用p r a m 模型开发的并行算法实际上是好算法， 甚 至有时一个不实际的基于 p r a m模型的算法能够改进成一个实用的并行 算法。 在算法界，p r a m 模型被广泛采用， 并普遍接受下来， 特别是算法 北京交通大学硕士研究生学位论文 理论研究者非常喜欢使用它。 2 . 2 b s p模型 b s p ( 块同 步并行) 模型16 定义一个并行结构由以 下三个部分组成: 一组处理器/ 存储器模块对; 实现处理器/ 存储器模块对之间点到点传递信息的选路器; 执行同步所有处理器/ 存储器模块对的全局通信机制。 根据上述情况，b s p 计算模型设定了三个定量参数: p 表示处理器数量; 9 表示选路器吞吐率， 也称带宽因子; l 表示全局路障同步之间的时间间隔。 一个基于b s p 模型的算法由若千个超步( s u p e r s t e p ) 组成， 在各个 超步之间用一个同步划分。 路障同步 图2 一 2超步示意图 北京交通大学硕士研究生学位论文 如图2 - 2 所示， 局部计算: 每个超步分成有序的三个阶段: 若干个处理器并行地完成分配给自身的计算任务; 全局通信:处理器之间相互通信，交换数据，协调动作; 障碍同步:确保通信过程中交换的信息被传送到目 的处理器 、夕、jz 110目 厂厂、 ( 3 ) 上，并使所有处理器达到一种可知的、 一致的 状态。 b s p计算模型的一个超步里，每个计算操作只使用它自 身局部存储 器中的数据。这些数据或在程序启动时，或由以前超步中的通信操作将 其存放到局部存储器中。所以一个进程的计算操作与其它进程无关。通 信总是以点对点方式进行，因此不允许多个进程在同一周期对同一存储 单元进行读写。 因为采用路障同步，在一个超步中，所有存储器和通信操作必须全 部完成后，才能开始下一超步中的任何操作。所有这些意味着b s p 计算 模型具有顺序一致性存储器模型。 b s p 模型是个分布存储的m i m d 计算模型。 它不需要任何特殊的交互 机制，可以是共享变量或是消息传递。它有一个单地址空间，一个处理 器不但能够访问它的局部存储器，而且能够访问在任何节点上的任何远 程存储器。 在一个实际并行计算机中，存在着许多部件之间的通信，它们要求 不同的通信模式。为了简单起见，b s p计算模型在超步中将这些通信操 作抽象为h 关系6 概念。 定义2 - 1一个h 关系是任何通信操作的抽象， 在其中， 如果每个节 点最多发出o u t 个字到各个节点， 并且每个节点最多接收i n 个字， 那么 h二o u t 9 i n ，其中 代表某种二元操作符，通常可以 取最大值 ( m a x ) 或者求和 ( 十 )。 在一个具体的全局通信阶段中，每个处理器可以向其它处理器发送 一组消息，也可以接收来自 于其它处理器的消息。一个处理器发送或接 收的消息个数构成的集合可以用 h关系来描述，h 关系的发送时间可以 s 北京交通大学硕士研究生学位论文 用参数9 来表示。 直观而言，如果所有消息的长度为一个字长， 那么h 关系的发送时间为h g . 按照超步结构的 设计和h 关系假设， 可以 很容易地根据b s p 计算模 型的参数抽象出b s p 计算模型的成本模型m l ， 如公式 ( 2 - 1 )所示: 第 ” 个 超 步 的 成 本 t h = m a x w f + m a x ( b ig0 s as p -l 0 5 is p - i 介 五 ( 2 - 1 ) 其中w , 是进程1 的局部计算所花费的时间， 力 ， 是进程.i 所进行的h 关系， p , g , l 是上面己 经设定的b s p 计 算模型的参数。 b s p计算模型允许在一个超步里重叠计算、通信和同步操作。 如果 三种操作完全重叠，则超步所需时间为 m a x ( w , g h ,刀 。 而通常只是 使用公式 ( 2 - 1 ) 的保守时间值。 如果整个计算包括s 个超步， 则总的运 行时间可以表示为公式 ( 2 - 2 ): t s , = 工 t n = 艺 二0n 秒 - 二 十 9 0 5 6 5夕 习 7, m a x ( h , ) + s l ( 2 - 2 ) 应用h 关系假设和成本代价分析公式，可以方便地进行性能预测和 算法复杂度分析。 根据成本代价公式，要充分开发出给予b s p 模型的性 能 优越的并行算法，至少要考虑如下两个原则: ( 1 ) 均衡地分配任务:每个超步完成局部计算的时间取决于计算 时间最长的节点。因此， 算法设计时要尽可能保证每个超步分配给每个 计算节点的计算任务相同; ( 2 ) 减少通信代价:由于通信的 速度相对较慢，过多的 通信将大 大增加计算代价，这就决定了程序设计时必须尽量减少各节点之间的通 信。 综上所述， b s p 模型在保留了p r a m 模型简单性的同时，引入了附加 的 参数表示由通信、 同步等所带来的开销， 以克服p r a m 模型的缺点。 除 了负载不平衡开销 ( p r a m 模型也考虑) 以外， b s p 模型设定了同步开销， 北京交通大学硕士研究生学位论文 其下限为通信网络延时 ( 即通过物理网络传递单字节所需要的时间)且 总是大于零;设定通信开销，是一个与平台有关的常数带宽因子， 它和与通信模式相关的 特定关系有关。 可见， 与p r a m 模型相比， b s p 模 型更为现实。 在b s p 模型上，已 经实现了 大量重要的 并行算法2 7 1 12 8 1 ， 最近的算法 研究成果可以 参考文献题 3 1 4 1 1 4 3 1 7 3 。 而且，一些b s p 模型研究者己 经为b s p 模型构造了 一些函数 库( 11 (1 11 (2 81 12 6 1 (2 8 1 。 利用这些b s p 库， 程序员 可以 直接编写b s p 应用程序，解决实际应用问 题。目 前， b s p 模型已经 在诸多 并行计 算应用中 取得成功1 81 (2 2 。 由 于 它能 适应多种并行计算结构， 在s g 工 p o w e r c h a l i e n g e , c r a y t 3 1 ) , i b m s p 2 , s u n 多处理机系统、 d i g i t a l a l p h a 等并行系统中得到应用。 2 .3 l 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 y p a r a l l e l p r o c e s s o r 简单记为 m p p ) 12 9 1 ，它是由 上千个 功能强大的处理器/ 存储器节点， 通过受限带宽和可观延迟的互联网络构 成。所以 建立并行计算模型应该充分考虑此情况，这样基于此模型的并 行算法才能够在现有的 和未来的并行计算机上有效运行。 在此情况下， 一个以m p p 为背景的计算模型 - l o g p 模型被提出 来。 l o g p 模型由以 下四 个参数描述: l ( l a t e n c y ) 表示在网络中源处理器与目 的处理器进行消息通信所 需要等待或延迟时间的上限; 。( o v e r h e a d ) 表示处理器发送或者接收一条消息所需要的额外开 销 ( 包含操作系统核心开销和网络软件开销)，在此期间处理器不能执 行其它操作; g ( g a p ) 表示一个处理器连续两次进行发送或者接收消息的最小时 1 1 北京交通大学硕士研究生学位论文 间间隔: p ( p r o c e s s o r ) 表示处理器/ 存储器模块对数。 g 的倒数为处理器的通信带宽， l 和g 反映了通信网络的容量。 l , 。 和9 都可以表示成处理器周期的整数倍。 ( 假定一个周期完成一次局部 操作，并定义为一个时间单位)。 可以 看出，l o g p模型是一种分布存储的点到点通信的多处理器模 型。它使用l ,。 、9 三个参数刻画了通信网络的特性，但是却屏蔽了网 络拓扑、选路算法和通信协议等具体细节。 本质上讲， 通信网 络可以 看作是一个启动率为9 、 延迟为l 、 端点处 理器开销为。 的流水线部件;网络的容量假定是有限的，在任何时刻至 多只能有夕e 条消息从一个处理器到另外一个处理器，且任何消息均可 以在有限但非确定的时间内到达目的地;在网络容限范围内，点到点传 输一条消息的时间为2 o + l o l o g p 模型在计算通信时间时屏蔽了拓扑结构对网 络性能的影响。 这 是因为 通过对具有上千个节点的网 络 ( 如超立方、 蝶形网、网 孔、胖树 等)的平均距离分析，发现它们的差别相对于整个消息传输时间的影响 是很小的。 在网络空载或轻载时，通信接口 部件对于系统性能的影响更大，在 网络超载时，则会出现竟争资源的现象，使得等待时间迅速增加，所以 l o g p 模型对网 络的容量加以限 制。同时l o g p 模型使用了 无竞争的 通信 模式， 因为这种模式重复传输时 可以 利用整个带宽，而其它的 通信模式 往往依赖于选路算法、路由 器缓存器数量和互联拓扑结构。另外作为推 广，针对特定的通信模式可以 采用适当的参数g 进行算法分析。 l o g p 模型鼓励编程人员采用一些好的策略， 如作业分配， 计算与通 信的重叠以及平衡的通信方式等等，但是这在另一方面，却增加了编程 者的负担。编程人员需要很强的技巧性，要对每个处理器的局部计算进 行仔细安排，以在网络通信能力的限制范围内将通信操作和计算操作尽 北京交通大学硕士研究生学位论文 可能重叠起来，此外还需要妥善分配处理器，以减少对通信带宽的要求 和降低远程访问的频率。 与p r a m 模型相比， l o g p 模型要复杂得多。 如果使l o g p 模型的参数 g = 0 , l = o , o = 0 ， 那么它就可以 等同 于p r 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 模型【2 对它进行扩展， 增加 了 一个参数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 m m u n i c a t i o n , c o n g e s t i o n ) 模型是通过分析 高性能可扩展的网络计算机系统特点得到的 2 3 1 。 它是一个与体系结构无 关的粗粒度的并行计算模型，其目的在于反映计算复杂度、通信模式和 通信期间潜在的拥挤因素对粗粒度网络算法的影响。 在粗粒度机器上，并行算法对通信模式非常敏感。前面所述的 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 模型考虑了最常 用的 选路方案: 存储转发( s t o r e - a n d - f o r w a r d ) 路由 和虫蚀( w o r m h o l e ) 寻径路由以及两种发送/ 接收原语: 阻塞方式和非阻塞方式对通信单元的 影响。 c 。 模型中， 拥挤作为一种全局现象，与体系结构、选路策略和处 理器间的传送数据量有关。度量拥挤是在所有消息都同时选路的假定下 进行的。 1 4 北京交通大学硕士研究生学位论文 c “ 模型特别适用于粗粒度算法的开发与分析，模型特别强调了通信 瓶颈的作用。在这个方面，它比b s p 模型和l o g p 模型都要准确和详尽， 不过这在一定程度上增加了模型的复杂度。 综上所述，c ， 模型是对一类基于消息传递的分布式粗粒度系统的特 征抽取， 它集中反映的是网 络拥挤和路由 影响。 粗粒度并行计算机上的 算法的性能非常敏感于通信模式，容易拥挤的通信模式很容易造成通信 瓶颈，并行计算机参数之间的关系以 及这些参数与通信数据量之间的 关 系对如何执行选路操作有着至关重要的影响，同时在准备消息包与建立 选路路径过程中所招致的大的软件开销也起着重要的作用。此外，粗粒 度算法通常是将串行和并行解题方法结合在一起，决定哪些子问题以及 多大的子问题应该串行解，哪些应该并行解，这对算法的总体性能也是 一个非常关键的问题。 目 前， c 模型作为开发敏感于并行计算机参数的 粗粒度算法的平台， 己经研究了诸如矩阵相乘、确定二元图像的连通性等并行算法，并且在 d e l t a 和p a r a g o n 等并行系 统上验 证了c3 模型的 有效性。 (8 3 2 . 5 b d m模型 b d m ( b l o c k d i s t r i b u t e d m e m o r y ) 模型， 是一种块分布模型，它可 以作为共享存储编程模式与基于消息传递的分布式存储系统之间的桥梁 模型。 b d m 模型主要使用四 个参数描述: p 表示处理器个数: m 表示局部存储器中连续的m 个字; t 表示处理器从发出访问请求到得到远程数据的最大延迟时间，它 包含了准备请求的时间、请求包在网络中路由的时间、目的处理器接受 请求的时间以及将包中m 个连续字返回给源处理器的时间; 。 表示处理器发送数据到网络或从网络接收数据的时间。 北京交通大学硕士研究生学位论文 由上述可知，处理器对远程连续访问m个字需要: + m 。 时间，k个 处理器访问同一主存段所需kc -r + m a) 时间。 b d m 模型认可流水线预取 技术， 即某个处理器的k 次 预取操作所需时间为2 + k m a ， 通过数据访问 进行消息传递处理。 参数m 反映了空间局部性特点， 提供了一种评价共 享主存的算法性能的方法，度量了由于远程访问引起的处理器之间的通 信。 b d m模型考虑了 共享主存中的存储竞争问题， 并且提供方法用来分 析网络的路由 情况。不过，b d m模型认为初始数据置于局部内存中，对 于共享主存程序的编程者来说，需要增加额外的数据移动操作。b d m模 型没有考虑网络中影响延迟的因素，例如处理器的本地性、网络的拥挤 状况，同时也未考虑系统开销。 综上所述，b d m模型是共享存储编程模式与消息传递的分布式存储 系统之间的一个桥梁模型， 反映的是存储系统中流水线预取等方面影响。 b d m 模型的研究者己 经在该模型上实现了诸如负载平衡、排序、 f f t 、 矩 阵相乘等并行算法，并且算法复杂度可以达到最优或近似最优。 2 . 6 模型列表比较 为了对考察的五种并行计算模型有一个清晰直观的认识，也便于对 它们进行直接比较， 作者