基于GPU的拉格朗日乘子優(yōu)化動(dòng)態(tài)經(jīng)濟(jì)調(diào)度

李 源，初 壯

(1.云南電網(wǎng)有限責(zé)任公司大理供電局，云南 大理 671000；2.東北電力大學(xué)，吉林 吉林 132012)

近年來(lái)，風(fēng)力削減相關(guān)的問(wèn)題[1-2]在電力系統(tǒng)中已備受關(guān)注。為了減少縮減風(fēng)電[3]，調(diào)度方案需要進(jìn)行相應(yīng)的調(diào)整。調(diào)整后的計(jì)算必須具有更高的效率，并且成本很少。調(diào)度方案的調(diào)整針對(duì)整個(gè)調(diào)度和調(diào)度周期的各個(gè)部分。調(diào)度周期的各個(gè)部分需要在滿(mǎn)足系統(tǒng)的約束條件下進(jìn)行機(jī)組的微調(diào)，調(diào)整將在一些連續(xù)的時(shí)間間隔內(nèi)進(jìn)行，并且不會(huì)啟/停發(fā)電機(jī)，它可以被制定為大規(guī)模，連續(xù)和非線(xiàn)性的優(yōu)化模型，這與傳統(tǒng)的動(dòng)態(tài)經(jīng)濟(jì)調(diào)度(DED)相同。

非線(xiàn)性編程方法，如二次規(guī)劃[4]、班德斯分解[5]和內(nèi)部方法[6-7]，常用于求解類(lèi)似DED典型的非線(xiàn)性?xún)?yōu)化問(wèn)題；同時(shí)，隨機(jī)優(yōu)化方法，如遺傳算法[7]、進(jìn)化規(guī)劃和粒子群優(yōu)化[8-9]，也被用于求解DED模型。這些方法的實(shí)現(xiàn)都為串行計(jì)算，它們適用于當(dāng)時(shí)的硬件和軟件環(huán)境。并行計(jì)算技術(shù)近年來(lái)發(fā)展迅速。計(jì)算機(jī)統(tǒng)一設(shè)備架構(gòu)(CUDA)、基于圖形處理單元(GPU)是一種高效、低成本的并行計(jì)算技術(shù)，使用CPU的“中央處理”向CPU和GPU并用的“協(xié)處理”發(fā)展，已應(yīng)用于電力系統(tǒng)[10-11]。在文獻(xiàn)[10-12]中，用于求解功率流問(wèn)題的牛頓-拉普森方法在GPU上實(shí)現(xiàn)，雅可比矩陣、LU分解和前車(chē)回代在GPU上實(shí)現(xiàn)；文獻(xiàn)[12]提出了一種GPU加速解決方案，它在分批處理ACPF(alternating current power flow,交流潮流)之間創(chuàng)建了一個(gè)額外的并行層，從而實(shí)現(xiàn)了更高水平的整體并行性。

本文基于GPU的拉格朗日乘子優(yōu)化建立了DED模型，引入并行計(jì)算加速求證過(guò)程，下面逐一進(jìn)行論述。

1 研究問(wèn)題模型

考慮風(fēng)電入網(wǎng)的電力系統(tǒng)調(diào)度模型，與常規(guī)經(jīng)濟(jì)調(diào)度不同點(diǎn)在于：電力系統(tǒng)經(jīng)濟(jì)成本的目標(biāo)函數(shù)；風(fēng)電出力的上下限約束；電力系統(tǒng)的功率平衡約束。

1.1 目標(biāo)函數(shù)

在常規(guī)能源達(dá)到限值時(shí)，風(fēng)電的引入能增加系統(tǒng)韌性，從而減少棄風(fēng)量。風(fēng)電入網(wǎng)后[9]，電力系統(tǒng)的經(jīng)濟(jì)目標(biāo)函數(shù)如下：

minZ=E1+E2

(1)

式中：E1表示常規(guī)火電機(jī)組的費(fèi)用，包括運(yùn)行成本、開(kāi)啟停成本；E2表示風(fēng)電機(jī)組的發(fā)電成本。

火電發(fā)電成本包括：燃料成本和開(kāi)啟停成本，具體表達(dá)形式如下:

(2)

(3)

式中：T代表T個(gè)調(diào)度周期；PWt為在第t時(shí)段風(fēng)電出力；F(Pit)為第i臺(tái)機(jī)組第t個(gè)調(diào)度周期的運(yùn)行成本；SUit、SDit分別為常規(guī)機(jī)組i在t時(shí)段的開(kāi)啟停成本；CW為風(fēng)功率的成本系數(shù)。

常規(guī)機(jī)組的開(kāi)啟停成本為:

SUit=CU×Iit×(1-Iit-1)

(4)

SDit=CD×Iit-1×(1-Iit)

(5)

式中:CU、CD分別為常規(guī)機(jī)組開(kāi)機(jī)和關(guān)機(jī)成本系數(shù);Iit為第i臺(tái)機(jī)組在第t個(gè)調(diào)度周期的機(jī)組狀態(tài)，取“1”時(shí)表示機(jī)組開(kāi)機(jī)，取“0”時(shí)表示機(jī)組關(guān)機(jī)。

1.2 約束條件

a.負(fù)荷平衡約束。在考慮風(fēng)電的并入和不計(jì)網(wǎng)絡(luò)損耗的情況下，機(jī)組的發(fā)電量并入風(fēng)電量后PWt和負(fù)荷Pbt相等：

(6)

Pother=PLianluo+PHedian+PGuangfu+PShuidian

(7)

式中:Pbt為電力系統(tǒng)在t時(shí)刻段內(nèi)的負(fù)荷值;Phdit為第i臺(tái)火電機(jī)組在第t時(shí)段的功率；PLianluo為電力系統(tǒng)的聯(lián)絡(luò)線(xiàn)功率;Pother為其他功率，包括核電功率PHedian;光伏功率PGuangfu;水電功率PShuidian。

b. 系統(tǒng)旋轉(zhuǎn)備用約束。為保證電力系統(tǒng)的安全運(yùn)行，在風(fēng)電入網(wǎng)后，電網(wǎng)需要使所有常規(guī)機(jī)組和其他并網(wǎng)能源之和滿(mǎn)足一定的限制，具體如下：

(8)

c.機(jī)組功率限制約束。對(duì)于常規(guī)火電機(jī)組，需要在每個(gè)時(shí)刻都得滿(mǎn)足最小、最大出力約束；對(duì)于電網(wǎng)并入風(fēng)電后，風(fēng)電入網(wǎng)功率也應(yīng)小于等于此時(shí)的風(fēng)電集群總?cè)萘縬wt，具體表達(dá)為：

0≤PWt≤qwt

(9)

(10)

2 基于GPU的拉格朗日乘子優(yōu)化

2.1 GPU并行計(jì)算架構(gòu)

單指令多線(xiàn)程(SIMT)是基于GPU的CUDA提供的計(jì)算的顯著特征，其與多指令多數(shù)據(jù)(MIMD)明顯不同。 在GPU內(nèi)部，八個(gè)或更多流處理器(SP)連接到流多處理器(SM)，每個(gè)GPU由許多SM組成，通常情況下，每個(gè)SM中包含32(或48)個(gè)流處理器(SP)。SP是GPU上數(shù)據(jù)處理的最基本單元。GPU計(jì)算平臺(tái)架構(gòu)含有兩臺(tái)2.40 GHz的英特爾 Core i7-4700HQ處理器，每臺(tái)處理器的CPU含有6個(gè)核心(core)。GPU和CPU通過(guò)外圍部件互聯(lián)(PCI)總線(xiàn)相連。GPU的型號(hào)為NVIDIA GeForce GT 745M。

一個(gè)程序的并行實(shí)現(xiàn)包含兩部分：CPU執(zhí)行(host)端和GPU執(zhí)行(device)端，見(jiàn)圖1的CUDA計(jì)算模式，其中kernel為在GPU上執(zhí)行的程序，GPU執(zhí)行端可使用信息多點(diǎn)傳遞接口(MPI)等技術(shù)并行。

圖1 CUDA計(jì)算模式

在SIMT中，每32個(gè)線(xiàn)程被調(diào)度為線(xiàn)程warp并同時(shí)工作，其中warp表示NVIDIA的線(xiàn)程粒度，為線(xiàn)程的集合。如果可以將問(wèn)題劃分為可以獨(dú)立解決的粗略子問(wèn)題，則可以通過(guò)GPU內(nèi)任何可用多處理器上的線(xiàn)程塊并行地求解。當(dāng)子問(wèn)題的數(shù)量巨大時(shí)，基于GPU的并行計(jì)算比傳統(tǒng)的基于CPU的串行計(jì)算花費(fèi)更少的時(shí)間。例如，在雅可比矩陣和海申矩陣的每個(gè)元素最優(yōu)求解中，可以采用GPU并行計(jì)算。

2.2 算法實(shí)現(xiàn)

本文中的拉格朗日乘子法包含了大量的向量運(yùn)算，例如有關(guān)前后兩個(gè)時(shí)刻的功率的變化關(guān)系為例，P(k+1)=P(k)+ΔP，這里的P為n維矢量。在CPU上，傳統(tǒng)的實(shí)現(xiàn)方法如下：

(11)

當(dāng)循環(huán)變量i從0增加到n，功率向量的對(duì)應(yīng)元素按照順序進(jìn)行加運(yùn)算。但是在此過(guò)程中，每一組元素的計(jì)算過(guò)程是獨(dú)立的，只有在計(jì)算完P(guān)W時(shí)才會(huì)計(jì)算PW+1，彼此沒(méi)有相互的依存。GPU中，上述的循環(huán)運(yùn)算可以在一條流水線(xiàn)Block中同時(shí)完成對(duì)P1,P2,…,PG的求解。

(12)

采用基于GPU的并行計(jì)算來(lái)加速優(yōu)化。式(12)可以以向量P的每個(gè)元素的形式重寫(xiě)如下：

(13)

由于這里需求解的機(jī)組功率為N×T的二維矩陣，其中N表示機(jī)組總數(shù)量。要實(shí)現(xiàn)并行運(yùn)算，可將上式先轉(zhuǎn)為單臺(tái)機(jī)組，化簡(jiǎn)為：

(14)

其中，sum1代表機(jī)組1等式約束的數(shù)量，sum2代表了機(jī)組1不等式約束的數(shù)量。

相對(duì)于機(jī)組的單個(gè)求解，由于每個(gè)機(jī)組的參數(shù)是固定的，所以在時(shí)間不同的時(shí)候，式(13)的表達(dá)形式是一樣的，假設(shè)系統(tǒng)總周期為T(mén)。為了對(duì)這T個(gè)未知量迭代求解，可以取T個(gè)Block作為一條流水線(xiàn)。再擴(kuò)展到G臺(tái)機(jī)組，便為G條流水線(xiàn)。將式(15)展開(kāi)，可得出具體的迭代表達(dá)式如下，同樣式(16)也為P1流水線(xiàn)所執(zhí)行的指令過(guò)程。

(15)

(16)

圖2 流水線(xiàn)迭代序列

2.3 更新不等式約束乘子的過(guò)程

至于不等式約束，它對(duì)于方程(8)-(9)具有不同形式來(lái)講有些復(fù)雜。SIMT并行計(jì)算只能處理具有相同形式的約束，因此，更新μ(k)的過(guò)程應(yīng)該分成幾個(gè)單獨(dú)的子程序，每個(gè)子程序?qū)?yīng)一種形式的約束。

機(jī)組的上下限約束，即方程式(9)，不需要通過(guò)拉格朗日乘子來(lái)處理。如果某個(gè)變量的值超出了它們自身的范圍，則應(yīng)將其值固定在超出的上限/下限邊界上。它可以通過(guò)簡(jiǎn)單的Kernel函數(shù)來(lái)完成。

方程式(8)和(9)分別是斜坡約束和旋轉(zhuǎn)儲(chǔ)備約束。它們具有相似的形式，每個(gè)表達(dá)式都包含兩個(gè)約束。例如，如果i和t是已知的，則式(8)可以等效為：

(17)

(18)

但是，兩個(gè)約束及其乘子應(yīng)該在相同的Kernel函數(shù)中計(jì)算。并且在函數(shù)中，兩個(gè)約束和乘子是串聯(lián)計(jì)算的。不等式約束多出現(xiàn)一個(gè)，在實(shí)現(xiàn)中也會(huì)多出一個(gè)線(xiàn)程執(zhí)行。

3 算例分析

3.1 方案制定

本文以拉格朗日乘子法為理論基礎(chǔ)，并考慮風(fēng)電并網(wǎng)的經(jīng)濟(jì)調(diào)度方案。在GPU的操作平臺(tái)上實(shí)現(xiàn)了并行算法。算法實(shí)現(xiàn)流程框圖見(jiàn)圖3。

圖3 算法實(shí)現(xiàn)流程框圖

由圖3得，一次變量迭代的計(jì)算步驟如下。

b. 以拉格朗日乘子法為整體框架，調(diào)整相應(yīng)的并行算法公式，在CPU上處理數(shù)據(jù)輸入接口和IEEE可靠性系統(tǒng)的串行部分。GPU通過(guò)流水線(xiàn)的形式處理具有相同表達(dá)公式的數(shù)據(jù)迭代部分，即功率變量迭代和乘子迭代, 其中功率變量迭代部分包括等式約束和不等式約束，其數(shù)量與機(jī)組的數(shù)量相關(guān)；

c. 當(dāng)算法一輪迭代后，其功率變量的變化值不滿(mǎn)足給定誤差時(shí)，k=k+1進(jìn)行下一輪迭代。先進(jìn)行寄存器中數(shù)據(jù)的傳導(dǎo)，傳入新值給GPU中，迭代完后將又一輪新值重新傳回CPU中，進(jìn)行串行部分的數(shù)據(jù)可靠性檢驗(yàn)和誤差檢驗(yàn)，直到滿(mǎn)足為止。

3.2 算例驗(yàn)證

為了展示基于GPU的拉格朗日乘數(shù)算法的有效性和效率，IEEE可靠性系統(tǒng)分別在CPU上進(jìn)行串行計(jì)算并在GPU和CPU上進(jìn)行并行計(jì)算。CPU是英特爾核心i5 4690，計(jì)算機(jī)內(nèi)存為16 GB，GPU為NIVIDIA 960，帶有4 GB圖形內(nèi)存。

由于拉格朗日乘數(shù)優(yōu)化已多年來(lái)成功應(yīng)用于解決DED問(wèn)題，因此證明了它的有效性和收斂性。 因此，只有基于GPU的異構(gòu)和并行計(jì)算與傳統(tǒng)的串行計(jì)算之間的差異才值得分析和討論。

表1列出了GPU和CPU以及CPU在4種不同計(jì)算規(guī)模上所花費(fèi)的時(shí)間。由表1可以看出，在計(jì)算規(guī)模較小的情況下，CPU上的串行計(jì)算速度比GPU和CPU上的異構(gòu)計(jì)算速度快。只有當(dāng)規(guī)模擴(kuò)大到一定程度時(shí)，并行計(jì)算的優(yōu)越性才能體現(xiàn)出來(lái)。

表1 并行與串行運(yùn)算時(shí)間對(duì)比

從表1中還可以看出，在算例2中具有96個(gè)周期的CPU的時(shí)間是具有24個(gè)周期的算例1的7倍。 花費(fèi)時(shí)間的增加趨勢(shì)可以見(jiàn)圖4。 曲線(xiàn)1是GPU和CPU上的異構(gòu)并行計(jì)算，曲線(xiàn)2是CPU上的串行計(jì)算?？梢钥闯?，曲線(xiàn)2的增長(zhǎng)速度快于曲線(xiàn)1。

圖5中分別給出了3臺(tái)機(jī)組在跌過(guò)程中，由全程CPU進(jìn)行功率求解數(shù)值變化過(guò)程和由CPU&GPU協(xié)同進(jìn)行功率求解數(shù)值變化過(guò)程，兩類(lèi)曲線(xiàn)在最后基本吻合。

圖4 并行與串行運(yùn)算時(shí)間對(duì)比

圖5 全程CPU和CPU&GPU協(xié)同運(yùn)算對(duì)比曲線(xiàn)

圖5給出了4種算例的CPU與并行運(yùn)算的時(shí)間對(duì)比，可以看出，GPU的并行協(xié)處理在運(yùn)算規(guī)模越大的情況下，其優(yōu)勢(shì)明顯會(huì)展現(xiàn)出來(lái)。

計(jì)算規(guī)模越大，異構(gòu)計(jì)算可以節(jié)省更多時(shí)間。在大規(guī)模風(fēng)電滲透增加DED復(fù)雜性情況，需要更多計(jì)算資源的情況下，基于GPU和CPU的異構(gòu)計(jì)算在電力系統(tǒng)發(fā)電調(diào)度計(jì)算中起著重要作用。

4 結(jié)論

由于大規(guī)模集成和風(fēng)電的高度不確定性，本文建立了一個(gè)新的模型，以減少不時(shí)出現(xiàn)的棄風(fēng)， 并且基于GPU和CPU的異構(gòu)并行計(jì)算拉格朗日乘子優(yōu)化已被應(yīng)用于求解所提出的模型。可以看出，在滿(mǎn)足相同效果的前提下，基于GPU的并行具有更高的效率，并且適用于電力系統(tǒng)的優(yōu)化計(jì)算。