林亞君

摘要 隨著并行計(jì)算的發(fā)展，實(shí)現(xiàn)潮流計(jì)算的并行化是提高計(jì)算速度的有效方法，而如何利用GPU技術(shù)優(yōu)化潮流計(jì)算中線性方程組的求解則是關(guān)鍵。研究了潮流迭代求解中易于并行的線性方程組求解方法，提出了采用預(yù)處理的穩(wěn)定雙共軛梯度算法（ Bi-CGSTAB），提高線性方程紐的并行性與計(jì)算性能。最后通過應(yīng)用InterPSS對(duì)所提的方法進(jìn)行驗(yàn)證。

【關(guān)鍵詞】潮流計(jì)算 并行計(jì)算 預(yù)條件處理穩(wěn)定 雙共軛梯度算法

現(xiàn)代電網(wǎng)朝著大規(guī)模、復(fù)雜性、多元性的方向發(fā)展，電力系統(tǒng)潮流的計(jì)算量與復(fù)雜度急劇增加，使得越來越多的研究者致力于將CUDA應(yīng)用于電力系統(tǒng)潮流計(jì)算中。文獻(xiàn)[1]主要是基于CUDA平臺(tái)通過對(duì)高斯消去法求解線性方程組并行化實(shí)現(xiàn)潮流計(jì)算的并行。文獻(xiàn)[2]利用GMRES （m）算法求解潮流計(jì)算中的線性方程組，并將該算法基于CUDA移植到GPU上執(zhí)行。文獻(xiàn)[3]研究了基于雙共軛梯度法實(shí)現(xiàn)牛頓.拉夫遜法潮流算法的并行化。

本文嘗試基于GPU針對(duì)大規(guī)模電網(wǎng)提出一種新的迭代法求解線性方程組的預(yù)處理方案，進(jìn)而大幅度提升大規(guī)模電網(wǎng)潮流求解的計(jì)算性能。

1 潮流計(jì)算的可并行性

所謂并行計(jì)算是一種可同時(shí)執(zhí)行多個(gè)指令的算法，目的是通過提高計(jì)算速度或擴(kuò)大問題求解規(guī)模，解決大型而復(fù)雜的計(jì)算問題。采用并行技術(shù)解決的問題必須具有以下兩個(gè)特點(diǎn)：

（1）對(duì)這些數(shù)據(jù)要執(zhí)行的指令基本相同;

（2）各個(gè)數(shù)據(jù)之間基本相互獨(dú)立，互不依賴。

1.1 各步驟可并行性分析

（1）形成節(jié)點(diǎn)導(dǎo)納矩陣的并行性：根據(jù)支路信息（包括開始節(jié)點(diǎn)編號(hào)、終止節(jié)點(diǎn)編號(hào)、支路等效導(dǎo)納）計(jì)算節(jié)點(diǎn)導(dǎo)納矩陣，即所謂支路追加法，各個(gè)支路對(duì)導(dǎo)納矩陣的貢獻(xiàn)相互獨(dú)立，互不干擾。并且對(duì)每個(gè)支路的處理指令是一致的，符合上述的并行計(jì)算原則。

（2）形成雅可比矩陣的并行性：在潮流計(jì)算中雅可比矩陣中各個(gè)元素的形成之間是相互獨(dú)立、互不干擾的。并且對(duì)于雅可比矩陣中各子矩陣上的元素除對(duì)角元素外，其余元素計(jì)算公式是一致的。即處理該數(shù)據(jù)所執(zhí)行的指令是相同的。于是符合并行計(jì)算的兩個(gè)特點(diǎn)，故形成雅可比矩陣的過程可以采用并行技術(shù)實(shí)現(xiàn)。

（3）求解修正方程組的并行性：在潮流計(jì)算過程中求解修正方程組，通常采用的是直接法和迭代法。文獻(xiàn)[4]對(duì)潮流計(jì)算中修正方程組求解的迭代法和直接法進(jìn)行了比較，結(jié)果表明，對(duì)于大規(guī)模電網(wǎng)（幾百個(gè)節(jié)點(diǎn)以上），采用適當(dāng)?shù)念A(yù)處理的迭代法計(jì)算速度優(yōu)于直接法。不僅如此，利用迭代法求解稀疏線性方程組時(shí)，會(huì)出現(xiàn)大量相對(duì)易于并行化的矩陣向量運(yùn)算。

1.2 潮流計(jì)算各步驟的耗時(shí)

上一小節(jié)分析了潮流程序中有三個(gè)步驟是可并行的，然而采用并行技術(shù)需要將計(jì)算任務(wù)映射到并行機(jī)中，中間的數(shù)據(jù)傳輸會(huì)帶來一定的延時(shí)。如果上述的三個(gè)步驟在采用串行技術(shù)時(shí)，已經(jīng)耗時(shí)較少，采用并行技術(shù)將得不償失。

通過InterPSS平臺(tái)，對(duì)不同大小電網(wǎng)進(jìn)行潮流計(jì)算，分析以上三個(gè)可并行步驟的串行計(jì)算耗時(shí)。結(jié)果表明形成節(jié)點(diǎn)導(dǎo)納矩陣和雅可比矩陣在串行計(jì)算中耗時(shí)很短，并且占整個(gè)潮流程序總耗時(shí)的比例很小，故不考慮將這兩個(gè)步驟并行。另一方面，隨著電網(wǎng)規(guī)模的增大，求解修正方程組在整個(gè)算法耗時(shí)所占比重越來越大。這與并行對(duì)規(guī)模越大的數(shù)據(jù)加速效果越顯著不謀而合，于是對(duì)潮流程序進(jìn)行加速就可以鎖定為對(duì)求解線性方程組過程進(jìn)行加速。

2 基于GPU的修正方程組求解

2.1 修正方程組求解算法及預(yù)處理技術(shù)

Bi-CGSTAB本質(zhì)上是Bi-CG和反復(fù)使用GMRES（1）的結(jié)合，利用遞歸的方法逐步減小殘量，因此占用的內(nèi)存小，被證明是一種處理稀疏矩陣為非對(duì)稱實(shí)矩陣的線性方程十分有效的算法。所以可以采用該算法實(shí)現(xiàn)潮流計(jì)算中的修正方程組的求解。

然而利用Bi-CGSTAB算法求解潮流中的修正方程組時(shí)，系數(shù)矩陣（雅可比矩陣）隨著網(wǎng)絡(luò)規(guī)模的變大會(huì)出現(xiàn)病態(tài)，亦即條件數(shù)會(huì)漸漸變大，迭代收斂性很差。為了提高迭代法的收斂性，需要對(duì)修正方程組進(jìn)行適當(dāng)?shù)淖儞Q，此過程即為預(yù)處理過程。

目前常用的預(yù)處理方法有不完全分解法（ILU）、PQ分解法、稀疏近似逆法和基于雅可比矩陣逆的預(yù)處理方法?？紤]到潮流計(jì)算過程中的兩個(gè)特點(diǎn)：

（1）雅可比矩陣在潮流程序整個(gè)迭代過程中不會(huì)大幅度變化;

（2）迭代法求解修正方程組的最大迭代次數(shù)都是在第一次外迭代時(shí)發(fā)生的，于是采用基于雅可比矩陣逆的預(yù)處理方法。

2.2 基于GPU的修正方程組求解

在帶預(yù)處理的Bi-CGSTAB算法中涉及到大量的向量相加、向量?jī)?nèi)積、向量與稠密矩陣相乘、向量與稀疏矩陣相乘等運(yùn)算?；贕PU實(shí)現(xiàn)Bi-CGSTAB算法并行化，主要就是根據(jù)GPU的硬件結(jié)構(gòu)確定合理的并行化方式完成以上四種運(yùn)算。

3 算例及分析

為了驗(yàn)證本文所提出的實(shí)現(xiàn)InterPSS中潮流并行化拓展的方法的實(shí)際效果，本節(jié)對(duì)不同規(guī)模的電網(wǎng)進(jìn)行測(cè)試。

在計(jì)算過程中Bi-CGSTAB算法的迭代誤差取l0^-10，最大迭代次數(shù)取5000;牛頓法的迭代誤差取l0^-20，其并行性能的一些指標(biāo)如表1所示。

從表1可以看出采用該方法在處理電網(wǎng)節(jié)點(diǎn)小于162左右時(shí)加速比小于1;在大于162節(jié)點(diǎn)的電網(wǎng)中，加速比大于1，且加速比隨著電網(wǎng)規(guī)模增大而增大。

4 結(jié)論

本文基于GPU實(shí)現(xiàn)了潮流計(jì)算的并行計(jì)算，并取得了理想的加速效果。電力系統(tǒng)仿真對(duì)計(jì)算能力的需求隨著電網(wǎng)規(guī)模的增大而越來越大。在電力系統(tǒng)的各種仿真中都會(huì)涉及到矢量矩陣運(yùn)算，所以InterPSS中的其他電力系統(tǒng)仿真的矢量矩陣運(yùn)算都可以采用本文提出的基于GPU的實(shí)現(xiàn)類來拓展，具有廣闊的推廣前景。

參考文獻(xiàn)

[1]夏俊峰，楊帆，李靜等，基于GPU的電力系統(tǒng)并行潮流計(jì)算的實(shí)現(xiàn)[J].電力系統(tǒng)保護(hù)與控制，2010， 38 （18）：100-103.

[2] Xue-Xin Liu， Hai Wang， Tan，S.X.-D.Parallel Power Grid Analysis UsingPreconditioned GMRES Solver onCPU-GPU Platforms [J]. Computer-Aided Design （ICCAD）， 2013 IEEE/ACM International Conferenceon，Page （s）： 561-568.

[3] Garcia N.Parallel Power FlowSolutions Using a Bi-ConjugateGradient Algorithm and a NewtonMethod：a GPU-based approach， "2010IEEE Power & Energy Society GeneralMeet ing，2010.

[4]吳建平，王正華，李曉梅.稀疏線性方程組的高效求解與并行計(jì)算[M].長(zhǎng)沙：湖南科學(xué)技術(shù)出版社，2004 （05）.

[5]李曉梅，吳建平.Krylov子空間方法及其并行計(jì)算[J].計(jì)算機(jī)科學(xué)，2005， 32 （01）：19-20， 40.

[6]Mori H，Tanako H， Kanno J.APreconditioned Fast DecoupledPowerflow Method for ContingencyScreening [J]. IEEE Trans on PowerSystems，1996，11（01）： 357-363.

[7]汪芳宗，何一帆，葉婧，基于稀疏近似逆預(yù)處理的牛頓一廣義極小殘余潮流計(jì)算方法[J].電網(wǎng)技術(shù)，2008， 32 （17）： 50-53.