（电力系统及其自动化专业论文）电力系统暂态稳定空间并行仿真.pdf

a st h es c a l eo ft h ei n t e r c o n n e c t i o no fp o w e rs y s t e m si se n l a r g i n gi n c r e a s i n g l y , i t h a sb e a ) o m ea l lu r g e n ti s s u et od e v e l o pf a s ta n de f f i c i e n tt o o lf o ro n - l i n ed y n a m i c s e c u r i t ya n a l y s i s i ti so b v i o u st h a tt h et r a d i t i o n a ls e r i a lc o m p u t a t i o nc o u l dn o ts a t i s f y t h er e q u i r e m e n to fr e a l - t i m es i m u l a t i o nf o rt h et r a n s i e n tp r o c e s so fl a r g ep o w e r s y s t e m s 1 1 1 ep a r a l l e l - i n - s p a c ec o m p u t i n gf o rl a r g 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 yo n t h ec l u s t e rs y s t e mi ss t u d i e di nt h i sd i s s e r t a t i o n t h em a i nw o r k sa r ef o c u s e do nt h r e e p r o b l e m si n c l u d i n gt h et a s kp a r t i t i o n i n g , t h ep a r a l l e la l g o r i t h md e s i g n i n ga n dt h e a s s e s s m e n tf o rt h es p e e d u p ( 1 ) b a s e do nf a c t o f i z a t i o np a t ht r e ep a r t i t i o n i n g ，an e wp a r t i t i o n i n gs c h e m ef o rt h e s i m u l a t i o n i n - s p a c eo f t r a n s i e n ts t a b i l i t yi sp r o p o s e dc o n s i d e r i n gt h ec o m p u t i n go f t h e d i f f e r e n t i a le q u a t i o n t h i sa l g o r i t h ma d o p t st h eg e n e r a t o rb u sw e i g h ta n dan e w p e r f o r m a n c ei n d e xf u n c t i o nf o ra s s e s s i n gt h ep a r t i t i o n i n g h e m ei nt h eo r i g i n a l a l g o r i t h mo f f a c t o r i z a t i o np a t ht r e ep a r t i t i o n i n gt om a k et h ed i s t r i b u t i o no f c o m p u t i n g l o a db e t w e e ne a c hp r o c e s s o rm o r er e a s o n a b l e ( 2 ) t h ep a r a l l e ls o l v i n gp r o c e s sf o ral a r g es p a r s el i n e a re q u a t i o nw h i c hh a st h e b o r d e r e db l o c kd i a g o n a lf o r mi sd e r i v e dc l e a r l yi nt h i sd i s s e r t a t i o n , i th a st w op a r t s i n c l u d i n gt h ep a r a l l e ll uf a c t o r i z a t i o na n dt h ep a r a l l e lf o r w a r da n db a c k w a r d s u b s t i t u t i o n s i na d d i t i o n , t h i sp a p e ra l s oo p t i m i z e st h ec o m p u t a t i o np r o c e s sa n dt h e c o m m u n i c a t i o np r o c e s si nt h e p a r a l l e l - i n - s p a c es i m u l a t i o no ft r a n s i e n ts t a b i l i t y n a m e l y , t h ep o s t - p a r t i t i o n i n go r d e r i n gp r o c e s si sa d o p t e dt od e c r e a s et h ec o m p u t a t i o n o ff o r w a r da n db a c k w a r ds u b s t i t u t i o n sb e c a u s eo n l yt h eg e n e r a t o rb u so w n st h e n o n z e r oi n j e c t i n ge l e m e n ti nt h en e t w o r ke q u a t i o n ；t h ec o m m u n i c a t i o np r o c e s si nt h e p a r a l l e ls i m u l a t i o ni si m p r o v e dt h r o u g ht h ea l t e r i n go f t h es t y l eo f d a t at r a n s m i s s i o n ( 3 ) 1 1 1 i sp a p e ra d v a n c e saf o r m u l af o re s t i m a t i n gt h es p e e d u pu n d e rt h ei d e a l c i r c u m s t a n c ea n da n a l y z e st h ef a c t o r st h a ti n f l u e n c et h ee f f i c i e n c yo ft h ep a r a l l e l s i m u l a t i o mi ta l s oi l l u s t r a t e st h ek e yp o i n tt h a tw h e nt h ed e c r e a s i n gt i m ec o n s u m e d b y t h ep a r a l l e lp a r ti se q u a lt ot h ei n c r e a s i n gt i m ec o n s u m e db yt h es e r i a lp a r ta n dt h e c o m m u n i c a t i o np a r ti nt h ep a r a l l e ls i m u l a t i o np r o c e s s ，t h es p e e d u pw i l lr e a c ht h e m a x i m u m m e a n w h i l e ，t h i sp a p e ra l s oe v a l u a t e st h en u m b e ro fp r o c e s s o r sn e e d e dt o a c h i e v et h em a x i m u ms p e e d u pw h e nt h e3 k b u sp o w e rs y s t e mi st e s t e do nt h e c l u s t e r l3 5 0 t h es i m u l a t i o nr e s u l t so b t a i n e df r o mt w od i f f e r e n tt e s t sv a l i d a t et h ea d v a n t a g e so f k e yw o r d s ：t h ep a r a l l e l i n - s p a c 圮s i m u l a t i o nf o rt r a n s i e n ts t a b i l i t y , f o r w a r da n d b a d c w a r ds u b s t i t u t i o n s ，c l u s t e rs y s t e n 1 ，f a c t o r i z a t i o np a t ht r e e ，s p e e d u p 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫生盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：嘲毒件签字隰加z 年2 月z 7 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘鲎有关保留、使用学位论文的规定。 特授权墨洼盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 扬莲持 导师签名： 月刁日 签字日期 b 月撕年 天津大学硕士学位论文 第一章绪论 1 1 课题的耳的和意义 第一章绪论 电力工业是现代社会的重要支柱，现代电力系统已经在大容量、高电压和远 距离输电等方面取得了重大进步。到2 0 0 4 年底为止，我国发电装机容量已突破 4 亿千瓦，居世界第2 位( 仅次于美国) 【l j ，我国已建成2 2 0 k v 及以上输电线路 2 2 3 万公里，5 0 0 k v 线路近5 6 0 0 0 公里，第一条7 5 0 k v 线路已经在西北电网正 式建成投产1 2 1 ，第一条1 0 0 0 k v 输电线路也正在积极筹建中 3 1 。 随着三峡电站各机组的并网发电，我国输电网已完成了川渝一华北一东北 华中的5 0 0 k v 交流互联，加之已经竣工的华中一华东直流联网以及正在进行 的海南独立省网与南方电网的联网工程，我国电网正在逐步形成以华北、东北、 华东、华中、西北和南方电网共六个跨省区电网为基础的全国范围内的超大规模 互联电力系统f ”。全国联网系统的建立有利于不同地区电力资源的互济和合理利 用，将大幅提高系统供电能力，改善缺电、窝电共存的不利局面。而我国电网网 架薄弱、负荷与发电中心远离、峰枯水期对运行方式影响显著等问题仍将长期存 在，甚至随着联网系统的形成而进一步凸显，局部故障会引发整个系统的安全稳 定问题。因此，对于这样一个交直流联合运行的超大规模电力系统，如何保证其 安全、稳定和经济运行，是世界级的研究课题。这其中，对大规模电力系统运行 特性进行全面、详尽、快速、准确的认识与把握，是保证全国联网安全经济运行 的首要问题，中国电力系统新发展阶段的规划和运行实际迫切需要面对全国联网 系统的仿真平台。 在线动态安全监测与分析系统的目的是建立高效和稳定的电力系统运行保 障体系【4 ，5 1 ，该体系对电网进行实时监控和仿真分析，提出了详尽的动态信息和 事故紧急处理建议，有效的增强了系统的运行稳定性，对大规模复杂电力系统的 实时调度起着至关重要的作用，而电力系统暂态稳定计算则是建立高安稳度和高 效率的电力系统运行保障体系的重要组成部分，实时和超实时仿真是该体系能够 有效工作的前提和基础。 天津大学硕士学位论文 第一章绪论 集成混合实时仿真系统将机电暂态计算与电磁暂态计算互联，对设备装置进 行系统级的运行分析研究和优化设计，是电力系统数字实时仿真发展的一个重要 方 甸1 6 , 7 1 。即使目前最先进的实时仿真器r t d s ( r e a l t u n ed i g i t a ls i m u l a t i o n ) 也 仅能满足百节点、十几机系统的电磁暂态过程的实时计算。集成混合实时仿真系 统引入机电暂态对外部系统进行分析，与内部电磁暂态计算通过实时电压和基波 电流进行交互。这种仿真策略有效的突破了仿真规模对实时仿真的限制，也将实 时计算的瓶颈由对小规模简化电网的电磁暂态计算转变为对大规模实际电网机 电暂态过程计算的实时要求。 此外，大规模电力系统的联合反事故演习也需要暂态过程的实时仿真来为培 训人员提供逼真的事故场景和详尽的系统动态变化过程，有效提高调度运行人员 的事故应变能力。 综上所述，在线动态监测和安全分析、集成混合实时仿真和联合反事故演习 等许多重大问题都对电力系统的机电暂态稳定计算提出了实时甚至超实时的仿 真要求，然而，随着电力系统互联规模的不断扩大以及暂态仿真过程中模型复杂 程度的不断提高，加之暂态仿真算法的缓慢发展( 仍然停留在基于数值积分为基 础的仿真算法之上) ，现有的串行暂态稳定分析程序根本无法实现大规模电力系 统暂态过程的实时仿真。为了从根本上解决这个问题，采用当前蓬勃发展的并行 处理技术是大幅提高暂态过程仿真速度的有效途径之一。本文就是采用了当前流 行的集群系统结合一定的并行算法对暂态稳定进行并行仿真的。 1 2 并行计算机的发展现状 随着超大规模集成电路( v l s i ) 技术的不断发展，计算机c p u 芯片等硬件制 造已经接近了理论极限( 如光速是不可逾越的速度极限，设备和材料也不可能做 得无限小等) ，很难再有更大幅度的提高，然而当今社会人们面临着诸如天气预 报、天文学、语音识别等方面的巨大挑战【删，这无疑需要计算处理能力更强大 的并行计算机的帮助。 并行计算机即能在同一时间内执行多条指令( 或处理多个数据) 的计算机，并 行计算机是并行计算的物理载体。根据一台并行计算机能够同时执行指令与处理 数据的多少，并行计算机可分为u 0 s i m d ( s i n g l c i n s t r u c t i o nm u t i p l c - d a t a ) 单指令 天津大学硕士学位论文第一章绪论 多数据并行计算和m i m d ( m u t i p l e - i n s t r u c t i o nm u t i p l e - d a t a ) 多指令多数据并行计 算机；此外，随着新的并行计算机组织方式的产生，按同时执行的程序与处理数 据的多少，人们又提出了s p m d ( s i n g l e - p r o g r a mm u t i p l e - d a t a ) 单程序多数据并行 计算和m p m d ( m u t i p l e - p r o g r a mm u t i p l e - d a t a ) 多程序多数据并行计算机的概念。 从物理划分上，并行计算机有共享内存和分布式内存两种基本的存储方式。 除此之外，分布式共享内存也成为一种越来越重要的并行计算机存储方式。对共 享内存的并行计算机，各个处理单元通过对共享内存的访问来交换信息、协调各 处理器对并行处理任务的处理。对这种共享内存的编程，实现起来相对简单，但 共享内存往往成为性能特别是扩展性的重要瓶颈。对于分布式内存的并行计算 机，各个处理单元都拥有自己独立的局部存储器，各个处理器间通过消息传递来 交换信息，协调和控制各个处理器的执行。本文所采用的消息传递并行编程模式 ( m p i 消息传递接口) 所对应的并行计算机就采用这种存储方式。通信对分布式内 存并行计算机的性能有重要的影响，复杂的消息传递语句的编写成为在这种并行 计算机上进行并行程序设计的难点所在，但是，对于这种类型的并行计算机，由 于它有很好的扩展性和很高的性能，因此，它的应用十分广泛。分布式共享内存 的并行计算机结合了前两者的特点，是当今新一代并行计算机的一种重要发展方 向。目前越来越多流行的集群计算( d u s t e rc o m p u t i n g ) 大多采用这种形式的结构。 集群系统b 1 , 1 2 是一群以网络技术连接起来的工作站或p c 机的组合，是当今 并行计算发展的一种主流技术，与传统的并行系统相比，集群系统具备以下特点： 1 采用商用处理器节点通过高速网络( 1 0 0 m ，i g ，2 g 、光纤等等) 互联而成， 系统构建灵活，开放性好； 2 商用硬件使集群系统较其他并行机更紧密跟踪最新硬件发展趋势，系统 扩展性好，性价比高； 3 集群系统各个节点具备完整的操作系统，这种节点自治的特点有效地限 制了系统故障影响，保护用户投资，提高系统可用率。 集群计算在大规模油藏模拟、天气预报、物理学模拟以及石油勘探等计算密 集型领域已经获得了巨大的成功1 3 1 ，为集群技术在大规模电力系统计算提供了很 好的借签作用。 天津大学硕士学位论文 第一章绪论 1 3 哲态稳定并行仿真的研究现状 1 3 1 暂态稳定计算模型 暂态稳定，是指电力系统遭受严重暂态扰动如输电设备上的故障、发电机跳 闸或失掉一个大的负荷之类时保持同步的能力1 4 1 。用于暂态稳定分析的电力系统 数学模型可由如下非线性微分代数方程组表示。 譬= 硝4 - b u ( x ，矿) ( 1 1 ) 1 ( x ，矿) = r ( r ) 矿 ( 1 2 ) 式( 1 1 ) 中的微分方程描述了电力系统中相关元件的动态特性，并为动态元件的状 态变量，输入是状态变量z 与电压y 的函数；非线性方程组式( 1 - 2 ) 代表电力系 统的网络方程，i ( x ，矿) 是与x 和v 相关的动态元件注入电流向量，y ( x ) 是与x 相关的系统导纳矩阵( 复矩阵) 。 现今常用的机电暂态时域仿真算法主要有两种阍，一种是微分方程代数方程 联立求解法，利用隐式梯形公式对微分方程差分化，把差分方程和网络方程联立 求解。隐式积分联立求解具有较好的数值稳定性，但在程序设计和实现上较为复 杂，需要建立联立的修正方程，程序的可扩展性和灵活性不足且仿真所用时间相 对较长。另一种算法是基于隐式积分法的微分方程、网络方程交替迭代法。交替 迭代法虽然存在微分方程和代数方程的交接误差，但保持了隐式积分数值稳定性 好的优点，又具备显示积分法简单灵活的特点，为许多串行暂态稳定程序所应用。 1 3 2 暂态稳定并行算法的研究现状 到现在为止，对电力系统暂态稳定并行算法的研究已经有2 0 多年的历史了， 有许多优秀的并行算法相继被提出，但客观的讲这些并行算法绝大部分都是以原 有串行算法为基础进行算法结构方面的修改，很少有彻底革新式的并行算法的提 出( 这可能归因于数学算法研究领域的发展缓慢) 。总体来讲，暂态稳定并行仿真 算法可分为三类【1 9 1 ，即空间并行算法、时间并行算法以及时空并行算法。 1 3 2 1 暂态稳定空间并行算法 空间并行仿真算法首先利用不同的网络划分技术对电力网络进行划分b 0 】，之 天津大学硕士学位论文 第一章绪论 后再采用相应的暂态稳定并行求解策略口1 1 进行并行求解。 1 9 9 1 年，j s c h a i 2 2 在微分代数方程联立求解的基础上，将单步超松弛牛顿 法( s o r - n c w t o n ) 用于电力系统暂态稳定计算，用松弛因子配合j a e o b i 矩阵的对 角元进行迭代运算，大大减少了牛顿法的计算相关性。其迭代矩阵可以表示为： 蹬哆糕 ( 1 - s ) 其中，墨代表( x ，矿) 中的任一变量，代表其所对应的加速因子，而 嘱啪兮毯 ( 1 川 本方法是将牛顿法的快速收敛性、j a c o b i 法的并行性和s o r 法的加速收敛性 结合起来，使并行计算更为有效，但该算法通信时间比较大，比较适合共享内存 结构的并行处理机，不适合基于消息传递的并行计算机，同时该并行算法采用的 松弛牛顿法也在一定程度上破坏了原串行算法的一致收敛性。 1 9 9 2 年，d e c h c r 【2 3 1 针对暂态稳定计算的交替求解策略，结合共轭梯度法 ( c o n j u g a t e g r a d i e n t m e t h o d ) 提出了两种基于分块思想的暂态稳定空间并行算法。 一种算法是通过节点排序将线性网络方程构造成如下的块对角加边形式 ( b b d f ) 来并行求解。其中，位于对角线上的p 个子区域相互解耦，通过边界块s 建立各子域间联系。如下式( 1 5 ) 所示： ( 五，巧) ( 耳，巧) ( 墨，珞) k b 1 i s ： 耳 珞乓 k ： 蚝 ( 1 - 5 ) 其中，分别代表了p 个子区域的注入电流向量；巧，巧分别表示p 个子区域的节点电压向量；，。和k 分别表示协调系统的注入电流和节点电压； x ，耳，乓表示各子区域和协调系统的自导纳矩阵；，与强，强表示 各子区域与协调系统的互导纳矩阵。 对网络方程式( 1 5 ) 的求解，d e c h e r 提供的求解步骤如下： 步骤1 ：求解h 珞= 厶 ( 1 6 ) 天津大学硕士学位论文 第一章绪论 其中交接矩阵垂：乓一圭珞r - 珞，：厶一圭】r 一 t = li = l 步骤2 ：求解z 巧= 一珞 ( 1 7 ) 文中d c c h e r 对式( 1 石) 中交接矩阵的计算首次引入了预处理的共轭梯度迭代 算法，大大增加了方程的求解并行度；文中对式( 1 7 ) 采用并行l u 分解的办法来 处理p 个相互独立的区域的计算。另外本文还采用了异步并行算法，大大减少了 通信损耗和同步等待时间，但是系统如何划分使协调系统尽量小、各个子区域之 间的计算负荷尽量平均是本算法实现过程中的一个关键因素。 另一种算法是通过节点排序将线性网络方程构造成如下的近似对角块形式 ( n b d f ) 来进行并行求解。其中，位于对角线上的g 个子区域之间相互弱耦合。 如下图所示： 小 x i写2 ： ； ( 1 - 8 ) 为了增加并行度，d e c h 魄略了导纳矩阵中的非对角元素，采用预处理的 共轭梯度法进行求解，但是在有些情况下该算法存在收敛一致性问题，与各区域 之间的耦合程度密切相关。 考虑到暂态稳定计算过程中需要进行大量的网络方程前代回代运算，很多学 者致力于开发基于指令级并行性 2 5 啪1 的算法，1 9 9 0 年，a l v a r a d o 基于稀疏矢量 法率先提出了形矩阵算法【躺3 】用于并行实现网络导纳阵( 或者j a c o b i 矩阵) 的l u 求解过程。网络导纳阵y 经过l u 分解为】r = l d u ，各节点电压为v = u 。1 d - 1 l - 1 i ， 将三角阵f 1 化为一系列因子矩阵相乘形式：= e 1 与1 f ，并进一步分组为 l - 1 = 睨( 理论证明显示，与上相比，其逆矩阵的分解矩阵彬，中不 会产生任何附加的注入元，但前代回代过程的串行步数将增大至2 n 步，大大增 加了算法的同步次数，使形矩阵算法失去了实际意义。而聚合为一个矩阵又会 在原有的因子表稀疏结构中引入较多的附加注入元，增大计算量，降低并行求解 效率) ，对于系统导纳阵对称系统u = 【r 1 ，= 彤7 呀孵，通过合并某些分 解矩阵形，节点电压的求解可以化为矿= 7 哆dl ，基于此形 辜_illi巧匕；_ 天津大学硕士学位论文第一章绪论 式，网络方程的求解可以实现p 台处理器上的并行计算。 另外，文献【3 4 】还针对详细模型的暂态稳定计算，提出了基于分块法的复合 导纳矩阵求逆方法；文献 3 5 1 贝1 j 介绍了一种预估一校正的空间并行算法；文献 3 6 】 进一步简化迭代矩阵利用卷积方法来计算变量波形，以实现其空间并行仿真；文 献 3 7 1 基于牛顿法提出了块对角加边形式的网络方程迭代求解的加速方法，即通 过在子系统与协调系统的迭代计算中引入附加矩阵变换，以加快各子系统内部和 子系统与协调系统之间的迭代收敛速度。 1 3 2 2 暂态稳定时问并行算法 暂态稳定时间并行算法的核心思想是通过多个时步同步求解，在牺牲一定收 敛性的前提下增大算法的并行度，提高暂态稳定并行仿真的计算性能。 利用隐式梯形积分方法可将( 1 1 ) 差分化为代数方程，与( 1 2 ) 联立得到： 五一五。= 尝 彳( 五+ 五。) + b l ( 置，k ) + “( 置。，巧。) f ；l ，丁( 1 9 ) l ，( z ，k ) = y ( e ) k 用紧凑形式表示：局，以q ) = o t = 1 ，r ( 1 - 1 0 ) 传统串行求解方法是利用牛顿迭代法 降矿一别：研。置( 矿蓐) ( 1 - 1 1 ) 。，- 吐 其中，c ，为t - 1 时段的收敛值，显然这种分步积分算法是一种串行算法。 1 9 9 0 年，m l s c a l a 提出了g a u s s j a r o n b l o c k - n e w t o n 暂态稳定并行算法1 3 7 ， 其迭代式为：只( 矿，z 7 - - o ，在每个时间段上采用n 怕n 法求解上式，即： 班矿一刮榭一( 矿剖 ( 1 1 2 ) 。r , _ j - y t - ； 各时段可同时求解。 1 9 9 1 年，m l s c a l a 又提出了g a u s s s e i d e l b l o c k - n e w t o n 暂态稳定并行算法 3 8 1 ，其迭代式为：羁( p ，珐) = o ，而在每个时间段上采用如下解法： 天津大学硕士学位论文 第一章绪论 班矿一刮a 珊y t t - i ，；he ( 班啪 ( 1 1 3 ) 耻i f r , z _ l m l s c a l a 设计了“流水线”并行计算方案，该算法收敛性比g a u s s - j a c o b i 算法 好，但是并行度有所降低，如下图所示( y 表示第f 时步的第_ ，次迭代) ： p 4 l r 嚣p 3 剐 氧 p 2 p 1 图1 - 1g a u s s - s e i d e l b l o c k - n e w t o n 时间并行算法流程图 1 3 2 3 暂态稳定时空并行算法 暂态稳定时空并行算法是时间并行算法和空间并行算法的结合，兼具了两种 并行仿真算法的优点，但其并行实现却比较复杂。 一种典型的时空并行算法是波形松弛法 4 0 , 4 1 l ( w a v e f o r mr e l a x a t i o n m e t h o d ，w r 法) ，该算法的提出为非传统方法的研究提供了一种较好的尝试。w r 法是一种求解微分代数方程的数值积分方法，其基本思想是：首先将全系统分为 弱耦合的子系统，各子系统独立求解，并且利用前面的迭代“波形”作为相关其 他子系统的状态变量和其他变量的估计值。这些波形在各子系统间相互传送，而 各个子系统则利用有关其他子系统的信息来求解，直至收敛。w r 法是任务或程 序级上的并行，它并不直接强调任务的分配，而是注重算法的内在并行性，因此 它比串行算法直接并行化改造更有效，但系统如何划分和具体的故障情况对计算 的收敛性有影响。1 9 8 7 年，m i l i c 4 2 j 首次在电力系统暂态稳定并行计算中引入波 形松弛法，分析了分区和时窗对波形松弛性的影响，指出波形松弛算法引入多时 步并行的同时，系统划分和具体故障情况对计算收敛性存在明显的影响，而且时 窗内各时步计算存在串行收敛问题，多个时步只能顺序收敛，因此时窗所包含的 天津大学硕士学位论文 第一章绪论 联解时步数不宜过大。 1 9 9 2 年，m l s e a l a t 4 3 1 将电力系统的微分代数方程用隐式梯形法变成纯代数 问题，采用逐次代入的p i c a r d 松弛法，研究了其空间和时间上的并行性，并采用 多重网络法进行迭代求解，以加强收敛性。 1 3 3 对各种暂态稳定并行算法的评价嗍 空间并行仿真算法原理比较简单，现有的大多算法主要是面向稀疏线性方程 组的并行求解，收敛性与相关串行算法相同。对角加边型的空间并行算法粒度较 大，在分布存储并行机上可获得较好的计算效率，而形矩阵法并行粒度较小， 更适合共享存储并行机。从算法实现的角度来讲，空间并行仿真算法的核心在于 并行任务的划分，如何划分电力网络使各子网络之间的计算负荷比较平均，使划 分得到的协调系统规模尽量小是该算法的核心。 时间并行仿真算法无非是在时间步和迭代次数的基础上对原有串行算法进 行的种种修正而己，是对暂态稳定问题求解空间的扩充，其实质是在通过增大联 立求解的问题规模来开发更高的算法并行度，同时引入松弛策略来降低各计算部 分的相互依赖关系。也正是因为如此，时间并行算法最大的缺点在于它增加了不 少附加计算量，收敛性要比串行计算差，而且难于处理暂态过程中由于继电保护 和自动装置动作所产生的随机事件，当联立求解的时步中出现新的事件时，会引 入大量的失效计算。 时空并行算法兼具空间和时间两种并行算法的特点，是一种很好的并行仿真 方案，但是其并行实现起来却比较复杂，有时候还得根据并行机的拓扑结构进行 并行任务的分配。 此外，各种并行算法必须适应不同的并行计算机，任何脱离具体并行处理平 台的并行算法都不算完整，换句话说，我们应该针对不同的并行处理平台设计与 其适应的并行算法。如对于分布存储式并行机而言，各处理器间的通信时间较长， 更加适合粗颗粒的并行算法( 粗颗粒并行算法是指在并行处理的过程中通信次数 较少，每次通信量较大的并行算法) ；而对于共享存储式并行机而言，各处理器 间的通信时间较短，更加适合细颗粒的并行算法( 细颗粒并行算法是指在并行处 理的过程中通信次数较多，每次通信量较小的并行算法) 。 总之，现有的暂态稳定并行算法相对快速发展的并行计算机而言是比较滞后 天津大学硕士学位论文第一章绪论 的，从已经提出的各种并行算法来看，绝大部分都是以原有串行算法为基础进行 算法结构方面的修改，尽管有极少数新颖的并行算法相继被提出( 如利用卷积、 各种智能算法等) ，但这些算法都有各自的缺点，计算效果也比较一般。 1 4 本文的主要研究工作 1 4 1 本文的主要工作 本文针对高性能集群系统下的电力系统暂态稳定空间并行仿真进行了研究。 文中同时考虑网络方程以及微分方程的计算量，利用因子路径树对电力系统暂态 稳定仿真进行并行任务划分。此外，本文还给出了并行加速比印的估算公式，并 以3 k 节点系统为例对其进行了评估。工作的具体内容包括： 1 针对求解大型稀疏线性方程组因子路径树网络划分方法的缺点，本文提出了 新的考虑微分方程计算量的暂态稳定并行仿真任务划分算法。该算法在原因 子路径树网络划分算法的基础上，通过给发电机节点附权值并采用新的电力 网络划分性能评价指标函数，使各处理器间计算负荷的分配更为合理。 2 利用前述划分结果把电力网络节点排成块对角加边形式( b b d f ) ，再通过电 力网络方程的并行因子分解、并行前代回代过程进行暂态稳定空间并行仿真， 并对算法实现过程中的计算和通信进行了优化。 3 针对本文所提任务划分算法，提出了近似的加速比印的估算公式，分析了影 响并行加速比印的各个因素，并以3 k 节点系统为例介绍了估算实现最大加 速比所需处理器数目的方法。 4 利用1 k 节点系统和3 k 节点系统算例验证了本文所提暂态稳定并行仿真算法 的正确性、合理性。 1 a 2 本文主要结构 本文第一章简单介绍了并行计算机的发展现状、暂态稳定并行仿真算法的研 究现状。第二章介绍了同时考虑网络方程前代回代计算量和微分方程计算量的基 于因子路径树的暂态稳定并行任务划分算法。第三章介绍了基于b b d f 的电力系 统暂态稳定空间并行仿真算法。第四章介绍了电力系统暂态稳定并行仿真软件设 计及其加速比评估。第五章介绍了两个不同规模系统的算例分析。 1 0 天津大学硕士学位论文 第二章基于因子路径树的暂态稳定并行任务划分算法 第二章基于因子路径树的暂态稳定并行任务划分算法 2 1 概述 从上一章对暂态稳定空间并行仿真的概述中，可以看出如何保证暂态稳定仿 真过程中各个c p u 的计算负荷相对均衡，减少同步等待，有效地降低协调系统 的计算规模和通信损耗，是提高暂态稳定空间并行仿真性能的一个重要问题。这 一问题也就是我们通常所说的并行任务分配问题，对暂态稳定空间并行仿真而 言，即为电力网络及其相关动态元件的合理划分问题，其目的是在各种分区方案 中寻找协调系统规模尽量小、计算负荷相对均衡的方案。 2 2 暂态稳定空间并行仿真任务划分方法概述 电力系统暂态稳定并行仿真算法的核心是并行任务的划分，对于空间并行仿 真任务划分而言，其实质也就是对电力网络的划分。现有的暂态稳定空间并行仿 真任务划分策略有两类，一类是静态划分策略，另一类是动态划分策略。 静态划分策略是针对暂态稳定微分代数方程的并行求解来进行电力网络的 划分，同一电力网络只需进行一次划分，划分结果在随后的计算中多次使用。静 态划分的目的是使电力网络的划分中各分区计算负荷尽量平均、协调系统规模尽 量小、对应的串行处理部分尽量小。从数学角度来讲，这样的多目标优化问题属 于n p 难【4 5 1 问题，没有多项式时间内的优化求解算法，启发式方法是解决这类问 题的主要手段。 动态划分策略是指在考虑了暂态稳定计算过程中由于故障或操作的不确定 性而引入的各分区计算负荷不均匀的问题，与静态划分策略不同，动态划分1 4 6 】 会根据扰动的位置和程度对网络分区进行动态调整，达到暂态稳定并行仿真计算 负荷的均衡。尽管动态划分策略从理论上更加注重划分结果的合理性，但是在实 用的过程中，每一次动态划分都会带来附加计算和大量的通信损耗，所以很少有 人采用动态划分策略进行电力网络的划分。尤其对于集群系统这样的分布式系统 天津大学硕士学位论文第二章基于因子路径树的暂态稳定并行任务划分算法 ( 通信速度相对计算速度来讲慢很多) ，采用动态分区技术会带来大量的附加通 信，通信损耗的增加会抵消平衡计算所带来的性能提高。另外，在暂态过程中， 故障相关区域动态过程变化剧烈，可以采用小步长精细仿真，而远离故障的区域 动态过程缓慢，可以采用大的计算步长减少总体计算量，针对这种不同区域采用 不同仿真步长的空间多时步并行仿真算法，也有相应的电力网络划分算法被提出 【4 7 朋。总之，针对本文所采用的集群系统平台通信速度相对较慢的特点，静态划 分策略更加适合并行仿真的实际需要。 现有的静态电力网络划分策略主要有基于主节点选择的划分策略、基于模拟 退火法的划分策略以及基于分层递归二分法的划分策略。下面本文对他们作一个 简单的概述。 2 2 1 基于主节点的哲态稳定空问并行任务划分算法 1 9 9 2 年，v a l e 4 9 1 提出了基于主节点的电力网络划分算法，该方法步骤如下： ( 1 ) 根据电力网络中各个节点的出线度以及各节点所连支路的电纳值对网络 中的各个节点附权值； ( 2 ) 根据电力网络中各个节点的权值以及各个节点在电力网络中的位置来选 取“种子”节点( “种子”节点的数目等于需要划分的分区数目) 。“种子”节点的 选取至关重要，首先它决定了电力网络需要划分的分区数目，同时它还对划分结 果的质量有着至关重要的作用。中小规模电力网络的“种子”节点的选取主要是 依据经验，而对于大规模电力网络的“种子”节点的选取则需要反复的实验。 ( 3 ) 根据已经选取的“种子”节点、各个节点的权值以及节点的连接关系进 行聚合和划分，逐步形成块对角加边形式( b b d f ) 或者近似对角块形式( n b d f ) 的 电力网络划分形式。 由上可见，基于主节点选择的划分策略概念非常清楚，但是“种子”节点的 选取至关重要，高出线度的选取方案并不一定能够解释网络的分区特性，算法的 实用性不是很强。 2 2 2 基于模拟退火原理的暂态稳定空间并行任务划分算法 1 9 9 0 年，有学者利用模拟退火方法进行电力网络的优化划分 5 0 5 。模拟退 天津大学硕士学位论文第二章基于因子路径树的暂态稳定并行任务划分算法 火法是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化 算法。在对固体物质进行退火处理时，常先将它加温使其粒子可以自由运动，以 后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降 足够慢，则固体物质便形成最低能量的基态，优化问题也类似此过程。该算法最 为显著的特征是以一定的概率接受使目标函数数值增大的移动，所以能够从局部 最优解的“陷阱”中爬出来而不会简单地终止于一局部最优解上，即具有全局收 敛性。而在理论上已经证明，只要系统过程满足一定的要求( 系统温度无限趋于 零度且在每一温度下模拟充分) ，则算法将以概率l 逐渐收敛于全局最优解。 该方法首先选择式( 2 1 ) 做为评价划分结果优劣的目标函数，即： 厂= a m 2 + ( 2 1 ) 其中，厂为评价函数，m 等于各个子区域中节点数目最多的区域中的节点数目， 工代表了各个子区域与协调系统之间所联络的支路数目，口和为加权系数，该 目标函数近似反映了并行求解稀疏线性方程组的计算量。其具体步骤如下： ( 1 ) 任意分配每个节点到不同的分区中； ( 2 ) 设定模拟退火过程中初试温度t ； ( 3 ) 设定模拟退火过程中的最大迭代次数； ( 4 ) 依次对每一个节点进行( 5 ) 一( 9 ) 的操作； ( 5 ) 随机选择一个子区域把这个节点归入到该区域当中； ( 6 ) 如果新的划分结果所对应的目标函数值小于原来的值的话，接受这种新 的划分结果； ( 7 ) 如果新的划分结果所对应的目标函数值大于原来的值的话，以 e x p ( - 6 e n 的概率接受这种新的划分结果，c 等于目标函数的增加值； ( 8 ) 否则，拒绝这种划分； ( 9 ) 继续下一个节点，转到( 5 ) ； ( 1 0 ) 降低温度退火温度t ； ( 1 1 ) 继续模拟退火法的下一次迭代； ( 1 2 ) 输出结果。 本文曾经对3 9 节点系统采用过该方法进行电力网络划分，划分结果比较理 想，但是对2 k 节点等大的系统进行划分的时候效果很不理想。其原因主要有： 天津大学硕士学位论文第二章基于因子路径树的暂态稳定并行任务划分算法 ( 1 ) 评价划分结果优劣的目标函数的选择并不一定能够真正的反映实际暂 态稳定任务划分的实质，而且往往与实际相差比较大； ( 2 ) 模拟退火的初试温度的确定、退火方案的选择以及充分搜索的大计算量 都限制了这种方法的发展和应用。 2 2 3 基于分层递归二分法的暂态稳定空问并行任务划分算法嘲 2 2 3 1 基于分层的多重图划分方法概述 对于电力网络的划分，其实质就是图划分问题的一种。一般的图划分问题定 义如下：对于一无向图g = ( v ，e ) ，其中顶点集合v = “，v 2 ，咋) ，边的集合 e s v x v 。现将图g 划分为七个顶点子集丑昱，最，且丑n 昱n n 只= ， 称置b ，e 为图g 的一个k - 划分，要求划分后连于不同顶点子集之间的边数目 最小。 图划分问题是一种n p 难问题，很难通过有限的步骤找到最优解，一般都是 基于各种启发式方法达到较优解。常用的方法【5 3 】有基于地理几何方法，基于谱分 析的方法【5 4 1 ，基于组合技术的图划分技术，和基于分层多重的图划分方法【5 5 1 。 而其中最流行的是基于分层多重的图划分方法。它分为三步：( 1 ) 构造浓缩图( 2 ) 对浓缩图进行划分( 3 ) 分层细化浓缩图并进行局部划分调整，如图2 1 所示。 这种方法的优点在于( 1 ) 对浓缩图进行划分的时候由于图的规模比较小，所 以容易实现较优的划分并且不至于使图划分陷入局部最优的陷井；( 2 ) 由于局部 划分调整的引入，使得最终的划分结果更加合理；( 3 ) 计算时间节省。但这种方 法也有缺点，由于是对浓缩图进行的划分，该方法在各分区划分规模上可能不够 平均。 2 2 3 2 基于分层递归二分法的暂稳并行任务划分算法嘲 最近，文献【5 6 】等人提出了基于分层递归二分法的暂态稳定空间并行任务划 分算法，其具体步骤如下： 天津大学硕士学位论文第二章基于因子路径树的暂态稳定并行任务划分算法 h h n 口p n 图2 - l 基于分层多重的图划分示意图 s t e p l 建立分层分区网络模型 1 1 通过变压器和母联支路网络拓扑分析，补全网络模型中的厂站信息； 1 2 建立大区、省、地区和厂站的双向索引关系，完成总体信息统计； s t e p 2 进行网络浓缩 2 1 根据分区总数确定合理的网络浓缩层次： 2 2 进行网络浓缩； 2 3 根据网络浓缩结果，计算图节点点权f 乃k 和节点关联边权翮； s t e p 3 分层细化浓缩图划分 3 1 采用递归二分法对浓缩图进行划分； 3 2 评估划分结果，如果评价指标大于上次划分结果或达到网络模型底 层，则认为已经达到优化划分，最终划分结果为上一次图划