（电力系统及其自动化专业论文）基于mpi的pq法潮流计算及暂态稳定的并行方法研究.pdf

浙江大学硕士学位论文 a b s t r a c t p o w e rs y s t e mi sac o m p l e xn o n l i n e a rt i m e v a r y i n gs y s t e m w i t ht h ee x p a n s i o no f t h es y s t e ms c a l ea n dt h er i s i n gr e q u i r e m e n to fo n l i n ea n a l y s i s ，t r a d i t i o n a la n a l y s i s m e t h o d sh a v eb e e nu n p r e c e d e n t e dc h a l l e n g e d t h es o l u t i o nt 0p o w e rs y s t e m c a l c u l a t i o ni su s u a l l yag r o u po fa l g e b r a i ce q u a t i o n so ra l g e b r a i ce q u a t i o n si n c o n j u n c t i o nw i t ht h ed i f f e r e n t i a le q u a t i o n s i no r d e rt os p e e du pt h ec o m p u t a t i o n ， p a r a l l e lp r o c e s s i n gt e c h n o l o g y i si n t r o d u c e di n t ot h e p o w e rs y s t e ma n a l y s i s c o m p u t i n gf i e l d i tp r o v i d e sa ne f f e c t i v ew a yt of u n d a m e n t a l l ys o l v et h ep r o b l e mo f t h ep o w e rs y s t e mr e a l t i m ea n a l y s i s t h i sd i s s e r t a t i o ni n t r o d u c e st h eb a s i ct h e o r yo ft h ep a r a l l e l c o m p u t i n ga n d p a r a l l e la l g o r i t h m ，a n da l s oi n t r o d u c e sm p ia n dp a r a l l e lp r o g r a m m i n gb a s e do nm p i a i m i n ga tt h eq u i c ks o l u t i o nt ot h ep o w e rf l o wc o m p u t i n g ，ad i m e n s i o n a lp a r a l l e lw a y i sp r o p o s e db a s e do nm e s s a g ep a s s i n gi n t e r f a c ea n dp qd e c o u p l e dp o w e rf l o w c a l c u l a t i o n t h i sp a r a l l e la p p r o a c hi sb a s e do nt h em a t r i xi n v e r s i o n i no r d e rt o e n h a n c ep a r a l l e ld e g r e e ，a n o t h e rp a r a l l e la p p r o a c hi sp r o p o s e da c c o r d i n g l y i tf o c u s e s o nt h ef o r m a t i o no ft h ec o e f f i c i e n tm a t r i xa n dt h es o l v i n go ft h ee q u a t i o n su s i n gt h e f a c t o r i z a t i o nt a b l e s t h i sd e s i g n e da p p r o a c hi sb a s e do nt h eg a u s s i a ne l i m i n a t i o n p a r a l l e la l g o r i t h m t h ep a r a l l e la l g o r i t h mi s e v a l u a t e do nas e r i e so ft e s tp o w e r s y s t e m s t e s tr e s u l t ss h o wt h a tt h ep a r a l l e la l g o r i t h mc a ng r e a d yr e d u c et h ec o m p u t e r r u n n i n gt i m ea n dg e tg r e a ts p e e d u pf a c t o ra n de f f i c i e n c y t h ea n a l y s i so ft h ep o w e rs y s t e mt r a n s i e n ts t a b i l i t yp r o b l e mi sr e l a t i v e l ym u c h m o r ec o m p l e x t l u sd i s s e r t a t i o na n a l y s e st h em a t h e m a t i c a lm o d e l so f t h em a i np o w e r s y s t e mc o m p o n e n t si n c l u d i n gg e n e r a t o r s ，l o a da n dp o w e rn e t w o r k d e a l i n gw i t ht h e f a u l t so ro p e r a t i o n si nt h ep r o c e s so f t h et r a n s i e n ts t a b i l i t yc a l c u l a t i o n ，a l la p p r o a c ho f f a u l th a n d l i n gi sp r o p o s e dw h i c hb a s e do nt h ed e c o m p o s i t i o no ft h eb r o k e n - d o w n l i n e s t a k i n gt h ea s y m m e t r yo f t h ef a u l t si n t oa c c o u n t ，an e t w o r km o d e li sb u i l ti nt h e f o r mo ft h r e es e q u e n c ea d m i t t a n c em a t r i x t h e nt h i sd i s s e r t a t i o ng a ! t i e so u tt h e t r a n s i e n ts t a b i l i t yc a l c u l a t i o np r o c e s sa n a l y s i sa n da l g o r i t h md e s i g nb a s e do nt h e 玎 塑垩奎堂要主兰堡堡兰 一 s i m p l i f i e dm o d e l i no r d e rt os p e e du pt h ec o m p u t a t i o n ，u s i n gt h ep a r a l l e la l g o r i t h m d e s i g ne x p e r i e n c e si np o w e rf l o wc a l c u l a t i o n ，ad i m e n s i o n a lp a r a l l e la p p r o a c h i s d e s i g n e db a s e do n t h es o l v i n go fa l g e b r a i ce q u a t i o n si nc o n j u n c t i o nw i t ht h e d i f f e r e n t i a le q u a t i o n s k e y w o r d s ：p a r a l l e lp r o c e s s i n g ，m p i ，p - qd e c o u p l e d ，p o w e r f l o wc a l c u l a t i o n , t r a n s i e n ts t a b i l i t y , p o w e rn e t w o r k ，f a u l th a n d l i n g ，g a u s s i a ne l i m i n a t i o np a r a l l e l a l g o r i t h m 1 1 i 浙江大学硕士学位论文 第一章绪论 1 1 课题研究的目的和意义 电力系统是一个复杂的非线性时变系统，电力生产的高质量、高效益需求， 使得电力系统暂态稳定分析、电磁暂态实时仿真、电力系统能量管理、优化潮流、 电力系统规划等，越来越复杂。为了提高计算速度，人们从许多方面进行了深入 研究。有的从算法上进行研究，如在暂态稳定直接法的研究中，e e a c 法已经被 成功地应用于在线分析；有的采用一些新矩阵运算技术，如稀疏矩阵技术、分块 矩阵技术、矩阵的三角分解技术等：有的采用新技巧，如节点优化编号方法；有 的将通用算法同电力系统的具体问题相结合，进行合理化简，如快速分解潮流计 算方法。尽管如此，在许多情况下，单个处理器的运算速度还不能很好地满足快 速增长的计算需求。 电力系统计算往往是解一组代数方程或联解代数方程与微分方程。由于电网 规模越来越大，考虑的因素越来越多，因此方程数目巨大，阶数很高，即使采用 了许多先进技术，采用传统的性能很高的计算机，计算仍十分耗时，但电力系统 的运行迫切要求能在短时间内迅速进行静态和动态安全分析计算，判断当时电网 的薄弱环节，作为采取调整和防范措施的依据，这对提高电网运行的可靠性，防 止大的系统性事故发生是十分重要的。随着电力系统规模的不断扩大和对在线分 析要求的不断提高，传统的分析计算方法受到了前所未有的挑战。自2 0 世纪8 0 年代以来，并行处理技术开始引入电力系统分析计算领域，可望从根本上解决电 力系统实时分析的难题。特别是近些年来并行处理软硬件的快速发展促进了它在 电力系统计算中的应用 心。 并行处理( p a r a l l e l 胁e s s m g ) 从本质上讲就是将多任务映射到多处理机中执 行，或将现实的多维问题映射到具有特定拓扑结构的多处理机上求解。并行处理 的主要目的是提高应用效率或用于实时控制。并行处理技术的发展，为解决电力 系统问题提供了一个颇具吸引力的机会。现今，并行处理的理论、软硬件技术和 有关并行处理应用的实践经验，都还在不断地完善之中，如何有效地将并行处理 技术同电力系统问题结合起来，满足电力生产的需要，需要认真考虑 浙江大学硕士学位论文 1 2 并行处理技术在电力系统中的应用 电力系统计算中的并行计算技术，主要解决以下几个闻题： ( 1 ) 潮流并行计算如何高效地并行求解修正方程式； ( 2 ) 暂态稳定并行计算如何充分利用空间和时间上的并行性，并行求解微分 和代数方程组； ( 3 ) 并行算法如何充分利用稀疏技术； ( 4 ) 如何选择处理机数目与计算速度之间的最佳匹配。 目前并行算法已在潮流计算、暂态稳定分析、静态安全评估等方面得到应用。 1 2 1 在潮流计算中的应用 潮流问题描述了电力系统的稳态情况，因而潮流公式或经过一些修改的潮流 公式是优化潮流和暂态稳定等重要问题的基本成分。一个有效的潮流并行化方法 同样也会有助于加快其它问题的求解，因而早期关于并行处理在电力系统中应用 的研究主要集中于并行化潮流闯题的求解上【3 】。 潮流计算是电力系统规划、运行的基本研究方法。随着现代电力系统大系统、 强非线性与多元件的特点日益突出，其计算量与计算复杂度急剧增加。如今，传 统的串行潮流计算方法在计算速度上不能更快更好地满足大电网模拟和实时控 制的仿真要求，高效的潮流问题并行算法和相应并行软件的研究已成为大规模电 力系统仿真计算的关键。随着并行机与并行计算技术的不断发展和成熟，潮流问 题的并行计算研究近年来得到了长足的发展。为真正解决大电网快速、详细的仿 真计算开辟了新路。长期以来，研究人员一直致力于寻求更适合电力系统特点的 潮流并行算法。希望能开发出具有最大的并行性而各任务之问的数据相关性最小 的方法。 无论潮流计算还是安全分析，代数方程组或微分方程组的求解都是最基本和 最核心的问题之一。电力系统并行计算的主要内容是潮流以及暂态稳定计算的并 行处理。以潮流计算为例，无论是采用牛顿法还是p - q 分解法，从数值计算上 最终可以归结为求解以下形式的方程组：4 y 日。 此类方程组的并行求解方法，大致上可以分为两类：一类是直接求解法，另 一类是迭代法。 2 浙江大学硕士学位论文 直接法建立在矩阵分解、矩阵求逆等数学原理基础上，这类方法不存在收敛 问题，但难以达到高度并行化，且通信开支较大，适于中等规模线性方程组，对 大系统，受到存储容量的限制，并行程度不高。而迭代法如雅可比和高斯塞德 尔法可直接并行化，只需少量通信，具有方法简单、所需空间小且易于有效实现 向量计算的优点，但收敛慢，迭代次数随处理器数目而增加。 由于并行计算机结构的多样性以及稀疏矩阵结构的不规则性，要找到一个适 于所有计算机和所有电力网络的统一算法几乎没有可能。 已有的并行化潮流计算的许多工作都集中在并行化三角分解、前代回代上， 如：通过对矩阵的重新组合分块来发掘并行性；降低由最大因子路径长度决定的 顺序执行步数；采用适合于向量机的向量化算法；多重因子分解方案和稀疏逆因 子方案；基于电力系统运行模式及人工神经网络的潮流并行算法；利用超立方体 结构寻找稳态稳定大矩阵的特征值和特征向量等。 现有的潮流并行算法主要是在共享存储结构的并行机上实现的，基于分布 式并行系统的潮流并行计算研究较少。近年来集群系统是实现并行计算的一种新 主流技术，随着高性能价格比的可扩展集群式计算机研究的逐步成熟及应用，为 更多的科研人员进行电力系统潮流并行计算的研究提供了物质基础。基于集群 系统的大规模电力系统潮流并行计算和分布式仿真已成为可能。另外由于电力 系统特有的分层分区特性，采用区域分解方法可开发出高效的粗粒度潮流并行 算法。因此基于高性能集群系统潮流计算的并行算法研究与实现将最具发展潜力， 这将是今后进一步的研究方向【4 】。 1 2 2 在暂态稳定中的应用 电力系统暂态稳定分析需要求解描述旋转运动的时变微分方程和描述电网 的代数方程。这组微分代数方程具有多种非线性，数值方法中的逐步积分法被用 来获得时域解。如果通过并行处理技术，能极大地提高速度，在线暂态稳定分析 也将具有很好前景。 将暂态稳定问题并行化有两个途径：( 1 ) 将系统的变量分组，称为空间并行 化；c ) 使几个时间段可以同时求解，称为时间并行化。非常明显的空间并行化 是将微分方程分解成每个发电机一组的多个方程组，而由代数方程提供它们之间 的耦合时间上的并行是形成每个时间段的牛顿方程，然后同时求解。有的先将 浙江大学硕士学位论文 网络方程分解，然后在微分方程或差分化的方程组上实施松弛法，如对微分方程 实施的波形松弛法。有的将差分化的微分方程和代数方程一起，对每一个系统变 量在所有的时间段中通过皮卡松弛法分解并同时求解，从而提供在时间和空间上 最大程度并行化的方法。有的在频域中将暂态稳定问题向量化以获得并行性。上 述方法的共同困难是收敛性较差，通常要经过更多的迭代次数才能收敛，有时甚 至难以收鲥5 一。 对暂态问题的细粒度并行化，也遇到了许多困难，所获得的效果不很理想。 为此粗粒度的并行化也被研究过，如通过同时计算在不同节点上的故障来并行 化，当s y r e l 稳定计算程序在一个1 6 节点的超立方体计算机上实现时，可以 获得一个数量级的加速比。 这些有限的实验表明，通过使用几十个处理器就可以获得一个数量级的加速 比。随着处理器数目的增加，计算时间也能减少，但效率下降得很快。若想进一 步提高加速比将会增加一些额外开销，如在消息传递机器上的通信时间和共享内 存机器上保持内存一致的开销。降低通信开销，减少不同处理器运算的相关性， 将会进一步提高并行加速比。为此通过重叠技术将通信时间隐藏，基于故障并行 的方案，具有很好的可扩展性。如果每个故障的计算时间能基本相等，那就会获 得较高的加速比。 1 3 本文的主要工作 本论文致力于在电力系统潮流计算及暂态稳定计算中运用并行处理技术以 大大加快计算时间。结合电力系统潮流计算及暂态稳定计算的特点，分别设计了 基于m p i 的并行算法，为大规模的电力系统的分析计算提供基础。 l 、本文首先介绍了有关并行计算的基本理论，对物理问题的并行求解过程 进行分析，学习如何将一个实际待求解问题着手并行化。对并行算法的设计方法 进行研究，为在电力系统问题中应用并行处理技术打下学习基础。介绍了几种并 行算法的性能评价标准。 2 、对最广泛的并行编程模型m p i 消息传递模型进行了介绍。详细介绍 了m p i 的几个最常用的接口函数。通过对这些m p i 库函数的熟练掌握，将m p i 和c 语言进行结合作为并行程序的设计语言，进行基于m p i 的并行程序设计。 3 、对电力系统p - q 分解法潮流计算进行研究，分析总结已有的几种并行算 4 浙江大学硕士学位论文 法，分别设计了基于分解一叠加原理的矩阵求逆的并行算法和基于并行高斯消去 法的算法，并通过几个标准测试系统验证了设计的潮流并行算法的有效性，为并 行求解暂态稳定问题的奠定了基础。 4 、对暂态稳定问题中的主要电力元件的数学模型进行了详细分析，考虑到 故障或操作的不对称性，建立了三序导纳矩阵形式的电力网络模型。针对暂态稳 定计算中的故障或操作，提出了一种基于分解故障线路的故障处理方案。应用改 进欧拉法对简化模型下的暂稳计算进行了流程分析与算法设计。最后借鉴潮流并 行算法的设计经验，针对暂态稳定计算过程中微分。代数方程组的求解设计了一 种空间并行算法。 浙江大学硕士学位论文 第二章并行计算的基本理论 2 1 并行处理概述 并行处理( p a r a l l e lp r o c e s s i n g ) 从本质上讲就是将多任务映射到多处理机中执 行，或将现实的多维问题映射到具有特定拓扑结构的多处理机上求解。并行处理 的主要目的是提高应用效率或用于实时控制。对于一给定的计算任务，并行处理 大致上可以分为两大步：首先必须设计出并行算法( p a r a l l e l a l g o r i t h m ) ，然后才能 从事并行装配即并行实现。 为什么要采用并行计算? 这是因为：( 1 ) 它可以加快速度，即在更短的时间 内解决相同的问题或在相同的时间内解决更多更复杂的问题，特别是对一些新出 现的巨大挑战问题，不使用并行计算是根本无法解决的；( 2 ) 节省投入，并行计 算可以以较低的投入完成串行计算才能够完成的任务；( 3 ) 物理极限的约束，光 速是不可逾越的速度极限，设备和材料也不可能做得无限小，只有通过并行才能 够不断提高速度。 并行计算机的发展基于人们在两方面的认识：第一，单机性能越来越难以满 足大规模科学与工程问题的计算需求，而并行计算机是实现高性能计算、解决挑 战性计算问题的有效途径；第二，同时性和并行性是物质世界的一种普遍属性， 具有实际物理背景的计算问题在许多情况下都可以划分成能够并行计算的多个 子任务。针对某一具体应用问题，我们可以利用它们内部的并行性，设计并行算 法，将其分解成为互相独立但彼此又有一定联系的若干个子问题，分别交给各台 处理机，而所有的处理机按并行算法完成初始应用问题的求解。 2 2 物理问题的并行求解过程 。一个物理问题并行求解的最终目的是将该问题映射到并行机上，这一物理上 的映射是通过不同层次上的抽象映射来实现的( 图2 1 ) 6 浙江大学硕士学位论文 图2 1 问题的并行求解过程 忽略并行机的非本质的细节特征，可以得到该并行机的并行计算模型，在这 一模型上，可以设计各种适合该模型的并行算法，这些算法精确描述了该并行模 型能够实现的功能，而这些算法是通过用特定的并行语言设计并行程序后得以实 现的。对于现实世界的物理问题，为了能够高效地并行求解，必须建立它的并行 求解模型，一个串行的求解模型是很难在并行机上取得满意的并行效果。有了并 行求解模型，就可以针对该模型设计高效的并行算法，这样就可以对该问题的求 解进行精确描述和定量分析，就可以对各种不同的算法进行性能上的比较，最后 通过并行程序设计，实现问题和并行机的结a 【”。 并行程序设计，需要将问题的并行求解算法转化为特定的适合并行计算模型 的并行算法，为了达到这一目的，首先是问题的并行求解算法必须能够将问题内 在的并行特征充分体现出来，否则并行求解算法将无法利用这些并行特征，从而 使问题的高效并行求解成为不可能；其次是并行求解模型要和并行计算模型尽量 吻合，这样，就为问题向并行机上的高效解决提供了前提。 2 3 并行语言 并行程序是通过并行语言来表达的，并行语言的产生主要有三种方式川：( 1 ) 设计全新的并行语言；( 2 ) 扩展原来的串行语言的语法成分，使它支持并行特征； ( 3 ) 不改变串行语言，仅为串行语言提供可调用的并行库。 7 。 浙江大学硕士学位论文 设计一种全新的并行语言的优点是可以完全摆脱串行语言的束缚，从语言成 分上直接支持并行，这样就可以使并行程序的书写更方便，更自然，相应的并行 程序也更容易在并行机上实现。但是，由于并行计算至今还没有象串行计算那样 统一的冯诺伊曼模型可供遵循，因此并行机、并行模型、并行算法和并行语言 的设计和开发千差万别，没有一个统一的标准，虽然有多种多样全新的并行语言 出现，但至今还没有任何一种新出现的并行语言，成为普遍接受的标准，设计全 新的并行语言，实现起来难度和工作量都很大，但各种各样并行语言的出现、实 践和研究，无疑都为并行语言和并行计算的发展作出了贡献。 一种重要的对串行语言的扩充方式就是标注，即将对串行语言的并行扩充作 为原来串行语言的注释，对于这样的并行程序，若用原来的串行编译器来编译， 标注的并行扩充部分将不起作用，仍将该程序作为一般的串行程序处理，若使用 扩充后的并行编译器来编译，则该并行编译器就会根据标注的要求，将原来串行 执行的部分转化为并行执行。对串行语言的并行扩充，相对于设计全新的并行语 言，显然难度有所降低，但需要重新开发编译器，使它能够支持扩充的并行部分， 一般地，这种新的编译器往往和运行时支持的并行库相结合。 仅仅提供并行库，是一种对原来的串行程序设计改动最小的并行化方法。这 样，原来的串行编译器也能够使用，不需要任何修改，编程者只需要在原来的串 行程序中加入对并行库的调用，就可以实现并行程序设计。 对于以上这三种并行语言的实现方法，目前最常使用的是第二种和第三种方 法，特别是第三种方法。本论文所采用的基于m p i 的并行程序设计，就属于第 三种方法。 2 4 并行算法 2 4 1 并行算法的定义和分类 并行算法是给定并行模型的一种具体、明确的解决方法和步骤。并行算法是 一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问 题的求解。 并行算法按照不同的划分方法，有多种不同的分类，可分成数值计算的和非 数值计算的并行算法；同步的、异步的和分布式的并行算法；共享存储的和分布 8 浙江大学硕士学位论文 存储的并行算法；确定的和随机的并行算法等等。 若其中一个进程必须等待其它进程，则称为同步并行算法；如果各个进程之 间不需互相等待，且处理机间的通信是通过动态地读取储存在共享存储器中的更 新整体变量来实现的，则称为异步并行算法。根据并行计算任务的大小，可以分 为粗粒度并行算法( 一个并行任务包含较长的程序段和较大的计算量) 、细粒度 并行算法( 一个并行任务包含较短的程序段和较小的计算量) 以及介于二者之间 的中粒度并行算法。一般而言，并行的粒度越小，就有可能开发更多的并行性， 提高并行度，这是有利的方面，但是另一个不利的方面就是并行的粒度越小，通 信次数和通信量就相对增多，这样就增加了额外的开销，因此合适的并行粒度需 要根据计算量、通信量、计算速度、通信速度进行综合平衡，这样才能够取得高 效率州。 2 4 2 并行算法中的同步与通信 ( 1 ) 同步是在时间上强使各执行进程在某一点必须相互等待。在并行算法的 各进程异步执行过程中，为了确保各处理器的正确工作顺序以及对共享可写数据 的正确访问( 互斥访问) 。同步可用软件、硬件和固件的办法来实现。 ( 2 ) 通信是在空间上对各并发执行的进程实施行数据交换。 进行并行计算时，处理器之间的数据调度、传输，需要通信开销。基于共享 存储的并行计算模型的通信是依靠全局存储变量来完成的，所以其通信开销并不 是很大。但是在基于分布存储、特别是使用消息传递的并行计算模型上，数据在 处理器之间选路、传输可能花费的时间要长得多。 并行系统执行给定算法的过程中，出现某些处理机的一些计算必须在其他处 理机的一些计算完成之后才能进行时，保持操作的同步是必要的，即保证此类情 况得以正确实施。同步要有两方面的开销：一是实现同步一般要求对所有处理机 作某种检查，在此是要花费时间的；二是某些处理器或是所有处理器都可能闲置， 等待准许继续进行计算的消息。 2 4 3 并行算法的性能度量 对于一个给定问题，如果设计了一个新的并行算法，就必须对该算法的性能 进行评价。性能度量的目的就是为并行算法的设计与分析提供一个统一的衡量标 9 浙江大学硕士学位论文 准。在当前并行计算环境中，并行算法的性能度量一般涉及到求解问题的规模与 分类、具体并行机的性能、影响算法的关键因素、并行算法评价准则等方面问题。 下面介绍度量并行算法性能的一些基本概念。 ( 1 ) 运行时间。并行算法的运行时间是指算法在并行计算机上求解一个问题 所需的时间。即表示从算法开始执行到执行结束的这一段时间。如果多个处理机 不能同时开始或同时结束时，则算法的运行时间定义为：从最早开始执行的处理 机开始执行时算起直到最后一台处理机执行完成所经过的时间。在计算机上实现 一种算法之前，通常需要对其运行时间进行理论分析。对并行算法运行时间的分 析包括估计它在最坏情况下的计算时间和通信时间，其中的计算时间是用算法所 需执行的基本操作次数或步数表示，通信时间则是根据计算得到的通信次数和每 步的通信量，依据并行计算模型计算得到。理论分析得到的算法运行时间常表示 为输入问题规模的函数。对于一个规模为月的问题，算法的运行时间可用玎砂 表示，它是输入问题规模r l 的函数。 ( 2 ) 并行度与粒度。算法的并行度d o p ( d e g r e eo f p a r a l l e l i s m ) 是指该算法中 可并行执行的操作数。若处理机资源无限，则算法的并行度也可以理解为可以利 用来做并行运算的处理机台数。然而很少有并行算法能在整个算法执行过程中保 持并行度不变，所以更准确的说法还应该加上时间范围的限制，即在某时间范围 内的并行度。从直观意义上可以说，并行度是刻画一个并行算法的“并行程度” 的量，它反映了软件并行性与硬件并行性匹配的程度。显然，与算法并行度有关 的概念是粒度。一般而言，大的粒度意味着能独立并行执行的是大任务，算法的 并行度小；小的粒度意味着能独立并行执行的是小任务，算法的并行度大。 ( 3 ) 加速比和效率。加速比和效率是传统的并行算法评价标准，它们体现了 在并行机上运用并行算法求解实际问题所能获得的好处。 并行算法的加速比是评价算法的并行性对运行时间改进的程度，定义为： 。算法在单处理机上实际执行时间 使用p 台处理机时算法的实际执行时间 并行算法的并行效率定义为： 占：昱l o o 4 2 吾1 0 0 1 0 浙江大学硕士学位论文 并行效率反映并行系统中处理器的利用情况。当s = p 时，我们称并行算法 具有完全或理想的加速比，此时e o = 1 0 0 。如果按照某种条件，如保持每台处 理机的计算规模，并行算法加速比与处理机的台数成正比，则称该并行算法在该 条件下，在该并行机上具有线性加速比。在某些条件下，若s 。 p 则称该条件下， 该算法具有超线性加速比。 大多试验表明，随着处理器数目的增加，算法效益将趋于饱和甚至出现负增 长，这是因为过多的处理器间的通信占用了较多时间。 ( 4 ) 可扩展性。可扩展性是设计高性能并行计算机和并行算法所追求的另一 个重要目标。由于并行系统的性能与系统规模、问题规模、算法内在并行性以及 由于通信、同步和进程创建等引起的系统开销等因素有关，而这些因素对并行系 统的结构和应用程序的可扩展性都有影响，因此可扩展性也是衡量并行系统性能 的一个重要度量指标。衡量系统可扩展性的方法有很多，一般采用等效率度量方 法。所谓等效率是指系统规模增加时，测量增加多少运算量会保持效率不变。 2 4 4 并行算法一般设计方法 并行程序设计是在并行计算机上编写求解应用问题的并行程序的技术。现实 并行程序设计的4 个要素是：并行体系结构、并行系统软件、并行程序设计语言 和并行算法。并行语言既是程序员进行并行程序设计的文本，也是并行编译系统 对并行程序进行编译所依据的文本。设计并行算法一般有三种方法： ( 1 ) 检测和开拓现有串行算法中的固有并行性而直接将其并行化，这种方法 虽不是对所有问题总是可行的，但对很多应用问题都是一种有效的方法。长期以 来人们积累了大量优秀的串行算法，因此在设计并行算法时，要充分利用现有求 解问题的串行算法，在其基础上而直接并行化，这显然是一种优先考虑的方法。 但是用这种方法时有两点需要考虑：对于一类具有内在顺序性的串行算法，则 恐难于并行化；并非任何优秀的串行算法都可以产生好的并行算法，相反一个 不好的串行算法有可能产生很优秀的并行算法。 ( 2 ) 从i 司题本身的描述出发，根据问题固有的属性，从头开始设计一个全新 的并行算法。但这并不是说完全排除某些串行算法设计的基本思想，而是更着重 从并行化的具体实现上开辟新的设计方法。 ( 3 ) 借用已有的并行算法使之可求解新的一类问题。此两类问题表面上看是 浙江大学硕士学位论文 迥然不同的，或似乎互不相干的，所以按照常规的办法，求解这两类问题似乎毫 无关系，但是可以通过某种内在联系，将两类不同的问题在求解方法上统一起来。 欲借用时，不但要从问题求解方法的相似性方面仔细观察，寻求问题解法的共同 点：而且所借来的方法要用得上算，效率要高，从而到达借用的目的。 2 4 5 并行算法设计应注意的问题 根据并行化的特点分析，无论采用什么方法进行设计并行算法，以下几点都 是决定并行效率的重要因素： ( 1 ) 挖掘并行性。针对一个具体问题设计其并行算法时，可根据求解该问题 的串行算法出发，分析其明显的并行性，加以并行化，并应该利用相关知识，深 亥挖掘问题内在的可并行性。 ( 2 ) 并行算法依赖并行的环境。并行算法与进行并行运算的环境密切相关， 同一个并行算法在不同的并行系统上运算的差别很大。所以说，要根据并行运算 的环境有针对性的设计并行算法。 ( 3 ) 考虑通信开销。通信开销是一个必须考虑的因素，因为有时通信在整个 算法中占用时间的比例很大，特别是在分布存储的并行环境下，要尽量减少通信 开销，才能设计出高效率的并行算法。 2 5 小结 本章对并行处理的一些基本原理做了介绍。对物理问题的并行求解过程进行 分析，学习如何将一个实际待求解问题着手并行化。在并行计算中，并行算法对 性能产生重大的影响，因此研究设计一个好的并行算法十分重要，挖掘出问题的 串行算法中的内在可并行性，加以并行化，是一种比较有效的并行算法设计方法。 对于已设计出的并行算法的性能进行评价，并行加速比和并行效率是目前广泛采 用的评价标准。一个好的并行算法，就是要追求大的并行加速比和高的并行效率。 浙江大学硕士学位论文 第三章m pl 及其并行程序设计 3 1 并行编程模型 目前两种最重要的并行编程模型是数据并行和消息传递。数据并行编程模型 的编程级别比较高，编程相对简单，但它仅适用于数据并行问题；消息传递编程 模型的编程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。 数据并行即将相同的操作同时作用于不同的数据，因此适合在s i m d 、s p m d 并行计算机上运行。在向量机上通过数据并行求解问题的实践也说明数据并行是 可以高效地解决一大类科学与工程计算问题的。 数据并行编程模型是一种较高层次上的模型，它提供给编程者一个全局的地 址空间。一般这种形式的语言本身就提供并行执行的语义，因此对于编程者来说， 只需要简单地指明执行什么样的并行操作和并行操作的对象，就实现了数据并行 的编程。因此数据并行的表达是相对简单和简洁的，它不需要编程者关心并行机 是如何对该操作进行并行执行的。 数据并行编程模型虽然可以解决一大类科学与工程计算问题，但是对于非数 据并行类的问题如果通过数据并行的方式来解决，一般难以取得较高的效率，数 据并行不容易表达甚至无法表达其它形式的并行特征。 消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、 控制执行。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并 行机消息传递，为编程者提供了更灵活的控制手段和表达并行的方法，一些用数 据并行方法很难表达的并行算法，都可以用消息传递模型来实现，灵活性和控制 手段的多样化，是消息传递并行程序能提供高的执行效率的重要原因。 消息传递模型一方面为编程者提供了灵活性，另一方面它也将各个并行执行 部分之间复杂的信息交换和协调控制的任务交给了编程者，这在一定程度上增加 了编程者的负担，这也是消息传递编程模型编程级别低的主要原因。虽然如此， 消息传递的基本通信模式是简单和清楚的，学习和掌握这些部分并不困难，因此 目前大量的并行程序设计仍然是消息传递并行编程模式。 目前最为流行的消息传递模型是m p i 和p v i v l 。其中m p i 以其移植性好、功 浙江大学硕士学位论文 能强大、效率高等多种优点在短短几年内便迅速普及，成为消息传递并行编程模 式的标准。 3 2m p l 简介 为了开发一个高效标准具有可移植性的消息传递库，1 9 9 2 年由i b m 、i n t e l 公司、p a r a s o f l 等开发商、g m p 等研究机构和e d i n b u r g h 等大学成立了m p i 论坛。 m p i 论坛于1 9 9 4 和1 9 9 7 年分别推出了m p i 1 和m p i 2 标准，提供了一个适合进 程间进行标准消息传递的并行程序设计平台。目前m p i 已经发展成为应用最广 泛的并行程序设计平台，几乎被所有并行计算环境( 共享和分布式存储并行机、 m p p 、机群系统等) 和流行的多进程操作系统( u n i x 、l i n u x 、w i n d o w s ) 所支持。 现行高性能计算机系统中使用的并行编程环境主要有两种：p v m ( p a r a l l e l v i r t u a lm a c h i n e ) 和m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 。p v m 的开发始于1 9 8 8 年， 由美国橡树岭国家试验室发起。本论文中的并行算法采用m p i 作为并行开发环 境，因为它具有如下特征与优点： ( 1 ) m p i 是一个库，而不是- - f - j 语言。可以把f o r t i 认n + m p i 或c + m p i 看 作是一种在原来串行语言基础之上扩展后得到的并行语言。m p i 库可以被 f o r t r a n 、c c + + 调用。从语法上说，它遵守所有对库函数过程的调用规则。 ( 2 ) m p i 提供了大约1 2 5 个高效的通信函数，编程者只需恰当地调用这些函 数就可以实现消息传递，无需开发新的通讯结构。 ( 3 ) 从理论上说，m p i 的所有通信功能可以用6 个基本的调用来实现，分别 为m p i _ _ i n i t ，m p l c o m m _ s i z e ，m p ic o r i mr a l ：1 l 【，m p i _ s e n d ，m p ir e c v ， m p i _ f i n a l i z e 。m p i _ i n i t 和m p i _ f i n a l i z e 实现m p i 环境的初始化和结束。 m p i _ _ c o m mw o r l d 通信因子是在m p i 环境初始化过程中创建的。 m p i _ c o m ms i z e 获取缺省组( g r o u p ) 的大小；m p l _ c o m m _ r a n k 获取本进 程( 调用进程) 在缺省组中的逻辑号( 从o 开始) ；m p l _ s e n d 和m p l r e c v 实现消息 的传递。 ( 4 ) m p i 是一种标准或规范的代表，而不特指某一个对它的具体实现。迄今 为止，所有的并行计算机制造商都提供对m p i 的支持，可以在网上免费得到m p i 在不同并行计算机上的实现，一个正确的m p i 程序，可以不加修改地在所有地 并行机上运行。m p i c h 是最重要的一种m p i 实现，是一个与m p i 规范同步发 1 4 浙江大学硕士学位论文 展的版本。每当m p i 推出新的版本时，就会有相应的m p i c h 的实现版本。 ( 5 ) m p i 具有移植性好、功能强大、效率高等优点。m p i 是为开发基于消息 传递模型的并行程序而制定的工业标准，其目的是为了提高并行程序的可移植性 和易用性，用户必须显式地通过发送和接受消息来实现处理器之间的数据交换。 3 3 六个接口构成的m p i 子集 在m p i 1 中共有1 2 8 个调用接口，在m p l 2 中有2 8 7 个。应该说m p i 是比较庞 大的，完全掌握这么多的调用是比较困难的。但是，从理论上说，m p i 所有的通 信功能可以用它的6 个基本的调用来实现嗍。掌握了这6 个调用，就可以实现所 有的消息传递并行程序的功能。 ( 1 ) m p l 初始化函数 m p l _ l m t ( i n t a r g e c h a r 。a r g v ) m p i l n i t 是m p i 程序的第一个调用，它完成m p i 程序所有的初始化工作， 所有m p i 程序的第一条可执行语句都是这条语句。 ( 2 ) m p i 结束函数 m p i _ f i n a l i z e ( ) m p i _ f i n a l i z e 是m p i 程序的最后一个m p i 函数调用，它结束m p i 程序的运 行，使程序退出m p i 编程环境。它是m p i 程序的最后一条可执行语句，否则程 序的运行结果是不可预知的。 ( 3 ) 获取当前进程标识 m p i _ _ c o m m _ r a n k ( m p i _ c o m m mc o m l n ，i n t + r a n k ) 这一调用返回调用进程在给定的通信域中的进程标识号，有了这一标识号， 不同的进程就可以将自己和其他的进程区别开来，实现各进程的并行和协作。 ( 4 ) 通信域包含的进程数 m p ic o m m _ s i z e ( m p ic o m m c o m m ，i n t + s i z e ) 这一调用返回给定的通信域中所包括的进程的个数，不同的进程通过这一调 用得知在给定的通信域中一共有多少个进程在并行执行。 ( 5 ) 消息发送 m p i _ s e n d ( v o i d + b u f , i n tc o u n t ，m p l d a t a t y p ed a t a t y p e ，h a td e s t ，h a tt a g ， m p i _ c o m me o m m ) 1 5 浙江大学硕士学位论文 m p i _ s e n d 将发送缓冲区中的c o u n t 个d a t a t y p e 数据类型的数据发送到目的 进程，目的进程在通信域中的标识号是d e s t ，本次发送的消息标志是t a g ，使用 这一标志，就可以把本次发送的消息和本进程向同一目的进程发送的其他消息区 别开来。该操作指定的发送缓冲区是由c o u n t 个类型为d a t a t y p e 的连续数据空间 组成，起始地址为b u t 注意这里不是以字节计数，而是以数据类型为单位指定 消息的长度，这样就独立于具体的实现，并且更接近于用户的观点。其中d a t a t y p e 数据类型可以是m p i 的预定义类型，也可以是用户自定义的类型。通过使用不 同的数据类型调用m p i _ s e n d ，可以发送不同类型的数据。 拍) 消息接收 m p ur e c v ( v o i d * b u f , i n tc o u n t ，m p i _ d a t a t y p ed a m t y p e ，h a ts o u r c e ，i n tt a g ， m p i _ c o m mc o m m ，m p i _ s t a t u s + s h a m s ) m p lr e c v 从指定的进程s o u r c e 接收消息，并且该消息的数据类型和消息标