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

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　分层法与链路因子表法示意图