基于并行SIMT 平臺(tái)的電網(wǎng)系統(tǒng)造價(jià)數(shù)據(jù)分析研究

郭嘉成，宋妙環(huán)，王炳文

（國(guó)網(wǎng)甘肅省電力公司經(jīng)濟(jì)技術(shù)研究院，甘肅蘭州 730050）

電網(wǎng)工程的建設(shè)包括決策設(shè)計(jì)、施工與管理等步驟，是一個(gè)大型的系統(tǒng)工程[1]。每個(gè)步驟的順利實(shí)施均建立在對(duì)電網(wǎng)工程準(zhǔn)確分析的基礎(chǔ)上[2]，而電網(wǎng)工程的造價(jià)數(shù)據(jù)影響因素多[3]、數(shù)據(jù)量大，導(dǎo)致對(duì)其精細(xì)分析的難度較高[4]。目前的分析與驗(yàn)證大量消耗了運(yùn)行時(shí)間和內(nèi)存，同時(shí)可優(yōu)化的程度較低[5]。

基于大規(guī)模并行單指令多數(shù)據(jù)（SIMD）或是基于單指令多線程（SIMT）的GPU 平臺(tái)的出現(xiàn)，為大規(guī)模電網(wǎng)數(shù)據(jù)分析提供了良好的解決方案[6]。目前的商用GPU 可以提供超過(guò)380 G的浮點(diǎn)運(yùn)算能力和86 GB/s的片外內(nèi)存帶寬，是現(xiàn)代通用四核微處理器的3～4 倍。文中基于SIMT GPU，設(shè)計(jì)了一套電網(wǎng)工程造價(jià)數(shù)據(jù)的分析系統(tǒng)[7]。

1 系統(tǒng)造價(jià)數(shù)據(jù)建模

假設(shè)建造者的資源有限，減少總預(yù)算的一種方法是將預(yù)算分配給選定的線路，以增加其建造成本。將系統(tǒng)預(yù)算定義為m行的元組數(shù)據(jù)，每行l(wèi)均有自身的預(yù)算成本函數(shù)，由dl(bl)描述。函數(shù)dl(bl)表示當(dāng)預(yù)算bl部署在生產(chǎn)線上時(shí)，生產(chǎn)線l的額外建造成本。

因此，第l行的建造成本可以表示為：

其中，Cl,0是第l行的初始建造成本。

函數(shù)dl(bl)應(yīng)根據(jù)l行的實(shí)際預(yù)算成本特征來(lái)制定，通常應(yīng)符合以下條件：

1）當(dāng)bl=0，dl(bl)=0；

2）當(dāng)bl=∝，dl(bl)=∝；

3）dl(bl)是單調(diào)遞增函數(shù)。

尤其是當(dāng)部署了足夠的預(yù)算來(lái)建造l行時(shí)，建造成本變得無(wú)限大，建造者必須具有足夠的建造能力才能成功建造該行。

假設(shè)一個(gè)建造計(jì)劃包括m條線，建造成本分別為C1,…,Cm，建造者的建造能力為R。

若建造者可以成功執(zhí)行建造計(jì)劃，則必須滿足以下條件：

從預(yù)算節(jié)省的角度來(lái)看，若預(yù)算審批者旨在優(yōu)化建造計(jì)劃，則應(yīng)將預(yù)算部署到計(jì)劃中的一組上。從而使計(jì)劃的建造成本大于R，即：

因此，預(yù)算審批者的目標(biāo)是減少電力系統(tǒng)的建造預(yù)算損害，將建造預(yù)算限制在預(yù)期水平。為了解決該問(wèn)題，預(yù)算審批者必須找到滿足以下兩個(gè)條件的所有線組合：

1）建造成本小于R；

2）預(yù)期收益效果必須大于給定值LS。

滿足以上兩個(gè)條件的任何線組合，均被定義為預(yù)算優(yōu)化的候選線組合。

因此，預(yù)算部署模型可以公式化為以下非線性優(yōu)化問(wèn)題：

限制條件為：

其中，fcr(·) 表示第r個(gè)候選行組合的建造成本。通過(guò)引入一個(gè)小的正常數(shù)R0，可以進(jìn)一步將式（6）轉(zhuǎn)換為以下形式：

對(duì)于式（5）與式（7）所示的預(yù)算分配問(wèn)題，使用改進(jìn)的蠻力搜索算法枚舉所有候選行組合。然后基于候選線組合來(lái)制定預(yù)算部署問(wèn)題，最終通過(guò)原始對(duì)偶內(nèi)點(diǎn)法解決該問(wèn)題，并確定最佳預(yù)算部署策略。預(yù)算優(yōu)化分析流程如圖1 所示。

圖1 預(yù)算優(yōu)化分析流程

預(yù)算審批者的目的是將建造成本限制在預(yù)期水平LS內(nèi)。為了實(shí)現(xiàn)該目標(biāo)，預(yù)算審批者必須找到所有候選的線路組合并部署預(yù)算，從而優(yōu)化建造成本。

首先確定可行的建造集A，其中包括所有建造成本小于R的線組合。這樣，由于丟棄建造成本大于R的線組合，從而減小了搜索空間。

接下來(lái)在可行建造集合A中找到所有候選行組合，使用兩種措施來(lái)加快搜索過(guò)程。

措施1：確定最小行數(shù)NAmin。忽略行數(shù)小于NAmin的組合，以減少搜索空間。使用雙層模型來(lái)解決該問(wèn)題，無(wú)需考慮線性規(guī)劃的線建造成本?；谏鲜龉ぷ鳎瑢⒕€建造成本約束引入模型中以計(jì)算NAmin。

措施2：定義PL是候選行組合。即任何線路組合PL+ΔPL均可自動(dòng)視為冗余線路組合，這是因?yàn)轭A(yù)算部署會(huì)使線組合PL的建造成本增加到高于R；而預(yù)算部署會(huì)自動(dòng)增加線組合PL+ΔPL的建造成本超過(guò)R。因此，無(wú)需部署預(yù)算來(lái)支持多余的候選行組合PL?ΔPL。

2 并行SIMT運(yùn)算系統(tǒng)設(shè)計(jì)

由于電網(wǎng)工程的復(fù)雜性，導(dǎo)致建立式（7）所示的優(yōu)化模型過(guò)于龐大，單線程的數(shù)據(jù)處理方法難以迅速處理，因此設(shè)計(jì)了基于并行SIMT的數(shù)據(jù)預(yù)算系統(tǒng)[8]。

要在SIMT 平臺(tái)上實(shí)現(xiàn)最佳的分析效率，充分了解實(shí)際電網(wǎng)系統(tǒng)造價(jià)涉及的物理特性至關(guān)重要[9]。可以預(yù)期，若可以類似于像素圖形一樣存儲(chǔ)與處理電網(wǎng)工程數(shù)據(jù)[10]，則GPU SIMT 平臺(tái)將比通用CPU 平臺(tái)具有顯著優(yōu)勢(shì)[11]。因此，文中考慮求解一個(gè)接近原始柵格的近似規(guī)則電源柵格[12]。

2.1 基于GPU的幾何多重網(wǎng)格方法

幾何多重網(wǎng)格方法是解決大型造價(jià)數(shù)據(jù)優(yōu)化問(wèn)題的最快數(shù)值算法之一，其中創(chuàng)建了給定線性問(wèn)題的層次結(jié)構(gòu)[13]。通過(guò)迭代更新，分別在細(xì)網(wǎng)格和粗網(wǎng)格上迅速衰減求解錯(cuò)誤的高頻分量與低頻分量，從而提高多重網(wǎng)格的效率。經(jīng)過(guò)適當(dāng)設(shè)計(jì)，多重網(wǎng)格方法可以實(shí)現(xiàn)未知數(shù)線性復(fù)雜度。由于GPU 片上共享內(nèi)存有限，因此多重網(wǎng)格的分層迭代性質(zhì)對(duì)GPU 平臺(tái)具有較為重要的意義[14]。多網(wǎng)格方法通常分為兩類：幾何多網(wǎng)格（GMD）和代數(shù)多網(wǎng)格（AMG）[15]。若可以利用問(wèn)題的特定幾何結(jié)構(gòu)，則AMG 可以被認(rèn)為是一種魯棒的黑箱方法[16]，雖然初始化代價(jià)較大，但GMD 可以更有效率地實(shí)現(xiàn)。該次的多重網(wǎng)格關(guān)鍵操作包括：

1）平滑：采用迭代方法Gauss-Seidel 來(lái)緩解網(wǎng)格上的求解誤差；

2）限制：從細(xì)網(wǎng)格映射到下一個(gè)較粗網(wǎng)格（用于將細(xì)網(wǎng)格殘差映射到粗網(wǎng)格）；

3）延長(zhǎng)：從粗網(wǎng)格到下一個(gè)較細(xì)網(wǎng)格的映射（用于將粗網(wǎng)格解映射到細(xì)網(wǎng)格）；

4）校正：使用映射的粗網(wǎng)格解決方案來(lái)校正細(xì)網(wǎng)格解決方案。

在具有vk初始解的第k級(jí)網(wǎng)格上，多網(wǎng)格循環(huán)MG(k,vk)步驟如下：

1）應(yīng)用預(yù)平滑更新解決方案；

2）計(jì)算第k個(gè)網(wǎng)格上的殘差，并通過(guò)限制將其映射到第k+1 個(gè)粗網(wǎng)格；

3）若達(dá)到最粗糙的水平，則使用映射的殘差直接求解第k+1 個(gè)網(wǎng)格；否則，初始估計(jì)為0；

4）通過(guò)延長(zhǎng)將解vk+1映射到第k個(gè)網(wǎng)格，并通過(guò)添加vk+1校正解vk；

5）應(yīng)用平滑，進(jìn)一步改善第k級(jí)網(wǎng)格的vk并返回最終的vk。

該次開(kāi)發(fā)了特定于GPU的GMD 方法。從規(guī)則化的電網(wǎng)開(kāi)始，在整個(gè)多重網(wǎng)格層次結(jié)構(gòu)中以幾何規(guī)則的方式實(shí)現(xiàn)多重網(wǎng)格的所有關(guān)鍵組件，從而實(shí)現(xiàn)簡(jiǎn)單的流控制和高度規(guī)則的內(nèi)存訪問(wèn)模式[17-18]。

2.2 混合多重網(wǎng)格迭代

使用該次建立的GMD 方法（如圖2 所示）可以有效地解決近似規(guī)則的電網(wǎng)問(wèn)題，而無(wú)需進(jìn)行顯式的稀疏矩陣矢量運(yùn)算。

圖2 GMD方法

為了保證最終電網(wǎng)解決方案的準(zhǔn)確性，其在GPU 與主機(jī)之間進(jìn)一步應(yīng)用了HMD 迭代，以消除僅解決近似規(guī)則網(wǎng)格可能引起的任何錯(cuò)誤。用GridO表示真實(shí)的數(shù)據(jù)網(wǎng)，用GridR表示正則化的電網(wǎng)，HMD 迭代涉及以下主要步驟：

1）在CPU 中計(jì)算GridO上當(dāng)前解決方案的殘差，并將其殘差映射到GridR。

2）在GPU 中使用GMD 解決映射殘差下的GridR問(wèn)題，并將解決方案返回給GridO。

3）在CPU 中 使 用GPU 結(jié)果更新GridO解決方案，并應(yīng)用其他平滑處理。

4）在CPU 中，若解決方法錯(cuò)誤足夠小，則退出運(yùn)算；否則，重復(fù)上述步驟。

HMD 方法的大量工作通過(guò)解決常規(guī)網(wǎng)格（即步驟2）在GPU 上完成，僅在主機(jī)上執(zhí)行例如簡(jiǎn)單的殘差計(jì)算、平滑步驟等工作。在此方面，通用CPU 在處理原始（不規(guī)則）數(shù)據(jù)的效率更高。

3 實(shí)驗(yàn)驗(yàn)證

為證明文中電網(wǎng)工程造價(jià)分析系統(tǒng)的性能，使用一組工業(yè)電網(wǎng)工程造價(jià)基準(zhǔn)來(lái)比較5 個(gè)求解器：基于GPU 加速的分析求解器（GPU GMD）、相同算法基于CPU的實(shí)現(xiàn)方案（CPU GMD）、基于GPU 加速的混合求解器（GPU HMD）、相同算法的CPU 實(shí)現(xiàn)方案（CPU HMD）以及基于CPU的直接稀疏矩陣求解器CHOLMOD，進(jìn)行對(duì)比實(shí)驗(yàn)。所有算法均使用C++和GPU 編程接口CUDA 實(shí)現(xiàn)，測(cè)試硬件平臺(tái)是一臺(tái)Linux 計(jì)算機(jī)，其CPU 主頻為3.0 GHz，帶有NIVDIA GeForce 8800 Ultra GPU 圖像處理器。

實(shí)驗(yàn)結(jié)果如表1 所示，當(dāng)實(shí)時(shí)殘?jiān)_(dá)到初始?xì)堅(jiān)?.1%（HMD 迭代時(shí)取為0.5%）時(shí)，將終止GMD解算器。當(dāng)平均節(jié)點(diǎn)電壓誤差小于0.5 mV 時(shí)，將停止HMD 解算器。分析可知，GPU GMD 和GPU HMD較CHOLMOD 快100～350 倍；GPU GMD的速度比CPU GMD 快20 倍；而GPU HMD的速度比CPU HMD快16 倍。此外，使用不同數(shù)量的HMD 迭代時(shí)，多一次迭代可以顯著提高精度。對(duì)于大多數(shù)基準(zhǔn)測(cè)試，GPU HMD 產(chǎn)生的平均節(jié)點(diǎn)電壓誤差小于0.5 mV，最大節(jié)點(diǎn)電壓誤差小于5 mV。

表1 五種求解器對(duì)比實(shí)驗(yàn)

GPU 內(nèi)存訪問(wèn)時(shí)，若算法執(zhí)行不當(dāng)，則延遲可能占據(jù)主導(dǎo)地位。圖3 顯示了所有工業(yè)基準(zhǔn)電路的純GPU 計(jì)算時(shí)間與總GPU 運(yùn)行時(shí)間（計(jì)算時(shí)間+存儲(chǔ)器讀/寫(xiě)時(shí)間）和比率。從圖3 可以觀察到，純粹的計(jì)算時(shí)間只能占總運(yùn)行時(shí)間的一小部分（15%～60%），對(duì)SIMT 平臺(tái)使用更多的本地LBJ 迭代可以更優(yōu)地減少內(nèi)存訪問(wèn)延遲。但進(jìn)行過(guò)多局部迭代所產(chǎn)生的收益并不理想，原因在于其無(wú)法解決GMD的整體求解問(wèn)題。因此，應(yīng)選擇合理的局部迭代次數(shù)k以在松弛運(yùn)行時(shí)間與全局收斂速度之間進(jìn)行權(quán)衡。

圖3 GPU運(yùn)算時(shí)間比

此外，文中在CPU 與GPU 上均運(yùn)行了500 個(gè)平滑步驟。如圖4（a）所示，GPU GMD 引擎的CPU 提速達(dá)到其18～32 倍速。在GPU 和CPU 上比較了多個(gè)周期的SIMT 解決方案運(yùn)行時(shí)間，如圖4（b）所示，文中的SIMT 實(shí)現(xiàn)了對(duì)小網(wǎng)格約10 倍的加速，對(duì)大網(wǎng)格約20 倍的加速。

圖4 分析引擎提速實(shí)驗(yàn)

圖5 顯示了4 個(gè)常見(jiàn)解決方案誤差與該方案迭代次數(shù)的對(duì)比結(jié)果。在兩次或三次HMD 迭代后，該方案可以迅速地衰減所有4 種平均誤差。

圖5 誤差衰減實(shí)驗(yàn)

使用該次設(shè)計(jì)的電網(wǎng)工程造價(jià)數(shù)據(jù)分析系統(tǒng)，建筑能源的使用減少了20%：優(yōu)化前為212 kWh/(m2·a)，優(yōu)化后為168 kWh/(m2·a)；優(yōu)化后的已交付能源使用量為216 kWh/(m2·a)。經(jīng)算法優(yōu)化后，建筑空間的供暖需求減少了約49%，用于加熱生活用水的交付能源需求減少了約40%。

4 結(jié)束語(yǔ)

文中通過(guò)開(kāi)發(fā)圖形處理單元加速引擎，來(lái)解決大規(guī)模電網(wǎng)系統(tǒng)的造價(jià)數(shù)據(jù)分析。為了在GPU 上獲得良好的運(yùn)算分析效率，將不規(guī)則的網(wǎng)格轉(zhuǎn)換為規(guī)則的結(jié)構(gòu)，以消除大多數(shù)隨機(jī)存儲(chǔ)器訪問(wèn)模式并簡(jiǎn)化控制流程。為了正確利用大規(guī)模并行單指令多線程（SIMT）GPU 體系結(jié)構(gòu)，文中設(shè)計(jì)了并行幾何多網(wǎng)格算法。通過(guò)采用新的粗網(wǎng)格結(jié)構(gòu)和塊平滑策略，以更加適配SIMT GPU 平臺(tái)。該算法的魯棒性通過(guò)CPU-GPU 混合多網(wǎng)格迭代方案增強(qiáng)。實(shí)驗(yàn)表明，該GPU 引擎可以在直接求解器上實(shí)現(xiàn)超過(guò)100 倍的運(yùn)行加速，且較基于CPU的多網(wǎng)格求解器快15 倍，能夠?qū)崿F(xiàn)對(duì)電網(wǎng)工程造價(jià)數(shù)據(jù)的準(zhǔn)確、快速分析。