賈燕成，黎 英,2

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

1 概述

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

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

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

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

2 任務(wù)圖描述

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

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

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

2.2 概念和定義

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

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

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

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

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)建

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

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

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

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

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

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

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

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

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

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

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

經(jīng)實(shí)際通信測(cè)試：

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

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

算法步驟如下：

(1)開始；

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

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

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

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

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

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

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

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

分別記錄任務(wù)組合的各個(gè)任務(wù)編號(hào)；

}

}

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

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

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

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

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

//條件滿足查詢下個(gè)節(jié)點(diǎn)任務(wù)

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

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

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

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

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

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

if (各個(gè)節(jié)點(diǎn)機(jī)任務(wù)均衡) exit；

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

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

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

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

}

go to (12)；

}

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

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

4 實(shí)例分析討論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 數(shù)據(jù)測(cè)試分析及對(duì)比

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

并行加速比：

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

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

(1)對(duì)異步電機(jī)進(jìn)行串行仿真計(jì)算一步需要111 μs，運(yùn)算 10次需 1 110 μs。

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

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

并行效率為：

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

(1)對(duì)異步電機(jī)進(jìn)行串行仿真計(jì)算一步需要111 μs，運(yùn)算 10次需 1 110 μs。

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

并行效率為：

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

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

按照?qǐng)D4調(diào)度并行系統(tǒng)運(yùn)算時(shí)間t=0.747 030 s。

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

5 結(jié)束語

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

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

[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í)維國(guó), 譚昆玲.考慮鐵損時(shí)異步電動(dòng)機(jī)的數(shù)學(xué)模型及其仿真研究[J].電氣傳動(dòng), 1998, (3): 7-9.

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

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