實時仿真并行調(diào)度算法研究

賈燕成，黎 英,2

(1.云南大學(xué)信息學(xué)院，昆明 650091；2.昆明理工大學(xué)信息工程與自動化學(xué)院，昆明 650093)

1 概述

隨著計算機技術(shù)和網(wǎng)絡(luò)的高速發(fā)展，仿真技術(shù)越來越顯得重要，尤其是實時的并行仿真。研究大型的電力系統(tǒng)和構(gòu)造真實的三維空間模型時，仿真是其研究的重要手段和工具。仿真在電力系統(tǒng)領(lǐng)域已被廣泛應(yīng)用，如用于系統(tǒng)規(guī)劃、運行優(yōu)化、故障分析等，并且可幫助有關(guān)人員做出合理的決策以避免或減少系統(tǒng)運行中可能出現(xiàn)的問題[1]。而視景仿真[2-3]采用計算機圖形圖像技術(shù)，構(gòu)造仿真對象的三維模型并再現(xiàn)真實環(huán)境，達(dá)到非常逼真的仿真效果。

隨著仿真任務(wù)復(fù)雜性的增加，單處理機的性能幾乎已經(jīng)發(fā)揮到極致，不能體現(xiàn)仿真的實時性。因此，文獻[4]提出了多機并行仿真的概念，主要針對電力系統(tǒng)、視景仿真提出了一些并行仿真的算法，在一定程度上體現(xiàn)了對實時性的需求。

由于并行系統(tǒng)的廣泛應(yīng)用，文獻[5]提出了基于嵌入式以太網(wǎng)的并行仿真計算的概念。并行計算是指用多個處理器并發(fā)地執(zhí)行不同的任務(wù)，其高效的計算潛能依賴于對并行任務(wù)的調(diào)度方法。網(wǎng)格計算[6]中常用的調(diào)度方法就是并行調(diào)度，但在網(wǎng)格計算的調(diào)度中一般針對有向無環(huán)的任務(wù)圖(Directed Acyclic Graph,DAG)[7]，任務(wù)圖中的每個任務(wù)都是非周期的，因此提出的調(diào)度算法具有一定的局限性。

針對一種有向帶環(huán)且交叉反饋的DAG任務(wù)圖，任務(wù)且具有周期性的特點，本文提出了一種基于負(fù)載均衡性的任務(wù)動態(tài)組合調(diào)度方法。

2 任務(wù)圖描述

2.1 系統(tǒng)調(diào)度的結(jié)構(gòu)圖

為了分析基于有向帶環(huán)且具有復(fù)雜交叉反饋任務(wù)圖的并行調(diào)度算法的可行性，采用異步電機的動態(tài)數(shù)學(xué)模型[8]為實例進行研究，其異步電機的動態(tài)模型如圖1所示。

圖1 異步電機在同步旋轉(zhuǎn)坐標(biāo)系下的結(jié)構(gòu)

2.2 概念和定義

在建立任務(wù)圖時，可借助圖論的方式對任務(wù)圖進行描述。將任務(wù)的有向有環(huán)圖用五元組 TG=(V,E,W,C,T)來表示[9]。其中：

V=[Vi]表示任務(wù)圖中節(jié)點(任務(wù)圖中的節(jié)點是指任務(wù))的集合，Vi表示第 i個任務(wù)，|V|表示圖中節(jié)點數(shù)目。

E=[ei,j]表示任務(wù)圖中邊(任務(wù)圖中的有向邊是指2個任務(wù)之間存在消息傳遞)的集合；ei,j是指節(jié)點 i指向節(jié)點j的有向邊，表示任務(wù)i和任務(wù)j存在相關(guān)性；|E|表示圖中邊的數(shù)目。由于每條邊是有向的，因此用“<”表示任務(wù)之間的依賴關(guān)系，即Vi

W=[Wi]表示任務(wù)的粒度，即子任務(wù)計算量的集合，Wi表示任務(wù)Vi的計算量。

C=[Ci,j]表示任務(wù)之間通信數(shù)據(jù)量的集合；Ci,j表示任務(wù)i發(fā)送給任務(wù)j的數(shù)據(jù)量。

T=[ti]表示任務(wù)的Vi的循環(huán)周期。

2.3 任務(wù)圖的構(gòu)建

由異步電機的結(jié)構(gòu)，可根據(jù)DAG任務(wù)圖[10]的構(gòu)圖思想建立異步電機并行仿真的任務(wù)圖。從結(jié)構(gòu)圖可知，整個電機由6個慣性環(huán)節(jié)和1個積分環(huán)節(jié)構(gòu)成，首先對結(jié)構(gòu)圖進行化簡，把反饋系數(shù)進行有效的合并。在任務(wù)圖的構(gòu)建中可以把7個環(huán)節(jié)看作是7個節(jié)點，不改變節(jié)點間數(shù)據(jù)的連接關(guān)系。構(gòu)建的任務(wù)圖如圖2所示。

圖2 異步電機任務(wù)圖

在以上節(jié)點任務(wù)圖中節(jié)點 1～節(jié)點 6的基本任務(wù)是對慣性環(huán)節(jié)的求解，而節(jié)點7是對積分環(huán)節(jié)的求解，這樣也就轉(zhuǎn)換成對一個微分方程組的求解。在對任務(wù)圖的構(gòu)建過程中，需考慮各子任務(wù)的均衡性，這也是對任務(wù)的合并與分解的重要參考依據(jù)。由于結(jié)構(gòu)圖具有一定的對稱性和相似性，其化簡過程也就相對簡化了。

其中，節(jié)點1、節(jié)點4所包含的任務(wù)是為慣性環(huán)節(jié)G1( s)、系數(shù)RFe、L1σ和固定輸入W1；節(jié)點2、節(jié)點5所包含的任務(wù)為慣性環(huán)節(jié)G2(s)、系數(shù)Lm、C；節(jié)點 3、節(jié)點 6所包含的任務(wù)為慣性環(huán)節(jié)G3( s)、系數(shù)、D、A；節(jié)點7包含任務(wù)為一個積分環(huán)節(jié)、系數(shù)E及固定輸入T1。

3 調(diào)度算法設(shè)計

定義 1 連接矩陣 Cn×n表示各任務(wù)關(guān)系圖中各子任務(wù)之間的連接關(guān)系：

在連接矩陣中，每行或每列代表一個子任務(wù)與其他子任務(wù)的數(shù)據(jù)傳遞關(guān)系。在矩陣中，每行表示一個節(jié)點任務(wù)的輸入關(guān)系，若其他節(jié)點對該節(jié)點有數(shù)據(jù)輸入關(guān)系，則 Ci×j=1，反之，則 Ci×j=0；每列表示一個節(jié)點任務(wù)的輸出關(guān)系，若該節(jié)點對其他節(jié)點有數(shù)據(jù)輸出關(guān)系，則 Ci×j=1，反之則 Ci×j=0。

定義2 任務(wù)組是任務(wù)圖中多個相關(guān)任務(wù)的合并，且被映射到同一個處理機執(zhí)行的任務(wù)集合。

規(guī)則 1 任務(wù)組組建規(guī)則：實驗環(huán)境采用 BF538作為節(jié)點機，具有雙網(wǎng)口，可允許各節(jié)點機有2個數(shù)據(jù)輸入或輸出。由于在并行調(diào)度過程中會產(chǎn)生一定的通信開銷，因此組建的任務(wù)組其執(zhí)行開銷應(yīng)優(yōu)于通信開銷，也即各節(jié)點機的執(zhí)行開銷應(yīng)滿足weight /2 ＜ xi＜ 2weight ，其中，weight為從機之間的通信開銷，并且根據(jù)連接矩陣中各個任務(wù)之間的連接關(guān)系應(yīng)盡量減少任務(wù)之間通信開銷。

規(guī)則 2 負(fù)載動態(tài)均衡規(guī)則：在任務(wù)的調(diào)度過程中，根據(jù)處理器不斷地記錄整個系統(tǒng)狀態(tài)信息，將執(zhí)行開銷較大的任務(wù)組進行分解動態(tài)映射到其他節(jié)點機上。與該節(jié)點機上的原始任務(wù)組進行組合形成該節(jié)點機上的后繼任務(wù)組，且其組合的原則按照規(guī)則1進行，原始任務(wù)組和后繼任務(wù)組在該節(jié)點機上循環(huán)執(zhí)行，使各個節(jié)點機上的任務(wù)組達(dá)到動態(tài)平衡，以避免節(jié)點機的空閑等待時間，同時也縮短了各個節(jié)點機的通信開銷，最大化提高了并行機的效率。

由于是基于以太網(wǎng)進行的并行調(diào)度，且各個節(jié)點機互聯(lián)，因此處于一個小型的局域網(wǎng)內(nèi)。根據(jù)任務(wù)圖建立的連接矩陣，查詢各個節(jié)點之間的數(shù)據(jù)傳遞關(guān)系，在進行數(shù)據(jù)的交換過程中，處理機通過廣播數(shù)據(jù)幀，相應(yīng)的MAC地址的處理機接受數(shù)據(jù)即可完成通信。對整個系統(tǒng)每個子任務(wù)的執(zhí)行開銷為：

經(jīng)實際通信測試：

任務(wù)調(diào)度算法的主要思想：由于研究的任務(wù)圖是有向有環(huán)且?guī)Ы徊娣答仯谌蝿?wù)的并行調(diào)度過程中，每個任務(wù)都具有依賴關(guān)系，因此應(yīng)根據(jù)結(jié)構(gòu)圖初始建立的任務(wù)圖構(gòu)建連接矩陣，根據(jù)連接矩陣計算各節(jié)點的輸入、輸出關(guān)系。

按照任務(wù)組的構(gòu)建規(guī)則建立并行調(diào)度的任務(wù)組，再依次將各任務(wù)組映射到各個節(jié)點機上，通過比較各個任務(wù)組的執(zhí)行開銷，進行任務(wù)的動態(tài)組合，以選取最優(yōu)的從機數(shù)目完成任務(wù)的調(diào)度。

算法步驟如下：

(1)開始；

(2)輸入：輸入連接矩陣Cij；

//根據(jù)連接矩陣中每行之和

(4)while(節(jié)點任務(wù)不為空)

{取出其中一個節(jié)點作為當(dāng)前節(jié)點；

if(Ci>2) //Ci代表一個節(jié)點與其他節(jié)點的連接//關(guān)系

for(j=1; j≤n; j++) //取連接矩陣的列

{if(Cji!=0) 將此時對應(yīng)的節(jié)點與 Ci所對應(yīng)的節(jié)點任務(wù)組合，在連接矩陣中查詢組合節(jié)點所對應(yīng)的局部關(guān)系并求和G，取其max(G)進行組合；

if(G相等) 將組合的該任務(wù)組與其他節(jié)點任務(wù)之間建立局部連接關(guān)系并求和G’，取其min(G’)進行組合；

分別記錄任務(wù)組合的各個任務(wù)編號；

}

}

(5)輸出：重新計算任務(wù)組的連接關(guān)系，輸出連接矩陣 Pij；

(7)if(Pi≤2) break; //繼續(xù)判斷各任務(wù)組是否雙//輸入、輸出關(guān)系

else do{將其他節(jié)點任務(wù)與Pi所對應(yīng)的節(jié)點任務(wù)重新組合；}while(該任務(wù)組的輸入和輸出小于或等于 2)；

(8)計算每個任務(wù)組的執(zhí)行開銷Xi；

(9)if (Xi>weight/2&&Xi<2×weight) break；

//條件滿足查詢下個節(jié)點任務(wù)

else do{將其他節(jié)點任務(wù)與該節(jié)點任務(wù)重新組合；}

while(該任務(wù)或者任務(wù)組輸入和輸出小于或等于2&& Xi>weight/2&& Xi<2×weight)；

(10)初始化各節(jié)點機的執(zhí)行開銷：fi=0，將各任務(wù)組依次映射到各個節(jié)點機上；

(11)for(j=1; j≤p; j++) //p為組合的任務(wù)組數(shù)

{在節(jié)點機上依次運算各任務(wù)組，并記錄各任務(wù)組的執(zhí)行開銷 costi, i ∈ (1,2,···,p )}

(12)循環(huán)比較各任務(wù)組的執(zhí)行開銷；

if (各個節(jié)點機任務(wù)均衡) exit；

else {取出max(c osti, i ∈ （1 ,2,···, p） )，將其任務(wù)組進行分解；

while(子任務(wù)不為空)

{取其一個子任務(wù)與其他節(jié)點機上的任務(wù)組進行組合，并建立各自的局部鏈接矩陣，并求其和 Mi,i∈(1,2,…,P?1)；

if(max(Mi)) 將其子任務(wù)與該節(jié)點機上的任務(wù)組組合；

}

go to (12)；

}

(13)算法結(jié)束。

在該算法中，采用了構(gòu)建連接矩陣建立數(shù)據(jù)的連接關(guān)系，并通過各任務(wù)組的計算量和通信量將各任務(wù)組進行動態(tài)組合，實現(xiàn)了各負(fù)載的均衡。由于仿真任務(wù)的周期性，使各個節(jié)點機上的原任務(wù)組和后繼任務(wù)組循環(huán)執(zhí)行，充分利用了有限資源，使系統(tǒng)總的執(zhí)行開銷最小，進而使系統(tǒng)獲得了較好的并行效率。

4 實例分析討論

4.1 任務(wù)圖的重構(gòu)與動態(tài)組合

按照以上連接矩陣的構(gòu)建方法，根據(jù)異步電機的任務(wù)圖按照任務(wù)圖中的節(jié)點順序 1～7建立相關(guān)的連接矩陣，如下所示：

根據(jù)以上調(diào)度算法，具體執(zhí)行如下：

(2)根據(jù)以上計算節(jié)點的輸入或輸出關(guān)系不滿足實驗的硬件條件(BF538為雙網(wǎng)口)，取第1個節(jié)點，根據(jù)連接矩陣的行、列關(guān)系，節(jié)點1與節(jié)點2、節(jié)點4關(guān)系緊密，建立局部的連接矩陣及組合后內(nèi)部連接矩陣，并求其和值比較，則取最小值將節(jié)點1與節(jié)點2進行組合。

(3)取節(jié)點 3，查詢該節(jié)點的輸入、輸出關(guān)系(即連接矩陣中節(jié)點3的非零元素)，由于節(jié)點1與節(jié)點2已組合，則節(jié)點3與節(jié)點6、節(jié)點7存在連接關(guān)系，并建立節(jié)點3與節(jié)點6、節(jié)點7的內(nèi)部連接矩陣和局部連接矩陣，則取其最小值將節(jié)點 3與節(jié)點 7進行組合。

(4)取出節(jié)點4，根據(jù)連接矩陣查詢節(jié)點4的連接關(guān)系，刪除已經(jīng)組合的節(jié)點，則節(jié)點4與節(jié)點5、節(jié)點6存在連接關(guān)系，建立節(jié)點4與節(jié)點5、節(jié)點6的內(nèi)部連接矩陣。比較得出組合后內(nèi)部連接矩陣和值G不相等，取出max(G)(減少節(jié)點間的通信開銷)，則取其最大值將節(jié)點4與節(jié)點5進行組合。

(5)取出節(jié)點6，則查詢連接矩陣中節(jié)點6的連接關(guān)系，節(jié)點6與已組合任務(wù)組3、任務(wù)組7和任務(wù)組4、任務(wù)組5存在連接關(guān)系，則建立節(jié)點6與2個任務(wù)組的內(nèi)部連接關(guān)系。比較得出組合后內(nèi)部連接矩陣和值 G不相等，取出 max(G)。則取其最大值將節(jié)點6與任務(wù)組3、任務(wù)組7進行組合。

根據(jù)以上任務(wù)的組合建立相關(guān)的連接矩陣，進行循環(huán)查詢并計算連接矩陣中每行每列之和(再次判斷是否滿足硬件條件)，根據(jù)如下矩陣得出每個節(jié)點為雙輸入、輸出關(guān)系，滿足條件。

組合的任務(wù)圖如圖3所示。

圖3 重構(gòu)的任務(wù)圖

(6)將各任務(wù)組映射到各節(jié)點機上計算，查詢到節(jié)點機3#上的執(zhí)行開銷大于節(jié)點機1#、2#，任務(wù)的不均衡造成節(jié)點機之間的相互等待，需按照調(diào)度算法中的負(fù)載均衡原則將節(jié)點機3#上的子任務(wù)進行動態(tài)分配?？筛鶕?jù)任務(wù)的組合規(guī)則建立局部的連接矩陣，經(jīng)過調(diào)度算法中的循環(huán)查找最終將任務(wù) 3映射到節(jié)點機 1#上與原始任務(wù)組組合成后繼任務(wù)組1～任務(wù)組3，任務(wù)6映射到節(jié)點機2#上組合成后繼任務(wù)組4～任務(wù)組6。由于任務(wù)7保持在該節(jié)點機上，此時各個節(jié)點機上的任務(wù)組執(zhí)行達(dá)到動態(tài)平衡。則按照此調(diào)度算法進行并行調(diào)度的進程如圖4所示。

圖4 并行調(diào)度的進程

根據(jù)圖4中的并行調(diào)度進程可知，各個節(jié)點機上的任務(wù)都是同時開始執(zhí)行，但節(jié)點機3上的任務(wù)組合3、組合6、組合7需要節(jié)點機1、節(jié)點機2的輸出數(shù)據(jù)，又需避免節(jié)點機之間的空閑等待時間，則節(jié)點機3開始運算的初始數(shù)據(jù)為 0，造成該系統(tǒng)在并行仿真計算中的兩步滯后，但是在一定程度上提高了該并行系統(tǒng)的效率。

根據(jù)以上調(diào)度進程得到最終的分配結(jié)果如表 1所示。

表1 任務(wù)分配結(jié)果

4.2 數(shù)據(jù)測試分析及對比

在并行仿真運算的過程中，由于各從機的負(fù)載量較小，采用 46個字節(jié)的通信時間作為從機之間互通消息的基準(zhǔn)。因此影響系統(tǒng)并行效率的是各從機的執(zhí)行開銷，對并行系統(tǒng)而言加速比和效率是衡量并行計算系統(tǒng)性能最重要的評價標(biāo)準(zhǔn)，這也體現(xiàn)了在并行計算系統(tǒng)上解決實際問題所能獲得的好處。

并行加速比：

其中，Ts是單處理機串行執(zhí)行時間；Tp(q)是指并行使用q臺處理機執(zhí)行所用的時間。則并行效率為：

根據(jù)以上關(guān)系可知，隨著各從機執(zhí)行開銷的增加，并行效率會適當(dāng)提高，但是執(zhí)行開銷受仿真精度和仿真環(huán)節(jié)滯后性的約束，并行效率不會隨之無限增大，而是無限趨于某個值。由于整個系統(tǒng)由幾個典型的環(huán)節(jié)構(gòu)成，因此可采用通用的數(shù)字仿真的方法把每個環(huán)節(jié)編制單獨程序作為單個任務(wù)執(zhí)行。在并行計算系統(tǒng)的基礎(chǔ)上結(jié)合RK4原理實現(xiàn)對單個任務(wù)的運算。按照圖4中的調(diào)度進程進行調(diào)度。

(1)對異步電機進行串行仿真計算一步需要111 μs，運算 10次需 1 110 μs。

(2)按照以上并行調(diào)度算法進行仿真計算兩步需要 83 μs，運算 10 次需 445 μs。

則該系統(tǒng)的并行加速比為：

并行效率為：

若采用流水線調(diào)度，將圖2分成2條流水線的形式，一條流水線依次求解1、2、3環(huán)節(jié)，另一條流水線求解 4、5、6、7環(huán)節(jié)，當(dāng)求解完整個結(jié)構(gòu)圖后系統(tǒng)達(dá)到并行。此方式將整個并行仿真任務(wù)分解到多個并行節(jié)點上求解，這樣每個節(jié)點機上的負(fù)載量較小，在一定程度上提高系統(tǒng)效率。按照多條流水線并行運算的方式對任務(wù)進行調(diào)度，則整個系統(tǒng)的并行時間將取決于最后一個環(huán)節(jié)的運算時間。

(1)對異步電機進行串行仿真計算一步需要111 μs，運算 10次需 1 110 μs。

(2)按照流水線調(diào)度進行仿真計算，運算10次需538 μs。

并行效率為：

實時性數(shù)據(jù)測試：

系統(tǒng)實際運行時間 t=步長×運算次數(shù)=0.000 044×18 000=0.792 s

按照圖4調(diào)度并行系統(tǒng)運算時間t=0.747 030 s。

通過對比以上實驗數(shù)據(jù)及系統(tǒng)的性能指標(biāo)分析可知，該負(fù)載均衡的動態(tài)調(diào)度算法使用較少的處理機完成相應(yīng)的任務(wù)，優(yōu)于流水線調(diào)度，提高了系統(tǒng)效率。系統(tǒng)實際運算時間大于并行系統(tǒng)運算時間，證明了該并行系統(tǒng)滿足實時性的要求。與串行運算相比，在時間復(fù)雜度上有了大幅度的降低。這一點可說明該并行計算系統(tǒng)比較適合用于通信量小但運算量大的場合。

5 結(jié)束語

本文針對有向帶環(huán)且交叉反饋任務(wù)圖提出了一種并行調(diào)度方法。充分考慮實驗的硬件環(huán)境及各節(jié)點機上負(fù)載的均衡性，采用任務(wù)的重組及動態(tài)分配的方式對任務(wù)進行調(diào)度，以選取最優(yōu)的從機數(shù)目完成任務(wù)的調(diào)度。此并行調(diào)度算法既節(jié)省了節(jié)點機之間的通信開銷，又避免了節(jié)點機的空閑等待時間。通過并行效率分析，此方法對運算量較大的系統(tǒng)具有很好的并行調(diào)度效果。

但是該并行仿真方法無法避免仿真的滯后現(xiàn)象，下一步的工作是優(yōu)化提高仿真的精度。由于通信條件及實驗硬件環(huán)境的限制，在無限制地增加執(zhí)行任務(wù)數(shù)的時候，節(jié)點機之間的通信需通過節(jié)點機的轉(zhuǎn)發(fā)，因此今后將改善實驗的運算環(huán)境，優(yōu)化節(jié)點機之間的通信時間。

[1]Huang Zhenyu, Kosterev M, Guttromson R, et al.Model Validation with Hybrid Dynamic Simulation[C]//Proc.of IEEE Power Engineering Society General Meeting.[S.l.]:IEEE Press, 2006: l-9.

[2]Cui Rongxin, Xu Demin, Xu Zhe, et al.Simulation of Autonomous Underwater Vehicles Formation Control Based on Simulink and VRML[J].Journal of System Simulation, 2007, 19(13): 2881-2884.

[3]Xu Zhe, Yan Weisheng, Gao Jian.Simulation of 6DOF AUV Based on Matlab[J].Journal of System Simulation,2007, 19(10): 2241-2243.

[4]Li Yalou, Zhou Xiaoxin, Wu Zhongxi.Personal Computer Cluster Based Parallel Algorithms for Power System Electromechanical Transient Stability Simulation[J].Power System Technology, 2003, 27(11): 6-12.

[5]Wang B, Zha G C.A General Sub-domain Boundary Mapping Procedure for Structured Grid CFD Parallel Computation[C]//Proc.of the 25th Applied Aerodynamics Conference.Miami, USA: [s.n.], 2007.

[6]Andronikos T, Koziris N.Optimal Scheduling for UETUCT Grids into Fixed Number of Processors[C]//Proc.of the 8th Euromicro Workshop on Parallel and Distributed Processing.[S.l.]: IEEE Press, 2000: 237-243.

[7]Ahmad I, Kwok Y K.Benchmarking and Comparison of the Task Graph Scheduling Algorithms[J].Journal of Parallel and Distributed Computing, 1999, 59(3): 381-422.

[8]黎 英, 時維國, 譚昆玲.考慮鐵損時異步電動機的數(shù)學(xué)模型及其仿真研究[J].電氣傳動, 1998, (3): 7-9.

[9]何 琨, 趙 勇, 黃文奇.基于任務(wù)復(fù)制的分簇與調(diào)度算法[J].計算機學(xué)報, 2008, 31(5): 733-740.

[10]杜 杰.網(wǎng)格環(huán)境中基于DAG的并行任務(wù)調(diào)度算法研究[D].上海: 上海交通大學(xué), 2009.