基于PC机群的电力系统机电暂态仿真并行算法李亚楼，周孝信，吴中习（中国电力科学研究院，北京100085）摘要：在电力系统的动态稳定在线评估和实时仿真计算中，并行处理是一种非常有发展前途的技术。许多种类的并行算法已被提出，并在不同类型的并行计算机上实现。由于具有性价比高、升级和扩展性能好的特点，PC机群并行计算机吸引了越来越多的注意力。本文综述和讨论了几种机电暂态并行算法，特别是在PC机群上实现这些算法的有利和不利条件。本文讨论的并行算法包括：网络分割、线性方程并行求解、牛顿类算法和一些时间并行算法。
关键词：电力系统仿真；机电暂态稳定；并行处理；PC机群
1引言
我国电力系统的发展速度很快，近十年来，随着大区联网的逐步完成和三峡电站机组的并网发电，电力系统的全国联网即将实现。电力系统的规模迅速扩大，系统变得更为复杂，因而对电力系统分析工具提出了更高的要求，如能快速地或以在线方式进行系统分析，甚至能实时仿真电力系统的动态特性。机电暂态仿真是分析电力系统的有效工具，在系统设计、规划、运行和调度等方面有广泛的应用。电力系统机电暂态仿真的计算量非常大，成为制约机电暂态仿真的在线和实时应用的关键因素。
为了提高仿真速度，并行处理技术被逐渐应用于电力系统暂态稳定仿真计算。近十几年来，用于电力系统并行计算的算法被不断提出。根据算法的实现原理，所提出的并行算法大致可以分为：空间并行、时间并行或两者的结合——时空并行。空间并行的原理是将系统分割为小的子系统后进行并行处理；而时间并行则通过同时求解多个积分步长来实现。按照划分后子任务的计算量还可以把并行算法分为细粒度并行算法和粗粒度并行算法。一般来说，细粒度并行算法的通信次数较多，适应于矢量并行机和共享内存的并行机；粗粒度并行计算的通信次数较少，适应于消息传递的的并行机。无论哪种类型的并行算法，通信次数和通信量越少，其并行效率越高。
按照处理器数目把电力网络分割为子网后进行并行处理，是一种常用的空间并行方法。网络分割算法的主要目标是按照指定的子网数目，均匀分割原始网络。现有的网络分割算法包括：模拟退火算法^[1]、边界点表法^[2]、道路树法^[3]和动态分割法^[4]。大部分算法能够按照规模均匀分割网络，部分算法还能够保持新增注入元最少。
线性方程组的并行求解是机电暂态仿真计算中最关键的部分。对此人们已经提出了许多算法，如因子法^[5]、W矩阵法^[5]、并行分解和回代法^[6]、对角块加边法（BorderedBlockedDiagonalForm,BBDF）^[7,8]和共扼梯度法^[9]等。因子法、W矩阵法和共扼梯度法的并行处理部分主要是矩阵和矢量的运算，并行粒度较小，通信较频繁；BBDF方法对各个子网的并行处理几乎是独立的，并行效率较高。
牛顿类的算法广泛应用于非线性方程组的计算。牛顿类算法并行化的难点在于雅可比（Jacobian）方程组的求解。伪牛顿算法^[10]使用近似雅可比矩阵，以避免对雅可比矩阵频繁的LU分解。尽管存在迭代次数多的缺点，伪牛顿法的计算速度仍然比普通牛顿法快。
在时间并行方面，经常使用的有高斯－雅可比迭代和高斯－塞德尔迭代^[11-14]。高斯－雅可比迭代非常简单，可以完全并行化，但收敛速度比较慢。高斯－塞德尔迭代的收敛性能优于高斯－雅可比迭代，但较难被并行化。
采用何种并行计算机来实现不同的并行算法，是一个十分重要的问题。对称多处理机采用共享内存结构，具有较好通信性能，被大部分并行算法采用。但是，对称多处理机价格昂贵，并且难以升级和扩展，这些因素限制了并行处理技术的广泛应用。随着个人计算机(PC)的计算速度和商用网络通信速度的提高，把PC机用商用高速网络连接起来后进行并行计算已成为可能。PC机群是由多个PC机和商用高速网络组成的并行计算机，其优点是性价比高、易升级和易扩展，这些是机电暂态并行算法能够广泛应用的理想条件。当然，PC机群也有不足之处，如相对较窄的通信带宽和较长的通信延时，这些不利因素对不同的并行算法有着不同的影响。
本文介绍了几种电力系统机电暂态仿真的并行算法，着重分析了在PC机群上实现这些算法的优势和不足。本文介绍的算法包括网络分割、线性方程并行求解、牛顿类算法和时间并行类算法。
2并行计算机
在并行计算机的发展历史上，出现过各种不同类型的并行机，包括矢量机、单指令多数据流（SingleInstructionMultipleData，SIMD）和多指令多数据流（MultipleInstructionMultipleData，MIMD）计算机。随着计算技术的发展，矢量机和SIMD逐渐被淘汰，MIMD类型的并行机占据主导地位。当代主流的MIMD并行机包括对称多处理机（SymmetricMultiProcessor，SMP）、大规模并行机（MassivelyParallelProcessor，MPP）和工作站机群（ClusterOfWorkstation，COW）^[15]。其中。SMP和COW已被用于电力系统机电暂态仿真并行计算。
SMP结构如图1(a)所示，它具有如下特点：①对称性，任何处理器都可以访问任何存储单元和I/O设备；②单地址空间；③通信速度高，延迟低。但SMP机也具有以下缺陷：①不易升级和扩充；②价格比较昂贵。
使用通用PC机代替COW中的工作站，而且各PC机间用商用高速网络进行连接，则形成本文所述的PC机群，其结构如图1(b)所示。PC机群具有如下特点：①性能/价格比较高；②系统结构灵活；③升级和扩充方便。PC机群的主要缺陷在于：通信速度较低，通信延迟较大。随着计算机网络技术的发展，网络的通信速度也将不断提高，有望消除机群系统的该项缺陷。
3机电暂态稳定方程
机电暂态稳定问题可以由以下一组非线性差分代数方程描述^[16]

式中x代表状态矢量，V代表节点电压矢量。方程组中，式(1)描述了电力元件的动态特性，式(2)描述了网络的静态特性。
两种方案被经常用于求解以上方程组，交替求解和同步求解。交替求解方案使用积分方法（如：隐式梯形积分法）求解式(1)，然后将计算结果代入式(2)后，再单独求解式(2)。同步求解方案的原理是：离散化式(1)，然后与式(2)一起求解。同步求解方案中，一般使用牛顿类算法求解。对于空间并行算法，交替求解方案中，方程组(1)所描述的动态元件之间，没有直接的联系，可以被很容易地并行化；同步求解方案中，无法单独并行计算方程组(1)。线性方程组的并行求解是两种求解方案的难点。
4线性方程组并行求解
4.1网络分割
一个电力系统可以被视为由多个子网组成，子网间由联络线互相连接。联络线与子网的联接母线，被称之为边界点。按处理器数目，把网络分割为多个子网，是最常用的并行化方法。为提高并行计算的效率，网络分割要满足以下要求^[3]：
（1）边界点的数目要尽量少，它和处理器之间的数据交换量直接相关;
（2）每个处理器的计算量要大体相等；
（3）由于网络新增的注入元要尽量少。
在网络分割方面已提出了许多算法，它们可以分为两大类，一类是静态分割方法，另一类是动态分割方法。静态分割在并行计算之前进行，不参与并行计算过程。
根据热力学原理，文[1]中提出了一种模拟退火方法，使用边界点和联络线的数目构造罚函数。尽管该方法可以实现网络分割，但计算时间很长。而且，初始温度的设定、退火方案的选择，都难以按照最优设定，影响了分割结果的品质。
在边界表概念的基础上，提出了许多算法^[2]。利用边界表，这些算法可以找到具有最少边界点的分割方案。如何选择合适的起始母线和搜索路径以形成最优边界点表，则是该方法的关键。
为了把网络分割为对角块加边（BorderedBlockedDiagonalForm，BBDF）形式，文[3]提出了一种启发式方法[1][2][3][4]下一页