基于MPI的电力系统潮流的并行算法研究及其实现.pdf

总第 4 8卷第 5 4 8期 2 0 1 1年第 8期 电测与仪表 El e c t r i c a l M e a s ur e me n t& I n s t r ume n t at i on VO I 4 8 N0 5 4 8 Au g 2 0 1 1 基于MP I 的电力系统潮流的并行算法研究及其实现 刘耀年 ， 艾 吕泽 ， 禹冰 ， 于晶 ， 张伟 民。 ( 1 东北电力大学 电气工程学院 吉林 吉林 1 3 2 0 1 2 ； 2 河南省电力公司洛阳供电公司， 河南 洛阳 4 7 0 1 2 3 ； 3 云南电网公司电力教 育中心， 昆明 6 5 0 2 0 4 ) 摘要 ： 提出了一种不受进程个数限定的电力系统潮流并行算法 ， 算法按机器的个数划分进程 ， 并用等间隔跳跃 与指定相结合的方式将系数矩阵的各行分配给各个进程， 最后利用并行消息传递接口M P I 在计算机机群上实现 了该算法。计算结果表明， 对于规模较大的电力系统， 该算法能有效地提高潮流计算速度。 关键词 ： 潮流并行算法 ； 进程数 ； MP I ； 三角分解 中图分类号 ： T M7 4 4 文献标识码 ： A 文章编号： 1 0 0 1 1 3 9 0 ( 2 0 1 1 ) 0 8 0 0 5 9 0 4 An a l y s i s o f Po we r S y s t e m Ti d e P a r a l l e l Al g o r i t h m Ba s e d o n M P I L I U Ya o - n i a n ， AI L v z e ， YU B i n g ， Yu J i n g ， Z HANG w e i mi n 。 ( 1 E l e c t ri c E n g i n e e r i n g D e p a r t m e n t ， N o r t h e a s t D i a n l i U n i v e r s i t y ， J i l i n 1 3 2 0 1 2 ， J i l i n ， C h i n a 2 L u o y a n g P o we r S u p p l y C o mp a n y ， L u o y a n g 4 7 0 1 2 3 ， He n a n ， Ch i n a 3 P o we r E d u c a t i o n Ce n t e r o f Yu n n a n P o we r Gr i d C o r p o r a t i o n ， K u n mi n g 6 5 0 2 0 4 ， C h i n a ) Ab s t r a c t ：A p o w e r s y s t e m t i d e p a r a l l e l a l g o r i t h m wh i c h u n c o n t a mi n a t e d b y t h e n u mb e r o f p r o c e s s e s i s i n t r o d u c e d T h e p r o c e s s o f t h i s me t h o d i s d i v i d e d b y t h e c o mp u t e r n u mb e r T h e n t h e l i n e s o f f i x e d e q u a t i o n c o e f f i c i e n t ma t r i x a r e p u t i n t o e v e r y p r o c e s s b a s e d o n t h e p ri n c i p l e o f c o m b i n i n g e q u a l l y s p a c e d j u m p i n g a n d a s s i g n m e n t A t l a s t ， t h i s a l g o r i t h m i s r e a l i z e d i n c o mp u t e r fl e e t b y t h e Me s s a g e P a s s i n g I n t e r f a c e T h e c a l c u l a t i o n r e s u l t s s h o w t h a t t h e a l g o r i t h m c a n i mp r o v e t h e fl o w c a l c u l a t i o n s p e e d i n t h e l a r g e s c a l e p o w e r s y s t e m Ke y wo r d s ： s y s t e m t i d e p a r a l l e l a l g o rit h m， p r o c e s s n u mb e r ， MP I ， t r i a n g u l a r f a c t o r i z a t i o n 0 引 言 决了因导纳矩阵维数不能被进程数整除而难以并行 现代电力系统已经发展成一个全新 的电力 网络 ， 的问题。 不但容量大 、 规模大 、 区域跨度大 ， 而且结构复杂电压 1 P Q分解法的潮流计算模型 等级高。对于电力系统的潮流计算而言， 要对如此之 电力系统潮流计算是用来描述电网稳定状态特 多的数据 自如地进行实时分析， 传统的串行计算方法 性的， 它是根据给定的运行条件， 确定系统的电压及 已经无法实现， 这就使得潮流并行算法同与之相对应 功率。从数学的角度讲， 这个过程就是在满足特定约 的并行软件的开发， 对规模较大的电力系统的仿真计 束条件的前提下， 求解一组非线性方程。 算起到关键性作用 1 。 对 于一个有n 个节点的电力系统 ， 假定其P Q 节点 基于分块思想2 1的潮流并行算法是将表征电力系 编号为从1 到m； P V 节点编号为从 + 1 ) 到( 一 1 ) ， 平衡 统网络特性的系数矩阵A ， 分成通过协调部分互联的 节点的编号为 。 由每个P v 或P Q 节点都能够列写出一 多个子矩阵 ， 各个子矩 阵都能够独立求解 ， 进而对潮 个有功功率 的不平衡方程 ： 流求解并行性进行研究。潮流并行计算的逆矩阵法、 稀疏矢量法和多重 因子化法均是以线性方程组 的前 代回代和因子分解过程为切人点实现并行的3 。 本文在研究潮流串行算法的基础上， 提出了一种 不受进程数限定的电力系统潮流并行算法。 该算法解 一 U G q c o s S o + B j s i n S i9a 8 = 8 c o s 6 0 + B s i n S i9 ( 1 ) 一 二 ( 1 ) 同时对每个P Q 节点又能够再列写出一个无功功 率的不平衡量方程： 59 学兔兔 w w w .x u e t u t u .c o m 总第 4 8卷第 5 4 8期 2 0 1 1年第 8期 电测与仪表 El e c t r i c a l M e a s u r e m e n t& I n s t r u m e nt a t i o n VoI 4 8 No 5 4 8 Au g 2 0 1 1 A Q i= Q i- s i B 晦) ( 2 ) P - Q 分解法在表示节点 的电压 时所采用 的方式 是极坐标形式， 其数学模型是在合理简化了牛顿法潮 流计算数学模 型的基础上得来 的， 由此得来的修正方 程展开可得 ： P， P A Q Bl 1 B1 2 B1 l m B 一1 1 B 一1 2 B 一1 ， 1 Bl 1 B1 2 1 B2 l B2 2 B2 B 1 B 2 B Ul A6 1 一 ， f ( 3 ) ( 4 ) 根据公式( 1 ) 和( 2 ) 来算出节点功率不平衡量 ， 并 由修正方程(3 ) 和( 4 ) 求解得出修正量， 再以下述条件 对其进行约束： 1 m a x I k l m a x f Q f ( 5 ) 2 并行算法与消息传递接 口MP I 2 1 潮流的高斯 消去并行算法 潮流的并行算法所研究的内容主要是如何并行 求解稀疏线性方程组 ，基于机群求解线性方程组的方 法 ， 主要是在线性方程组求解方法的基础上改造而来 。 高斯消去法是利用主行对其余各行作初等行变 换 ， 对系数矩阵A 按行交叉划分。设处理器个数为p ， 矩 I 4 的阶数为n ， m ： n p ，对矩阵A 行交叉划分后， 编 号为i( i = 0 1一 ， p 1 ) 的处理器含有A 的第 ， ， (m l 行租向量B 的第 ， i + p ， ， + ( m 一 1 )p 共有m 个元素。 消去过程的并行算法， 是由各处理器轮流选出主 行， 然后将主行广播给所有处理器 ， 各处理器利用接 收到的主行元素对其部分行向量做行变换。 在消去计 算中， 首先对主行元素作归一化操作 ： a k =a J a k ， b = 一 6 0 6 。若以编号l为 的处理器的第i 行作为主行 ， 并将 它播送给所有的处理器。 则编号在 前面的处理器( 包 括 本身) 利用主行对其第i + 1 ， ， m 一 1 行数据和子向 量日 做行变换。 编号在 后面的处理器利用主行对其第 i， ， m 一 1 行数据和子向量 做行变换。 回代过程的并 行是按 ， ， 的顺序由各处理器依次计算x ( i x p + j ) ， 一旦 ( ) 被计算 出来就立即广播给所有处理 器， 用于与对应项相乘并做求和计算 。 在主进程进行数据发送之前， 需求得每个处理器 应分得 的数据 的行数 ， 也就是执行m= U p， 当其余 数 不为0 时 ， 即矩阵的阶数不能被处理器整除时 ， 执行m 加1 操作 ， 此时的mx p 大于矩 阵的阶数。由于每个处 理器分得m 行数据， 必然有m x p N 个进程等待主进程 发送实际不存在的数据 ， 死锁因此而产生。实际上 电 网中某条线路的关闭或开启都会导致电网结构的变 化从而使导纳矩阵发生变化 ， 而导纳矩阵的变化直接 影响修正方程式方程组的阶数。 这种对 于矩阵的阶数 只能被处理器整 除的情况 ， 具有很 大的局限性 ， 既浪 费计算机资源， 也不可能达到计算机速度与进程数的 最佳匹配 。 2 2 并行潮流算法的并行性能 对一个规模是n 的问题 ， 算法运行时间用 表示 ， 它是 ( 俞 入的问题规模) 的函数。 加速比5 。 与效率E 是传统并行算法的评价标准 ， 能体现出并行算法应用于并行机上解决实际问题时 所得到的好处 。 ( 6) 式中 是最优的串行算法运行在单机上的时间； 是 并行算法在p 台处理机上计算所需要的时间。 并行算法效率定义是 ： E 毒 (7 ) E 反映的是处理器在并行系统 中的运用情况 ， 0 E p 1。 2 3 消息传递接 口MP I MP I ( Me s s a g e P a s s i n g I n t e r f a c e MP I ) 为消息传递 接 口的简称 ， 它是一种传递消息的编程模型 ， 目前的 应用很广泛， 它定义了一个实现消息传递模型标准的 程序库， 并且它的接口能够被C C + + 与F O R T R A N 语言 方便地调用c 7 l。M P I 要求把任务分解为许多子任务， 启 一 一 一 ： 学兔兔 w w w .x u e t u t u .c o m 总第 4 8卷第 5 4 8期 2 0 1 1年第 8期 电测与仪表 El e c t r i c al M e a s u r e m e nt& I n s t r um e n t a t i o n VO l 。 4 8 N0 5 4 8 Aug 2 01 1 动许多进程并行执行任务 ， 各进程不可以直接对其他 进程的数据进行访问， 各个进程之间要 由消息传递实 现数据交换 。 3 不受进程个数 限定的潮流并行算法 本文提出的不受进程个数限定的潮流并行算法 ， 首先 由主进程读取并处理数据 ， 计算 出导纳矩阵并且 形成有功和无功迭代的简化可 比矩阵B 和B ， 然后对 B 和B ，矩阵进行三角分解。 主进程通过读取各节点 初始电压， 进而计算各节点最大功率误差 ， 再由各进 程一起并行求解修正方程并修正电压的幅值和相角。 潮流并行计算程序流程如 图1 所示。 主进程读取并处理原始数据 主进程形成导纳矩 阵BI和B” 主进程读取各节点电压初值 主进程计算各节点功率误差 N、 Y KG ( KQ O) = I 并行求解修正方程式 并修正各值 ( D K G M ( K O 。 0 ) ) = 0 、 图1 潮流并行计算程序流程 图 F i g 1 F l o wc h a r t o f t i d e p a r a l l e l c o mp u t i n g p r o g r a m ( a 1 主程序执行 ( b ) 子程序执行 图2避免死锁的程序流程 图 F i g 2 F l o w c h a r t o f a v o i d d e a d l o c k p r o g r a m 4 仿真结果分析 一 本文分别以I E E E 3 0 和I E E E l l 8 和I E E E 3 0 0 母线标 准测试 系统为例 ，利用C 语言编制 了基于MP I 的并行 潮流计算程序 ， 分别在2 台、 3 台、 4 台和5 台机器上同时 并行计算， 经仿真实验得其各自的运行时间 、 并行 为解决因导纳矩阵维数不能被进程数整除而难D n t L s 和并行执行效率 结果如表1 所示。 以并行的问题， 本文按机器的个数划分进程， 并用等 表1 并行潮流计算性能分析 间隔跳跃与指定相结合的方式将系数矩阵的各行分 T a b 1 T h e p e r f o r m a n c e a n a ly s i s o f p a r a l l e l f l o w c a l c u l a t io n 配给各进程。 主进程先用等间隔跳跃的方式将矩阵的 数据依次分给P 个进程，再用指定的方式将矩阵的最 后一行发送给剩余的mx p 一 个进程 ( P 为进程总数 ， 为矩阵的阶数 ) ， 使得每个进程恰好分得m行数据 ， 由 此避免了主进程发送数据和子进程接收数据之间由 于不同步而产生 的死锁。 当子进程发送结果给主进程 时 ， 主进程通过判断当前数据的行号在原矩阵中的大 小 ， 来决定接收与否 ， 从而避免 了增补 的数据参加计 算。避免死锁的程序设计流程如图2 所示。 I EEE3 0 0 ( ) 4 1 7 ( 】3 3 3 3 2 5 6 1 2 2 3 0 节 点 s p 1 6 0 3 2 0 0 7 2 6 1 O 2 9 9 7 ! Q ： ： ! 箜： 垄 一 6 1 学兔兔 w w w .x u e t u t u .c o m 总第 4 8卷第 5 4 8期 2 0 1 1 年第 8期 电测与仪表 El e c t r i c a l M e a s ur e m e nt& I n s t r u m e n t a t i o n VO 1 4 8 NO 5 4 8 Au g 2 0 1 1 仿真结果表明 ： 当系统规模不变增加处理器个数 时， 计算速度因进程间通信开销增加而下降； 当处理 器数 目相对不变时 ， 并行执行效率与并行加速 比均随 计算规模的增加而增加， 即问题规模越大 ， 并行优势 越显著。 5 结束语 通过对潮流算法的深人研究， 提出了等间隔跳跃 与指定 相结合 的方法将 系数矩阵的各行分配给各进 程， 在保证各进程问通信同步的前提下， 解除了进程 数必须被导纳矩阵维数整除的限定 ， 从而使得算法具 有更广泛的应用 。算法可行性强 ， 适合于大系统 的计 算机机群并行运算， 仿真试验也证明了该算法的有效 性 参 考 文 献 f l 】 谷源 基于M P 1 的电力系统潮流并行计算实现 D 】 硕士论文 西安： 电 子科技大学2 0 0 5 5 2 】 T o alb a A ， G o m e z A T h r e e me t h o d s f o r t h e p a r a l l e l s o l u t i o n o f a l a r g e ， s p ars e s y s t e m o f l i n e a r e q u a t i o n s b y m u h ip r o c e s s o r s J I n t J E n e r g y S y s t e ms ， 1 9 9 2 ， 1 ( 2 ) ： 1 - 5 3 V a l e M H_ M，F alc a o D M，K a s z k u r e w i c z E E l e c t r i c al P o w e r N e t w o r k D e c o m p o s i t i o n f o r P a r al l e l C o m p u t a t i o n s 【 A1 I E E E P r o c e e d i n g s o f t h e 1 EEE S y mp o s i u m o n Ci r c uit s a n d S y s t e ms ，Ne w Yo r k ：I EEE， 1 9 9 2 ： 2 7 61 2 7 6 4 I 4 J u n Q i a n g Wu ，An j a n B o s e P ara l l e l S o l u t i o n o f L arg e S p ars e Ma t r i x E q u a t i o n s and P ara l l e l P o w e r F l o w l J l】 I E E E T r a n s o n P WRS ， 1 9 9 5 ， 1 O ( 3 ) ： l 3 43 1 3 4 9 5 F e n g T u ，F l u e c k ， A J A m e s s a g e - p a s s i n g D i s t r i b u t e d m e m o r y P a r al l e l P o w e r F l o w A l g o r i t h m fJ P o w e r E n g i n e e r i n g S o c i e t y Wi n t e r Me e t i n g ， 2 0 0 2 I E E E ， V o l u me l ， 2 7 3 1 ，J a n 2 0 0 2 ， P age ( s ) ： 2 1 1 - 2 1 6 6 MAb d e l - A k h e r ， K MN o r ，a n d A H A b d u l R a s h i d I m p r o v e d T h r e e P h ase P o w e r F l o w Me t h o d s Us i n g S e q u e n c e C o mp o n e n t s J 1 I E E E T r a n s a c t i o n o n P o w e r S y s t e m， 2 0 0 5 ， 2 O ( 8 ) ： 1 3 8 9 1 3 9 7 7 D o n g a r r a J I n t r odu c t i o n t o MP I J J T h e I n t e r n a t i o n al J o u rnal o f S u p e r c o mp u t e r A p p l i c a t i o n ， 1 9 9 9 ， ( 1 1 ) ： 7 7 - 9 3 8 王锡凡 ， 方 万 良， 杜正 春 现代 电力 系统 分析【 Mj 北 京： 科学 出版社， 2 0 o 3 作者简介： 刘耀年( 1 9 5 1 一 ) ， 男， 辽宁省沈阳人， 教授， 研究方向为配电自动化 、 人 工智能等方 面的研究 。 艾 吕泽 ( 1 9 8 4 一 ) ， 男 ， 吉林省 临江人 ， 硕士研究 生 ， 主要研 究方 向为 电力系统 自动化 。 E ma i l ：a i l v z e a i l v z e C a h o o e n 禹冰( 1 9 8 2 一 ) ， 女 ， 河南省 洛阳人 ， 助 理 工程 师 ， 主要 研究 方 向为电力 系统 自动化 。 于 晶( 1 9 8 5 一 ) ， 女 ， 吉林省 梅河 口人 ， 硕士 研究 生 ， 研 究力 向为电力系统及其自动化。 张伟民( 1 9 7 9 一 ) ， 男， 黑龙江省齐齐哈尔人， 硕= L 研究生， 助理工程师 ， 主要研究方向为电力市场及其运 营 、 配电系 统 自动化 。 收稿 日期 ： 2 0 1 1 0 7 0 2 ( 杨长江编发) ( 上接第 5 2页 ) 计量算法的比对评测等一些方面， 其应用前景值得期 待 。 参 考 文 献 1 江西省电力科学研究院 采算分离式电能表校验方法与电能表现场 参数记录仪【 P J 中华人民共和国： 2 0 1 0 1 0 1 0 8 6 4 7 ， 2 0 1 0 0 2 1 0 2 裴学元 F E E 一 3 型工频基波电子电能表的原理及应用 【 J 电测与仪 表 ， 1 9 9 6 ， 3 3 ( 1 ) ： 3 - 6 3 】 陈向群 电能计量技能考核培训教材 M 北京 ：中国电力出版社， 2 o 0 3 4 】 E ff fi n a Y a n t i H a m i d ， Z e n - I n c h i r o K a wa s a k i Wa v e l e t P a c k e t T r a n s f o r m f o r RMS a n d P o we r Me asu r e me n t P o we r En g i n e e r i n g Re v i e wI EEE， 2 0 0 1 ， 2 l ( 9 ) ： 4 9 - 5 1 【 5 】 粟时平， 王长城， 金维宇 冲击负荷电能计量理论与算法研究 J 电 测与仪表， 2 0 0 4 ， 4 6 6 ( 1 0 ) ： 1 - 4 一 6 2- 收稿 日期 ： 2 0 1 1 - 0 7 0 8 ( 田春雨编发 ) _ l - 学兔兔 w w w .x u e t u t u .c o m