（电力系统及其自动化专业论文）互联电网在线过负荷校正的研究.pdf

声明 本人郑重声明：此处所提交的硕士学位论文并行计算在电力系统暂态稳定分 析中的应用研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行 的研究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：缰盘i l l 日期：丝堑竺：兰 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：蟹盘! 垒 导师签名： 日期：日期：兰业生 华北电力大学硕士学位论文 1 1 本课题的背景和意义 第一章绪论 大区域电网互联和电力市场化改革是2 1 世纪中国电力工业发展的两大特征，日 益复杂的电力系统，发生故障的几率也在增加。某些扰动可能导致大面积停电和系 统的稳定性问题日趋严重。停电范围大，时间长，对社会的政治，经济，文化及人 们的生活都将产生无法估计的严重后果。因此加强大电网安全稳定性的研究，开发 大电网的在线实时安全稳定控制系统，是电网调度技术的一个重要研究方向。 电力系统的校正控制是电力系统安全监控的重要课题之一。负荷校正过程是当 系统元件故障造成系统功率越限时，研究如何调整发电机输出功率使得过负荷解 除；或者当调整发电机输出功率不能消除越限时，给出切负荷方案。当系统处于紧 急事故状态时，系统的运行状态已不满足约束条件，虽然还没有出现大面积的停电 事故，但运行参数已经越限，若不及时采取措施，运行情况将进一步恶化，系统进 一步开断甚至可能崩溃。美国，加拿大东部的大停电正是在高峰负荷期，由于机组 的意外退出使得部分线路处于过负荷状态。调度因故未能及时处理，导致了一系列 线路直接或间接的因过负荷跳闸，区间潮流波动较大，电压下降，先后引发了一些 大机组跳闸。继而系统崩溃，美加东北部全部停电。如果此时能够尽快的进行过负 荷校正，消除过负荷状态，情况就能够得到很好的控制，不会导致进一步的恶化， 直至最后崩溃。因此，一旦发现系统处于紧急状态，就要立即采取措施，进行在线 过负荷校正，通过系统中可控变量的再安排使系统尽快恢复到正常状态。而这其中 的关键就是速度，过负荷校正的速度越快，情况就能越早得到控制，破坏就越小。 同时，过负荷校正计算也能够应用在安全分析中。电力系统在线安全分析主要 是分析线路开断，变压器、发电机切除是进否会造成系统负荷约束条件和电压约束 条件的破坏，即是否会导致某些元件过载或节点母线电压越限，同时若有约束条件 的破坏，提出可行的控制措施。其中要对大量的预想事故进行分析，对于大电网， 这种计算所需要的计算量是十分庞大的。因此提高安全校正计算的速度，对于安全 分析将起到很好的帮助。 过去的电力系统安全校正一般是把有功安全校正和无功安全校正分开来进行 研究，有功校正研究假设无功潮流不变，仅有功潮流越限，主要用于解决有功经济 调度问题；无功校正研究则假设有功潮流不变，仅无功潮流越限，主要用于解决无 功经济调度问题。这种把有功校正和无功校正分开独立研究的方法适用于电力系统 正常状态下的预防控制，因为运行条件并不恶劣，一般采用有功校正和无功校正之 一即可实现预防控制。然而，电力系统紧急状态下的运行条件已变得相当恶劣，多 i 华北电力大学硕士学位论文 数情况是有功校正和无功校正必须一起使用，即使如此，往往还不得不采取甩负荷 措施。同时，在电网处于紧急状态下事故处理的快速性更为重要，这就要求我们尽 量采用简化模型，寻找求解速度快，收敛性好的算法，并非必须在安全校正“费用” 上取得最优，争取能达到次最优也是很好的。 随着电力系统规模的不断扩大和对在线分析要求的不断提高，传统的分析计算 方法受到了前所未有的挑战。自8 0 年代以来，并行处理技术开始引入电力系统分析 计算领域，可望从根本上解决电力系统实时分析的难题。特别是近十年来，并行处 理软硬件的快速发展促进了它在电力系统计算中的应用。目前并行算法己在潮流计 算、暂态稳定分析、静态安全评估等方面得到了应用。 所以在传统的串行计算方法在计算速度上已经无法满足大电网模拟和实时控 制的仿真要求，高效的并行算法和相应并行软件的研究己成为大规模电力系统仿真 计算的关键。 1 2 国内外并行计算及机群的发展现状 并行计算( p a r a l l e lc o m p u t i n g ) ，就是在并行机( 含机群) 上做的计算，它和 常说的高性能计算( h i g hp e r f o r m a n c ec o m p u t i n g ) 、超级计算( s u p e rc o m p u t i n g ) 是同意词，因为任何高性能计算和超级计算总离不开使用并行技术。并行计算机具 有功能强、性能高、规模大的特定，它具有巨大的数值计算和数据处理能力，能够 广泛应用于国民经济、国防建设、科技发展等个项领域中。 随着计算机和算法的发展，在科学发展的各个领域都向定量化和精确化发展， 由此而导致对计算速度的不断增长，例如在石油勘探、地震预测预报、气候模拟及 大范围天气预报、新型武器设计和核武器系统的研究模拟、地质研究、天体和地球 科学、虚拟现实系统等等都需要大量的计算来解决。要解决这些问题，用传统的串 行算法很难解决，必须要使用并行计算。并行计算给了我们一个解决大计算量的一 般方法。使用并行计算机可以解决这些在一般计算机上难以解决的问题，具有巨大 的社会和经济效益。在国际上，高科技竞争日益激烈，而并行计算技术已成为体现 一个国家综合实力的一种标志，它对保障国家安全、促进科技进步、推动经济发展 有着不可替代的重要作用。对高速并行计算的需求是广泛的，主要集中在三种类 型的的应用需求：计算密集型，如数值模拟：数据密集型，如数据仓库；网络密集 型，如远程医疗等。而正是这些重大的应用领域推动了计算技术的发展。 高性能计算技术在国内外受到高度的重视，它在科学研究工程技术以及军事技 术方面的应用已取得了巨大的成就。国际上科学家广泛认为2 1 世纪人类所面临的重 要科技问题( 被称为巨大挑战。“g r e a tc h a l l e n g e ”) ，如人类基因全球气候准 确预报海洋环流循环等等没有万亿次以上的高性能计算机是无法解决的。 2 华北电力大学硕士学位论文 当今硬件技术( 包括处理器技术、存储技术以及网络方面的技术) 的发展，使得 构建机群系统的性能价格比得到进一步提高，从而使得机群系统的应用也得到进 一步的发展。 2 0 0 3 年1 1 月的国际t o p 5 0 0 超级计算机排名中，由机群组建的超级计算机占总数 的4 1 6 。也就是说，国际上机群在很多领域已经取代了昂贵的大型计算机来做并 行计算。在国内，机群系统也得到了一定程度的应用。 目前国内外机群计算的应用：首先是科学计算，各种物理化学仿真和模拟，大 量科学数据的处理等等不胜枚举。其次是关系到国计民生的方面，有石油勘探、天 气预报、大型网站事务处理，电信或无线等行业。 本课题由于条件所限，将采用较为廉价且易于实现的机群系统作为试验平台， 对算法进行测试。 1 3 目前安全校正计算的研究现状 电力系统安全校正问题是典型的最优潮流问题。就采用的求解技术而言，求解 该问题的方法可以分为两类：一类是采用非线性优化技术直接求解最优潮流问题的 一阶库恩一图克条件，同时得到控制解和系统运行点，如牛顿法和内点法等；另 一类是将优化控制问题与潮流计算问题分开来迭代求解，如简化梯度法、连续线性 规划法( s u c c e s s i v el i n e a rp r o g r a m m i n g ，s l p ) 和连续二次规划法( s u c c e s s i v e q u a d r a t i cp r o g r a m m i n g ，s q p ) 等。由于安全校正问题的控制目标通常要求控制数 目最少及其控制成本最低，因此后一类方法在求解安全校正问题时具有许多优点： ( 1 ) 计算量小。前一类方法通常需形成和因子化二阶海森矩阵，随着系统规模 的增大，计算量增大。尤其当需考虑的约束和控制变量数目巨大时，直接求解会造 成实用化困难。 ( 2 ) 模型更为灵活。第二类方法在考虑一种新的约束条件或增加一种新的控制 时十分灵活，只需在灵敏度计算模块中做一些修改。 ( 3 ) 求解更为灵活。有了灵敏度指标，可以方便地使用一些缩小问题规模、提 高计算效率的策略。 ( 4 ) 更为透明。在电力市场环境下，市场参与者要求运行调度方给出更为清晰 的模型来指导市场的参与活动。 ( 5 ) 求解具有鲁棒性。如果安全校正问题没有最优解，该类方法可以方便地给 出一个次优解 1 4 本论文的主要工作 华北电力大学硕士学位论文 本文研究了在p c 机群系统下实现互联电网过负荷校正计算的相关问题。论文首 先研究利用现有的计算机资源，构建小型的p c 机群系统，建立基于w i n d o w sx p 和m p i 的实验环境，构建基于m p i c h 下的并行计算平台。在此基础上介绍t m p i 并行程序的 丌发过程，并结合电力系统过负荷校正计算的特点，引入了基于并行处理技术的求 解线性方程组的对角块加边( b b d f ) 理论及求解线性规划的并行算法，设计并实现 了基于m p i 的并行互联电网过负荷校正计算程序。并且在实验环境中测试了该并行 计算程序的性能。 本论文对p c 机群环境下的互联电网过负荷校正计算的研究和探索，主要包括以 下工作： 第一，首先，研究了消息传递模式下机群系统并行程序模型以及影响并行程序 性能的因素，讨论t m p i 程序设计的基本模式和方法，以及在m p i 机群环境下开发并 行程序的框架和过程。 第二，对并行计算机体系结构进行讨论，通过建立基于w i n d o w sx p 和m p i 的并 行p c 机群环境，实现了可扩展p c 机群系统的构建。 第三，分析了现有的串行过负荷校正算法以及一些并行算法，然后结合机群系 统的特点，引入并行计算理论设计了适合机群计算的过负荷校正并行算法，并且实 现了在机群环境下m p i 并行计算程序的设计。 第四，通过建立的并行实验平台，对并行过负荷校正程序的性能进行了测试。 最后，根据理论研究和实验测试的结果，总结了利用机群系统进行并行过负荷 校正计算的可行性，以及分析提出可进一步改进的思路。 4 华北电力大学硕士学位论文 2 1 并行化概述 第二章并行计算理论 并行计算机的发展”3 基于人们在三方面的认识：第一， 它可以加快运算速度， 即在更短的时间内解决相同的问题或在相同的时间内解决更多更复杂的问题，特别 是对一些新出现的巨大挑战问题，不使用并行计算是根本无法解决的：第二，针对 某一具体应用问题，我们可以利用它们内部的并行性，将其分解成为互相独立但彼 此又有一定联系的若干个子问题，分别交给各台处理机，而所有的处理机按并行算 法完成初始应用问题的求解。第三，节省投入，并行计算可以以较低的投入完成 串行计算才能够完成的任务。 - 实现或提高计算机系统的并行性，可以通过时间重叠、资源重复和资源共享等 技术途径来实现。 时间重叠( t i m es u p e r p o s i t i o n ) 是在并行性概念中引入时间因素，让多个处理 过程在时间上相互错开，轮流重叠的使用同一套硬件设备的各个部分，以加快硬件 周转而赢得速度。 资源重复( r e s o u r c er e p l i c a t i o n ) 是在并行概念中引入空间因素，通过重复设 置硬件资源来提高可靠性或并行性能。在结构上，采用多操作部件和多存储部件， 早期受限于硬件价格，资源重复是以提高可靠性为主，随着硬件价格的减低，资源 重复利用被大量用于提高系统的速度性能，成为提高并行性的一个重要方面。 资源共享( r e s o u r c es h a r i n g ) 是按时间顺序轮流地使用同一套资源，包括c p u 、 主存、外设硬件资源和软件、信息资源，以提高其利用率，从而提高整个系统的性 能。 2 2 并行计算机的分类 并行计算机即并行计算环境，是并行算法赖以生存的物质基础，它们的发展直 接影响着并行算法的设计和实现。计算机系统分成以下四类： ( 1 ) 单指令流单数据流s i s d ( s i n g l ei n s t r u c t i o ns t r e a ms i n g l ed a t a s t r e a m ) ： ( 2 ) 单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t a s t r e a m ) ： ( 3 ) 多指令流单数据流m i s d ( m u l t i p l ei n s t r u c t i o ns t r e a ms i n g l ed a t a 5 华北电力大学硕士学位论文 s t r e a m ) ： ( 4 ) 多指令流多数据流m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l e d a t a s t r e a m ) ： 其中，s i s d 计算机就是传统的单处理器计算机，其指令顺序执行，一次只执行 一条指令并且只对一个操作部分分配数据。直到目前，还很少见到m i s d 类型的计算 机。s i m d 型和m i n e d 型并行计算机是研究和开发的主流。 2 2 1 向量处理s i m d 型并行机 向量处理机是典型的s i m d 并行机。向量机的特点是利用流水线的概念，把一个 计算部件拆成几段，在流水线的每一部分操作一个子功能，通过时间重叠实现并行 加速，其代表机型为c r a y 一1 向量机。s i m d 类型并行机对并行计算机的发展起到了重 要推动作用，但由于微处理芯片技术的发展，单处理器的性能都变得非常强大。9 0 年代以后，并行机均朝着m e a d 方向发展。s i m d 类型并行机基本退出了历史舞台 2 2 2 共享存储m i m d 并行多处理机 共享存储m i m d 并行多处理机将多台处理机通过互连网络共享一个统一的内存 空间，并通过该内存空间来实现处理机之间的协调。内存空间也可以由多个存储器 模块构成。在此类并行机中，每台处理机可以执行相同或不同的指令流，可以直接 访问到所有的数据。处理机间的通信是借助主存来实现的。 该系统的优点是并行化的效率较高，相对容易编写并行程序。由于处理器间传 送数据经由共享存储器进行，延迟较小。因此，容易设计出小粒度、负载平衡、高 效的并行程序。其缺点是系统中处理器太多时，对共享内存的竞争会严重影响效率， 虽然可以使用高速缓冲存储( c a c h e ) 和交叉开关存储( c r o s s b a rs w i t c hm e m o r y ) 等 技术来减少竞争现象，但这些技术依然有一些难以克服的局限性如使用高速缓冲 存储技术：即系统中每一个处理器有一个独立的高速缓冲存储模组，以减少处理器 对共享内存的访问：但在共享内存中某内存单元有写入操作时，则应同时更改存在 各高速缓冲存储中相关单元的内容，称为缓冲存储一致性问题。虽然己经有许多方 法可解决此问题，但仍无可避免地对系统性能产生负面影响。通过上述措施虽可以 减少竞争，但处理器的数目一般不能超过1 0 0 个，从而影响此类系统的发展。 2 2 3 分布存储m d 并行多处理机 为了突破共享存储并行机系统中处理器与内存系统问的瓶颈，分布存储m i m d 并 行多处理机器系统应运而生。该系统中每台处理机有自己的局部存储器，构成一个 单独的节点，节点之间通过互连网相互连接。每台处理机只能直接访问局部内存， 6 华北电力大学硕士学位论文 不能访问其它处理机的存储器，它们之间的协调以消息传递的方式进行。 与共享存储器并行机比较，分布式存储并行机具有很好的可扩展性，可以最大 限度地增加处理机的数量，是目前实现超大规模科学与工程计算的唯一途径。 但由于它的每个节点机需要依赖消息传递来相互通信，而消息传递对编程者是 不透明的，所以，分布存储并行多处理机系统的编程较共享存储复杂。 分布存储m i m d 并行多处理机其主要有m p p 系统和c l u s t e r 系统两种形式。 m p 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 s ) 系统是最常见的并行系统，由成百上 千台功能相同的处理机通过互连网络连接而成，且往往都采用专用结构。m p p 的优 点是拥有良好的伸缩性，只要给系统增加更多的结点，便能增加系统的计算性能( 峰 值) 。现时市场上大部分的高性能计算机都是m p p ，如i n t e rp a r a g o nx p s ，c r a v t 3 d 、 国产y h 一3 和曙光1 0 0 0 等。但是，m p p 的缺点是较难为其开发并行程序，程序员需要 根据系统的特点来平衡并行程序的粒度和结点间通信量。 计算机集群也叫计算机机群。是指把两台以上高性能的工作站或高档次p c 用互 连网连接在一起，并配以相应的支撑软件，构成一个分布式并行计算机系统，结点 间的消息传递和程序执行均是并行化的。集群系统具有并行计算性能而且能加速作 业的执行，这和一般的网络系统是不同的。c l u s t e r 的互连大多采用通用局部网， 如e t h e r n e t ，f d d i ，m y r i n e t ，a t m 等。集群系统可包括工作站群n o w ( n e t w o r ko f w o r k s t a t i o n s ) ，p c 机群、全对称s n i p 机群等。 2 2 4s p m d 和m p m d 虽然人们至今还在广泛使用s i m d 和m i m d 这种表达方法，但是随着新的并行计算 机组织方式的产生，按同时执行的程序和数据的不同，人们又提出了s p m d ( s i n g l e p r o g r a mm u l t i p l e - d a t a ) 单程序多数据并行计算机和m p m d ( m u l t i p l e p r o g r a m m u l t i p l e d a t a ) 多程序多数据并行计算机的概念。这种划分方式依据的执行单位 不是指令而是程序，显然其划分粒度( 划分对象的大小程度) 要大得多。 如果一个程序的功能就是为一个矩形网格内的不同面片涂上相同的颜色，则对 于一个划分得很细的特大矩形面片可以将它划分为互不交叉的几个部分，每一部分 都用相同的程序进行着色。s p m d 并行计算机可以很容易地实现类似的计算。一般地 讲，s p m d 并行计算机是由多个地位相同的处理器或计算机组成的。而m p m d 并行计算 机内处理器或计算机的地位是不同的。根据分工的不同，它们擅长完成的工作也不 同。因此，可以根据需要将不同的子程序( 子任务) 放至u m p m d 并行计算机上执行，使 得这些子程序协调一致地完成给定的工作。 7 华北电力大学硕士学位论文 2 3 并行计算机的应用和发展 作为并行计算物质基础的计算机硬件在不断的更新。最初是在单处理机内部增 设流水线处理部件、多功能单元、关联存储器等来开发指令级的并行性：为了进一 步提高并行度，必然导致向开发程序级和任务级的并行性的多计算机系统发展。即 把多台计算机联合起来，互相配合，各尽其能。利用功能专门化、多机群和网络化 这三种基本技术向着异构型多处理机系统，同构型多处理机系统和分布式处理系统 发展。 并行计算机是一种高性能的超级计算机，其运算速度应达到每秒万亿次、百万 亿次甚至于更高，以此来解决诸如气象模拟、流体分析、污染分析、人类染色体、 燃烧系统、海洋环境以及核试验模拟等一系列的超大规模计算问题。 上述种种应用，早己不仅仅用于实验室，而且已经有了实用产品。美国于1 9 9 1 年度开始执行“高性能计算与通信( h p c c ) ”项目，目的是解决一批重要的并对科学 技术具有挑战性的问题，其中的两个基于并行计算的问题是： ( 1 ) 高性能计算机系统( h p c s ) ：内容主要为并行计算机系统研究。 ( 2 ) 先进软件技术与算法( a s t a ) ：内容主要为高性能计算的软件与算法研究。 目前，高性能计算的发展应用可分为以下两大类： ( 1 ) 面向高端用户，追求细粒度、超高速的大规模并行计算机系统，由数百乃 至更多数目的c p u 组成，如以下的计算机系统： 1 陈列处理机，如d a p ： 2 向量并行机，如c r a y i 、国产银涧一l 等： 3 s i m d 并行机，如t h i n km a c h i n e 公司的c m 2 ，：s i p1 ，m p 2 等： 4 大规模并行机( m p p ) ，如i b ms p 2 ，i n t e lp a r a g o n ，c m 一5 、国产曙光机等。 这类计算机系统由于其价格昂贵、使用针对性较强，因此主要面向高端用户， 难于普及，不利于开发这类系统的软件及相关的并行算法。 ( 2 ) 基于网络技术的并行计算环境 此类系统一般由p c 微机通过网络构建而成。一般微机的平均使用率只有3 0 左 右。随着网络技术高速发展，此类系统的性能在过去几年里得到高速增长。 幽大量计算机通过网络组成的虚拟并行计算环境，其能力足以进行高性能计 算，其优点为可伸缩可扩展性强、能利用现有资源组建并行计算环境、价格便宜、 系统灵活等。这类网络并行多计算机系统中，各台计算机具有自己的存贮器地址空 8 华北电力大学硕士学位论文 间，通过消息传递( m e s s a g e p a s s i n g ) 来进行并行计算。典型的实现方式有： 1 扩充现有的顺序高级语言的语法和保留字来处理消息传递( 如c 、 c + + 、 f o r t r a n 扩展为并行c ，c + + ，f o r t r a n ) ， 2 设计专用的并行程序设计语言( 如o c c a m 并行语言) 3 利用现有的顺序高级语言并提供用于消息传递的外部函数库( 如 e x p r e s s 。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 p a r a l l e lv i r t u a lm a c h i n e ) 2 4 物理问题的并行求解过程 一个物理问题并行求解的最终目的是将该问题映射到并行机上，而映射过程是 通过不同层次上的抽象来实现的。一般的映射模型如图2 一l 所示。 并行机 器映射 物理问题 抽象 抽象 r t f 7 1并行求解模型 并行计算模型 、： 精确描述 r 问题的并行求解算 精确描述 、j 法 ， 适合并行计算模型 的并行算法 2 5 并行计算模型 图2 一i 问题的并行求解过程图 并行计算模型( 也称为编程模型、类型性模型、概念性模型或理想化模型) 是 指将各种并行机( 至少是某一类并行机) 的基本特征抽取出来，形成一个处于具体并 行机之上的抽象并行计算机，类似于顺序计算的v o nn e u m a n n 模型。 9 华北电力大学硕士学位论文 并行算法的设汁可以从两个角度进行：( 1 ) 依据并行计算模型设计并行算法，然 后将其映射到具体并行机中：( 2 ) 直接基于具体并行机进行并行算法的设计与分析。 显然，相比于第二种并行算法设计而言，并行计算模型起到了屏蔽并行机实现 细节的作用，使得设计的算法可映射到一类并行机上，具有更强的生命力。 具体而言，并行计算模型的主要作用如下： 1 为并行算法的研究提供了一个比较通用的物质基础： 2 为并行算法的设计与分析提供了一种简单、方便的框架： 3 使得设计的并行算法具有一定的生命力，可以适用于多种具体的并行机。 迄今为止，己经有多种并行计算模型存在，如p r a m 模型、l o g p 模型、c 3 模型、 b d m 模型等。但其中的每一种模型只抽象了实际并行机的一个或几个方面，尚无一 种模型适用于所有并行机。 2 6 并行通信与同步 进行并行计算时，处理器之间的数据调度、传输，需要通信开销。基于共享存 储的并行计算模型的通信是依靠全局存储变量来完成的，所以其通信开销并不是很 大。但是在基于分布存储、特别是使用消息传递的并行计算模型上，数据在处理器 之间选路、传输可能花费的时间要长得多。 并行系统执行给定算法的过程中，出现某些处理机的一些计算必须在其他处理 机的一些计算完成之后才能进行时，保持操作的同步是必要的，即保证此类情况得 以正确实施。同步要有两方面的开销：一是实现同步一般要求对所有处理机作某种 检查，在此是要花费时间的：二是某些处理器或是所有处理器都可能闲置，等待准 许继续进行计算的消息。目前已经有各种技术来实现同步，包括软件技术与硬件支 持。 2 7 并行算法的性能度量 对于一个给定问题，如果设计了一个新的并行算法，就必须对该算法的性能进 行评价。性能度量的目的就是为并行算法的设计与分析提供一个统一的衡量标准。 在当前并行计算环境中，并行算法的性能度量一般涉及到求解问题的规模与分类、 具休并行机的性能、影响算法的关键因素、并行算法评价准则等方面的问题。本节 主要介绍度量并行算法性能的一些基本概念。 ( 1 ) 运行时间。并行算法的运行时间是指算法在并行计算机上求解一个问题所 需的时间。即表示从算法开始执行到执行结束的这一段时间。如果多个处理机不能 0 华北电力大学硕士学位论文 同时开始或同时结束时，则算法的运行时间定义为：从最早开始执行的处理机开始 执行时算起直到最后一台处理机执行完成所经过的时间。在计算机上实现一种算法 之前，通常需要对其运行时间进行理论分析。对并行算法运行时间的分析包括估计 它在最坏情况下的计算时间和通信时间，其中的计算时间是用算法所需执行的基本 操作次数或步数表示，通信时间则是根据计算得到的通信次数和每步的通信量，依 据并行计算模型计算得到。理论分析得到的算法运行时间常表示为输入问题规模的 函数。对于一个规模为n 的问题，算法的运行时间可用t ( n ) 表示，它是输入问题规 模n 的函数。 ( 2 ) 并行度与粒度。算法的并行度d o p ( d e g r e eo fp a r a l l e l i s m ) 是指该算法中 可并行执行的操作数。若处理机资源无限，则算法的并行度也可以理解为可以利用 来作并行运算的处理机台数。然而很少有并行算法能在整个算法执行过程中保持并 行度不变，所以更准确的说法还应该加上时间范围的限制，即在某时间范围内的并 行度。 从直观意义上可以说，并行度是刻画一个并行算法的“并行程度”的量，它反 映了软件并行性与硬件并行性匹配的程度。显然，与算法并行度有关的概念是粒度。 一般而言，大的粒度意味着能独立并行执行的是大任务，算法的并行度小：小的粒 度意味着能独立并行执行的是小任务，算法的并行度大。 ( 3 ) 加速比和效率。加速比和效率是最传统的并行算法评价标准，它们体现了 在并行机上运用并行算法求解实际问题所能获得的好处。 并行算法的加速比定义为： s e = 导 ， 式中，互一最优串行算法在单处理机上的运行时间：l 一并行算法使用p 台处 理机的计算时间。 并行算法的效率定义为： 廓= 等 式中，p 为处理机台数。 如果按照某种条件，如保持每台处理机的计算规模，并行算法加速比s 。与处理 机的台数p 成正比，则称该并行算法在该条件下，在该并行机上具有线性加速比。 在某些条件下，s p p ，则称该条件下，该算法具有超线性加速比。 ( 4 ) 可扩展性。可扩展性是设计高性能并行计算机和并行算法所追求的另一个 华北电力大学硕士学位论文 重要目标。由于并行系统的性能与系统规模、问题规模、算法内在并行性以及由于 通信、同步和进程创建等引起的系统开销等因素有关，而这些因素对并行系统的结 构和应用程序的可扩展性都有影响，因此可扩展性也是衡量并行系统性能的一个重 要度量指标。衡量系统可扩展性的方法有很多，一般采用等效率度量方法。 所谓等效率是指系统规模增加时，测量增加多少运算量会保持效率不变。 2 8 并行算法设计应注意的问题 根据并行化的特点分析，无论采用什么方法进行设计并行算法，以下几点都是 决定并行效率的重要因素“3 第一，挖掘并行性。针对一个具体问题设计其并行算法时，可根据求解该问题 的串行算法出发，分析其明显的并行性，加以并行化，并应该利用相关知识，深刻 挖掘问题内在的可并行性。 第二，并行算法依赖并行的环境。并行算法与进行并行运算的环境密切相关， 同一个并行算法在不同的并行系统上运算的差别很大。所以说，要根据并行运算的 环境有针对性的设计并行算法。 第三，考虑通信开销。通信开销是一个必须考虑的因素，因为有时通信在整个 算法中占用时间的比例很大，特别是在分布存储的并行环境下，要尽量减少通信开 销，才能设计出高效率的并行算法。 1 2 华北电力大学硕士学位论文 第三章m pi 消息传递及并行程序设计 3 1m p i 系统简介 并行程序日益增强的简易性和灵活性增加了它对于科学家或工程师的吸引力。 在众多的并行程序库中，应用较广泛的有消息传递接口( m p i ) 标准和并行虚拟机 ( p v m ) 环境。p v m 是o a kr i d g e 美国国家实验室和t e n n e s s e e 大学在1 9 8 9 年开发出来 的：m p i 诞生于数年之后，是由美国几所大学和美国国家实验室出于创建消息传递库 标准的目的共同开发成功的。 对m p i 的定义，可从以下三个方面来认识： ( 1 ) 帅i 是一个库，而不是一门语言。m p i 库可以被f o r t r a n 或c 语言 调用，它遵守调用语言语法中对过程或函数的调用规则。 ( 2 ) m p i 是一种标准或规范的代表，而不特指某一个对它的具体实现。现在， 几乎所有的并行计算机制造商都提供对m p i 的支持，可以在网络中免费得至i m p i 在不 同并行计算机上的实现。一个正确的m p i 程序，可以不加修改地在所有并行机上执 行。 ( 3 ) m p i 是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标 准。m p i 虽然很庞大，但是它的最终目的是服务于进程间通信这一目标。 m p i 的标准化开始于1 9 9 2 年4 月。在1 9 9 2 年1 1 月推出了m p i 。并在1 9 9 3 年2 月完成 修订版本。1 9 9 5 年6 月推出了m p i 的新版本m p i i 。对原来的m p i 作了进一步的修改、 完善和扩充。1 9 9 7 年7 月，在对m p i 做了重大扩充的基础上，又推出了m p i 的扩充部 分m p i - 2 ，而把原来的m p i 各种版本称为m p i 一1 。m p i 一1 目前己经基本成熟稳定。m p i 一2 目前己经出现实验测试性版本( 如m p i c h 2 ) ，但还没有完整的正式版本。 m p i 的特点概括来说有三方面：较高的通信性能：较好的程序可移植性：强大的 功能。具体来说，包括以下几个方面： ( 1 ) 通用性：m p i 是可移植的标准平台，其通信单元包含上、下文和组的信息， 以保证消息传递的安全性。 ( 2 ) 点对点通信：m p i 能有效地管理消息缓存区，具有结构化缓存、扩充数据类 型及异构性，m p i 异步执行时能保护用户的其它软件不受影响，能实现完全的异步 通信。立即发送与接收可完全与计算重叠进行。 ( 3 ) 数据汇集方式：具有内定和用户自定义的数据汇集操作方式，可对大量数据 进行整体传输，可直接或依拓扑结构定义子组。 1 3 华北电力大学硕士学位论文 ( 4 ) m p i 的实现方式多样化，同一编程界面可有多种开发工具，具有面向应用的 信息传递拓扑结构：内定支持网格和图拓扑结构。 ( 5 ) 良好的操作环境：具有差错控制功能。n i p l 2 在i o 、主动消息、进程启动、 动态进程控制等方面有进一步增强。b i p i 还有在x 窗口下运行的m p i c h 版本。用户可 以在x 窗口下用u p s h o t 或n u p s h o t 直观地考察m p i 运行程序过程中各处理器之间的同 步、计算、消息发送、接收等情况，从而为程序的修改提供依据。 3 2m p i 的通信模型 分布存储环境下，消息传递是多个并行任务之间沟通的桥梁。m p i 消息传递的 灵活性也体现在通信机制方面。并行程序设计者可以根据通信需求，选择合适的通 信方式，实现高效率的消息传递。b i p i 提供了点到点通信和全局通信两种通信形式“1 。 3 2 1 点到点通信 对于源和目的任务之间的直接通信， 责发送的任务将数据放入到发送缓冲区， b i p i 提供了点到点的发送和接收函数。负 发送给接收数据的特定目标任务，后者有 相应的接收缓冲区。点到点的通信有两种发送和接收方式：阻塞和非阻塞。阻塞发 送的完成意味着数据已拷贝出缓冲区，即通信缓冲区可重新分配。阻塞接收的完成 意味着到来的消息己拷贝入用户接收缓冲区，即接收方已可以使用。但是，发送的 完成并不意味着一个匹配的接收己发生，发送的消息可能被缓存在系统的缓冲区 中。这样，发送可在匹配接收发生之前完成。非阻塞操作可以使得计算与通信重叠 泌须有系统硬件支持，m p i 的非阻塞操作立即返回一句柄，这不意味着数据已经拷 贝出发送缓冲区( 或数据己拷贝入用户接收缓冲区) ，该句柄可用来在适当的时候完 成即( m p i - w a i t ) 或检测( m p i t e s t ) 对应的非阻塞操作。 m p i 提供具有以下语义的阻塞和非阻塞发送： 标准发送：发送可以在相应接收前后发生，发送完成则发送者缓冲区可用； 就绪发送：发送仅在相应接收发生后才能发出，其完成则发送者缓冲区可用； 同步发送：发送可在相应接收前后发生，但仅在接收完成后才返回( 完成) 。 图3 1 描述了点到点通信的一般形式。 1 4 华北电力大学硕士学位论文 3 2 2 通信器 图3 - 1 点到点通信的一般形式 m p i 的一个关键特征就是通信器。其以对象形式存在，作为通信操作的附加参 数。通信器为开发消息传递程序提供了模块化支持，从而强有力地支持开发并行库 和大规模代码。通信器的概念来自于z i pc o d e 和c c l 的全局通信。在m p i 中，进程以 组内的相对r a n k 来标识，通信器参数则说明所涉及的进程组，使用该通信器的通信 操作限制在该进程组的进程之间。这样，一组进程集上的库代码被用于另一组进程 集时，库代码无需改动，而只要重定义描述该进程集的通信器。每一个通信器定义 了一个唯一的进程组通信上下文。由上下文和区别消息的t a g 一起来进一步区别不 同进程上下文的具有同一个标识的消息。上下文由系统严格管理，对用户是透明的， 有力地保证了库代码的消息通信互不干扰。m p i 提供了各种机制用于创建和管理通 信器。在初始化时预定义一个通信器( m p i c o 删一w o r l d ) ，相应的进程组包含了初始 化时存在的所有进程。 3 2 3 全局通信 m p i 有一组丰富的全局通信函数，包括b a r r i e rs y n c h r o n i z a t i o n ， b r o a d c a s t ，s c a t t e r ，g a t h e r 和各种规约操作。通信器用来标识参与全局通信的进程 组，这样全局通信可以包括任意预定义的进程子集。 3 3m p i 的主要实现啪 m p i 处于讨论阶段时，就己经出现了m p i 的模型实现：m p i 标准发布后，国际上己 有许多m p i 实现，其中以自由软件形式发布的l a m “”和m p i c h “”较为流行。 l a m ( l o c a la r e am a c h i n e ) 是o h i o 超级计算中心开发的基于异构网络机群的并 华北电力大学硕士学位论文 行程序支撑环境，向用户提供m p i 编程界面及一个完整的运行调试环境。l a m 的结构 是开放的、高度结构化的。其运行代码由三部分组成：d a e m o n 、接口库及维护调试 工具( l a m 命令) 。l a m 启动后，在虚拟机的每一个节点上运行一个d a e m o n ，用户通过 l a m 的加载命令以s p m d 或m p m d 形式将任务加载到指定的节点上运行，用户通过调用 库接口完成消息传递。l a m 支持动态进程组及虚拟机的动态扩充。 m p i c h 是由a r g o n n e 美国国家实验室和密西西比州立大学伴随m p i 制定的过程联 合开发的一个可移植的m p i 实现。在此过程中，i b m 也做出了自己的贡献。其主要目 标是实现一个可移植性好而且高效的m p i 接口。 m p i c h 含三层结构，最上层是m p i 的a p i ，基本是点到点通信和在点到点通信基 础上构造的集群通信( c o l l e c t i v ec o m m u n i c a t i o n ) ：中间层是a d i 层( a b s t r a c t d e v i c ei n t e r f a c e ) ，其中d e v i c e 可以简单地理解为某一种底层通信库，a d i 就是对 各种不同的底层通信库的不同接口的统一标准：下层是具体的底层通信库。 3 4m p l 并行程序的两种基本模式 对等模式和主从模式是m p i 并行程序的两种最基本的设计模式“町“”。大部分的 m p i 程序都是这两种模式之一或二者的组合。掌握了这两种模式，就掌握了并行程 序设计的主线。m p i 程序一般是s p m d 程序，当然也可以用m p i 来编写m p m d 程序，但是 所有的m p m d 程序都可以用s p m d 程序来表达，二者的表达能力是相同的。s p m d 程序有 很强的表达能力，s p m d 只是形式上的表现，其内容是很丰富的。本论文中涉及的m p i 程序均是s p m d 程序。 3 4 1 对等模式 以下以j a c o b i 迭代为例来描述m p i 对等模式的并行程序设计。 j a c o b i 迭代是一种比较常见的迭代方法，简单说j a c o b i 迭代就是用某点四周相 邻数值点的平均值替代该点的值。它的局部性很好，可以取得很高的并行性，是并 行计算中常见的一个例子。 假设需要迭代的数据在( n + i ) ( n + i ) 的二维数组a ( n + i ，n + i ) 中，j a c o b i 迭 代的串行算法描述如下( 程序1 ) “” 程序l串行表示的j a c o b i 迭代( 边界值在迭代中是不变的) d o u b l ea n + i n + 1 ，b n + 1 n + i ： f o r ( i n tj = 1 ：j + + ：j = n 一1 ) f o r ( i n ti = 1 ：i + + ：i = n 1 ) 1 6 华北电力大学硕士学位论文 b i j = o 2 5 * ( a i 一1 j + a i j - 1 + a i j + 1 ) ： f o r ( i n tj = l ：j + + ：j = n 1 ) f o r ( i n ti = 1 ：i + + ：i = n i ) a i j = b i j ： j a c o b i 迭代的串行算法就是依照矩阵行列，按先后顺序计算每个元素的四邻域 的平均值，最后得出迭代结果。 为了并行求解，在对等模式下，将参加迭代的数据进行按列进行近似等分分割， 并假设共有4 个进程同时并行运算。并行运算的模型如图3 - 2 所示。 发送接收发送接收发送接收 3 图3 2j a c o b i 迭代的数据划分与对应进程 由于在迭代的过程中，边界点的新值的计算需要相邻边界其他块的数据，因此 在每一个数据块的两侧又各增加1 列的数据空间，用于存放从相邻数据块通信得到 的数据。进程0 和进程3 的数据块只需扩大一块即可满足通信的要求，但这里为了编 程的方便和形式的一致，在两边都增加了数据块。计算中的每一个新迭代点的值都 是由相邻点的旧值得到的。 2 4 2 主从模式 主从模式下，一组进程中的一个进程为主进程，负责从进程的生成、初始化， 并分配负载给从进程。从进程完成计算后，将结果传送给主进程，最后由主进程收 集计算结果并合并后输出。 华北电力大学硕士学位论文 以下以矩阵向量乘c = a * b 为例子介绍主从模式。实现方法：主进程将向量b 广播 给所有的从进程，然后将矩阵a 的各行依次发送给从进程，从进程计算一行和b 相乘 的结果，然后将结果发送给主进程。一旦主进程将a 的各行发送完毕，则每收到一 个结果，就向相应的从进程发送结束标志，从进程收到结束标志后退出执行。主进 程收集完所有的结果后也结束。分解过程如图3 - 3 所示。 送 3 5m p l 基本编程技术 图3 - 3 矩阵向量乘的主从并行分解 m p i 由一组库函数组成，并行程序的各任务通过这些函数进行通信。一个m p i 并 行程序由m p i 任务组成，这些任务可以相同也可以不同。每个m p i 任务在使用m p i 库 之前必须在m p i 环境中登记。一旦m p i 任务在m p i 环境中登记，就可以和其他w p i 任务 进行通信。其本身和目标任务之间可以采用原始的点到点通信，一组中的所有成员 则可以采用集中式通信方式。 m p l l 标准基于静态加载“”，即所有进程在加载完以后就全部确定，直至整个程 序结束才终止，在程序运行期间没有进程的创建和结束。一个m p i 程序的所有进程 形成一个缺省的