电力系统潮流并行算法的研究进展

电力系统潮流并行算法的研究进展

清华大学学报(自然科学版)2002年第42卷第9期

CN1122223 N.42,No.9JTsinghuaUniv(Sci&Tech),2002,Vol15 37

119221195,1199

电力系统潮流并行算法的研究进展

薛　巍1,　舒继武2,　王心丰1,　郑纬民2

(1.清华大学电机工程与应用电子技术系,北京100084;2.清华大学计算机科学与技术系,北京100084)

摘　要:随着高性价比可扩展集群并行系统的逐步成熟和应用,大规模电力系统潮流并行计算和分布式仿真成为可能。法,分析了算法中存在的困难。4力系统潮流并行算法:和逆矩阵法,实用效果,,并指出基。关键词:潮流并行算法;大型稀疏线性方程组;电力系统中图分类号:TM744

文章编号:100020054(2002)0921192204

文献标识码:A

,,而高效。随着并行机与并行计算技术的不断发展和成熟,潮流问题的并行计算研究近年来得到了长足的发展,为真正解决大电网快速、详细的仿真计算开辟了新路。

本文主要综述了迄今为止的潮流并行算法研究成果。指出了各种算法的优点和局限性。针对不同并行体系结构特点,提出了潮流并行算法的研究方向。

1　潮流计算模型

Advanceofparallelalgorithmsforpower

flowsimulation

XUEWei1,SHUJiwu2,WANGXinfeng1,ZHENGWeimin2

(1.DepartmentofElectricalEngineering,TsinghuaUniversity,Beijing100084,China;2.DepartmentofComputerScienceandTechnology,

TsinghuaUniversity,Beijing100084,China)

Abstract:Thewideuseofscalableclusterparallelsystems,whichhaveahighperformance2priceratio,hasenabledthepowerflowparallelcomputinganddistributedrealtimesimulationoflargescalepowersystem.Thispaperoutlinedthecomputationalmodelsandthebasicalgorithmsofpowerflowcomputation,andanalyzedthemaindifficultiesinthealgorithms.Then,startingfromthebasicprinciplesandpracticaleffectsofthealgorithms,itpresentedtheresearchprogressofparallelpowerflowalgorithmsbasedonpartitioning,

multiple

factoring,

sparse

vectors

and

inverse

matrices.Finally,comparingtheadvantagesandlimitationsoftheseparallelalgorithms,promisingmethod.

Keywords:powerflowparallelalgorithm;large2scalesparselinear

systemequations

thecoarsegranularitydomaindecomposed

powerflowparallelalgorithmonclusterparallelsystemsisthemost

电力系统潮流计算描述的是电网稳定状态的特

性。从数学角度来讲,它可以归结为求解一组非线性方程,并使其解答满足一定的约束条件。对于节点数为N,PV节点数为r的网络,各节点有两个状态变

),其极坐标形式表示的潮流方程为:量(U,Η

f

Pi

=Pis-Ui

∑U

j∈i

j

(GijcosΗij+B(GijsinΗBij-

ij

sinΗij)=0,cosΗ.ij)=0

(1)

fQi=Qis-Ui

∑U

j∈i

jij

其中:fPi,fQi分别表示节点有功潮流方程(N-1

个)和无功潮流方程(N-r-1个);Pis表示各节点的有功注入量;Qis表示PQ节点的无功注入量;Ui,Uj表示节点i和j的电压幅值;Ηij表示节点i和j的相角差;另外第N个节点作为系统的松弛节点,用以平衡全系统功率。

有关潮流方程的计算方法很多。以导纳阵为基础的Guass迭代法,原理简单,内存需求少,但算法收敛性差;以阻抗矩阵为基础的迭代法收敛性有所

收稿日期:2000212229

潮流计算是电力系统规划、运行的基本研究方法。随着现代电力系统大系统、强非线性与多元件的特点日益突出,其计算量与计算复杂度急剧增加。如

基金项目:国家自然科学基金资助项目(69933020)作者简介:薛巍(19742),男(汉),北京,博士研究生。

E2mail:xw98@

电力系统潮流并行算法的研究进展

薛　巍,等:　电力系统潮流并行算法的研究进展1193

提高,但矩阵存储内存需求量大,限制了解题规模;如今,最基本、最实用的潮流求解方法是结合了稀疏矩阵技术的Newton2Raphson法(以下简称牛拉法)以及PQ分解法。

牛拉法极坐标形式的迭代方程为:

-1

f

p9Η

9U

(2)=-.

f U

9Η9U

由式(1)(2),牛拉法可归结为结构对称的大型稀疏线性方程组的求解问题,即

(3)Ax=b,其中系数矩阵A为高维、阵,向量x为待求的解,向量b。

牛i成和分解。,对初值要求较高,。

为提高计算速度,PQ分解法忽略了电压幅值对有功功率及电压相角对无功功率的影响,将Jacobi矩阵简化为稀疏对称常数阵。相应的潮流问题也转化成为对称稀疏线性方程组的求解。在迭代过程中,PQ分解法只需形成一次Jacobi矩阵,大大提高了计算速度,拉法稍慢。

对于电力系统具有杂散稀疏结构的线性方程组,一般采用直接法结合稀疏矩阵技术进行求解。整个计算过程可分为LU分解、前代回代两部分,其方法为:对矩阵A进行三角因子分解,则原方程式(3)可转化为LDUx=b,其中L为单位下三角矩阵、D为对角矩阵、U为上三角矩阵。再分别令y=DUx,z=Ux,可得前代和回代计算公式分别为:

(4)Ly=b,　Ux=z.

为了减少分解过程中产生的注入元,计算中还引入了节点排序策略。Alvarado对电力系统的矩阵计算进行大量分析后,总结得出:在采用半动态节点优化策略的基础上,LU分解的计算量与N1.4成正比,前代回代计算量与N1.2成正比[1],其中N为系统的节点规模。

由于PQ分解法中节点排序只进行一次,LU分解也只在系统结构改变时才进行修正或重新计算,所以实际潮流计算中重复运算最多的还是前代回代部分。因此,现有的文献中对前代回代并行算法的研究较多。

处理机中执行,或将现实的多维问题映射到具有特定拓扑结构的多处理机上求解,以大大提高计算速度。长期以来,研究人员一直致力于寻求更适合电力系统特点的潮流并行算法,希望能开发出具有最大的并行性而各任务之间的数据相关性最小的方法。

如上所述,电力系统潮流计算问题通常演化为求解一组稀疏线性代数方程。因此,潮流并行算法的,根据其实现方案的不同,:分块法、多重G.Kron,其将表征电力系统网A分为通过协调部分互联的多个子矩阵,各子矩阵可独立求解,从而开发潮流求解的并行性。而潮流并行计算的多重因子化法、稀疏矢量法和逆矩阵法都是从线性方程组的因子分解和前代回代过程入手来实现其并行化。2.1　基于分块法的潮流并行算法

A.Torralba于1992年提出电力系统潮流的分

块并行算法[2]。其基本思想是通过合理的节点排序策略,将系统的系数矩阵转化为对角加边形式(BBDF):

A1

A1,n+1

x1

b1

ω

An

An+1,1

An,n+1An+1

xnxn+=

bnbn+.

…An+1,n

(5)

其中:A1～An为n个子系统的系数矩阵,An+1为协调系统系数矩阵,n一般与并行机结点数相同。

这样,稀疏线性方程组的计算转换为子系统和协调系统计算两部分,各子系统方程可并行求解。

由上可见,基于分块法的潮流并行算法物理意义明确,程序实现简单,适合于在计算结点数较少,分布存储的并行机上实现。但如何有效地将系数矩阵转化为各子系统计算量平衡的对角加边形式是本算法的难点。

Vale在分块法的基础上对网络方程求解的并

行算法进行了研究[3],着重讨论了如何通过对“种子”节点的选取和系统节点的重新排序,将稀疏矩阵转化为具有固定节点数的块对角加边形式(BBDF)或近似块对角形式(NBDF),以便于分块并行求解。2.2　基于多重因子化的潮流并行算法

2　潮流并行算法的研究进展

从本质上讲,并行计算就是将多任务映射到多

为进一步在潮流线性方程组求解中增大并行

电力系统潮流并行算法的研究进展

1194

清华大学学报(自然科学版)2002,42(9)

度,文[4]提出了多重因子化的概念,对原有的L U矩阵进行连续变换得到:

I

K

OI

L11

LDU11

UIO

RI

x=b.(6)

进行LU分解比采用分层法具有更大的优越性。然而,若其Hypercube结构的维数加大,则结点间数据通信时间将急剧增大,引起加速比趋于饱和。在分层法的基础上,M.Montagna针对向量处理中的循环问题,采用“锁”机制,进一步提出了稀疏矩阵计算的细粒度DLA(DynamicLevelwise

[7]

Algorithm)算法。在Cray向量计算机上,该算法

由上式可见,矩阵计算中上、下部分矩阵的依存关系被削弱了,增加了并行求解的可能性,但同时也增加了计算中的串行步数,文[4]中还提出了面向计算结点数的任务分配方案。该方法用于1723节点的系统,在16CPU的共享内存机Symmetry上得到了7.48的加速比[4]。

2.3　基于稀疏矢量技术的潮流并行算法

曾用于求解节点规模为11670,与上面的分,50%,LU,。

4(W矩阵法)

传统的因子分解和前代、,进行并行求解。出,。这种方,然后找出,以便区分计算操作中的可并行部分。

一些研究者致力于通过适当的排序算法,减少因子表路径深度,目的是在分解和前代、回代的计算中尽量增大并行计算量,并保持原有的稀疏性。J.

回Q.Wu仔细分析了稀疏矩阵在因子分解和前代、

代过程中各个元素的计算关系,并对其进行了重新划分与组合,最大程度地揭示了因子分解和前代回代过程中的“指令级”并行性[5]。该想法应用于牛2拉法潮流计算,在20个处理器的共享内存机

[5]

Symmetry上曾获得高达13的加速比。

为了增加算法的计算粒度,u在32结点分布存储的iPSC 2型并行处理机上进行了研究[6],提出了两种粗粒度的因子路径并行算法,分别称为分层法和链路因子表路径法。前者是并行消去同层因子表路径树中的节点,上层消完后,继续下一层,依次进行。后者是在分层法的数据结构中引入相应的一些特征项(如数据链指针等),对因子树重新划分,可以同时进行多层元素的消去。分层法和链路因子表法示意如图1。文[6]还对这两种方法作了比较,研究表明,在iPSC 2上采用链路因子表路径法

部分研究者致力于将前代回代过程中难于并行的依赖关系转化为易于并行的矩阵-向量乘法计算。Betancourt研究了因子图与其逆矩阵稀疏部分

的关系[8],建立了所谓的非循环有向图(DirectedAcyclicGraph),并得出在处理器数足够的情况下,

全逆矩阵与稀疏逆矩阵有相同并行计算时间的结论。

这个观点进一步发展,Alvarado基于稀疏矢量法的基本思想,提出了W矩阵法[9]。对于对称A阵,式(4)的前代、回代部分可表示为:

y=Wb,z=D

-1T

y,(7)

x=Wz.

其中:W=L-1,且W=Wn…W2W1。

可见,式(7)的矩阵2向量乘法易于并行求解,其分解的数量与串行求解的步数相关。如果将W矩阵分解为n个矩阵相乘,则前代、回代过程的串行步数将大大增加至2n步,使W矩阵方法变得毫无意义;而聚合为一个矩阵又会在原有的稀疏结构中引入较多的附加注入元,增大计算量。由此可见,不同的分区方法大大影响W矩阵法的计算效率。文[9]还研究了节点排序对W矩阵稀疏性的影响,同时希望通过增加分区数量限制注入元的引入。

1990年,Enns对W矩阵方法进一步探讨[10],

提出一种最小化W矩阵非零元的节点排序策略,与限定新增注入元的分区方法相结合,会取得较高的计算效率。值得关注的是,不同的节点排序算法在降低W矩阵注入元的同时,会在原有的L U矩阵中引入更多的注入元,好的算法应该对这两方面兼顾[11]。Gomez在快速解耦潮流的并行算法研究中,引入“非显著节点(IndistinguishableNodes)”的概

图1　分层法与链路因子表法示意图

电力系统潮流并行算法的研究进展

薛　巍,等:　电力系统潮流并行算法的研究进展1195

念[12],与因子图相结合对节点进行重新排序分区,其目的是消除W矩阵的注入元。

在W矩阵方法的具体实现中,A.Padilha采用了按照不同因子树深度进行分区的方法和按行的任务分配方案,并采用“卷帘法(Roll)”进行矩阵并行计算[13]。在8CPU的多处理器并行机上对该算法进行评测,1729节点系统计算加速比达到5.95。Huang则进一步研究了W矩阵的存储方法及相应的矩阵运算算法的实现[14]。

为同时利用稀疏矢量法和W矩阵方法的优势,

[15]

A.Morelato研究了两者的结合,即在因子树的顶部采用并行前代回代计算,减少由于W注入元引入而增加的计算量;随着L U零元的大量增加,W求逆方法,系;量的和,。此算法在8CPU多处理机系

[15]

统上进行实现,IEEE118系统计算加速比为4.49。

无论是直接并行方法还是W矩阵方法,最初都较少考虑电力系统的稀疏特性所导致的短向量问题。G.P.Granelli首先在W矩阵法中引入“伪列(pseudocolumns)”的想法[16],将W矩阵中同一分区中互不相关的操作进行组合,大大增加了向量处理的效率。Aykanat进一步对“伪列”的存储方案进行了研究[17]。Vuong[18]与R.Basso[19]在稀疏矢量法的前代回代并行算法中提出了类似的概念,并讨论了其相对“伪列”的优势:更长的向量特性。

目前,国内也已开始潮流并行算法的研究。文[20]提出了基于分解叠加原理的逆矩阵求解方法,该方法面向电力系统的支路,采用Scherman2Morrison2Woodbery矩阵公式:

-[Y0+MlDMll]

T

1

2)稀疏矢量直接法和W矩阵方法是潮流稀疏

线性方程组并行计算的主流。它们各有其优势和不

足:稀疏矢量法,能够保持因子表的稀疏性,但操作间依赖关系较强;W矩阵法并行性较好,但逆矩阵的使用大大增加了矩阵中的非零元,增加了计算量。因此,要想提高潮流问题求解的并行效率还在于把稀疏矢量直接法和W矩阵方法结合起来[15];

3)稀疏矢量直接法和W细粒度的并行算法,、共享存储其算法实现效70%;

,基于分布式并行系统的潮流并行计算研究较少。近年来集群系统是实现并行计算的一种新主流技术,随着高性能价格比的可扩展集群式计算机研究的逐步成熟及应用,为更多的科研人员进行电力系统潮流并行计算的研究提供了物质基础,基于集群系统的大规模电力系统潮流并行计算和分布式仿真已成为可能。另外,由于电力系统特有的分层分区特性,采用区域分解方法可开发出高效的粗粒度潮流并行算法。因此基于集群系统潮流计算的并行算法研究与实现将最具发展潜力,这将是今后进一步的研究方向。

参考文献　(References)

[1]

putationalcomplexityinpowersystems[J].IEEETransonPAS,1976,PAS-95(4):10281037.

[2]

TorralbaA,GomezA.

Threemethodsfortheparallel

solutionofalarge,sparsesystemoflinearequationsbymultiprocessors[J].IntJEnergySystems,1992,12(1):1

5.

[3]ValeMHM,FalcaoDM,KaszkurewiczE.Electricalpower

=

-1

T

-10

Y

-10

-YMl(Dl

-10

-1

+MlYMl)MlY,

T

-10

networkdecompositionforparallelcomputations[A].IEEE

(8)

[4]

ProceedingsoftheIEEESymposiumonCircuitsandSystems[C].NewYork:IEEE,1992.2761algebraicequations[J].19(2):743[5]

749.

2764.

1994,

Shyan2LungLin,JEVanNess.Parallelsolutionofsparse

IEEETransonPWRS,

完成阻抗阵的求解,并在4个Transputer处理器系

统上进行了算法实现,效率可达67.5%[20]。

3　结　论

本文主要论述了分块法、多重因子化法、稀疏矢量法和逆矩阵法4种典型潮流并行算法的基本原理和实用效果,介绍了潮流并行算法的一些最新研究进展,可得出如下结论:

1)如今潮流并行算法的设计和实现主要集中在稀疏线性方程组的并行求解上,而直接从潮流非线性方程本身出发的并行算法研究相对较少;

JunQiangWu,AnjanBose.Parallelsolutionoflargesparsematrixequationsandparallelpowerflow[J].IEEETrans

onPWRS,1995,10(3):1343

1349.

[6]KawahLau,DanielJTylavsky,AnjanBose.Coarsegrainschedulinginparalleltriangularfactorizationandsolutionofpowersystemmatrices[J].IEEETransonPWRS,1991,6(2):708

714.

(下转第1199页)

电力系统潮流并行算法的研究进展

黄益庄,等:　提高工频电流电压基波计算精度的Fourier均值算法1199

3　计算时间分析

相对于普通的FFT算法,相位补偿均值算法所增加的计算量在于:增加了对超前1 4个数据窗口周期的数据所进行的FFT计算。如果测量装置是进行连续采样和计算,由于领先的数据窗口的FFT计算结果可以使用历史数据,因此实际上在这方面并没有增加任何计算量。其他的计算量主要增加在式(13)中进行相位补偿所涉及的计算。包括求两个数据窗口的基波向量相位差的一次复数除法以及作相位补偿计算时的一次复数乘法,所以增加的计算量是非常有限的,完全可以满足现有的微机监控、保护和自控装置的实时性要求。

(上接第1195页)

[7]MontagnaM,GranelliGP.Levelwisealgorithmsforvector

processingofsparsepowersystemmatrices[J].IEEETrans

onPWRS,1996,11(1):239

245.

[8]RamonBetancourt,FernandoLAlvarado.Parallelinversionofsparsematrices[J].IEEETransonPWRS,1986,1(1):74

81.

IEEE

TransOn

[9]FernandoLAlvarado,DavidCYu,RamonBetancourt.PartitionedsparseA21methodsPWRS,1990,5(2):452

.

[10]MarkKLAlvarado.

].ETransonPWRS,5(2:466

]Bose.Anewsuccessiverelaxation

efortheW2matrixsolutionmethodonasharedmemoryparallelcomputer[J].1996,11(1):233

238.

Implementationofthe

IEEE

IEEETransonPWRS,

4　结　论

MVR2III微机电压。该系统已经广泛应用于国内数十个不同电压等级的变电站。大量的现场运行数据和经电力工业部电力设备及仪表质量检验测试中心检测结果表明,在不同的电网运行方式和潮流情况下,此算法都可以快速准确地获得高精度的电压电流信号测量值,即使系统频率偏移达±2Hz,均值算法均能保证基波幅值计算结果的误差小于0.5%,相角计算结果的误差小于2.5%。

参考文献　(References)

[1]

[12]AntonioGomez,RamonBetancourt.

TransonPWRS,1990,5(3):977

fastdecoupledloadflowonavectorcomputer[J].

983.

on

[13]PadilhaA,MorelatoA.

solving1029.

sparse

network

AW2matrixmethodologyforequations

multiprocessor

computers[J].IEEETransonPWRS,1992,7(3):1023[14]HuangHS,LuCN.Efficientstorageschemeandalgorithms

forW2matrixvectormultiplicationonvectorcomputers[J].

IEEETransonPWRS,1994,9(2):1083

1091.

[15]MorelatoA,AmanoA,biningdirectand

inversefactorsforsolvingsparsenetworkequationsinparallel[J].1948.

[16]GranelliGP,MontagnaM.PasiniGL,MaranninoP.A

W2matrixbasedfastdecoupledloadflowforcontingencystudiesonvectorcomputers[J].1993,8(3):946

953.

Algorithmsforefficient

[17]CevdetAykanat,NezihGuven.

IEEETransonPWRS,

IEEETransonPWRS,1994,9(4):1942

张伏生,耿中行,葛耀中.电力系统谐波分析的高精度FFT

算法[J].中国电机工程学报,1999,19(3):6367.

ZHANGFusheng,GENGZhongxing,GEYaozhong.HighaccuracyFFT2basedmeasurementofharmonicanalysisinpowersystem[J].ChineseSocietyforElectricalEng,1999,19(3):63

67.(inChinese)

IEEETransactionon

vectorizationofrepeatedsparsepowersystemnetworkcomputations[J].IEEETransonPWRS,1995,10(1):448

456.

of

sparsematrix

forward backward

[18]VuongGT,ChahineR.Dependency2basedalgorithmsfor

vectorprocessing205.

[19]AlessandroRBasso,CarlosRMinussi,AntonioPadilha.

Fast2forward fast2backward1374.

[20]汪芳宗.电力系统并行计算[M].北京:中国电力出版社,

1998.

WANGfangzong.PowerSystemParallelComputing[M].Beijing:Chinese)

ChinaPowerPublishingCompany,

1998.

(in

substitutions

on

vector

substitutions[J].IEEETransonPWRS,1996,11(1):198

[2]NarduzziC,OffelliC.Real2timehighaccuracymeasurement

ofmultifrequencywaveforms[J].[3]

GrandkeT.32:350

355.

Somewindowswithverygoodsidelobe

91.

InstrumentMeasurement,1987,IM-36(4):964

970.

InterploationalgorithmsfordiscreateFourier

transformsofweightedsignals[J].IEEETransTM,1983,[4]NuttallAH.

behavior[J].IEEETransactionsonAcoustics,Speech,and

SignalProcessing,1981,ASSP-29(1):84

computers[J].IEEETransonPWRS,1999,14(4):1369

[5]

丁仁杰.电力系统同步相量动态测量技术的研究和实现

[D].北京:清华大学博士论文,1995.

DING

Renjie.

Technology

on

Synchronized

Phasor

MeasurementsinPowerSystem[D].University,1995.(inChinese)

Beijing:Tsinghua

本文来源：https://www.bwwdw.com/article/rak4.html