袁雨馨 唐宏偉 趙曉芳③ 嚴劍峰 周二專

(*中國科學(xué)院計算技術(shù)研究所 北京100190)

(**中國科學(xué)院大學(xué) 北京100049)

(***中國電力科學(xué)研究院 北京100192)

0 引言

大規(guī)模電網(wǎng)仿真計算是進行電力系統(tǒng)穩(wěn)定性分析的重要手段,通過對大規(guī)模電力系統(tǒng)的全數(shù)字建模與仿真,可以掌握電力網(wǎng)絡(luò)及各種動態(tài)元件的穩(wěn)態(tài)、暫態(tài)和動態(tài)特征,進而保證電網(wǎng)安全穩(wěn)定運行[1]。傳統(tǒng)大電網(wǎng)數(shù)字仿真技術(shù)為基于離線數(shù)據(jù)進行仿真計算,采用電網(wǎng)生產(chǎn)運行提供的歷史數(shù)據(jù)進行潮流、短路電流與暫態(tài)穩(wěn)定等仿真分析,計算時間長、計算量大,對失穩(wěn)狀況只能進行事后分析處理,無法對電網(wǎng)在線運行提供輔助決策。目前,隨著電網(wǎng)實時數(shù)據(jù)采集精度和效率不斷提升,利用在線運行數(shù)據(jù)進行實時仿真甚至超實時仿真成為了可能,在線實時仿真能夠在短周期內(nèi)快速評估其安全狀況及變化趨勢,并給出輔助決策控制策略,為事故預(yù)警提供更靈活的支持[2-4]。

針對具有泛在工業(yè)物聯(lián)網(wǎng)屬性的現(xiàn)代電網(wǎng),國家電網(wǎng)提出了智能全景電網(wǎng)[4](intelligent panoramic grid,IPG)的概念,在線超實時機電-電磁混合仿真(hybrid electromechanical and electromagnetic transient simulation,TS-EMT)是其核心計算引擎之一。混合仿真不僅實現(xiàn)了在多核節(jié)點及集群上并行執(zhí)行以提高效率[5],還接入了來自于智能電網(wǎng)調(diào)度技術(shù)支持系統(tǒng)(D5000)[6]的在線實時數(shù)據(jù)流,實現(xiàn)了同步調(diào)短周期并行計算。在集群環(huán)境下,仿真任務(wù)執(zhí)行效率受到資源和通信的約束,任務(wù)在執(zhí)行中一旦遇到資源分配不足或通信開銷過大的情況,極有可能導(dǎo)致執(zhí)行超時,從而影響結(jié)果判定。因此,將任務(wù)部署到合適的工作節(jié)點上并分配合理的資源,成為了大電網(wǎng)在線仿真能否實現(xiàn)實時性目標的關(guān)鍵之一。

本文的主要貢獻如下:(1)對大規(guī)模電網(wǎng)的機電-電磁暫態(tài)混合仿真任務(wù)進行了特性分析,總結(jié)出了資源利用率規(guī)律,即仿真任務(wù)具有短時運行、資源需求較穩(wěn)定、對通信敏感較高的特點;(2)提出了一種通信敏感的組調(diào)度框架(communication-aware gang scheduling framework,CGS),采用集中式兩階段調(diào)度架構(gòu),在不中斷在線流運行過程中對任務(wù)進行采樣和調(diào)度,最大程度保障在線實時任務(wù)運行的穩(wěn)定性;(3)提出了一種CGS 調(diào)度算法,實現(xiàn)了對任務(wù)多資源的主動采樣以預(yù)測需求,并基于通信圖對任務(wù)進行進程級的組調(diào)度[7](gang scheduling)。實驗表明,CGS 降低了37%的進程間通信開銷,減少了19%的資源碎片,平均提高了34%的集群資源利用率。

1 相關(guān)研究

目前,任務(wù)管理與資源調(diào)度計算平臺[8-10]大多是基于資源請求的,而實際中資源需求與執(zhí)行復(fù)雜度和集群硬件密切相關(guān),使得提交的請求往往難以準確提出資源需求,導(dǎo)致集群資源碎片化嚴重、利用率較低?；诖笠?guī)模電網(wǎng)實時仿真這一特定領(lǐng)域,CGS 提出了一種基于采樣的資源調(diào)度方法,類似于Sparrow[11]的批量抽樣,根據(jù)實際運行數(shù)據(jù)不斷修正調(diào)度策略。

現(xiàn)有的調(diào)度方法由面向約束機制組成。Google Borg[9]考慮到任務(wù)的優(yōu)先級特征,設(shè)計了任務(wù)排序算法和低優(yōu)先級任務(wù)替代機制。YARN[8]最近進行了擴展,支持多種資源類型、優(yōu)先級、搶占和高級接納控制。Apache Mesos[10]為異構(gòu)框架實現(xiàn)了一種基于offer 的方法,主要采用主導(dǎo)資源公平(dominant resource fairness,DRF) 算法[12]實現(xiàn)了公平性。Sparrow[11]采用隊列模型,提出了一種批量采樣方法,其目的是考慮優(yōu)先級、公平性、異質(zhì)性和數(shù)據(jù)的位置性。Tetris[13]支持完成時間敏感任務(wù)的多資源分配。CGS 針對在線調(diào)度,提出了一種通信敏感的任務(wù)多資源分配策略,考慮了任務(wù)進程級別下的通信相關(guān)性,最大化滿足進程間的親和性約束。

2 電網(wǎng)在線實時仿真概述

2.1 電網(wǎng)在線實時仿真介紹

本研究針對的是大規(guī)模電網(wǎng)的機電-電磁暫態(tài)混合仿真(TS-EMT)任務(wù)的調(diào)度問題,TS-EMT 是描述電力系統(tǒng)物理特性的解決方案[14-15]。機電瞬態(tài)穩(wěn)定性仿真(electromechanical transient simulation,TS)主要用于處理大型電力網(wǎng)絡(luò),仿真速度快,而電磁瞬態(tài)仿真(electromagnetic transient simulation,EMT)則在較小的范圍內(nèi)對電網(wǎng)進行高時間分辨率仿真?；旌戏抡媸荰S 和EMT 的統(tǒng)一,可以利用TS仿真的速度模擬非常大的網(wǎng)絡(luò),同時在關(guān)鍵部件上提供EMT 仿真的精度[16]。具體而言,混合仿真任務(wù)包括TS 和EMT 兩個過程,并結(jié)合二者優(yōu)勢進行綜合分析。

本文討論的每個仿真任務(wù)負責(zé)對電網(wǎng)拓撲結(jié)構(gòu)中的不同故障進行TS-EMT 混合仿真,任務(wù)內(nèi)的進程間通信基于消息傳遞接口(message passing interface,MPI)協(xié)議。文獻[17]總結(jié)并優(yōu)化了大規(guī)模電力系統(tǒng)的并行仿真算法,指出電網(wǎng)可以被分割成多個子網(wǎng),并以聯(lián)絡(luò)線相連接,每個子網(wǎng)由其計算進程(COMP)計算,而管理計算和計算聯(lián)絡(luò)線、匯總結(jié)果和I/O 進度的過程被稱為控制進程(CTRL)。

文獻[18]闡述了電力系統(tǒng)實時仿真的關(guān)鍵是仿真執(zhí)行時間小于等于求解模型方程的仿真時間步長。為了實現(xiàn)在線實時仿真,除了自身的計算執(zhí)行時間外,由調(diào)度(如等待更多資源或通信)造成的延遲決定了任務(wù)處理的延遲。

仿真任務(wù)由應(yīng)用和配置組成。應(yīng)用指的是仿真計算邏輯,配置包括仿真規(guī)模、仿真步長、電網(wǎng)分割策略、故障類型等仿真參數(shù)。影響計算的因素有很多,例如不同的電網(wǎng)分割策略也會導(dǎo)致不同的計算量,不同的電網(wǎng)故障類型相應(yīng)的計算量也會有所不同。一般來說,那些具有相同應(yīng)用和配置的任務(wù)可以被視為相同的任務(wù),在不同的潮流數(shù)據(jù)下,其執(zhí)行時間和資源利用率都是相似的。

2.2 機電-電磁暫態(tài)混合仿真任務(wù)特性分析

任務(wù)執(zhí)行環(huán)境如表1 所示,以表2 中列出的3個典型故障下的TS-EMT 混合仿真任務(wù)為例。這些任務(wù)相互獨立,代表了不同故障下的仿真,數(shù)據(jù)來自2019 年國家電力調(diào)度通信中心,覆蓋了6 個地區(qū)(即華北、華東、華中、西北、西南、東北)的電網(wǎng)。3個任務(wù)的仿真步長均為10 s,每個任務(wù)中的每個過程按照執(zhí)行時間采樣約100 次。

表1 分析環(huán)境

表2 TS-EMT 任務(wù)相關(guān)信息

圖1 中對應(yīng)任務(wù)的3 張圖描述了不同任務(wù)的整體資源使用情況。左邊的子圖展示了每個任務(wù)的中央處理器(central processingunit,CPU)使用率,右邊的子圖展示了這段時間內(nèi)的內(nèi)存使用率。在所有的剖析結(jié)果中,CPU 的利用率都很高,幾乎達到了n×100%(n為進程數(shù)),證實了這些任務(wù)是受CPU約束的。同時,內(nèi)存使用率呈現(xiàn)上升趨勢,說明對內(nèi)存的需求在增加。另外,從3 種情況的對比來看,任務(wù)規(guī)模越大,所需的計算資源越多。

圖1 任務(wù)資源利用率采樣曲線

為了深入分析內(nèi)存相關(guān)的統(tǒng)計數(shù)據(jù),表3 和表4匯總了任務(wù)中進程的內(nèi)存使用情況。在每個任務(wù)中,COMP 的變異系數(shù)(coefficient of variation,CV)較小,而CTRL 的平均值比COMP 大。原因是由于COMP 需要對網(wǎng)格進行盡可能均勻地劃分,所以COMP之間的內(nèi)存使用量是相似的。而CTRL需要做的其他工作包括聚合、通信、邊界接觸線的計算等。這個觀察結(jié)果可以用于生成大量的模擬實驗數(shù)據(jù),使其更貼近實際生產(chǎn)環(huán)境。

表3 TS 進程內(nèi)存分析

表4 EMT 進程內(nèi)存分析

由于仿真是以流式數(shù)據(jù)驅(qū)動運行的,因此需要觀察多個截面數(shù)據(jù)在一段時間內(nèi)的資源使用情況。任務(wù)2 選取連續(xù)的電網(wǎng)實時潮流數(shù)據(jù)集進行多次執(zhí)行,截取部分結(jié)果繪制在圖2 中。從圖2 中可以發(fā)現(xiàn),不同的數(shù)據(jù)下多次執(zhí)行的資源需求曲線差異很小,而且在資源充足的情況下,同一仿真任務(wù)中每個執(zhí)行的完成時間都是相似的。因此,在線調(diào)度框架在流式過程中可以對資源使用情況進行采樣,作為需求預(yù)測。

圖2 任務(wù)2 資源利用率采樣曲線

另一個特性分析是為了表現(xiàn)進程間的通信關(guān)系。文獻[19]闡述了EMT 網(wǎng)絡(luò)分區(qū)的拓撲方案,該方案是由子網(wǎng)的相互連接形成的。圖3 通過分析任務(wù)3 的通信關(guān)系得出進程間通信熱力圖,橫縱坐標均為進程號,圖中點代表橫向到縱向進程的通信數(shù)據(jù)量,顏色越深代表進程傳輸?shù)臄?shù)據(jù)量越大。該圖表明,通信強度是不平衡的,進程間通信的差異化使得進程聚集成組成為了可能。

圖3 任務(wù)3 的通信熱力圖

由上文分析可知,仿真任務(wù)具有短時運行、資源需求較穩(wěn)定、對通信敏感較高的特點。根據(jù)這些特點,面向大電網(wǎng)的在線實時仿真調(diào)度必須做到的就是保障在線實時運行效率,并解決資源分配的準確性,提高集群的資源利用率,減少碎片化。

3 在線調(diào)度問題描述

為了解決多資源上的在線調(diào)度問題,本文提出了通信敏感組調(diào)度框架(CGS)。本節(jié)介紹CGS 中的調(diào)度模型,作為在線調(diào)度的形式化表示。

3.1 定義

假設(shè)一個集群有N個資源容量為的異構(gòu)節(jié)點,節(jié)點h的容量可以由一個d維向量表示,如果節(jié)點沒有某些類型的資源,比如圖形處理器(graphic processing unit,GPU)或特定的硬件,向量中的元素可以用0來填充。

一個仿真任務(wù)由n個MPI 進程組成,資源需求被寫作,任務(wù)中進程p的資源需求可以由一個d維向量表示。一般來說,每個進程都會被綁定在一個CPU 核心上,內(nèi)存則會按需分配。任務(wù)的需求則是所有進程資源需求的總和,即為D=

根據(jù)式(1)可知資源向量可比性,從而可判斷進程p的資源向量是否可以被節(jié)點h滿足。具體而言,當(dāng)所有維度的進程需求小于節(jié)點可用容量時,可以判斷節(jié)點能夠滿足該進程需求。換言之,如果有一個維度的資源不能滿足任務(wù)的需求,資源匹配就會失敗。

當(dāng)進程數(shù)n ＞1 時,進程間的通信基于MPI 協(xié)議。計算進程pj負責(zé)仿真分網(wǎng)拓撲下的子網(wǎng)j,并向鄰居集set(pj′)、pj≠pj′傳輸數(shù)據(jù)。任務(wù)進程間通信集的拓撲結(jié)構(gòu)描述為一個有向無環(huán)圖G=(V,E),其中V是n個頂點的有限集,對應(yīng)n個進程,E?V×V是一個有定向邊的有限集,代表頂點之間的通信關(guān)系。圖G滿足如果{j,j′}∈E,則j∈E∧j′∈E。

假定任務(wù)可將n個進程劃分為b1∪b2∪…∪bk這k個劃分,并滿足約束bl∩bl′=?,l≠l′和=V,那么每個劃分b就可以部署在一個節(jié)點上,不同劃分就可以部署在不同節(jié)點上,從而實現(xiàn)任務(wù)的跨節(jié)點調(diào)度。每個劃分均為多個進程的集合,稱為進程組(gang)。

當(dāng)定義了任務(wù)劃分后,邊{j,j′} 的通信開銷ω({j,j′}) 如式(2)所示,與進程間的通信長度Lj,j′(bits)、帶寬B和在不同節(jié)點下的性能損耗ε∈(0,1) 有關(guān)。

通信圖G刻畫了進程間的通信關(guān)系。為簡單描述,對圖的所有邊和頂點引入二元決策變量ej,j′,對于每條邊{j,j′} ∈E,變量取值為ej,j′∈{0,1},當(dāng){j,j′} 為割邊時ej,j′=1,否則ej,j′=0。由于位于同一節(jié)點上的連通性邊緣的通信開銷可以忽略,因此總開銷COMM是任務(wù)劃分的割邊成本。

由于任務(wù)進程采用MPI 通信協(xié)議,其中有較多同步操作,降低進程組的割邊成本有助于減小由于通信造成的同步等待時間,從而提高任務(wù)執(zhí)行的效率。

3.2 調(diào)度模型

調(diào)度負責(zé)將在線提交的任務(wù)與最多個節(jié)點進行匹配,最小的調(diào)度單元是進程,它只能分配給一個節(jié)點。調(diào)度的主要目標是盡可能減少有負載的節(jié)點數(shù)量,更好地降低能耗,實現(xiàn)綠色節(jié)能計算,并且空閑的節(jié)點可以作為備用節(jié)點,以實現(xiàn)高可用性或為其他計算提供服務(wù)。除了這個目標之外,還要考慮到多節(jié)點的通信開銷。

調(diào)度模型可以形式化為多維裝箱問題[20](multi-dimensional bin packing problem,MD-BPP),它是經(jīng)典的一維裝箱問題的推廣,是NP 難問題。在多資源調(diào)度的基礎(chǔ)上,在多節(jié)點上調(diào)度一個任務(wù)的多個進程是復(fù)雜的,這也是TS-EMT 混合仿真任務(wù)調(diào)度的難點。為了解決這些問題,調(diào)度模型采用整數(shù)線性模型將MD-BPP 解與圖劃分策略相結(jié)合,其決策變量如下。

(1)xij:若進程i被分配到節(jié)點j上,則xij=1,否則xij=0。

(2)yj:若節(jié)點j有任務(wù)進程在運行中,則yj=1,否則yj=0。

(3)zib:若進程i在子任務(wù)b中時zib=1,否則zib=0。

調(diào)度模型的線性整數(shù)規(guī)劃公式可以寫為

目標是最小化有負載節(jié)點數(shù)量和任務(wù)劃分的割邊成本,用式(4a)和式(4b)表示。約束條件式(4c)說明一個任務(wù)的任何進程都應(yīng)且必須部署在一個節(jié)點上,而式(4d)說明節(jié)點上的進程需求之和不應(yīng)該超過節(jié)點的可用容量,確保資源不會被過度分配。式(4e)和(4f)保證了一個有效的劃分,式(4g)保證了每個進程正好分配到一個分區(qū)。最后,可以得到一個集合(xij,yj),將任務(wù)的所有進程與集群中的節(jié)點進行匹配。

4 通信敏感的組調(diào)度CGS

本節(jié)首先介紹CGS 的體系結(jié)構(gòu),再具體說明CGS 算法與調(diào)度模型,最后介紹了CGS 框架的實現(xiàn)方式。

4.1 CGS 架構(gòu)

CGS 架構(gòu)如圖5 所示,可歸為集中式調(diào)度框架,由控制節(jié)點上的調(diào)度器、資源管理器以及工作節(jié)點上的執(zhí)行器和監(jiān)控器組成。調(diào)度器通過非侵入式采集器收集資源需求,負責(zé)調(diào)度任務(wù)。資源管理器負責(zé)檢測集群的狀態(tài)及最新的可用容量。執(zhí)行器負責(zé)任務(wù)的全生命周期活動管理,監(jiān)控器負責(zé)記錄任務(wù)和節(jié)點的資源使用情況。架構(gòu)上將資源管理服務(wù)與調(diào)度服務(wù)解耦,可部署多種不同優(yōu)先級的調(diào)度策略,方便更換策略,增強了靈活性。

圖5 CGS 兩階段架構(gòu)工作流

架構(gòu)采用了先采樣后調(diào)度兩階段架構(gòu)。采樣是調(diào)度的基礎(chǔ),是為了收集和預(yù)測任務(wù)資源需求,包括將在線任務(wù)部署在采樣節(jié)點上,以非侵入式的方式持續(xù)收集使用情況并估算資源需求。采樣工作流程如圖5(a)所示。任務(wù)由應(yīng)用程序和一些配置文件組成,將在流式過程中隨時提交。提交后,調(diào)度器會向資源管理器申請最新的可用容量,再將任務(wù)部署在采樣節(jié)點上。之后執(zhí)行器開始運行任務(wù),同時監(jiān)控器來記錄任務(wù)的執(zhí)行情況和資源使用情況。在多次采樣獲得穩(wěn)定需求后,監(jiān)控器會將任務(wù)資源使用情況報告給資源管理器,然后執(zhí)行器會清理執(zhí)行垃圾,為下一次任務(wù)采樣做準備。

圖5(b)展示了調(diào)度階段。詳細來說,調(diào)度器使用了預(yù)定義的調(diào)度策略,根據(jù)任務(wù)需求和集群可用容量運行CGS 算法(4.2 中有更詳細介紹),將任務(wù)部署在節(jié)點上,為所有進程分配一定的資源并進行資源隔離。之后執(zhí)行器初始化任務(wù),當(dāng)任務(wù)準備就緒,且輸入數(shù)據(jù)接收完畢后,任務(wù)會在監(jiān)控器的監(jiān)視下執(zhí)行。一旦任務(wù)拋出資源使用異常,監(jiān)控器就會擴大使用閾值,直到節(jié)點上沒有資源可用,然后執(zhí)行器就會清除該任務(wù)并予以警告,以免影響其他任務(wù),清除后的任務(wù)將會被允許重新提交。此外在任務(wù)執(zhí)行過程中,執(zhí)行器會與控制節(jié)點保持聯(lián)系。

4.2 CGS 算法

CGS 的一個重要組成部分是組調(diào)度的設(shè)計,它結(jié)合了貪心調(diào)度和圖劃分策略。該算法引用了分治法[21]思想。算法可分為以下3 個部分:

(1) 分解。將任務(wù)劃分為子任務(wù)。

(2) 解決。遞歸搜索最優(yōu)節(jié)點,直到匹配成功。

(3) 合并。組合子任務(wù)節(jié)點集得到最終的解決方案。

分治算法判斷子問題能否解決的方法是過濾,即找到部署任務(wù)的可行候選節(jié)點集。如果集合為空,說明目前任務(wù)需求不能被任何一個節(jié)點滿足,那么任務(wù)將被遞歸地劃分成子任務(wù),即子進程組。只要候選集不為空,就會結(jié)束遞歸分支。

任務(wù)劃分意味著必然出現(xiàn)跨節(jié)點調(diào)度,進程間的通信開銷將成為效率的瓶頸。為了降低開銷,CGS 利用了圖劃分策略,如k-way 多級劃分算法[22]或其他啟發(fā)式算法[23]。圖劃分策略平衡了處理器之間的工作負載,使得通信開銷最小化。

CGS 算法利用扁平化匹配策略搜索最優(yōu)節(jié)點以求解MD-BPP,該策略同時考慮了多維資源,以獲得一個適應(yīng)值,表示為SCORE。該值量化了任務(wù)與節(jié)點的匹配程度,最常見的方法是在Grandl 等人[13]提出的多資源啟發(fā)式策略,包括余弦相似度、點積、L2距離等。這些方法都考慮了集群中的多維資源,并將任務(wù)需求與最優(yōu)節(jié)點進行匹配,CGS 框架并沒有限制SCORE的計算方式,可以根據(jù)實際測試選擇最優(yōu)的資源匹配計算方案。

CGS 算法遞歸實現(xiàn)的流程如算法1 所示。

在CGS 算法的形式描述中,前7 行用于篩選出有足夠資源的節(jié)點(Candidates),并計算出與任務(wù)的匹配度。第8 行到第10 行表明,如果有一些Candidates,將其部署在最佳匹配節(jié)點上并更新資源。第11 和12 行表明,如果任何節(jié)點的可用容量不足,任務(wù)將不會被調(diào)度。第13 行到第18 行利用圖劃分將任務(wù)分割成子集,并遞歸地重新調(diào)度。

該框架將圖劃分策略與基于調(diào)度模型的匹配策略相結(jié)合。CGS 算法中,任務(wù)的圖劃分策略采用kway 多級算法,將通信圖中包含m條邊的n個進程任務(wù)劃分為k個子任務(wù),劃分圖的時間復(fù)雜度為O((n +m)×log(k)),遞歸實現(xiàn)的總時間復(fù)雜度為O((n+m)×log(k)×logn)。

4.3 CGS 實現(xiàn)

CGS 包括資源采樣和調(diào)度2 個階段。在采樣階段,調(diào)度器接收并解析任務(wù)信息,包括進程數(shù)和一些執(zhí)行配置,同時會使用性能分析工具如Intel Vtune Profiler[24]收集MPI 進程間通信開銷。采樣過程被設(shè)計成多次重復(fù),直到得到一個比較穩(wěn)定的值(根據(jù)經(jīng)驗通常是3～5 次),為了減少由于資源限制導(dǎo)致的任務(wù)失敗或超時,可以將進程的內(nèi)存需求放寬到最大內(nèi)存的δ倍。

在資源調(diào)度方面,調(diào)度器會篩選出滿足約束條件的節(jié)點,并使用優(yōu)化的資源匹配策略來匹配任務(wù)。此外,資源管理器在任務(wù)提交或固定時間段內(nèi),會觸發(fā)監(jiān)控器收集任務(wù)需求和可用容量。此外,調(diào)度器、資源管理器、監(jiān)控器和執(zhí)行器會作為框架的常駐服務(wù)運行。

5 實驗與分析

為了更全面地評估CGS 的調(diào)度性能,而不僅僅局限于2.2 節(jié)所述的任務(wù),本文進行了模擬實驗。本節(jié)首先討論了實驗環(huán)境,再評估性能結(jié)果。

5.1 實驗指標

實驗設(shè)置了一個大規(guī)模節(jié)點和一批任務(wù)的環(huán)境,分別從任務(wù)平均劃分數(shù)、平均割邊成本、有負載節(jié)點數(shù)、集群資源利用率和資源碎片率5 個指標對算法進行比較。為了顯示出CGS 調(diào)度框架的優(yōu)勢,實驗采用了5 種常用的調(diào)度策略作為基線算法,包括自適應(yīng)先到先得[25](adaptive first-come-firstserved,AFCFS)、最大組優(yōu)先調(diào)度[25](largest gang first served,LGFS)、最佳適應(yīng)算法[25](best fit decreasing,BFD)、主導(dǎo)資源公平算法[12](dominant resource fairness,DRF)與Tetris[13]。實驗比較了基線算法與應(yīng)用了CGS 的算法之間的差異。調(diào)度算法均以進程為最小單元進行調(diào)度。詳細的性能指標介紹如下。

(1) 任務(wù)平均劃分數(shù)。任務(wù)劃分的數(shù)量反映了策略中對任務(wù)進程之間親和力的考慮。劃分數(shù)量越多,進程被調(diào)度的越分散,任務(wù)執(zhí)行效率越低。該指標較低有助于保證任務(wù)執(zhí)行的效率和穩(wěn)定性。

(2) 平均割邊成本。該值表示跨節(jié)點的通信開銷,如式(2)所示。該開銷由邊緣切割權(quán)重決定,成本越低表明跨節(jié)點通信開銷越小。

(3) 有負載節(jié)點數(shù)。該指標衡量的是集群中的負載聚集程度,降低碎片的同時更好地降低能耗,實現(xiàn)綠色節(jié)能計算。

(4) 集群資源利用率。該指標會對每個節(jié)點的不同維度資源進行加權(quán)。式(5)中用于表示節(jié)點k在維度i上的資源需求與可用容量之比,式(6)中uk衡量節(jié)點k在所有維度中的平均資源利用率。值越大代表資源利用率越高、閑置越少。

(5) 集群資源碎片率。資源碎片率反映了一個節(jié)點中資源耗盡而其他資源剩余的硬約束,這種剩余的碎片化導(dǎo)致了資源的浪費,無法再用于任何其他任務(wù)。式(7)顯示的是節(jié)點k的碎片率,式(8)中w衡量的是集群中所有節(jié)點的資源碎片程度。

5.2 實驗環(huán)境

雖然CGS 支持任何維度的資源,但在實時模擬中,其性能主要取決于CPU 和內(nèi)存資源,記為(Ch,Mh)。本文電網(wǎng)實時仿真環(huán)境中,CPU 和內(nèi)存資源被認為是同等重要的。實驗設(shè)置了一個由1000 節(jié)點組成的集群,其中CPU 和內(nèi)存容量來自一個截斷的正態(tài)分布。實驗1 探究了不同CPU 和內(nèi)存下算法的有效性,實驗設(shè)置了集群中每個節(jié)點的CPU 平均值為10～50 核,步長為10,內(nèi)存范圍為300～1500 MB,步長為300,變異系數(shù)設(shè)置為1.5。實驗2 探究不同變異系數(shù)下的算法在評價指標體系下的表現(xiàn),因此本實驗重點分析了在CPU 和內(nèi)存均值分別為30 核和1000 MB 環(huán)境下方法的有效性。由于在實際場景中,集群可用容量幾乎不可能是完全同質(zhì)的,因此變異系數(shù)從0.5 到3.0,以0.5 為增量,產(chǎn)生6 種不同的集群環(huán)境。隨著變異系數(shù)的增加,資源的異質(zhì)性逐漸增強。

實驗構(gòu)建了100 個在線任務(wù),模擬的需求是基于2.2 節(jié)中的分析結(jié)果。實驗設(shè)置TS 的數(shù)量小于EMT 的數(shù)量,并隨機生成2～200 的進程數(shù)量,其中3%的進程被設(shè)置為CTRL,其余都是COMP。在所有進程中,CPU 資源需求被設(shè)置為1,內(nèi)存則存在差異。在TS 中,內(nèi)存是由截斷的正態(tài)分布產(chǎn)生的(Mean=300,CV=0.1)。在EMT 中,CTRL 中內(nèi)存需求的平均值為400,COMP 中截斷正態(tài)分布設(shè)置為Mean=30,CV=0.3。此外,通信圖是根據(jù)相應(yīng)的任務(wù)進程數(shù)生成的,邊權(quán)重設(shè)置為0～10。如果一對連接的節(jié)點被分割成兩組不同的節(jié)點,權(quán)重將被加到整體的割邊成本中。

所有的模擬任務(wù)在表1 所述的平臺環(huán)境中被調(diào)度,實驗首先對5 種基線算法進行單獨實驗(稱為X),再分別利用這5 種算法計算SORE的方式置入CGS 算法中(稱為X+CGS),以評估在CGS 圖劃分策略與匹配策略相結(jié)合的算法下的優(yōu)勢,共8 種策略。實驗參數(shù)采用k=2,δ=1.5。

5.3 實驗結(jié)果

實驗1 探究了不同CPU 和內(nèi)存下算法的表現(xiàn)情況,為了方便展示,實驗分別選取了CPU 為瓶頸和內(nèi)存資源為瓶頸時的兩種場景展示。首先當(dāng)固定CPU 而內(nèi)存以一定步長增長時,各方法在不同指標下的結(jié)果如圖6 所示,其中未分配數(shù)指標表示了由于集群節(jié)點資源短缺導(dǎo)致集群無法滿足的任務(wù)個數(shù),即任務(wù)調(diào)度失敗的個數(shù)。圖6 中虛線表示基線算法,實線表示應(yīng)用了CGS 的算法,隨著內(nèi)存的不斷增大,CPU 愈發(fā)成為了瓶頸資源,使得集群利用率有所下降而碎片率上升。圖6 結(jié)果表明,CGS 方法在不同內(nèi)存場景下保持了負載聚集從而降低能耗,使得更多任務(wù)得以調(diào)度執(zhí)行,并大幅降低了跨節(jié)點通信開銷,提高了資源利用率并降低了碎片化程度。

圖6 CPU 為10 時不同指標下各方法隨內(nèi)存增長的結(jié)果

其次,當(dāng)固定內(nèi)存而CPU 以一定步長增長時,各方法在不同指標下的結(jié)果如圖7 所示。從圖中發(fā)現(xiàn)CGS 方法在CPU 資源不同時依舊比基線算法有性能優(yōu)勢,尤其是在降低通信開銷上。

圖7 內(nèi)存為300 時不同指標下各方法隨CPU 增長的結(jié)果

在實驗2 中,每個指標的結(jié)果用分別代表了6種不同的異構(gòu)環(huán)境下的子圖表示,每個子圖都以柱狀圖的形式顯示。橫軸顯示的是5 種基線算法,而縱軸則表示性能指標。線型陰影條形圖表示基本策略X,點型陰影條形圖表示X+CGS 中應(yīng)用的策略。

圖8 說明了所有任務(wù)的平均劃分數(shù),顯示了任務(wù)的進程間聚集程度,值越大意味著任務(wù)越分散。所有基本策略中任務(wù)都相對切分得較為分散,尤其是Tetris 方法。通過CGS 框架的應(yīng)用,任務(wù)按遞歸方式進行劃分,一旦能放置成功就結(jié)束劃分,最大程度減少了任務(wù)的劃分數(shù)量,保證了任務(wù)進程間的親和力。

圖8 任務(wù)平均劃分數(shù)

圖9 中,每個子圖中的縱軸展示了任務(wù)劃分的割邊成本,代表了通信開銷。顯然,無論集群環(huán)境的異質(zhì)性程度如何,CGS 均顯著降低了跨節(jié)點通信開銷,至少降低了37%的通信開銷(CV=0.5 環(huán)境下的LGFS 方法中),最大達到了89%(CV=3.0 環(huán)境下的Tetris 方法中)。

圖9 平均割邊成本

圖10 所示的有負載的節(jié)點數(shù)證明CGS 盡可能將任務(wù)調(diào)度在較少的節(jié)點上,使得節(jié)點負載更加緊湊。但在BFD 的調(diào)度策略中,任務(wù)會被放置在資源最合適的節(jié)點上,大幅提升了節(jié)點資源的緊湊度。而CGS 框架為了保證任務(wù)的親和性,會盡量少切分大需求任務(wù),這導(dǎo)致了負載節(jié)點數(shù)相比基線BFD 方法近乎相同,但CGS 是基于基線算法進行的優(yōu)化,并不會導(dǎo)致其負載節(jié)點數(shù)大為增加。

圖10 有負載的節(jié)點數(shù)

圖11 以帶誤差條的直方圖形式,比較了集群中所有節(jié)點的的平均值和標準差。結(jié)果表明,CGS 不僅提高了利用率(平均提高了34%),還縮小了標準差,間接證明了集群負載更加均衡。此外采用CGS方法可以更好地利用節(jié)點上的閑置資源,使得調(diào)度結(jié)果更加穩(wěn)定。

圖11 節(jié)點利用率平均值和方差

圖12 顯示了集群中碎片率的平均值。CGS 框架降低了AFCFS、LGFS、BFD、DRF 方法的集群的平均碎片化程度,至少降低了19%的碎片率(CV=2.5環(huán)境下的AFCFS方法中),最大達到了81%(CV=0.5環(huán)境下的BFD 方法中),這證實了使用CGS 可以降低集群碎片率,并可提高資源多維度間的平衡性。但在Tetris 方法中,由于余弦相似度的多維資源匹配策略使進程能被分配在多維資源最合適的節(jié)點上,最大化避免了多維資源碎片化。而CGS 框架優(yōu)先考慮任務(wù)間進程的親和性,盡可能將任務(wù)劃分為大組進行分配,會導(dǎo)致一定程度上的資源碎片化。

圖12 集群平均碎片率

綜合考慮所有指標發(fā)現(xiàn),CGS 方法能夠在各種集群資源情況下合理有效調(diào)度任務(wù)并分配資源。CGS 方法在滿足任務(wù)資源需求的同時,綜合考慮了多維度資源,優(yōu)化了任務(wù)和節(jié)點之間的匹配策略,盡可能減少有負載的節(jié)點數(shù)量,更好地降低了能耗,減少碎片化的同時提高了集群的資源利用率。

6 結(jié)論

本文首先對大規(guī)模電網(wǎng)的機電-電磁暫態(tài)混合仿真(TS-EMT)任務(wù)進行了特性分析,總結(jié)了資源利用率規(guī)律:短時運行、資源需求較穩(wěn)定、對通信敏感較高。其次,針對大規(guī)模電網(wǎng)機電-電磁混合仿真計算的應(yīng)用場景,提出了一種用于實時電網(wǎng)仿真的通信敏感組調(diào)度框架(CGS),采用了集中式兩階段調(diào)度架構(gòu),在不中斷在線流運行過程中對任務(wù)進行主動采樣和調(diào)度,最大程度保障在線實時任務(wù)運行的穩(wěn)定性。最后,本文提出了一種CGS 調(diào)度算法,基于通信圖的圖劃分策略與基于調(diào)度模型的匹配策略相結(jié)合,實現(xiàn)了進程組調(diào)度,降低了任務(wù)跨節(jié)點的通信開銷。

通過模擬實驗證實,CGS 算法會最大程度保證任務(wù)進程的聚合性,與基本策略相比至少降低了37%的進程間的通信開銷,保證了任務(wù)執(zhí)行效率。同時CGS 將任務(wù)調(diào)度在較少的節(jié)點上,一方面在保證集群不過載的前提下,提高了節(jié)點資源利用率,降低了資源碎片率;另一方面降低了集群能耗,符合當(dāng)今綠色節(jié)能計算的主題。此外,未來可以研究更細粒度的調(diào)度優(yōu)化,如使用非均勻內(nèi)存訪問(non uniform memory access,NUMA)架構(gòu)優(yōu)化節(jié)點內(nèi)的通信開銷;調(diào)度算法方面可以嘗試群體智能方式,在在線調(diào)度允許的范圍內(nèi)進行全局搜索得到較優(yōu)解。