大规模电力系统潮流计算的分布式GESP算法

2010年6月电工技术学报VOL25NO6第25卷第6期TRANSACTIONSOFCHINAELECTROTECHNICALSOCIETYJUN2010大规模电力系统潮流计算的分布式GESP算法谢开贵张怀勋胡博曹侃吴韬（重庆大学输配电装备及系统安全与新技术国家重点实验室重庆400044）摘要并行计算已成为大规模电力系统潮流计算的主要解决手段之一。为取得良好的加速比和并行效率，基于GESP算法提出牛顿法潮流迭代计算中修正方程组求解的分布式算法。根据方程组系数矩阵非零元主要集中于对角带及高度稀疏等特点确定系数矩阵的超节点，并基于超节点的边界将潮流修正方程组的系数矩阵划分为若干个2维分块矩阵以实现分块存储；在LU分解过程中，采用基于流水线技术的并行分解以提高计算速度。本文设计了分布式存储的并行算法，并应用于3000、12000节点等不同规模电力系统。算例分析表明在网络达到2000节点及以上时，本文分布式GESP法相对串行计算和分布式牛顿法具有明显的速度优势。关键词大规模电力系统潮流计算GESP算法分块存储流水线技术分布式计算中图分类号TM744DISTRIBUTEDALGORITHMFORPOWERFLOWOFLARGESCALEPOWERSYSTEMSUSINGTHEGESPTECHNIQUEXIEKAIGUIZHANGHUAIXUNHUBOCAOKANWUTAO（STATEKEYLABORATORYOFPOWERTRANSMISSIONEQUIPMENTSYSTEMSECURITYANDNEWTECHNOLOGY,CHONGQINGUNIVERSITYCHONGQING400044CHINA）ABSTRACTPARALLELCOMPUTINGHASBECOMEAMAINMEANSFORPOWERFLOWCALCULATIONOFLARGESCALEPOWERSYSTEMSINORDERTOOBTAINAGOODPARALLELSPEEDUPANDEFFICIENCY,THISPAPERPRESENTSADISTRIBUTEDALGORITHMFORSOLVINGLINEARPOWERFLOWITERATIONEQUATIONSOFNEWTONAPPROACHUSINGTHEGAUSSIANELIMINATIONWITHSTATICPIVOTINGGESPTECHNIQUEBASEDONTHEPROPERTIESOFCOEFFICIENTMATRIX,SUCHASTHEDIAGONALDOMINANCEANDSPARSITY,THEMATRIXCANBESPLITINTOSEVERALBLOCKSWITHASMALLERDIMENSIONANDBESTOREDINADISTRIBUTEDSTORAGEMODEBASEDONTHEBORDEROFSUPERNODESTHEPIPELINETECHNIQUEISALSOUSEDTOIMPROVETHEEFFICIENCYOFTHEPROPOSEDALGORITHMINTHEPROCESSOFPARALLELLUDECOMPOSITIONADISTRIBUTEDPARALLELALGORITHMFORPOWERFLOWISDESIGNEDANDAPPLIEDTOANUMBEROFPOWERSYSTEMS,SUCHASTHEPOWERSYSTEMSWITH3000AND12000BUSESRESULTSOFCASESTUDIESSHOWTHATTHEMAJORADVANTAGEOFTHEPROPOSEDDISTRIBUTEDGESPMETHODISTHATITHASBETTERPARALLELSPEEDUPANDEFFICIENCYWHENAPOWERSYSTEMHASMORETHAN2000BUSESKEYWORDSLARGESCALEPOWERSYSTEMS,POWERFLOWCALCULATION,GESPALGORITHM,DISTRIBUTEDSTORAGE,PIPELINETECHNIQUE,DISTRIBUTEDCOMPUTING1引言区域大电网互联的运行行为分析以及电力市场环境下实时安全控制和潮流跟踪计算，都迫切需要快速地进行大规模甚至超大规模电力潮流计算1。在潮流计算中，需对形如AXB的高维稀疏线性修正方程进行反复求解，以得到收敛的潮流解。文献2指出在用牛顿法计算电力系统潮流时，超过80的时间用于求解高维修正方程组，而LU分解更占据了大规模电力系统潮流单步迭代的绝大部分国家自然科学基金（50777067），输配电装备及系统安全与新技术国家重点实验室项目（2007DA10512709103）和重庆市自然科学基金重点项目（CSTS2008BC7031）等资助。收稿日期20081015改稿日期2009031690电工技术学报2010年6月时间。在求解超大规模电力系统潮流问题时，已有的潮流算法呈现出计算机内存不足、收敛速度慢等维数灾问题。高性价比可扩展集群并行系统的逐步成熟和应用，使大规模电力系统潮流并行计算和分布式仿真成为可能。采用并行技术处理LU分解和三角方程的求解，已成为大规模电力系统潮流计算的新思路。并行计算的本质是将多任务映射到多处理机中进行处理。电力系统潮流并行计算的主要研究内容正是设计具有较高并行性、较低数据相关性的高效并行算法。现有的潮流并行计算方法主要有3类分解协调计算法、稀疏矢量法、KRYLOV子空间迭代法。分解协调计算法34通过对大规模电力网络进行物理意义上的区域分块，并将各子块通过协调层联系起来。这样便将潮流计算转换为各个子块潮流的并行计算和协调层的计算。但是，对大电网进行合理区域划分的策略和依据，以及对协调层进行平衡计算已成为该算法的难点。稀疏矢量法5需提前判断前代和回代过程中所必需的运算，然后根据运算过程中的因子表路径找出其中可以并行执行的部分。文献6将消去树理论与稀疏向量法相结合使得LU分解过程也具有了可并行性。KRYLOV子空间方法78在潮流计算过程中将高维非线性方程组划分为内、外双层迭代，在求解内层线性化方程组时采用KRYLOV子空间方法并行求解。但是，文献9指出KRYLOV子空间方法的收敛速度和稳定性严重依赖于系数矩阵的条件数和特征值分布，所以必须对其进行恰当的预条件处理才能取得良好的收敛特性。GESP（GAUSSIANELIMINATIONWITHSTATICPIVOTING）算法10已在20世纪末提出，其适用于分布式并行处理大规模稀疏方程组。该算法通过采用静态选主元技术来代替传统稀疏高斯消去过程中的部分选主元技术。文献11指出，GESP算法已在电路仿真、石油工程、流体力学等领域取得了初步的应用，并且在分布式存储的并行计算平台上显示出良好的稳定性。但是到目前为止，GESP算法在电力系统潮流计算中的设计、实现及应用还很鲜见。已有的电力系统潮流并行算法大都基于共享存储的并行计算平台，使得潮流并行计算严重依赖于昂贵的共享存储并行计算机，以至于在实际工程应用中潮流并行计算很难实现。本文在分布式集群环境下，结合电力系统潮流方程固有的稀疏性特点，利用GESP算法对潮流计算中修正的大型稀疏方程组进行并行LU分解以及LU分解后的三角方程进行并行求解。2GESP算法及其在潮流计算中的应用传统牛顿潮流算法将大量非线性方程组转换成线性修正方程组进行反复迭代、串行求解。但是，随着网络规模不断扩大，串行计算面临着越来越严重的维数灾问题。利用潮流问题修正方程系数矩阵固有的超稀疏性，对其进行快速并行求解成为解决问题的新思路。21GESP算法稀疏线性方程组的直接求解常需进行系数矩阵的LU分解。进行矩阵分解时，可能会引入填充元，从而增加了计算复杂性和储存需求。另外，分解过程中的主元为0或者主元的模太小也会导致分解无法进行或者数值不稳定。传统的部分选主元LU分解算法在计算过程中通过对主元进行修正，在保证矩阵的非零元结构情况下取得较高的数值稳定性。但是，部分选主元算法必须动态改变数据的存储结构，由此所采用的细粒度通信模式使其难以在分布式存储的集群系统上并行执行。静态选主元相对于部分选主元的优点在于可以提前决定高斯消去过程中的数据结构和通信模式。基于静态选主元技术的GESP算法在LU数值分解之前对矩阵A进行对称置换和选主元操作，减少了分解过程中非零元的填入，提高了分解过程的并行性。这使得GESP算法可以提前确定填入模式、分布式的数据结构和通信模式，便于对A矩阵进行块状划分的粗粒度的并行计算。设AAIJ为线性方程组AXB的系数矩阵，为收敛容差（可根据实际问题需要选取合适的值），EB、ELB分别表示当前回代误差和最小回代误差。GESP算法11求解大规模稀疏方程组的计算步骤如下（1）通过双向加权匹配算法对A执行行置换，以实现其对角占优。（2）对A进行符号分解并执行列置换，以保证其在分解过程中的稀疏性，同时对A进行静态选主元。（3）因式分解ALU并控制对角元绝对值的大小IF（|AII|1ATHENDOAII1A第25卷第6期谢开贵等大规模电力系统潮流计算的分布式GESP算法91ENDIF（4）用矩阵L和U进行三角求解。如有必要，进行迭代修正ITERATERBAX/稀疏矩阵矢量乘SOLVEAXR/三角求解MAXIBIIREAXB/回代误差IFORBBEE12LBEBREAK/满足精度退出ELSEXXX/对解进行修正EBELBGOTOITERATEENDIF从GESP算法流程可以看出，第2步的静态选主元操作可能使所得解中包含较大的误差，但通过（4）的迭代修正保证了最终解的精度。GESP算法作出这种改进的目的正是为了适应大规模线性方程组分布式存储、求解的需要。22基于GESP算法的牛顿潮流算法牛顿潮流算法的突出优点是算法具有二次方收敛特性，且算法的迭代次数与网络规模基本无关，对某些病态问题也具有较可靠的收敛特性12。但牛顿法每次迭代计算时间过长以及所需的存储量较大，所以很难直接应用于超大规模电力系统潮流求解。由于牛顿潮流修正方程的系数矩阵是一个超稀疏矩阵，且系数矩阵的非零元主要分布于对角带上。如果能够充分利用系数矩阵的稀疏性，进行各块都较小的某种分块划分时，只有少量块中存在非零元素，而其他块中的元素都是0。利用GESP算法对牛顿法潮流的修正方程组进行求解，可以充分利用修正方程系数矩阵的稀疏性，降低计算过程中的存储需求。此外，GESP算法所具有的可并行性，使得对修正方程进行直接并行求解成为可能，从而大大降低了程序所需的计算时间。根据牛顿法潮流计算的步骤，可形成基于GESP算法的牛顿潮流分布式算法的流程，如图1所示。3基于MPI的分布式潮流计算下面将根据潮流修正方程系数矩阵的结构和分布的特点，设计GESP算法的数据结构以及稀疏LU图1GESP算法在牛顿潮流计算中应用FIG1DISTRIBUTEDALGORITHMFORPOWERFLOWUSINGTHEGESPTECHNIQUE分解的分布式处理算法，算法流程如图1所示。本文利用MPI（MESSAGEPASSINGINTERFACE）进行数据通信和进程同步。MPI是目前国内外高性能集群中最广泛使用的并行通信接口，采用消息传递的方式实现并行程序间通信13。在分布式计算过程中数据复制的速度和延迟是影响消息传递效率的关键因素，因而如何减少进程之间的数据交换是提高并行效率的关键。31分布式数据结构的设计如22节所述大规模电力系统牛顿潮流修正方程的系数矩阵为一超稀疏矩阵且非零元主要集中于对角带。由此可见，对系数矩阵的分块存储可以在很大程度上减少存储量与计算量。本文将系数矩阵基于超节点（超节点即是基于L或U阵的非零元结构划分的方阵）12的边界划分为若干个二维分块矩阵。由于系数矩阵的非零元主要集中于对角带上，所以每个超节点中只存在少量的非零元。如果一个NN矩阵里面有M（MN）个超节点，那么该矩阵即被划分为M2个子块。如图2所示图2A为一个由6个处理器节点（即0，1，2，3，4，5）排列成23的2维处理器网格；图2B表示系数矩阵分块划分后，分块存储在由图2A中的处理器网格循环排列成的处理器网格上，即92电工技术学报2010年6月方格中的数字表示该子块对应的处理器编号。图2B中位于系数矩阵对角线上的阴影子块皆为超节点，而其他子块的维数则取决于其所处行块与列块中超节点的维数。基于直接对分块进行存储的思想，系数矩阵的每个子块被看作一个元素存储在2维处理器网格的某个节点上。设PR、PC分别表示2维处理器网格中行、列所含处理节点的个数，则在这种存储方式中，子块AI,J（0I,JM1）将被存储在坐标为（IMODPR,JMODPC）的处理器网格节点上。如图2中，设图2B中A3，5表示A阵中第4行、第6列的子块，则其被存储在图2A中坐标为（1，2）的5号处理器上。图2对应于处理器网格的矩阵分块存储FIG2DISTRIBUTEDSTORAGEMODEFORTHEMATRIXBASEDONTHEPROCESSORGRID对于稀疏矩阵，尽管1维划分更常用且更易于执行，但是采用上述2维分块划分存储方式后，系数矩阵中下三角子块LI,J在分解过程中仅被存储了行块I的那些处理器用到。同样，上三角子块UI,J也仅被存储了列块J的那些处理器用到。由此可见，2维分块存储可以带来更好的负载平衡和更低的通信量，其也更利于算法的升级。32基于流水线技术的并行LU分解在矩阵分块存储中，系数矩阵的每个列块、行块都存储在多个处理器节点上。记PRI、PCJ分别为存储了行块I、列块J的处理器集合。如图2中，PR23,4,5，PC10，3。并行稀疏LU分解算法在各个超节点之间进行迭代分解。其第K步迭代主要由3步组成（1）处理节点列PCK参与列块LKM,K（即列块K中位于超节点下方的所有子块）的因子分解。（2）处理节点行PRK参与分解行块UK,K1K。（3）对所有节点用LK1M,K和UK,K1M进行更新。上述过程中第3步为并行LU分解的主要工作，同时相对于其他两步也具有更大的可并行性。设DIA为当前迭代过程所处理的超节点，并行稀疏LU分解算法的基本流程如下FOR块K1TOMDO1IFDIAPCKTHEN分解列块LKM,K发送LKM,K到对角块所处的节点行中需要它的节点上ELSE从节点列PCK中某个节点接收LKM,KENDIF2IFDIAPRKTHEN分解行块UK,K1M发送UK,K1M到对角块所处的节点列中需要它的节点上ELSE从节点行PRK中某个节点接收UK,K1MENDIF3FORJK1TOMDOFORIK1TOMDOIFDIAPRIANDDIAPCJANDLI,K0ANDUK,J0THEN更新子矩阵AI,JAI,JLI,KUK,JENDIFENDFOR并行稀疏LU分解单步迭代时的第3步工作耗时最长，可以与下一个单步迭代的第1、第2步工作并行执行。本文采用流水线技术来实现其并行计算，即在处理器列PCK完成第K步迭代列块K1的分解后，处理器列PCK1可以同时并行执行第K1步迭代的前两步计算，而不必等到处理器列PCK完成第K步迭代的所有列块分解后才开始第K1步迭代的计算。其过程如图3所示，图中TIJ表示第I步迭代的第J步计算工作。由图可见，基第25卷第6期谢开贵等大规模电力系统潮流计算的分布式GESP算法93于流水线技术的并行算法相对于串行算法，可以使相邻的两步迭代在计算时间上得到重叠，从而达到了减少程序整体计算时间的目的。图3基于流水线技术的并行处理过程FIG3PARALLELPROCESSINGBASEDONTHEPIPELINETECHNIQUE在并行计算过程中，本文使用MPI标准非阻塞通信接口MPI_IRECV和MPI_ISEND完成节点间的数据接收和发送操作。非阻塞通信可以解决节点间数据同步时等待时间过长的问题，实现计算与通信的时间重叠。因为在此通信模式下，计算节点可以在等待接收所需数据的同时向其他节点发送数据。而在传统阻塞通信模式下，节点在一个通信时间段内只能执行发送操作或者接收操作，从而导致节点间耗费大量的相互等待时间，极端情况下甚至导致进程间发生死锁，使程序的计算效率大大降低。基于MPI非阻塞通信模式的流水线技术大大减少了进程间的等待、数据同步时间，提高了程序的并行效率。4算例测试及分析本文利用曙光TC1700服务器和CISCO千兆以太网交换机搭建了具有若干处理节点的分布式计算平台。每个节点处理器为XEON20GHZ/512KB，具有1GB内存存储空间，操作系统为LINUXV90，节点间的并行通信接口为MPICH125。由于对系数矩阵采用了基于超节点的分块存储，如果不同的超节点之间规模差异过大将不利于节点间负载平衡，同时单个超节点的规模过大会使其失去稀疏性从而增加计算量、降低了单个处理器节点的计算效率，所以本文选定单个超节点的最高维数不超过20。潮流计算中，收敛容差为104（基准功率100MVA）。测试系统包括由IEEE标准测试系统（30和118节点系统）合成的多个大规模系统。合成系统15将IEEE标准系统按NN网格结构通过联络线互联起来，从而得到更大规模的测试系统。合成系统的节点导纳矩阵与同等规模的实际输电网络的节点导纳矩阵具有接近的条件数。表1给出了8个算例系统的网络规模和JACOBI矩阵条件数。表1测试系统的规模及JACOBI矩阵条件数TAB1THESCALEOFTESTSYSTEMSANDCONDITIONNUMBEROFJACOBIMATRIX系统支路数节点数JACOBI矩阵条件数IEEE30IEEE118SYN472SYN1062SYN1920SYN3000SYN7680SYN1200041179720162023764280180801716030118472106219203000768012000164E03297E03371E03127E04214E04514E04964E04284E05表2为本文分布式GESP法与分布式牛顿法、串行牛顿法潮流计算结果的对比，其中分布式GESP法与分布式牛顿法为4节点4进程的计算结果，串行牛顿法为单节点的串行求解结果。收敛时间指10次潮流计算的平均时间。从表2可以看出分布式GESP潮流算法与分布式牛顿法的收敛特性相同，且收敛速度明显快于分布式牛顿法。这表明GESP算法已对直接牛顿法做出了重要改进，使其利于分布式并行计算。表2三种潮流计算方法的速度比较TAB2COMPARISONOFCALCULATIONSPEEDSFORTHREEPOWERFLOWCALCULATIONMETHODS计算时间/S测试系统串行牛顿法分布式牛顿法分布式GESP法IEEE30IEEE118SYN472SYN1062SYN1920SYN3000SYN7680SYN12000003006021055483127191422204715516417219423129599326910880971281331481628312326由表2可见，随着系统规模的增大，分布式GESP求解潮流的收敛时间呈超线性增长。此时，增加计算节点成为解决问题的思路之一。表3给出3000和12000节点系统在采用不同数目计算节点时的加速比与并行效率。由表3可看出随着计算节点的增加，并行加速比的增大会出现瓶颈并呈逐步94电工技术学报2010年6月下降趋势，并行效率亦将趋于降低。其原因为一方面，随着并行度的增大，并行计算部分的计算负荷将减小而串行计算负荷将增大，串行计算所引起的开销在整个计算过程中所占的比例越来越高；另一方面，GESP算法涉及全局通信操作，其耗用的时间将随着参与通信操作的并行处理单元的数目以及通信量的增加而增加。因此，对大规模电力系统方程进行分布式计算时，随着计算节点的增多，并行加速比在达到某一值后，便会随着并行度的继续增大而下降，并行效率亦趋于下降。这符合AMDAHL并行加速比定律14。表3逐步增加计算节点时的加速比与并行效率TAB3COMPARISONOFPARALLELSPEEDUPANDEFFICIENCYWITHDIFFERENTNUMBEROFPROCESSORSSYN3000SYN12000计算节点数加速比并行效率加速比并行效率246810321716797736569161179133092057223948150321822420112237251273243表4给出了节点数为3000的系统在采用不同并行算法时加速比和并行效率的变化情况。从表中可以看出在相同计算节点的情况下，GESP算法比分布式牛顿法具有更高的加速比和并行效率。这说明本文采用的稀疏矩阵分块存储技术可以有效降低并行计算过程中进程间的通信量，而基于流水线技术的LU并行分解则进一步减少了进程间的等待和同步时间，以上两者使得本文方法的加速比和并行效率相对传统并行算法得到了明显的提升。表4采用不同并行算法计算SYN3000网络的加速比与并行效率TAB4COMPARISONOFPARALLELSPEEDUPANDEFFICIENCYUSINGDIFFERENTPARALLELMETHODSFORTHESYN3000SYSTEM分布式GESP法分布式牛顿法计算节点数加速比并行效率加速比并行效率2468103217167977365691611791330920572814784434223381411190740530345结论基于新型数学模型的潮流快速并行计算越来越得到研究人员的重视，为提高潮流并行计算的加速比和并行效率，本文利用GESP算法对牛顿潮流修正线性方程组的分布式并行求解进行了研究。根据牛顿潮流方程修正线性方程组系数矩阵的稀疏性特点，本文对其进行基于超节点划分的分块存储，并在此基础上将流水线技术应用于并行LU分解过程中。在分布式计算平台上，采用LINUXMPI的软件架构，实现了GESP牛顿潮流算法的并行计算。通过对不同规模的测试系统计算表明本文方法对较大规模电力网络进行潮流计算时，在满足相同求解精度的条件下，相对于串行潮流算法、传统并行算法具有较好的速度优势。通过对同一系统在不同计算节点下测试表明本文方法相对传统潮流分布式算法具有可扩展性，且有较高的加速比与并行效率。参考文献1卢强，周孝信，薛禹胜，等面向21世纪电力科学技术讲座M北京中国电力出版社，20002刘洋，周家启，谢开贵，等基于BEOWULF集群的大规模电力系统方程并行PCG求解J电工技术学报，2006，213105111LIUYANG,ZHOUJIAQI,XIEKAIGUI,ETALPARALLELPCGSOLUTIONOFLARGESCALEPOWERSYSTEMEQUATIONSBASEDONBEOWULFCLUSTERJTRANSACTIONSOFCHINAELECTROTECHNICALSOCIETY,2006,2131051113张海波，张伯明，孙宏斌基于异步迭代的多区域互联系统动态潮流分解协调计算J电力系统自动化，2003，272419ZHANGHAIBO,ZHANGBOMING,SUNHONGBINADECOMPOSITIONANDCOORDINATIONDYNAMICPOWERFLOWCALCULATIONFORMULTIAREAINTERCONNECTEDSYSTEMBASEDONASYNCHRONOUSITERATIONJAUTOMATIONOFELECTRICPOWERSYSTEMS，2003，2724194陈颖，沈沉，梅生伟，等基于改进JACOBIANFREENEWTONGMRESM的电力系统分布式潮流计算J电力系统自动化，2006，30959CHENYING,SHENCHEN,MEISHENGWEI,ETALDISTRIBUTEDPOWERFLOWCALCULATIONBASEDONANIMPROVEDJACOBIANFREENEWTONGMRESMMETHODJAUTOMATIONOFELECTRICPOWERSYSTEMS,2006,30959第25卷第6期谢开贵等大规模电力系统潮流计算的分布式GESP算法955WUJUNQIANG,BOSEAPARALLELSOLUTIONOFLARGESPARSEMATRIXEQUATIONSANDPARALLELPOWERFLOWJIEEETRANSACTIONSONPOWERSYSTEM,1995,103134313496徐得超，李亚楼，郭剑，等消去树理论及其在潮流计算中的应用J电网技术，2007，31221216XUDECHAO,LIYALOU,GUOJIAN,ETALELIMINATIONTREETHEORYANDITSAPPLICATIONINPOWERFLOWCALCULATIONJPOWERSYSTEMTECHNOLOGY,2007,312212167CHENTSUNGHAO,CHARLIECHUNGPINGCHENEFFICIENTLARGESCALEPOWERGRIDANALYSISBASEDONPRECONDITIONEDKRYLOVSUBSPACE