李億淵 ，穆清 ，薛巍

(1.清華大學(xué) 計算機科學(xué)與技術(shù)系，北京 100084；2.中國電力科學(xué)研究院，北京 100192)

0 引言

近年來我國經(jīng)濟不斷發(fā)展，社會對能源的需求不斷上升，電力的消耗也隨之上升。我國電網(wǎng)的特高壓工程持續(xù)投運以滿足日益增長的用電負荷需求。電力系統(tǒng)整體規(guī)模的擴大也給整個系統(tǒng)的穩(wěn)定和可靠運行帶來了更高的安全風(fēng)險。

電力系統(tǒng)仿真是分析電網(wǎng)特征、分析電網(wǎng)穩(wěn)定性最重要的量化手段。電力系統(tǒng)仿真分為穩(wěn)態(tài)仿真和動態(tài)仿真兩類。動態(tài)仿真更關(guān)注電力系統(tǒng)的動態(tài)變化行為，主要包括機電暫態(tài)和電磁暫態(tài)兩種。電磁暫態(tài)仿真建模更加精細，是動態(tài)安全評估的重要工具。通過電磁暫態(tài)仿真，研究人員能更好地理解電網(wǎng)在實際運行中的工作狀態(tài)及其變化，從而在運行中有效調(diào)整控制方案，確保電力系統(tǒng)的安全、穩(wěn)定運行。

電磁暫態(tài)是指電磁從一個穩(wěn)定狀態(tài)到另一個穩(wěn)定狀態(tài)中所經(jīng)歷的過程。在電力系統(tǒng)運行過程中，通常由于電子元件的開關(guān)切換、偶發(fā)的交直流故障以及雷擊等干擾，造成電磁暫態(tài)過程的快速變化[1]。模擬電磁暫態(tài)現(xiàn)象一般通過電力系統(tǒng)的時域建模來完成。其目標是求出系統(tǒng)中各個時刻所有節(jié)點的電壓值和電流值，核心算法是將連續(xù)的微分系統(tǒng)離散化，并使用迭代法隱式求解。仿真步長代表離散時間點間隔，步長越短就能模擬更高頻的電網(wǎng)行為，故步長大小是衡量電磁暫態(tài)仿真系統(tǒng)質(zhì)量的重要指標。

根據(jù)仿真平臺計算所需時間和步長的大小關(guān)系，電力系統(tǒng)仿真又被分為離線仿真和硬實時仿真兩種。離線仿真可以通過更長的計算時間得到單位時間中精準的計算結(jié)果，但較長的計算時間也限制了其應(yīng)用場景。而實時仿真的應(yīng)用場景更廣，但為了能和真實電網(wǎng)保持同步運轉(zhuǎn)，仿真程序的步長越小，計算負載也越大，想單單依靠通用處理器完成仿真有著不小的挑戰(zhàn)[2]。

進一步，現(xiàn)代電力電子技術(shù)的發(fā)展也給電磁暫態(tài)仿真的實現(xiàn)提出了新的挑戰(zhàn)。近年來電力系統(tǒng)中開始大量使用可再生新能源元件[3]，區(qū)域間電網(wǎng)互聯(lián)水平大幅提升，總電網(wǎng)規(guī)模不斷擴大[4-6]，電力電子設(shè)備被頻繁應(yīng)用在電網(wǎng)系統(tǒng)中[7-9]。這些都導(dǎo)致電力系統(tǒng)的規(guī)模和復(fù)雜性顯著上漲。同時，大量電力電子設(shè)備通常伴隨著高頻的開關(guān)切換，為了依舊能對電力系統(tǒng)進行準確的仿真，電力系統(tǒng)電磁暫態(tài)仿真的步長越變越小[10]。這就需要充分挖掘計算平臺的性能才能滿足實時計算需求。

計算硬件的發(fā)展也同樣給仿真算法的設(shè)計與優(yōu)化提出挑戰(zhàn)。隨著摩爾定律持續(xù)的放緩，集成電路特征尺寸的縮小愈發(fā)困難，單個通用處理器的計算性能增幅也很難維持十年前的趨勢。計算平臺只能走向多核、眾核、異構(gòu)等架構(gòu)。雖然總計算性能繼續(xù)得以增長[11-15]，但與此同時應(yīng)用通信性能卻隨著非一致性內(nèi)存訪問(Non-Uniform Memory Access，NUMA)架構(gòu)的廣泛使用呈現(xiàn)層次化趨勢。圖1 為鯤鵬920 處理器的節(jié)點示意圖，圖中標出了跨不同NUMA 層時兩處理器核MPI 點對點通信的延遲情況，可以看到隨著兩處理器核間跨越的NUMA層數(shù)越多，其通信延遲越大。這就要求在算法相對固定的前提下任務(wù)到處理器核的映射更為合理，使更多的通信發(fā)生在同NUMA 內(nèi)，盡可能減少通信延遲對仿真性能的影響。同時復(fù)雜的硬件通信延遲問題也給子網(wǎng)劃分提出了更高的要求[16]。

圖1 鯤鵬920 核間通信延遲示意圖

本文針對中國電力科學(xué)研究院自研電磁暫態(tài)仿真系統(tǒng)(Advanced Digital Power System Simulator，ADPSS)[17]，提出了一種電磁暫態(tài)任務(wù)劃分與映射算法，最大限度地降低通信延遲與抖動，提高仿真性能。該算法利用兩階段優(yōu)化方法，將子網(wǎng)計算時間、子網(wǎng)間通信量、多NUMA層間不同的通信性能統(tǒng)一納入考慮，并設(shè)計了多規(guī)模不等子圖最小割算法，有效解決了子網(wǎng)在集群節(jié)點資源不對稱情況下的任務(wù)優(yōu)化映射問題，并在華東和西北真實電網(wǎng)算例上進行模擬性能測試。在目前ADPSS 真實運行中，計算集群由于需配合FPGA 進行異構(gòu)加速，原本8節(jié)點、每節(jié)點28 核的集群只剩下150 核可用，且不均勻地分散在8 節(jié)點上，在子網(wǎng)計算規(guī)模較大的西北算例上，計算性能已無法滿足75 μs 的實時仿真步長。而本文算法較ADPSS 默認劃分與映射算法取得了平均40%和50%的通信性能提升，平均10%和12%的總體計算性能提升，且所有算例均可滿足實時步長需求。

1 ADPSS 介紹

隨著特高壓交直流電網(wǎng)發(fā)展，國家電網(wǎng)公司于2009 年建成了國家電網(wǎng)仿真中心，并由中國電力科學(xué)研究院研發(fā)了基于高性能集群的電力系統(tǒng)全數(shù)字仿真裝置ADPSS。

ADPSS 實現(xiàn)交流大電網(wǎng)連多回直流輸電系統(tǒng)的數(shù)?；旌戏抡?，即該仿真系統(tǒng)中包括了數(shù)字模擬電網(wǎng)，同時又包括了真實的控制保護裝置，為確保實際控制保護裝置能正確運行，數(shù)字電網(wǎng)需要和真實電網(wǎng)保持同步運轉(zhuǎn)。故此系統(tǒng)為硬實時系統(tǒng)，數(shù)字電網(wǎng)的單時步計算時間需永遠小于真實電網(wǎng)單步時間。

數(shù)?；旌戏抡嬗袃蓚€主要作用。一是通過數(shù)字電網(wǎng)模擬真實電網(wǎng)，在該場景下測試實際控制保護裝置自身工作是否正常，能否真正接入真實電網(wǎng)使用。二是部分實際控制保護裝置結(jié)構(gòu)復(fù)雜，無法直接在數(shù)字系統(tǒng)中建模，必須使用數(shù)字系統(tǒng)加控制保護裝置共同準確描述電網(wǎng)真實特性，如此一來就能基于準確的電網(wǎng)和設(shè)備模型來研究真實電網(wǎng)中出現(xiàn)故障后的運行特點，防患于未然。所以能否對更大規(guī)模的電磁暫態(tài)網(wǎng)絡(luò)進行仿真，直接決定對真實電網(wǎng)進行模擬與研究的能力。

為了應(yīng)對更大規(guī)模電網(wǎng)電磁暫態(tài)實時仿真需求，對仿真系統(tǒng)提出了更高的性能要求，并行求解變成了必不可少的一環(huán)。ADPSS 提供了節(jié)點分裂分網(wǎng)和傳輸線分網(wǎng)兩種并行方案。節(jié)點分裂分網(wǎng)算法需要子網(wǎng)統(tǒng)一到主控節(jié)點進行求解[18-19]，而根據(jù)傳輸線劃分得到的子網(wǎng)間在同一時步內(nèi)沒有耦合關(guān)系，不需要統(tǒng)一求解。對于大規(guī)模交直流電網(wǎng)的實時仿真系統(tǒng)而言，節(jié)點分裂的方式雖然更加靈活，但會帶來更多的固有串行計算部分，當(dāng)分網(wǎng)斷面較多時，串行計算會嚴重影響仿真的實時性。而基于傳輸線分網(wǎng)可以讓整個網(wǎng)絡(luò)解耦成為很多子網(wǎng)，每一個子網(wǎng)之間沒有導(dǎo)納陣上的耦合聯(lián)系，只有信號量的交互。相互交互的信號量自然延遲一個時步，天然并行。故為了確保大規(guī)模仿真計算的有效性，ADPSS 采用了傳輸線分網(wǎng)的并行方案。

如上所述，傳輸線分網(wǎng)并行方案中交流大電網(wǎng)首先會被分割成多個解耦的小網(wǎng)絡(luò)。小網(wǎng)數(shù)量往往遠大于并行計算機的處理器核數(shù)，因此需要對小網(wǎng)進行融合完成任務(wù)劃分。ADPSS 系統(tǒng)中配套了以不同子網(wǎng)間電器元件數(shù)量均衡為目標的自動分網(wǎng)程序：該程序先根據(jù)長傳輸線位置將電網(wǎng)分至最小網(wǎng)絡(luò)狀態(tài)，并把它們按元件數(shù)量從大到小排序。再使用貪心的策略將它們合并至指定個數(shù)(總處理器核數(shù))。

在完成分網(wǎng)后，在每個進程上的計算則相對固定，其流程如下：

(1)各子網(wǎng)計算基于LU 分解矩陣的前代和回代的求解；

(2)各子網(wǎng)(進程)間通信，傳輸分網(wǎng)線路上的端口電壓、電流和控制系統(tǒng)的交互量，此處只完成發(fā)送操作；

(3)各子網(wǎng)計算每一個元件狀態(tài)；

(4)等待各元件(含外部元件)返回的結(jié)果，即接收第(2)步中的通信數(shù)據(jù)；

(5)數(shù)據(jù)收齊后進入下一時步，重新回到第(1)步。

在以上5 步中，步驟(1)和步驟(3)的計算時間相對穩(wěn)定，且計算所需時間與真實小網(wǎng)中電子元件有關(guān)，無法進一步縮短，只有步驟(2)和步驟(4)中的通信性能可能進一步優(yōu)化，同時也成為了性能瓶頸。而通信量也和小網(wǎng)中電子元件相關(guān)，可優(yōu)化幅度有限，如何更好地映射進程，將每條通信更合理地分配在不同NUMA 層間，成為優(yōu)化關(guān)鍵。

同時ADPSS 面臨的仿真規(guī)模越來越大，需要越來越大規(guī)模的計算設(shè)備才能有效完成實時仿真的問題。當(dāng)跨不同NUMA 間通信性能差異越來越大，此時原有自動分網(wǎng)程序只針對電器元件數(shù)量均衡為目標的優(yōu)化算法和默認進程映射方案就會出現(xiàn)性能不足的問題。同時，這種通信容易出現(xiàn)性能抖動，使整個硬實時仿真失效。

同時，交直流混合電磁暫態(tài)仿真計算也需要更復(fù)雜的異構(gòu)硬件來支持。為了對外接口以及提高性能，ADPSS 在硬件架構(gòu)上整合了現(xiàn)場可編程邏輯門陣列(Field Programmable Gate Array，F(xiàn)PGA)，導(dǎo)致部分集群計算節(jié)點的處理器核需配合FPGA 計算，無法參與仿真。因此，集群節(jié)點層面存在不同節(jié)點上的可用核數(shù)不同的問題。如圖2 所示，其中每個小圈代表一個處理器核，核內(nèi)顯示了該核是否可用。顯然如此分配的16 核比集中在2 個節(jié)點上的16 個核更難于映射，容易在節(jié)點間暴露更多的通信量，這就對仿真任務(wù)的映射提出了更高的要求。

圖2 節(jié)點資源異構(gòu)示意圖

針對以上需求，ADPSS 遇到的問題是如何自動劃分、合并子網(wǎng)，如何在考慮節(jié)點資源異構(gòu)的前提下更合理地將子網(wǎng)映射到處理器核上進行計算，使性能最佳。

2 ADPSS 的任務(wù)劃分與映射需求

根據(jù)第1 節(jié)介紹，ADPSS 需要優(yōu)化算法完成的工作如圖3 所示。從傳輸線分網(wǎng)后的小網(wǎng)開始，將其合并至特定個數(shù)子網(wǎng)(圖3(b)中同種數(shù)字小網(wǎng)合并)，并映射至處理器核(圖3(c)中代表每個處理器核的狀態(tài)，不可用或計算某個子網(wǎng)任務(wù))。

圖3 小網(wǎng)劃分、子網(wǎng)映射算法工作流程示意圖

針對上述目標，分網(wǎng)問題可以看作一個優(yōu)化問題。該問題的輸入為全部小子網(wǎng)的信息(計算成本、對外連接情況等)，目標為將子網(wǎng)聚合成與計算核數(shù)相等個子網(wǎng)，并映射在對應(yīng)核上，在運行時每步抖動不超過閾值的情況下，盡可能快。

給出如下問題定義：

無向圖GO=(VO，EO)，VO為點集，EO為邊集，代表最小子網(wǎng)狀態(tài)下各子網(wǎng)的連接狀態(tài)。|VO|=NO為子網(wǎng)總數(shù)，|EO|=MO為子網(wǎng)間通信邊數(shù)，集合CalcO={Calc1，Calc2，…，CalcNO}為每子網(wǎng)的計算時間，計算時間可由子網(wǎng)中每種電子元件計算時間累加近似得到或者實測得到。WO(u，v)=CommWO(u，v)代表子網(wǎng)節(jié)點u、v 間存在一條通信量為CommWO(u，v)的通信邊，即EO={WO1，WO2，…，WOMO}。

無向圖GP=(VP，EP)，VP為點集，EP為邊集，代表子網(wǎng)合并后各子網(wǎng)的連接狀態(tài)。|VP|=NP為子網(wǎng)總數(shù)，|EP|=MP為子網(wǎng)間通信邊數(shù)，集合CalcP={Calc1，Calc2，…，CalcNP}為每子網(wǎng)的計算時間，計算時間由合并至此子網(wǎng)中每個小網(wǎng)計算時間累加得到，假設(shè)為原始小網(wǎng)X、Y 合并為子網(wǎng)Z，則：

其中f(CommW(X，Y))為合并W(X，Y)的代價，由小網(wǎng)X、Y間傳輸線的組成決定。WP(u，v)=CommWP(u，v)代表合并后子網(wǎng)節(jié)點u、v 間存在一條通信量為CommWP(u，v)的通信邊，即EO={WP1，WP2，…，WPMP}在合并后對應(yīng)邊權(quán)疊加即可。

無向圖GD=(VD，ED)，VD為點集，ED為邊集，代表無向圖GP中的子網(wǎng)映射在計算節(jié)點上的狀態(tài)。|VD|=ND=NP為總處理器核心數(shù)，|ED|=|EP|=MP，代表子網(wǎng)間通信實際在計算硬件上的通信鏈路。WD(u，v)=CommWD(u，v)代表處理器核u、v間存在一條通信延遲為CommWD(u，v)的邊，代表當(dāng)某兩個子網(wǎng)被映射在處理器核U 和V 上時，子網(wǎng)間的通信延遲為多少。S 為硬件集群節(jié)點數(shù)，Ci為i 號節(jié)點上的可用核數(shù)，。

上述優(yōu)化問題的目標為將圖GO合并為圖GP，并將GP中的子網(wǎng)映射在GD上。為了使抖動盡可能低，需要跨節(jié)點通信量盡可能低，同時每步的計算時間盡可能低。下面，將介紹一種兩階段的優(yōu)化方案，即先完成GO到圖GP的子圖劃分，再考慮GP到GD的任務(wù)映射。

3 基于貪心策略和最小割圖劃分的兩階段優(yōu)化算法

3.1 基于貪心策略的小網(wǎng)劃分算法

根據(jù)ADPSS 算法流程可知，通信需要在第一步LU分解完成后才能開始，而第三步中電子元件的計算時間又遠小于LU 分解，故每時步時間可近似看作LU 的計算時間加通信時間。LU 計算時間越小，就能越早開始通信，更早地完成時步的計算。而硬實時仿真需要每個子網(wǎng)永遠都能在預(yù)設(shè)的時間內(nèi)完成一步仿真，換個角度看，即需要所有子網(wǎng)中每時步所需時間最長的子網(wǎng)，能永遠在閾值時間內(nèi)完成，即可滿足要求。根據(jù)以上分析，可得子網(wǎng)合并的優(yōu)化目標：使計算時間最大的子網(wǎng)，計算時間盡可能小。

同時根據(jù)式(1)定義可知，任意兩節(jié)點合并，可使全圖總邊權(quán)下降，同時總計算時間上升，即對最小割圖劃分有益，而對盡可能小的計算時間有害。因此每次合并的策略很明確：使每次合并后得到的新子網(wǎng)時間，是當(dāng)前所有滿足合并條件的子網(wǎng)對中最小的，這樣無論從總計算時間上考慮，還是從單個子網(wǎng)計算時間上考慮，都是計算時間增長最小的。

根據(jù)上述思想可直接得到貪心算法：每次遍歷邊集EO，計算合并每一對WO(u，v)子網(wǎng)后得到的新子網(wǎng)計算時間Calcp=CalcUO+CalcVO+f(CommW(U，V))，并找出此步內(nèi)最小的Calcp，并合并所對應(yīng)的子網(wǎng)U 和V。重復(fù)該策略多次，直至合并后的子網(wǎng)數(shù)等于總處理器核心數(shù)NP。

3.2 基于最小割算法的計算節(jié)點核數(shù)不對稱問題的映射優(yōu)化

3.2.1 最小割算法建圖分析

在上述劃分完成的圖GP基礎(chǔ)上，由于計算處理器規(guī)格相同，電磁暫態(tài)仿真計算時間相對固定，核心是通過進程映射實現(xiàn)通信性能盡可能優(yōu)化。

基于進程映射的通信優(yōu)化主要有兩方面：

(1)進程間MPI 通信可以使用節(jié)點內(nèi)共享內(nèi)存通信，性能較節(jié)點間更優(yōu)。同時，電磁暫態(tài)仿真的通信量僅僅是子網(wǎng)邊界的節(jié)點信息，總量相對較低，帶寬競爭問題較少。因此，要保證盡可能多的通信是在同一個計算節(jié)點內(nèi)發(fā)生，使用共享內(nèi)存通信方式，讓更少的通信通過性能不佳且容易出現(xiàn)抖動的跨節(jié)點MPI 進程通信接口完成。這一策略的優(yōu)化目標可以直接將通信量看為圖上的邊權(quán)，直接選擇圖上的最小割算法完成。

(2)盡可能讓容易抖動的跨節(jié)點核間通信與計算時間較長子網(wǎng)的計算同時進行。利用計算通信重疊，掩藏掉核間通信的時間和抖動。如果每時步最后完成的時刻為計算時間最長子網(wǎng)完成計算，并通過節(jié)點內(nèi)完成通信的時間，其他子網(wǎng)間通過節(jié)點間通信的時間就會被完全覆蓋，無需擔(dān)心性能抖動帶來的影響。完成這一目標，不能簡單地將通信量作為邊權(quán)并求最小割。如圖4 所示，有3 個子網(wǎng)，子網(wǎng)1 的計算時間最長，子網(wǎng)1、2，子網(wǎng)2、3 間各有一條通信，且子網(wǎng)2、3 間的通信量更大。3個子網(wǎng)需分在2 個節(jié)點上計算，如果直接按通信量劃分，則會將子網(wǎng)2、3 映射在一個節(jié)點內(nèi)，如圖4(a)所示，雖然更大的通信量得以更高效的完成，但當(dāng)子網(wǎng)1 計算完畢后，需要通過更低效的核間通信完成與子網(wǎng)2 的數(shù)據(jù)交換，使得最終的完成時間被進一步拖慢。而如果能將計算通信重疊納入考慮，將子網(wǎng)1、2 映射在一個節(jié)點內(nèi)，雖然子網(wǎng)2、3 間更大的通信需要花費更長的時間完成，但這些通信時間都被子網(wǎng)1 的計算所覆蓋了，而當(dāng)子網(wǎng)1 完成計算后，可以通過高效的節(jié)點內(nèi)通信迅速完成與子網(wǎng)2 的數(shù)據(jù)交換，使得整體時間更短。

圖4 計算通信重疊示意圖

基于上面的思路，對邊權(quán)EP的定義進行調(diào)整，將邊權(quán)CommWP(u，v)定義為：

其中，α 為硬件通信抖動系數(shù)，α 需在不同平臺上通過點對點和模擬真實Mesh 場景的MPI 基準測試得到。每條邊權(quán)代表的意義由原來的通信延遲，變成每步內(nèi)完成該邊通信的最晚時刻，通信開始的時間為映射在兩側(cè)核上子網(wǎng)的計算時間的較大值，而通信取最壞情況下抖動上限，CommWP(u，v)取跨多NUMA 層通信時性能的最大值。

通過建圖，就將子網(wǎng)本身的通信與計算集群的通信性能相結(jié)合，子網(wǎng)到計算核的映射問題，就轉(zhuǎn)化成了經(jīng)典的圖劃分問題，計算集群有幾個計算節(jié)點、每個節(jié)點中有幾個處理器核，對應(yīng)圖劃分問題中將原圖劃分為幾個子圖，各個子圖中有幾個圖節(jié)點。圖劃分的割邊之集總和越小，跨節(jié)點通信的總邊權(quán)就越小。下面幾節(jié)將介紹如何解決在已建完的圖上求出一個子圖規(guī)模不等的最小割劃分，只要得到最小割圖劃分，就能對應(yīng)得到子網(wǎng)到計算節(jié)點的映射關(guān)系。

3.2.2 基于KERNIGHAN-LIN ALGORITHM 算法的規(guī)模不等子圖最小割算法

為了解決上述圖的最小割劃分問題，本文選擇使用KERNIGHAN-LIN ALGORITHM 算法[20](后續(xù)簡稱KL 算法)，使用遞歸分支的策略將圖逐層劃分至最終目標。

傳統(tǒng)的KL 算法只能解決將圖劃分成兩個大小均等的子圖。根據(jù)第2 節(jié)中優(yōu)化問題的定義，在本文優(yōu)化需求下，計算子網(wǎng)映射到的計算節(jié)點是資源異構(gòu)的，即每個計算節(jié)點上的可用處理器核數(shù)不盡相同。從圖劃分角度看，即為將全圖劃分成若干個大小不同的子圖，使割邊之和盡可能小且最長計算時間最小。要解決這個優(yōu)化問題，就需要對原始的KL 算法做調(diào)整。

下面將先分別解決兩個子問題：(1)劃分成二的冪次個大小相等的子圖；(2)劃分成兩個大小不等的子圖。再使用劃歸的思想將這兩個子問題的解決方案合并，實現(xiàn)劃分成若干個大小不等的子圖，得到最終的最小割算法。

3.2.3 劃分二的冪次個大小相等子圖的最小割算法

該子問題對應(yīng)真實場景中不使用計算資源異構(gòu)的情況，即每顆處理器上能使用的核數(shù)都是相等的，映射到每個處理器節(jié)點上的子網(wǎng)數(shù)是相等的。

假設(shè)需要將圖劃分成S=2n大小相等的子圖，直觀地，可以通過n 輪的遞歸分治，將原圖劃分為S 部分。即先通過KL 算法將原圖劃分為2 個均勻子圖，再分別對這2 個子圖使用KL 算法，將它們劃分為4 個大小均等的子圖，以此類推。總共通過調(diào)用S-1 次KL 算法即可完成劃分。需要注意的是，如果每次遞歸劃分都是在不同NUMA 層上，需要根據(jù)當(dāng)前情況下的最大通信延遲調(diào)整圖中的邊權(quán)。如圖1 中，假設(shè)第一次劃分代表將子網(wǎng)映射在socket0 還是socket1 上，而具體在哪個NUMA 上并不由該次劃分決定，則邊權(quán)中通信延遲取48 μs；當(dāng)?shù)诙嗊f歸劃分，決定已經(jīng)在socket0 上的子網(wǎng)，是映射在numa0還是numa1 上時，需要將邊權(quán)按通信延遲27 μs 調(diào)整。

但是，KL 算法是隨機設(shè)定初值的算法，仍需要通過多次運行取最優(yōu)的方式來找到盡可能優(yōu)的全局解。針對遞歸的計算模式，可以選擇直接將整個遞歸過程運行若干次取最優(yōu)，也可以在每層遞歸調(diào)用的KL 內(nèi)部，運行多次隨機，取最優(yōu)。在本文實現(xiàn)中，選取的是每次遞歸調(diào)用KL 時都運行多次的方案，運行10 000 次。

3.2.4 劃分兩個規(guī)模不等子圖的最小割算法

假設(shè)圖中有N 個節(jié)點，需要劃分成分別包含N1和N2個節(jié)點的子圖N=N1+N2。

利用化歸的思想，可以通過向圖中添加虛擬節(jié)點的方式，把問題變成劃分成兩個大小相等的子圖進行求解。具體方案如圖5 所示。

設(shè)N1>N2，則向圖中添加N1-N2個虛擬節(jié)點，并讓它們?nèi)B接，并把邊權(quán)設(shè)置為無窮大，這樣在劃分過程中這些虛擬節(jié)點必然不會被劃分開。接著對這個包含了N+N1-N2個節(jié)點的圖調(diào)用KL 算法。算法為了保證劃分得到的兩個子圖大小相等，這N1-N2個虛擬節(jié)點必然會和N2個原圖節(jié)點分在一組形成一個擁有N1個節(jié)點的子圖，與另一個包含N1個原圖節(jié)點的子圖大小相等。圖5展示了當(dāng)N=8，N1=6，N2=2 時的添加虛擬節(jié)點、劃分的過程，先添加了4 個全連接的虛擬節(jié)點(用正方形表示，以方便區(qū)分)，后正常劃分為均包含6 個節(jié)點的子圖。

圖5 KL 算法不均等二分示意圖

3.2.5 劃分若干個規(guī)模不等的子圖的最小割算法

假設(shè)需要將圖劃分成S 個大小不等的子圖，子圖大小為N1N2…NS。

首先解決S=2n的情況。同樣利用遞歸分治的策略，先將圖劃分成兩個子圖，并將前一半子圖節(jié)點之和作為第一個子圖的節(jié)點個數(shù)，后一半子圖節(jié)點之和作為第二個子圖的節(jié)點個數(shù)。即定義Nx=N1+N2+…+N0.5S-1，Ny=N0.5S+N0.5S+1+…+NS，設(shè)Nx≥Ny，則在圖中添加Nx-Ny個虛擬節(jié)點，并調(diào)用KL 算法進行圖劃分。依此類推，直至劃分完成。圖6 為假設(shè)S=4，N1=1，N2=2，N3=2，N4=3 時的示意圖。

圖6 KL 算法不均等2 的冪次劃分示意圖

其次，解決S≠2n的情況。同樣按遞歸分治的方法逐層劃分，唯一的區(qū)別是當(dāng)某次劃分時需要劃出的子圖數(shù)無法被2 整除時，需要額外處理。假設(shè)S mod 2≡1，定義Nx為前(S+1)·0.5 個子圖的節(jié)點之和，Ny為(S-1)·0.5 個子圖的節(jié)點之和，設(shè)Nx≥Ny，則同樣在圖中添加Nx-Ny個虛擬節(jié)點并調(diào)用KL 進行劃分，則可以正常將原圖分為包含(S+1)·0.5和(S-1)·0.5個子圖的子圖。依次類推，即可劃分得到所有S 個子圖。圖7 為假設(shè)S=5，N1=1，N2=2，N3=1，N4=1，N5=3 時的示意圖。

圖7 KL 算法若干不均子圖劃分示意圖

通過上述最小割算法構(gòu)建，只要將需要圖信息、需要劃分至幾個子圖、每個子圖上有多少個節(jié)點作為算法輸入，就能得到以最小割為目標的可行解。對應(yīng)真實場景下，只要將劃分完成的子網(wǎng)信息、計算集群節(jié)點資源信息輸入，就能得到子網(wǎng)到處理器核的映射關(guān)。

3.3 兩階段優(yōu)化算法總結(jié)

優(yōu)化算法的完整流程如圖8 所示。在運行ADPSS前，先將傳輸線劃分后的小網(wǎng)數(shù)據(jù)和集群計算資源的可使用情況輸入給優(yōu)化程序，小網(wǎng)數(shù)據(jù)包括每個子網(wǎng)內(nèi)電子元件數(shù)據(jù)和子網(wǎng)間的通信關(guān)系。優(yōu)化程序會運行一遍子網(wǎng)劃分的貪心算法，再根據(jù)用戶指定的迭代次數(shù)，運行若干次最小割算法，保留最優(yōu)解，并輸出進程映射關(guān)系。此后，ADPSS 的仿真程序讀入劃分結(jié)果和進程映射關(guān)系，并根據(jù)該映射關(guān)系分配每個進程上的子網(wǎng)計算任務(wù)，進入正常仿真流程。

圖8 優(yōu)化算法與仿真程序運行關(guān)系流程圖

4 算法性能評測

本算法在ADPSS 中的應(yīng)用仍在電力科學(xué)研究院進一步開發(fā)之中。本文僅能利用各計算小網(wǎng)的計算部分實測得到的時間，以及網(wǎng)間通信量的記錄結(jié)構(gòu)，加上本文構(gòu)建的底層通信中間件搭建的模擬程序在真實集群系統(tǒng)上進行評測，并與已有方案進行性能對比。

測試算例為華東和西北真實電網(wǎng)算例。真實算例1為西北電網(wǎng)算例。該算例電網(wǎng)包含8 400 個母線，1 000臺發(fā)電機，3 900 條線路，共673 個小網(wǎng)，步長大小75 μs。真實算例2 為華東電網(wǎng)算例。該算例電網(wǎng)包含5 000 個母線，400 臺發(fā)電機，4 640 條線路，共364 個小網(wǎng)，步長大小35 μs。兩個算例的小網(wǎng)每時步內(nèi)計算量和通信量如圖9 所示。真實算例性能對比如圖10 所示。

圖9 算例小網(wǎng)計算時間、通信量

圖10 真實算例性能對比

具體評測方案如下：首先在APDSS 真實運行場景中，最大并行度為150 進程，所以所有測試中并行度固定為150 進程。其次設(shè)置了多種資源異構(gòu)場景，不同算例中每個節(jié)點資源情況如表1 所示，既包括了8 節(jié)點計算資源平均的情況，也包括模擬真實場景各節(jié)點資源不一的情況，以及極端不均衡的情況(某個節(jié)點無核可用，或只有1 個核可用)。極端不均衡的情況容易對ADPSS默認劃分、映射算法帶來巨大的性能影響，因為子網(wǎng)一般按照計算時間順序排列，無論是從大到小還是從小到大，計算時間最長的子網(wǎng)都會在某個極端算例下被單獨映射在只有1 個核能用的節(jié)點上，從而大大影響仿真性能。同時，不均衡的算例也可以理解成白盒測試，在已知默認算法的劃分、映射策略的情況下，人為選擇可能對其性能影響最大的處理器核分配方式。因為默認算法只包含貪心策略，故無論子網(wǎng)按何種貪心策略排列，總能出現(xiàn)對其性能影響最大的算例。而如同前文所述，ADPSS 為按計算時間大小排序，故測試中的極端算例將核數(shù)較少的處理器分配在頭或尾。最后，電網(wǎng)算例皆為圖9 中展示的真實算例。測試對比算法為ADPSS 目前使用的默認劃分與映射算法。

表1 不同算例中各節(jié)點資源情況

模擬程序測試的底層平臺為基于Intel?Xeon?Gold 6132 處理器，共8 計算節(jié)點，每節(jié)點2 顆CPU，24核(全集群192 核)，配有192 GB 內(nèi)存。通信采用Infiniband 互聯(lián)，帶寬100 Gb/s，測試代碼采用Intel 2019 套件編譯，MPI 采用Intel 2019 編譯版本。在測試中采用向集群申請全部192 核的方式，并根據(jù)模擬的處理器核可用情況和優(yōu)化算法的圖劃分結(jié)果，將子網(wǎng)映射到對應(yīng)的處理器核上進行模擬計算。

從上述兩個算例(圖10)可以看出，本文算法較ADPSS默認算法在通信性能上分別取得了平均50%和40%的性能提升，而由于計算時間不變的影響，在總時間上取得的提升略低，分別為平均12%和10%。而且在西北算例中，由于初始小網(wǎng)中最大計算時間就高達58 μs，已與75 μs 的步長相差不大，原始算法是在不同核數(shù)分配下均無法完場硬實時仿真，而優(yōu)化后的算法在不同核數(shù)下都能穩(wěn)定在70 μs 下，完成仿真。

當(dāng)節(jié)點資源出現(xiàn)不同情況的異構(gòu)時，本文優(yōu)化算法的魯棒性更好。在整體性能相當(dāng)穩(wěn)定，波動不到10%。與原有算法相比，本文算法在算例3、4、5 的性能甚至略有提升。這主要因為這幾個算例中最大的計算資源為24 核，大于算例1 平均狀態(tài)下的19 核，這樣就有更多的空間去將關(guān)鍵通信鏈路藏在同一節(jié)點內(nèi)，而算例6、7雖然也同樣有大量24 核的節(jié)點，但卻包含一個核的節(jié)點，則不可避免地會出現(xiàn)較多的跨節(jié)點通信，整體性能依然與平均狀態(tài)相當(dāng)。

反觀原始算法，在華東和西北算例上隨著資源異構(gòu)都出現(xiàn)了不同程度的性能波動，上下波動幅度甚至高達60%。在默認映射狀態(tài)下，進程隨著異構(gòu)核被動變化，跨節(jié)點通信鏈路的多少無法針對通信性能進行優(yōu)選。若出現(xiàn)映射不佳情況，就會出現(xiàn)大量通信處于跨節(jié)點狀態(tài)，大大影響通信性能。

綜合來看，本文優(yōu)化算法取得了可觀的優(yōu)化效果。ADPSS 計算性能的持續(xù)提升未來將有賴于對計算部分的進一步優(yōu)化。

5 結(jié)論

本文針對中國電力科學(xué)研究院自研的電磁暫態(tài)仿真系統(tǒng)ADPSS，在資源異構(gòu)集群上進行了任務(wù)劃分和進程映射算法的優(yōu)化與改進，取得了通信性能的有效優(yōu)化。本文所提出的優(yōu)化算法實現(xiàn)了從初始小網(wǎng)合并劃分，再到進程映射的全自動優(yōu)化，并基于KL 算法設(shè)計了能解決不同節(jié)點資源各異的任務(wù)映射問題的方案。在華東和西北兩大真實電網(wǎng)算例上的模擬測試顯示，相較ADPSS默認劃分算法，本文算法在整體仿真性能上取得了平均10%和12%的提升，通信性能上取得了平均40%和50%的提升。