（计算机应用技术专业论文）nhbl并行计算模型的扩展及其性能验证.pdf

摘要 并行计算模型为并行算法和并行计算机系统结构的分析与设计提供了具有指 导意义的理论界面和模型框架，它是并行计算研究的重要领域。基于l o g g p 模型 的非独占异构模型n h b l 模型是一个重要并且实用的并行计算模型，本文重点研 究了对n h b l 模型的扩展，并进行了性能验证。 本文首先介绍了五种重要的并行计算模型，重点研究了n h b l 模型的定义和 时间代价分析。然后在n h b l 模型的基础上，针对n h b l 模型的局限性，本文将 n h b l 模型中通信丌销参数扩展为发送开销向量和接收丌销向量两个向量参数， 并增加了并行计算进程对c p u 的占用比参数。然后论文阐述了测量扩展的e n h b l 模型的各个参数的方法。最后论文在m p i 并行环境下进行了扩展模型的验证，通 过对并行p s r s 排序算法的执行时间进行预测，并与实际执行时间比较，验证了 e n h b l 模型的准确性。 关键词：并行计算模型；n h b l 模型；e n h b l 模型；m p l 分类号：t p 3 9 3 9 a b s t r a c t a sa ni m p o r t a n tr e s e a r c ha r e ao fp a r a l l e lc o m p u t i n g , p a r a l l e lc o m p u t i n gm o d e l p r o v i d e sad i r e c t i v et h e o r e t i c a li n t e r f a c ea n dm o d e lf r a m e w o r kf o ra n a l y s i sa n dd e s i g n o f b o t hp a r a l l e la l g o r i t h m sa n ds y s t e ma r c h i t e c t u r e s ap a r a l l e lc o m p u t a t i o n a lm o d e l ， c a l l e dn o n d e d i c a t e dh e t e r o g e n e o u sb a r r i e rl o g g pm o d e l ，n h b l ，i sav e r yi m p o r t a n t a n dr e a l i s t i cm o d e l 1 1 1 ee x t e n s i o no fn h b li st h em a i nc o n t e n to ft h i sp a p e r , a n d m o d e lv a l i d a t i o ni sa l s op r e s e n t e d f i r s t l y , f i v ei m p o r t a n tp a r a l l e lc o m p u t a t i o n a lm o d e l sa r ei n t r o d u c e di nt h ep a p e r t h e nt h ed e f i n i t i o no fn h b la n dt h ea n a l y s i so fe x e c u t i o nt i m ea r ei l l u s t r a t e d d u et o i t sd i s a d v a n t a g e st h en h b lm o d e lh a sb e e ne x t e n d e d t h eo v e r h e a dp a r a m e t e ri nt h e n h b lm o d e lh a sb e e nr e p l a c e db yt h es e n d e ro v e r h e a dv e c t o rp a r a m e t e ra n dr e c e i v e r o v e r h e a dv e c t o rp a r a m e t e r , b e s i d e s ，an e wp a r a m e t e ra b o u tt h ep r o p o r t i o no fap a r a l l e l p r o c e s so c c u p y i n gc p uh a sb e e ni n c l u d e di nt h ee x t e n d e dm o d e l 1 1 1 ew o r kp r e s e n t e d h e r ea l s oi n c l u d e st h ep a r a m e t e r i z a t i o no far e a lp a r a l l e ls y s t e m f i n a l l y , a ne x p e r i m e n t p e r f o r m e di sp r e s e n t e d ，w h i c hc a r lb eu s e df o ra s s e s s i n gt h ee x t e n d e dm o d e l sv a l i d i t y t h ep r a c t i c a le x p e r i m e n t ，s e tu pb yc o m p a r i n gt h e o r e t i c a l l ye s t i m a t e dt i m eu s i n gt h e e n h b lm o d e la n de x p e r i m e n t a l l ym e a s u r e de x e c u t i o nt i m e ，s h o w st h ea c c u r a c yo ft h e e n h b lm o d e l k e y w o r d s ：p a r a l l e lc o m p u t a t i o n a lm o d e l ；n h b lm o d e l ；e n h b lm o d e l ；m p i c i 。a s s n 0 ：t p 3 9 3 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：渤支 签字日期：矽诱年b 月b 日 导师签名： 一 寸溯乙 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：澎r 入灾 签字日期：邪年易月否日 5 2 致谢 本论文的工作是在我的导师于双元教授的悉心指导下完成的，于老师严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来于老 师对我的关心和指导。 于老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了 我很大的关心和帮助，在此向于老师表示衷心的谢意。 于老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的 感谢。 在实验室工作及撰写论文期间，石磊峰、陈晨、赵维东等同学对我论文中的 研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 1研究背景和现状 1 绪论 随着科学技术的发展，人类对计算机性能的要求日益提高，在众多领域中对 计算提出了极高的具有挑战性的要求。面对这种挑战，在一般的计算机上用传统 的计算方法往往是无能为力的，而并行计算正是实现高性能计算、解决挑战性计 算问题的有效手段。在对并行计算的广泛需求中，归纳起来主要有三种类型的应 用： 第一，计算密集型应用，如大型科学工程计算与数值模拟等； 第二，数据密集型应用，如数字图书馆、数据仓库、数据开采和计算可视化 等； 第三，网络密集型应用，如协同工作、遥控和远程医疗诊断等。 从另一方面来说，也正是这些重大的应用需求推动了当代并行计算技术的迅 速发展。 并行计算的出现源于实际应用程序存在内在并行度这一个基本事实。同时性 和并行性是物质世界的一种普遍属性，具有实际物理背景的的计算问题在许多情 况下都可以划分为能够并行计算的多个子任务。针对某一具体应用问题，可以利 用它们的内在并行度，设计并行算法，将其分解成相互独立、但彼此又有一定联 系的若干个子问题，分别交给各台处理机，而所有处理机按照并行算法完成初始 应用问题的求解。 可以看到，应用程序中是否存在可挖掘并行度是并行计算机应用的关键，而 并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地 位。 在使用并行计算机解决一个实际问题时，并行算法的设计是很重要的，而且 最终它要成为一个由程序实现的结构依赖性的算法。这就需要有一个抽象的并行 计算机结构来作为研究高效的结构依赖性的算法的基础，以保证所设计的并行算 法适应广泛的并行计算机结构，并能依照抽象的结构来分析并行算法的效率，从 而指导与并行结构相匹配的并行算法设计。 从并行算法的设计和分析出发，从各种具体的并行机中抽象出来，在一定程 度上反映出具体并行机的属性，可以使算法研究不再局限于某一具体的并行机的 模型，即为并行计算模型【1 】。从更广阔的意义来说，并行计算模型为并行计算提供 了硬件与软件的界面。在该界面的约定下，并行系统的硬件设计者和软件设计者 可以开发对并行性的支持机制，从而提高系统的性能。 并行计算模型的主要作用如下： ( 1 ) 并行计算模型是并行算法实现的基础。并行算法设计与分析依赖于并行 计算模型，通常人们针对统一问题可以设计出多种不同算法以适应在不同模型上 对该问题的求解，并分析和评价并行算法的优劣。 ( 2 ) 并行计算模型给并行计算设计与分析提供了一个简单方便的框架。由于 并行计算模型抽象了一类并行计算机的基本特征，避开了硬件结构过多的繁琐细 节的限制，从而保证了它在相当范围内的通用性，同时又能反映出不同算法的主 要特征，为算法设计提供启发、指导和评价的依据。 ( 3 ) 并行计算模型使并行算法设计具有一定的生命力。算法设计者避开了多 种多样的具体的并行计算机结构，依据并行计算模型来设计算法。这样，一方面 可以使算法研究者集中精力在开发应用问题本身固有的并行性，分析算法性能； 另一方面设计出的算法具有通用性，从而使并行算法的研究成为一项相对独立的 活动。 因此，研究并行计算模型具有十分重要的意义【引。 并行计算模型为并行算法和并行计算机系统结构的设计和分析提供具有指导 意义的理论界面和模型框架，是并行计算研究的重要领域，为此研究者做了大量 的工作，研究合理适用的并行计算模型。 在并行计算模型的研究中，最有影响的早期理论模型是p r a m ( p a r a l l e l r a n d o ma c c e s sm a c h i n e ，p r a m ) 模型【3 1 。p r a m 模型是由f o r t u n e 和w y l l i e 于19 7 8 年提出的。p r a m 模型是一个理想化的并行计算模型，它被广泛地用来评估并行 算法的理论性能。p r a m 模型假设一个共享存储器多处理机系统是由一个具有无 限存储容量的共享存储器以及可对它进行访问的许多处理机所组成的系统，其中 每个处理器还有自己的本地存储器。这些处理器由一个公共时钟加以控制，并以 同步方式运行。 p r a m 模型的算法设计和分析比较简单，在评估并行算法的性能方面获得了 广泛的应用，为理论分析提供了许多有价值的结果，具有重要的理论指导意义， 至今仍是最重要的并行计算模型之一。但p r a m 模型集中于并发性而忽略实际的 考虑，并不能够真实地反映实际的并行计算机，是一种理想化的模型，在现实中 无法实现。 b s p ( b u l ks y n c h r o n o u sp a r a l l e l ) 模型【4 j 是由v a l i a n t 于19 9 0 年提出的。b s p 模型中，一个并行计算系统由以下三个部分组成：第一，若干个处理器，每一个 处理器有自己的本地存储器；第二，个点对点的通信网络以在处理期间传递消 2 息；第三，在定义的时间间隔内对所有或部分处理器进行同步的机制。在b s p 模 型中，不要求关于通信系统、互连网络和同步系统的额外信息。 b s p 模型比p r a m 模型更接近于实际的并行机，在保留了p r a m 模型简单性 的同时，引入了附加的参数表示通信、同步等所带来的开销，以克服p r a m 模型的 缺点。但b s p 模型仅刻画同步执行机制。因此，严格按照b s p 模型实现的并行程序 难于提高程序的效率，且易于产生通信拥挤。另夕i b s p 模型没有考虑并行计算系统 中各计算节点通信时网络存在潜在拥塞的影响，也没有详细描述网络通信对时间 的影响。 l o g p 模型1 5 j 是由c u l l e r 等人于1 9 9 3 年提出的。l 0 9 p 模型没有如p r a m 和b s p 模型中所具有的显示同步操作，l o 妒模型建立在这样的基础上，即占统治地位的 系统结构，不论通信方式是共享存储方式还是消息传递方式，都是由具有本地存 储器的多个处理器组成的，这些处理器通过通信网络连接在一起。在共享存储器 的情况下，这些消息不是用显式的发送或接收进程产生的，而是在对非本地数据 进行访问时出现的。l o g p 是一个能很好地符合并行计算机系统中分布式存储、多 处理器网络通信机制的计算模型。 l o g p 模型将现在和将来的并行计算机的特性进行了精确的综合，以少量的参 数刻画了并行计算机的主要瓶颈，其详尽程度足以反映并行算法设计时的主要问 题，而其简捷性也足以支持详细的算法分析。 l o g g p 模型1 6 是由a a l e x a n d r o v ，m 1 0 n e s c u 和k e s c h a u s e r 于1 9 9 5 年提出的。 由于在l o 眇模型中，并不对长消息做特别的处理，但是现在许多并行计算机对长 消息都提供了特别的支持，比如i b m 的s p 2 等。与发送短消息相比，许多并行机 采用处理长消息的方法来达到更高的带宽。因此，在l o g g p 模型中引入了对长消 息的支持，它比l o g p 多一个参数g ，代表长消息每字节问距，即发送长消息每字 节所需要的时间，它的倒数对应于处理机发送长消息时的网络带宽。与l o g p 模型 相比，l o g g p 模型指导的算法的执行速度和性能有较大提高。 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 ) 模型p j 是由s e h a m b r u s h 和 a k h o k h a l - 于1 9 9 6 年提出的。在c 3 模型，计算划分为一系列的超级步，同步出现 在两个超步之间，且由路障实现。在每个超级步内内施行局部计算继之以发送和 接收消息；一个超级步的时间由所完成的计算单位数和通信单位数来度量，其中 计算单位数取决于所做的局部计算量，通信单位数取决于处理单元所发送的数据 量、所接收的数据量、消息的传输延迟、处理单元之间超容限通信所引起的拥塞； 在分析算法的时间复杂度时，必须累加每一个超级步中的计算单位数和通信单位 数。c 3 模型刻画了并行系统的各个节点在互相通信时可能会存在的网络拥塞，但 没有刻画并行系统的节点的异构性。 另外，除了p r a m 模型，b s p 模型，l 0 9 p 模型与c 3 模型这几种重要的模型 之外，研究者还提出了一些其他的并行计算模型，如p o s t a l 8 】模型，q s m 9 】模型等。 这些模型在并行计算的研究和发展方面起都到了重要的作用。 n h b l l ( n o n d e d i c a t e dh e t e r o g e n e o u sb a r r i e rl o g g pm o d e l ) 模型是计永昶、丁 卫群、陈国良等人于2 0 0 1 年提出的。n h b l 模型是基于l o g g p 模型的非独占异构 同步模型。n h b l 比较准确地刻画了并行计算系统的节点的可扩展性和节点的异 构性、节点计算资源的非独占性对计算时间的影响。 虽然n h b l 模型对并行系统的描述已经比较准确，但是n h b l 模型并没有准 确描述出考虑异构的并行计算系统中各个不同的计算节点的特性和通信网络的异 构性对节点通信时间的影响。因此本文针对上述背景，在n h b l 模型的基础上， 对其进行了扩展，研究了适用于异构的并行计算系统的并行计算模型。 1 2 论文研究内容 在本文中，提出了一种扩展的并行计算模型。这个模型建立在n h b l 模型的 基础上，能够更加准确地描述复杂的异构的并行计算系统。n h b l 模型仅仅描述 了异构的并行计算环境中计算节点计算能力的差异性，这在真实的异构的并行计 算系统中是远远不够的。因此，为了更加全面地考虑异构的并行计算环境中各个 不同的计算节点的特性以及计算节点的非独占性，本文将原n h b l 模型的单一数 量参数通信丌销扩展为新模型罩的发送开销和接收开销两个向量参数，并增加了 并行进程的c p u 占用比参数以取代原模型的其他用户进程到达概率参数和其他用 户进程执行时间参数。e n h b l 模型用更加细致但是同样很直观的方式通过对 n h b l 模型中参数的扩展来描述并行系统中计算节点的异构性和非独占性，使该 模型更贴近一个真实的异构并行计算系统。然后本文阐述了如何计算一个实际的 异构并行系统的参数，分析了参数的特性，说明了各节点的多样性对模型的参数 的影响。最后，本文在一个实际的异构的并行计算系统中进行了实验，根据实验 结果对e n h b l 模型的有效性进行分析，分析结果证明了e n h b l 模型的准确性， 表明e n h b l 模型对描述异构非独占的并行系统非常有效。 1 3 论文组织结构 论文的组织结构如下： 4 第一章简要介绍了论文的研究背景，并行计算模型研究现状和研究内容， 目前存在的主要问题，然后介绍了研究目标和论文的主要研究内容，以及研究的 重要意义。 第二章首先详细介绍了五种重要的并行计算模型：p r a m 模型，b s p 模型， l 0 9 p 模型，c 3 模型和n h b l 模型，阐述了每种模型的定义、特点及其各自的应用 情况，对每个模型的参数进行了分析和讨论。最后对这五种模型进行了比较，总 结了这五种重要的并行计算模型的特点，阐述了n h b l 模型的优点。 第三章首先分析了提出扩展n h b l 模型的原因，即n h b l 模型的局限性， 然后阐述了扩展的模型e n h b l 模型的定义，参数的定义，以及并行程序执行时间 的分析。 第四章首先阐述了如何针对一个实际的异构系统测量扩展的模型中的各个 参数的值，以及参数测量应当遵循的规范。并在实验环境下进行了实际的测量， 给出了测量的各个参数的结果；然后利用扩展的模型，分析一个具体的并行计算 在这个系统上的运行情况；最后，通过将在异构的并行计算环境下使用模型预测 的值和实验结果进行比较，验证了扩展的并行计算模型的可行性和准确性。 第五章对论文的主要研究内容和结论进行了总结，阐述了下一步研究的展 望。 5 2 并行计算模型 随着并行计算的发展，并行计算模型在估计和评价系统的性能、引导并行计 算机的体系结构发展以及指导并行算法和程序的设计等方面都越来越重要。目前， 研究者们已经提出了多种多样的并行计算模型，对于目前已有的并行计算模型的 设计思想和原理的了解和分析，非常有利于新的模型的设计与研究。 本章研究了五种重要的并行计算模型，分别是：p r a m 模型、b s p 模型、b g p 模型、c 3 模型和n h b l 模型。与p r a m 模型有所不同，后四种模型为了弥补p r a m 模型的不精确性，均通过将某些机器特征抽象成一些参数的方法来刻画并行计算 模型，并且考虑到同步、通信等因素，能够较为真实地反映并行计算机的性能， 这些改变代表了并行计算模型研究的趋势。以上五种模型在并行计算各个阶段的 研究和发展方面都起到了非常重要的作用。然后通过对这五种模型的特点进行了 比较，阐明了n h b l 模型的优点，以及研究n h b l 模型的意义。 2 1几种重要的并行计算模型 2 1 1p r a m 模型 p r a m ( p a r a l l e lr a n d o ma c c e s sm a c h i n e ) 模型是最有影响的早期理论模型， 是一个理想化的并行计算模型，它被广泛地用来评估并行算法的理论性能。p r a m 模型假设一个共享存储器多处理机系统是由一个具有无限存储容量的共享存储器 以及可对它进行访问的许多处理机所组成的系统，其中每个处理器还有自己的本 地存储器。这些处理器由一个公共时钟加以控制，并以同步方式运行。它们同时 执行指令，这些指令可能是不同的也可能是相同的，尽管p r a m 模型通常所用的 算法是使各处理器对不同的数据执行相同的指令。当然，并非所有的处理器必须 要执行所提供的指令，个别处理器可以不参加执行。各处理器均可在单位时间内 读写共享内存，处理器间同步在一个全局时钟下以锁步方式实现，因而在算法设 计和分析时同步是隐含的，无需在算法中明确设置同步点。 p r a m 模型如图2 1 所示。 6 时钟 具有本地存 器的处理器 图2 1p r a m 模犁 f i g u r e2 1p r a mm o d e l 一个p r a m 模型的计算由一连串的读、计算和写序列组成。在读步骤中，每 个处理器从全局内存中读取数据到局部内存中。在计算步骤中，每个处理器处理 各自局部内存中的数据，并把结果存放在局部内存中。在写步骤中，每个处理器 将各自局部内存中的结果写入相应的全局内存中。处理器以读或写的方式访问保 存在共享存储器中的数据。一个p r a m 操作可能读出一个存储单元的内容，对它 完成一次算术运算，然后将运算结果写回存储器。由于可能有多于一个的处理器 执行相同的指令，并且系统又是同步的，因而就可能有多个存储器的同时读操作 和多个存储器的同时写操作。因此共有四种p r a m 模型的类型，由如何处理同时 读和写的定义可对它们进行分类： ( 1 ) 互斥读互斥写( e x c l u s i v er e a de x c l u s i v ew r i t e ，e r e w ) 在e r e wp r a m 模型中，每次只能有一个处理器访问一个存储单元，不论是 读存储单元内容还是写新值。这是最严格的模型。 ( 2 ) 并发读互斥写( c o n c u r r e n tr e a de x c l u s i v ew r i t e ，c r e w ) 在c r e wp r a m 模型中，允许多个处理机同时读一个存储单元的内容，但每 次只允许一个处理器向该存储单元写新值。 ( 3 ) 互斥读并发写( e x c l u s i v er e a dc o n c u r r e n tw r i t e ，e r c w ) 在e r c w 模型中，可由多个处理机同时对一个存储单元进行写，但不允许同 时读。 ( 4 ) 并发读并发写( c o n c u r r e n tr e a dc o n c u r r e n tw r i t e ，c r c w ) 在c r c w 模型中，一个存储单元可由多个处理机同时进行读或写。这是功能 最强的模型。 在允许进行同时写的模型，即e r c w 和c r c w 中，必须有附加的说明来指明 如何解决写冲突以及最后应将哪个结果存入该单元。通常会有以下四种冲突解决 7 方式： ( 1 ) 公共冲突解决( c o m m o n ) 仅当所有要写入的新值相同时，才允许同时写。因此，结果用写入的新值定 义。 ( 2 ) 任意冲突解决( a r b i t r a r y ) 只选出一个处理器完成写操作，所有其他处理器被禁止，即写失败。 ( 3 ) 优先冲突解决( p r i o r i t y ) 与任意冲突解决类似，优先冲突解决方法是根据预先定义的优先顺序来选择 允许写的那个处理器，其他处理器不能进行写。预先定义的优先权是根据处理器 的识别符加以确认的。 ( 4 ) 求和冲突解决( s u m ) 这种方法是将各个处理器欲写入的值求和，将求和值作为最后写入的结果。 可见，p r a m 模型保持了简单性，它被广泛用来分析并行算法复杂性，特别 适用于并行算法的表达、分析与比较。它使用简单，很多并行机的低级细节，如 处理器1 自j 通信、存储管理和进程同步等都隐含于模型中，算法设计者可以容易地 设计算法，并且稍加修改就可以运行在不同的并行计算机上。 但是，p r am 模型也存在一些缺点。p r a m 模型是同步的，意味着所有的指 令都按照锁步方式操作，这种方法比较费时，不能反映现实系统的异步性。p r a m 模型假定共享单一存储器，不适合分布存储的异步的m i m d ( m u l t i p l ei n s t r u c t i o n s t r e a m m u l t i p l ed a t as t r e a m ，多指令流多数据流) 计算机。p r a m 模型假定每个处 理器都可以在单位时间内访问任何存储单元而忽略了存取竞争和有限带宽，是不 现实的。p r a m 模型假设处理器有限或无限，对并行任务的增大不加限制，也是 不现实的。因为p r a m 模型对零通信开销和指令级同步的不现实假设，所以它并 不能够真实反映实际的并行计算机，至今它未被用于实际的并行计算机。 由于p r a m 模型的这些特点，研究者对p r a m 模型的认识不断深化，并对它 做出了若干改进，提出了许多p r am 模型的扩展模型，主要包括： ( 1 ) 局部p r a m 模型。局部p r a m 模型考虑了通信带宽，它假定每个处理 器都有无限的本地存储器，而访问全局存储器的时间开销是比较大的。 ( 2 ) 分层存储p r a m 模型。分层存储p r a m 模型将存储器视为分层的存储 模块，每个模块由大小和传送时间表征，多处理器由模块树表示，树的叶子表示 处理器。 ( 3 ) 异步p r a m 模型【l l 】。异步p r a m 模型使用同步路障控制程序，并且考 虑了成本参数的定量化，更接近于实际的并行机。 ( 4 ) 另外在参考文献【1 2 】中，又提出了一种新的模型q r q wp r a m ( q u e u er e a d q u e u e w r i t ep r a m ) ，每一个共享单元可以同时被多个处理机读写，这些读写操作 被放在一个队列中依次进行。 综上所述，尽管p r a m 模型与实际机器差别较大，还未被用于实际的并行计 算机，但是它仍然能够提供有价值的设计信息。p r a m 模型忽略了实现并行性所 需要的代价，目的是让设计者揭示给定问题的可能的最大并行度，并且给出了理 想的并行时间复杂度的度量标准。由于p r a m 模型抽象了很多细节，使得它异常 简单，所以p r a m 模型是开发高级并行算法的重要的模型。在算法设计等领域， p r a m 模型获得了广泛的应用，有重要的理论指导意义。 2 1 2b s p 模型 b s p ( b u l ks y n c h r o n o u sp a r a l l e l ) 模型定义一个并行计算系统由以下三个部分 组成：第一，若干个处理器，每一个处理器有自己的本地存储器；第二，一个点 对点的通信网络以在处理期间传递消息；第三，在定义的时间间隔内对所有或部 分处理器进行同步的机制。在b s p 模型中，不要求关于通信系统、互连网络和同 步系统的额外信息。b s p 模型如图2 2 所示。 i 存储器存储器 1 i 处理器处理器 i ； l 通信网络 i 工 i 路障同步机构 图2 2 b s p 模型 f i g u r e2 2b s pm o d e l b s p 模型中的参数定义如下： ( 1 ) p ：表示带有本地存储器的处理器数。 ( 2 ) l ：表示周期性同步，即两个同步操作间的最小时间步数。l 是进行全 局同步检查的时间单位。 ( 3 ) g ：表示在一个处理机上将一个数据包写入互连网络的时间，它决定 了进程两次通信之间的时间间隔，反映了通信带宽。 在b s p 模型中，连续的两个同步之间的周期被定义为超步( s u p e r s t e p ) 。在每一 9 个超步中，各个处理器使用存于本地的数据执行一些计算步，并且进行消息的发 送和接收。具体地说，在一个超步中，各处理机执行以下三个操作： 首先，各处理机处理本地存储器中的数据，执行本地计算。操作的所有数据 只能是本地存储器中的数据，这些数据是在程序启动时，或由以前超步中的通信 操作存放在本地存储器中的。一个处理器的计算与其它处理器无关。 然后，各处理机向别的处理机提出远程内存读写请求，处理器之间相互交换 数据，通信总是以点对点的方式进行。 最后，在超步的末尾所有处理机进行路障同步，确保通信过程中交换的数据 被传送到目的处理器上，并使一个超步中的计算和通信操作必须全部完成之后， 才能开始下一个超步中的任何动作。一次超步的数据通信仅当同步以后有效。在 同步之后所有消息均已被接收，但在同步之前，消息不必一定己被接收。 b s p 模型允许一个处理器执行多个进程或线程。可以将计算描述为由线程或 进程( 或虚拟处理器) 组成的，它们由路障实现同步，且在同步点之间有一个计 算部分和一个通信部分。 在一个超步中，一个处理器最多发送h 个消息和最多接收h 个消息。若有h 个消息，就称此通信有一个h 关系。在一个h 关系中，传递h 个消息所需的时间 为曲。 综上所述，b s p 模型的超步如图2 3 所示。 本地计算 通信 路障同步 线程或进程 图2 3 b s p 模型的超步 f i g u r e2 3as u p e r s t e pi nt h eb s pm o d e l 1 0 送最魔的一 nu彤火一nu嚣一 几u吖a几u吖a 几uk 一个基于b s p 模型的程序是由一系列超步组成的。 b s p 模型中程序的总的执行时间等于各个超步执行时间之和。每个超步执行 时间由如下三个部分确定： ( 1 ) 计算时间w 。考虑到负载可能不平衡，或者各个处理器性能差异，w 是 指处理器中完成计算操作所需的最大时间。即w = m a x w i ，w i 是超步内各个处理 器执行时间。 ( 2 ) 通信时间曲。g 与平台有关，与通信模式无关。h 可认为是一个超步中 的最大通信量，即h - - m a x h i ) ，其中1 1 i 表示处理器i 发送或接收的数据量。 ( 3 ) 同步时间l ：l 是完成一次同步的代价，其下限为网络通信迟延其值 总大于零。 因此完成一个超步所需的时间即代价由下式给定： t s u p e r s t e p = m a x w i + m a x f i + l - - w + g h + l 。 则程序的总的执行时间为( w + g h + l ) n ，n 为超步数。如果超步内三个操作完全 重叠，则超步时间可达到m a x w , g h ，l ) ，总的执行时间可达m a x w , g h ，l n 。 可见，b s p 模型在保留了p r a m 模型简单性的同时，引入了附加的参数表示 通信、同步等所带来的开销，以克服p r a m 模型的缺点。除了负载不平衡开销以 外，b s p 模型设定了同步开销，其下限为通信网络延( 即通过物理网络传递单字 节所需要的时间) ，并且总是大于零。b s p 模型还设定了通信开销，是一个与平台 有关的常数带宽因子。可见，与p r a m 模型的理想性相比，b s p 模型更为现 实。 另外，b s p 模型高度结构化的特性使得b s p 程序能够预测全局通信的时间， 这是许多并行模型所不具备的。因为b s p 模型全局地处理通信过程，统一地分布 进程，就能预测通信进程间相互影响的结果，从而就能能够估计出总体的通信时 间。 但是b s p 模型也存在一些缺点，因此研究者通过对b s p 模型的不断研究，对 它做出了一些改进，提出了一些建立在b s p 模型基础上的扩展和改进模型，主要 包括： ( 1 ) 异步b s p 模型( a b s p 模型) 【1 3 】。异步b s p 模型模型取消了同步限制， 进程可以异步执行，在第k 个超步内，当进程j 完成通信后，就可以继续下一个 超步的计算，而不必等待其它进程都完成该超步的计算。但是由于超步的通信操 作都在该超步的最后，无法实现计算与通信的重叠，因而程序异步执行的效率受 到限制。 ( 2 ) h b s p 模型1 4 】。h b s p 模型取消了b s p 模型中处理机间通信要满足h 关 系的限制，为算法和程序设计提供了更多的自由。 ( 3 ) 另外还有很多b s p 模型的扩展模型，例如c g m 模型【l5 1 ，e b s p 模型【l6 】， b s p * 模型1 7 1 ，c s a b s p 1 8 】模型，h b s p 模型【1 9 1 等。 综上所述，b s p 模型的最大特点是大块同步，它介于完全串行的模型和严格 同步的模型之间，以超步作为同步的基本单位，引入了路障同步机制，并且忽略 了发送和接收消息的额外开销。b s p 模型定义了程序的结构，能够引导用户进行程 序设计，在正确性和编程方法上都简单易行。另外，b s p 模型具有高度结构化的 特性，能够简单方便地预测出全局通信的时间。但是b s p 模型仍存在要求节点通 信满足h 关系，g 的测算不够精确等问题。 2 1 3 l o g p 模型 l o 妒模型没有如p r a m 和b s p 模型中所具有的显示同步操作，l o g p 模型建 立在这样的基础上，即占统治地位的系统结构，不论通信方式是共享存储方式还 是消息传递方式，都是由具有本地存储器的多个处理器组成的，这些处理器通过 通信网络连接在一起。在共享存储器的情况下，这些消息不是用显式的发送或接 收进程产生的，而是在对非本地数据进行访问时出现的。l o g p 是一个能很好地符 合并行计算机系统中分布式存储、多处理器网络通信机制的计算模型【2 0 】。 l o g p 模型中的参数定义如下： ( 1 ) l ：表示从一个源向一个目的发送消息时引起的时延上限。 ( 2 ) o ：表示通信开销，即处理器进行消息发送或接收所需要的时间，在这 段时间内处理器不能进行其他操作。 ( 3 ) g ：表示通信间隔，即进行两次连续的消息发送或接收时必须间隔的最 小时间。 ( 4 ) p ：表示处理器个数。 l o 妒模型中的参数，除p 以外均是以处理器周期数来衡量，本地操作为一个 周期。 l o g p 模型通过抽象出来的这4 个参数来抽象一个并行计算系统，使得算法设 计者不需要关心具体的网络信息，可以更容易地设计符合l 0 妒模型的算法。 l o 妒模型的参数如图2 4 所示。 1 2 图2 4b g p 模型的参数 f i g u r e2 4p a r a m e t e r so ft h el o g pm o d e l g 在参数的抽象上，l 0 9 p 模型并不是对每个单独的处理器部件作详细描述，它 从整体上确定以上四个参数，这种构思和机制是在忠实地获得实际机器的执行特 点、提供一个有效的算法设计和分析的框架之间取一个折中，既兼顾了反映实际 机器的运行特性，又为算法提供合理的框架支持。 在不同的情况下，l o g p 模型中的各个参数也可以适当地化简来降低系统的复 杂性。这是因为在不同的情况下，各个参数的重要性也是不一样的，在和现实的 并行系统相结合时，可以忽略一个或者更多参数，从而获得一个更简单的模型。 例如，在一个数据传输量很少的算法中，就可以忽略网络的带宽和容量限制，从 而可以忽略l 、o 、g 三个参数。在有些系统中，采用网络信息管道来发送很长的 字节流，这样，信息传输时间中信息之间的时间间隔占主要地位，而延迟时间可 以忽略，所以在这种情况下可以认为消息的传输时间主要受g 的限制，从而忽略l 这个参数。而在某些机器中，系统的瓶颈是o ，则可以认为g = o ，这样就可以不考 虑g 对算法的影响。 在l o g p 模型中，通信网络的能力是有限的。在任何瞬间互连网络中只能传递 有限数量的消息，由从任一处理器向任何其他处理器可发送的l g 个消息定义。如 果一个处理器企图发送的消息数超过l g 的上限时，该处理器将会停顿。 从处理器只向处理器只发送消息的时间如图2 5 所示。 1 3 处理 图2 5l o g a 模型中的消息传递 f i g u r e 2 5m e s s a g ep a s s i n gi nt h el o g pm o d e l 发送和接收一个消息共需2 0 + l 个周期。处理器只在向处理器p 发送消息后， 在发送下一个消息之前必须等待g 个周期，露要向处理器发送下一个消息。l o g p 模型中假设消息都是短消息。 l o g p 模型几乎适用于当前所有高性能并行计算系统，包括已经商品化的 n t e l i p s c 、d e l t aa n dp a r a g o n 、t h i n k i n gm a c k i n e sc m 5 、n c u b e 、c r a yt 3 d 以及p a r s y t e c g c 。i x ) g p 模型反映了当前并行计算机系统的本质，这个并行计算模型适用于商用 的并行计算机系统。 研究者在l o g p 模型基础上，针对不同通讯特点进一步扩展，提出了许多模型， 最著名的l o g g p 2 1 1 ，l o g g p s t 2 2 1 ，l o g p c t 2 3 1 ，l o g p q t 2 4 1 等等。l o g g p 模型通过参 数g 以加入长消息的因素，参数g 代表长消息每字节间距，表示发送长消息每字 节所需要的时间。l o g g p s 模型在l o g g p 模型的基础上，加入了隐藏在m p i 实现 中的同步因素，即同步过程带来的时间开销。它定义了一个参数s ，表示消息长度 的阈值。当消息长度大于s 时，处理机之间就要发送和接收同步消息了。使用 l o g g p s 模型可以确定在m p i 实现中，何时从使用异步( a s y n c ) 协议转向使用同 步( s y n c ) 协议。l o g p c 模型则主要考虑了消息流水( m e s s a g ep i p e l i n e ) 和网络 拥塞( n e t w o r kc o n t e n t i o n ) 的因素。l o g p q 模型则是把通信队列考虑进了l o 妒模 型，它在l 0 9 p 模型的基础上加入了发送队列( s q ) 、接收队列( r q ) 和全局的传 输队列( t q ) 3 个队列。 综上所述，l o g p 模型为快速的可移植的并行算法建立良好的基础与以往的 1 4 算法模型相比，l o 妒模型更符合现实并行系统的运行方式，更有适应性且更灵 活。 2 1 4c 3 模型 c 3 模型是通过分析高性能可扩展的网络计算机系统特点得到的。它是一个与 体系结构无关的粗粒度的并行计算模型，其目的在于反映计算复杂度、通信模式 和通信期间潜在的拥挤因素对粗粒度网络算法的影响。 在粗粒度机器上，并行算法对通信模式非常敏感。b s p 模型和l 0 9 p 模型将复 杂的通信操作交由编程人员实现，这无疑加重了人们的负担。而c 3 模型却强调使 用公用的通信操作来开发粗粒度的并行算法。另外，前面所介绍的模型均未反映 通信操作中潜在拥挤的影响，c 3 模型考虑了网络链路拥挤和处理器拥挤对并行算 法性能的影响。 c 3 模型中的参数定义如下： ( 1 ) p ：表示处理器的个数。 ( 2 ) h ：表示网络延迟。 ( 3 ) b ：表示网络的对分宽度，即将网络等分为两个子网络时所需断开的处 理器连接的个数。 ( 4 ) s ：表示启动时间，即建立一个消息的丌销。 ( 5 ) 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 o l e ) 寻径路由，以及两种发送接收原 语，即阻塞方式和非阻塞方式对通信单元的影响。c 3 模型中，拥挤作为一种全局 现象，与体系结构、选路策略和处理器问的传送数据量有关。度量拥挤是在所有 消息都同时选路的假定下进行的。 c 3 模型特别适用于粗粒度算法的开发与分析，模型特别强调了通信瓶颈的作 用。在这个方面，它比b s p 模型