實時仿真并行調度算法研究

賈燕成，黎 英,2

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

1 概述

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

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

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

針對一種有向帶環且交叉反饋的DAG任務圖，任務且具有周期性的特點，本文提出了一種基于負載均衡性的任務動態組合調度方法。

2 任務圖描述

2.1 系統調度的結構圖

為了分析基于有向帶環且具有復雜交叉反饋任務圖的并行調度算法的可行性，采用異步電機的動態數學模型[8]為實例進行研究，其異步電機的動態模型如圖1所示。

圖1 異步電機在同步旋轉坐標系下的結構

2.2 概念和定義

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

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

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

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

C=[Ci,j]表示任務之間通信數據量的集合；Ci,j表示任務i發送給任務j的數據量。

T=[ti]表示任務的Vi的循環周期。

2.3 任務圖的構建

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

圖2 異步電機任務圖

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

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

3 調度算法設計

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

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

定義2 任務組是任務圖中多個相關任務的合并，且被映射到同一個處理機執行的任務集合。

規則 1 任務組組建規則：實驗環境采用 BF538作為節點機，具有雙網口，可允許各節點機有2個數據輸入或輸出。由于在并行調度過程中會產生一定的通信開銷，因此組建的任務組其執行開銷應優于通信開銷，也即各節點機的執行開銷應滿足weight /2 ＜ xi＜ 2weight ，其中，weight為從機之間的通信開銷，并且根據連接矩陣中各個任務之間的連接關系應盡量減少任務之間通信開銷。

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

由于是基于以太網進行的并行調度，且各個節點機互聯，因此處于一個小型的局域網內。根據任務圖建立的連接矩陣，查詢各個節點之間的數據傳遞關系，在進行數據的交換過程中，處理機通過廣播數據幀，相應的MAC地址的處理機接受數據即可完成通信。對整個系統每個子任務的執行開銷為：

經實際通信測試：

任務調度算法的主要思想：由于研究的任務圖是有向有環且帶交叉反饋，在任務的并行調度過程中，每個任務都具有依賴關系，因此應根據結構圖初始建立的任務圖構建連接矩陣，根據連接矩陣計算各節點的輸入、輸出關系。

按照任務組的構建規則建立并行調度的任務組，再依次將各任務組映射到各個節點機上，通過比較各個任務組的執行開銷，進行任務的動態組合，以選取最優的從機數目完成任務的調度。

算法步驟如下：

(1)開始；

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

//根據連接矩陣中每行之和

(4)while(節點任務不為空)

{取出其中一個節點作為當前節點；

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

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

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

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

分別記錄任務組合的各個任務編號；

}

}

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

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

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

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

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

//條件滿足查詢下個節點任務

else do{將其他節點任務與該節點任務重新組合；}

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

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

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

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

(12)循環比較各任務組的執行開銷；

if (各個節點機任務均衡) exit；

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

while(子任務不為空)

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

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

}

go to (12)；

}

(13)算法結束。

在該算法中，采用了構建連接矩陣建立數據的連接關系，并通過各任務組的計算量和通信量將各任務組進行動態組合，實現了各負載的均衡。由于仿真任務的周期性，使各個節點機上的原任務組和后繼任務組循環執行，充分利用了有限資源，使系統總的執行開銷最小，進而使系統獲得了較好的并行效率。

4 實例分析討論

4.1 任務圖的重構與動態組合

按照以上連接矩陣的構建方法，根據異步電機的任務圖按照任務圖中的節點順序 1～7建立相關的連接矩陣，如下所示：

根據以上調度算法，具體執行如下：

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

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

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

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

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

組合的任務圖如圖3所示。

圖3 重構的任務圖

(6)將各任務組映射到各節點機上計算，查詢到節點機3#上的執行開銷大于節點機1#、2#，任務的不均衡造成節點機之間的相互等待，需按照調度算法中的負載均衡原則將節點機3#上的子任務進行動態分配。可根據任務的組合規則建立局部的連接矩陣，經過調度算法中的循環查找最終將任務 3映射到節點機 1#上與原始任務組組合成后繼任務組1～任務組3，任務6映射到節點機2#上組合成后繼任務組4～任務組6。由于任務7保持在該節點機上，此時各個節點機上的任務組執行達到動態平衡。則按照此調度算法進行并行調度的進程如圖4所示。

圖4 并行調度的進程

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

根據以上調度進程得到最終的分配結果如表 1所示。

表1 任務分配結果

4.2 數據測試分析及對比

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

并行加速比：

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

根據以上關系可知，隨著各從機執行開銷的增加，并行效率會適當提高，但是執行開銷受仿真精度和仿真環節滯后性的約束，并行效率不會隨之無限增大，而是無限趨于某個值。由于整個系統由幾個典型的環節構成，因此可采用通用的數字仿真的方法把每個環節編制單獨程序作為單個任務執行。在并行計算系統的基礎上結合RK4原理實現對單個任務的運算。按照圖4中的調度進程進行調度。

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

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

則該系統的并行加速比為：

并行效率為：

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

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

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

并行效率為：

實時性數據測試：

系統實際運行時間 t=步長×運算次數=0.000 044×18 000=0.792 s

按照圖4調度并行系統運算時間t=0.747 030 s。

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

5 結束語

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

但是該并行仿真方法無法避免仿真的滯后現象，下一步的工作是優化提高仿真的精度。由于通信條件及實驗硬件環境的限制，在無限制地增加執行任務數的時候，節點機之間的通信需通過節點機的轉發，因此今后將改善實驗的運算環境，優化節點機之間的通信時間。

[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]黎 英, 時維國, 譚昆玲.考慮鐵損時異步電動機的數學模型及其仿真研究[J].電氣傳動, 1998, (3): 7-9.

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

[10]杜 杰.網格環境中基于DAG的并行任務調度算法研究[D].上海: 上海交通大學, 2009.