面向大電網(wǎng)在線實(shí)時(shí)仿真的通信敏感資源調(diào)度①

袁雨馨 唐宏偉 趙曉芳③ 嚴(yán)劍峰 周二專

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

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

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

0 引言

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

表1 分析環(huán)境

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 定義

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

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

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

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

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

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

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

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

3.2 調(diào)度模型

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

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

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

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

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

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

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

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

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

4.1 CGS 架構(gòu)

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

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

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

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

4.2 CGS 算法

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

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

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

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

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

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

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

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

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

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

4.3 CGS 實(shí)現(xiàn)

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

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

5 實(shí)驗(yàn)與分析

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

5.1 實(shí)驗(yàn)指標(biāo)

實(shí)驗(yàn)設(shè)置了一個(gè)大規(guī)模節(jié)點(diǎn)和一批任務(wù)的環(huán)境,分別從任務(wù)平均劃分?jǐn)?shù)、平均割邊成本、有負(fù)載節(jié)點(diǎn)數(shù)、集群資源利用率和資源碎片率5 個(gè)指標(biāo)對(duì)算法進(jìn)行比較。為了顯示出CGS 調(diào)度框架的優(yōu)勢(shì),實(shí)驗(yàn)采用了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]。實(shí)驗(yàn)比較了基線算法與應(yīng)用了CGS 的算法之間的差異。調(diào)度算法均以進(jìn)程為最小單元進(jìn)行調(diào)度。詳細(xì)的性能指標(biāo)介紹如下。

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

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

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

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

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

5.2 實(shí)驗(yàn)環(huán)境

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

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

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

5.3 實(shí)驗(yàn)結(jié)果

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

圖6 CPU 為10 時(shí)不同指標(biāo)下各方法隨內(nèi)存增長(zhǎng)的結(jié)果

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

圖7 內(nèi)存為300 時(shí)不同指標(biāo)下各方法隨CPU 增長(zhǎng)的結(jié)果

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

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

圖8 任務(wù)平均劃分?jǐn)?shù)

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

圖9 平均割邊成本

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

圖10 有負(fù)載的節(jié)點(diǎn)數(shù)

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

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

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

圖12 集群平均碎片率

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

6 結(jié)論

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

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