異構網絡化汽車電子系統中多DAG離線任務調度

2013-09-18 02:42:20謝國琪李仁發楊帆黃衛紅

通信學報 2013年12期

關鍵詞：排序

謝國琪，李仁發，楊帆，黃衛紅

(湖南大學嵌入式與網絡計算湖南省重點實驗室，湖南長沙 410082)

1 引言

近年來，為了滿足人們在安全性、駕駛性能等方面提出的更高要求，汽車電子系統規模和復雜性驟增。它由動力控制子系統、底盤控制子系統、安全控制子系統和車身控制子系統等多個子系統組成，每個子系統又包括多個功能任務(如安全控制子系統包括防抱死制動、線控剎車等)[1,2]。這些子系統由遍布車身的上百個的異構電子控制單元（ECU,electronic control unit）通過各類異構總線互聯和協作以完成各種智能控制功能[2]。如寶馬7 系，其6個子系統共享70多個ECU，ECU之間通過LIN、CAN、FlexRay、MOST 和Ethernet 5種類型的網絡和網關實現互連[3]；奧迪A8則包含95個ECU遍布7個子系統，由CAN、FlexRay、LIN和MOST 4種總線類型互聯[4]。因此新一代汽車電子系統體系結構演變為異構化、網絡化和復雜化的分布式網絡體系結構。

然而，異構網絡化汽車電子系統是一個典型的混合關鍵級嵌入式系統[5]，對性能與安全關鍵功能子系統的調度要求極其苛刻，例如防抱死制動功能與線控剎車功能，即使調度結果正確，但只要有一個無法在截止期限內完成，執行結果也就毫無意義，甚至造成車毀人亡的災難性后果；與此同時，網絡化使系統產生的通信數據量劇增且結構多樣化，使調度極易產生大量的通信開銷，從而造成系統調度結果延遲，通信開銷已成為影響調度性能的主要瓶頸[1]。因此如何同時保證多個功能子系統都能在截止期限內完成并降低調度長度和減少通信開銷已成為異構網絡化汽車電子系統調度問題所面臨的主要挑戰。

2 調度模型

汽車電子系統的異構化、網絡化使其調度問題變得復雜，因此需要一種形式化的調度模型加以描述。由于汽車電子系統由多個異構 ECU（不同供應商提供的ECU在設計方法或硬件實現上不同）、傳感器和執行器等處理設備組成，本文將這些處理單元統稱為處理器，并用集合描述這些異構處理器的集合。以安全功能子系統為例，它的實現是由多個相互具有數據依賴的任務組成。首先通過攝像頭采集車道偏離、紅外傳感器感知夜視、雷達自適應巡航控制，超聲波輔助停車等；然后通過傳感器融合，目標對象監測和識別技術交由剎車片、方向盤和節流閥等執行設備處理；再由線控轉向、線控剎車、線控加速等功能做出行駛決策。上述功能任務在不同的處理器上執行，并產生大量的通信開銷[6]。

因此，可以用一個有向無環圖DAG描述一個功能子系統[7,8]。G={N,W,E,C}表示一個 DAG，其中，N={n1,n2,…,ni}表示任務集合；由于處理器處理能力的異構性，使不同任務在不同的處理器計算時間不盡相同，因此描述W是一個|N|×|P|的矩陣，wi,k表示任務 ni在 pk上的計算執行時間開銷；E={e1,2,e2,3,…,ei,j}描述為任務間的優先級約束與數據依賴關系集合；由于處理器之間通過 CAN、FlexRay、LIN和MOST 等多種類型的網絡和網關實現互連，不同總線的帶寬不盡相同，因此任務之間的通信開銷也不同，描述 C={c1,2,c2,3,…,ci,j}具有數據依賴的任務之間的通信開銷集合，如果將這2個任務分配到同一個處理器上，則通信開銷為0。 pred(ni)表示任務ni的直接前驅任務集合，ind(ni)表示ni的入度，也就是其直接前驅任務集合的個數，當前任務只有在它全部前驅任務的數據到達后才能執行。succ(ni)表示任務 ni的直接后繼任務集合，outd(ni)表示 ni的出度，也就是直接后繼任務集合的個數。沒有前驅任務的任務為入口任務，記為nentry。沒有后繼任務的任務為出口任務，記為nexit。DAG任務模型不僅考慮了考慮任務的優先級，還考慮了任務和處理器之間的相關性以及任務之間的通信開銷，因此適合于汽車電子系統的調度問題研究。

異構網絡化汽車電子系統包括動力控制子系統、底盤控制子系統、安全子系統和車身子系統等多個網絡子系統，因此需以多DAG[9～13]來表示汽車電子系統調度模型，每個子系統表示一個 DAG，DAG之間共享處理器和通信總線，由于各DAG都是同時發生，因此屬于離線模型。本文用 GS={G1,G2,…,Gm}表示多DAG離線任務調度模型。因此可將異構網絡化汽車電子系統的任務調度問題形式化為多DAG離線任務調度問題并進行研究。以下給出在多DAG中與本文密切相關的幾個概念。

定義1 DAG調度長度(schedule length)。Makerspan(Gm)表示Gm的所有任務調度完畢后，其出口任務的完成時間。

定義2 多DAG調度長度(multiple DAG schedule length)。makerspan(GS)就是GS中具有最大調度長度DAG的調度長度。

如圖1為一個多DAG任務模型，包含DAG-A和DAG-B，表1為相應的多DAG計算開銷矩陣，本文采用與文獻[11]相同的模型實例，如圖1和表1所示，例如圖1中，A1與A2之間的數字18表示任務A1與任務A2若分配不在同一處理器上執行的通信開銷，若A1與A2在分配在同一處理器上，則通信為0；表1中A1與p1所結合表示的數字18表示為任務A1在處理器p1上的計算執行開銷為14。

圖1 2個DAG任務模型實例

3 相關研究與理論知識

謝勇[8]等研究時間觸發網絡總線技術 FlexRay的靜態段配置消息調度，KLOBEDANZ[14,15]等研究FlexRay的靜態段配置容錯調度，然而上述算法僅針對單一網絡總線 FlexRay，且限于同一功能子系統內調度，不適應于汽車電子系統的異構化、網絡化和復雜化需求。

3.1 多DAG任務調度的公平性

異構系統多DAG也包含任務優先級排序和處理器分配 2個步驟。HEFT[7]算法提出了向上排序值的概念，其計算公式為

向上排序值已成為事實的任務優先級排序標準而被多種多DAG任務調度算法采用，但采用平均值wi作為計算開銷，對于大規模的多DAG任務調度，計算結果則不夠精確。

H?NIG[9]等提出了將多個 DAG合成一個復合DAG后，再利用諸如HEFT等經典的單DAG啟發式調度算法調度。但是此方法對于某些短DAG有明顯的不公平性，例如在采用HEFT算法的情況下，盡管它們是同時調度，但是由于短DAG的向上排序值相比長DAG明顯要小，因此短DAG中的任務始終得不到執行，最終造成短DAG調度長度和整個多DAG的調度長度都過長，因此需要在多DAG調度中保證一定的公平性，以降低調度長度。

ZHAO[10]首次指出了在多 DAG調度中的公平性問題，并提出了slowdown驅動的多DAG公平任務調度算法Fairness。其思想是首先基于HEFT算法對每個DAG調度一次且記下每個DAG的調度結果，并把各自的調度長度作為此 DAG的值，然后將所有 DAG按降序排列放入列表，選擇具有最大 slowdown值的就緒任務進行調度，并更新slowdown值(如果有多個DAG的slowdown值相等，則選擇向上排序值最大的任務調度)。slowdown計算公式為

其中，ftown(ni)表示 ni單獨調度的完成時間，ftmulti(ni)表示ni在多DAG中調度的完成時間。如此重復，直到列表中沒有未調度完成的DAG為止。同時文獻[10]也提出了評價DAG不公平性的具體方法，首先計算某個DAG的slowdown值，其計算公式為

其中，makespanown(Gm)表示 Gm單獨調度的調度長度，makespanmulti(Gm)表示 Gm在多 DAG中調度的調度長度。基于slowdown(Gm)計算多DAG系統調度的不公平性，其計算公式為

由于選擇任務調度是slowdown驅動的，因此算法的關鍵思想是 slowdown的更新。此算法雖然在每分配一個任務后通過更新 slowdown值來保證DAG之間的公平性，但還是會產生不公平性的問題。例如，在DAG-A和DAG-B中，它們各自的slowdown值相等并且值都是1，但是DAG-A中就緒任務的向上排序值大于DAG-B，根據策略，則會選擇DAG-A中的就緒任務調度，調度完后，DAG-A的slowdown還是1，則會繼續選擇DAG-A中的就緒任務進行調度，從而造成DAG-B中的就緒任務得不到分配處理器的機會，這樣在調度開始處，就出現對后調度的DAG的不公平問題。田國忠[11]等將Fairness算法改成動態調度算法E-Fairness，除了對新提交的DAG優先調度一次外，沒有其他改進方法。但由于還是 slowdown值驅動選擇任務，因此同樣會出現較高的不公平性。而且Fairness算法和E-Fairness算法在每次分配一個任務后需要更新slowdown值并對各DAG按升序排列，造成算法的復雜度較高，特別是在DAG個數很多的情況下，算法的效率更低。

表1 DAG-A和DAG-B中各任務在處理器上的計算開銷

3.2 多DAG任務調度中的輪轉調度

輪轉調度(round-robin)[17,18]由于具有較好的公平性，在數據通信網絡和多處理器調度中得到了廣泛的應用。LI[17]等提出的DWRR(distributed weighted round-robin)算法則讓大規模多處理器系統的調度具有更好的調度效率和更少的延遲；MOHANTY[18]等提出的 FBDRR(priority based dynamic round robin)等算法則在減少等待時間和響應時間上具有更好的性能。輪轉調度在實現公平調度上具有優勢，并且具有較高的調度效率。

HSU等[12]提出了基于輪轉調度的在線公平調度OWM(online workflow management)算法，在OWM中，其策略是從每一個DAG中選擇一個向上排序值最大的就緒任務放入DAG就緒隊列。然后從 DAG就緒隊列中輪轉選擇最大向上排序值的任務并選擇具有最小完成時間的處理器準備調度。此算法的輪轉調度策略是優先調度最大的就緒任務，而短 DAG就緒任務的相比長DAG就緒任務的總是要短，因此對短DAG造成了明顯的不公平性，策略標準過于單調。

ARABNEJAD等[13]提出了基于輪轉調度的FDWS(fairness dynamic workflow scheduling)算法，該算法也是在線調度，其策略也是從每一個 DAG中選擇一個向上排序值最大的就緒任務放入就緒隊列，然后從就緒隊列中不再選擇具有向上排序值的任務，而是根據各個DAG剩余的未調度任務的比例及其關鍵路徑長度定義了一個 rankr值，其計算公式為

其中，PRT表示剩余任務數的百分比，CPL表示關鍵路徑長度。此算法在考慮插入的基礎上將任務分配具有最小完成時間的處理器，但由于短DAG的rankr相比長DAG總是要長，策略標準同樣較單調，因而此算法對長DAG造成了明顯的不公平性。雖然OWM和FDWS都是在線調度，但只要多個DAG同時發生，也就簡化成了離線調度。

與單 DAG任務調度的最大不同之處在于多DAG任務調度必須要保證每個DAG中的每個任務都能夠及時被調度。表2總結出了目前多DAG任務調度算法的特點，其中，M_HEFT算法即將多個DAG合成一個DAG后，再使用HEFT算法調度。

綜上所述，現有多DAG任務調度算法并不能適應于當今汽車電子系統的異構化、網絡化和復雜化特征，主要體現在：slowdown值驅動的多DAG公平任務調度算法復雜度高，且容易在開始調度時就出現較高的不公平性；輪轉調度的多DAG公平任務調度算法的策略標準過于單調而易導致不公平性；通信開銷已成為影響調度性能的主要瓶頸，但缺乏相應的解決方案。汽車電子系統是一個典型的混合關鍵級嵌入式系統，既需要確保實時性又要降低調度長度。為此，本文旨在通過采用減少通信開銷的輪轉調度的任務優先級公平排序標準以及綜合考慮通信開銷、完成時間和拓撲結構的處理器選擇標準。提出相應的減少通信開銷、降低調度長度和滿足安全關鍵與實時性的多DAG離線任務調度算法，以適應于汽車電子系統的異構化、網絡化和復雜化需求。

表2 4種多DAG任務調度算法比較

4 調度算法

下面通過圖1和表1所示的多DAG任務調度模型來說明本文所提出的調度方法。這個多 DAG調度模型的復雜度、結構及各項參數與文獻[11]使用的實例完全一樣。

4.1 任務優先級排序

1)DAG內的任務優先級排序

由于 E-Fairness[11]、OWN[12]和 FDWS[13]等多DAG任務調度算法使用經典的任務優先級排序ranku(ni)中采用平均值wi作為計算開銷，實際上將處理器的異構特性消除，演變成同構計算。本文考慮異構計算特性，認為每個任務在每個處理器上都要有相應的向上排序值rankupd(ni，pk)，計算公式為

任務的出度也是影響任務優先級排序的因素。直接后繼節點更多的任務如果不優先執行，則其所有后繼節點都不能就緒，直接或間接地加大了DAG的調度長度。所以把任務的出度當作計算向上排序值的因子。

這樣得出的 r ankupd(ni)更符合異構化特征。依據圖1和表1提供的多DAG實例，可計算出每個任務的向上排序值rankupd(ni,pk)和rankupd(ni)，如表3所示。

2) 多DAG任務公平性優先級排序

定義 3 通信開銷權值(COW, communication overhead weight)。任務ni的通信開銷權值cow(ni)表示此任務與其所有直接前驅可能產生的最大通信開銷之和，其計算公式為

slowdown值驅動的多DAG公平任務調度算法復雜度高，不公平性也高，特別是在多DAG規模很大的情況下，算法的效率更低，因此不適應于復雜化的汽車電子系統。本文也采用公平性較好的輪轉調度，針對多DAG系統GS={G1,G1,…,Gm}，首先分別從各DAG就緒任務中取出一個rankupd(ni)最大的就緒任務放入 REDAY_QUEUE。對于 REDAY_QUEUE隊列中的就緒任務，如果其通信開銷權值較大，說明其容易與其直接前驅節點產生更大的通信開銷；如果此任務優先執行，則處理器空閑槽出現的幾率大增，從而造成調度長度過長。

汽車電子系統的異構化和網絡化使通信數據劇增，各總線的帶寬又受限，再加上調度產生的大量開銷，則使網絡負載不堪重負，因此減少通信開銷成為調度的主要目標之一，因此，本文優先調度通信開銷權值較小的任務，則會盡可能地減少空閑槽出現的幾率。本文提出基于通信開銷權值的輪轉調度的公平排序標準，具體策略為：

(a) 計算每個 DAG中每個任務的向上排序值rankupd(ni)；

(b) 分別從各DAG中取出一個rankupd(ni)最大的就緒任務，放入到 DAG的就緒隊列 REDAY_QUEUE；

表3 DAG-A和DAG-B中的向上排序值

(d) 從REDAY_QUEUE中輪轉選擇具有最小通信開銷權值的任務分配處理器，直到 REDAY_QUEUE為空再重復步驟（b）。

4.2 處理器選擇

相比任務優先級排序，處理器選擇則更加復雜。例如，DAG-B中，如果將所有任務分配到同一個處理器，那么其總通信開銷為 0，但使調度長度最大串行化；反之，如果將任務負載均衡的分配到相應處理器，不但不一定使調度長度最小化，而且可能消耗較大的通信開銷。

1) 處理器選擇值

定義4 最早開始時間（EST, earliest start time）。est(ni, pk)表示在處理器pk上，從入口任務nentry到任務ni的最長路徑長度(不包含ni本身的計算時間)，也就是在處理器pk上，ni最早可能開始執行的時間，計算公式為

其中，cj,i為任務nj和任務ni的通信開銷，xj,i取值為 0或 1， nj∈ p red(ni)，若任務nj和任務ni分配在同一處理器上則xj,i=0，否則xj,i=1； a vail[k]表示處理器pk獲得的最早可用時間； a ft(nk)表示任

i務ni的實際完成時間且ni被分配在處理器pk執行，由此公式可知當ni為出口任務時，a f t(nk)為DAG

exit的調度長度，因此 a ft(nk)影響DAG的調度長度。

j任務ni在處理器pk的最早完成時間eft(ni, pk)表示為

E-Fairness、OWN和FDWS等多DAG任務調度算法都以最早完成時間eft(ni，pk)作為分配處理器的策略，一方面以“向下看”的角度綜合考慮了調度長度和通信開銷；但另一方面，忽略了DAG的拓撲結構對調度長度的影響，即還需要以“向上看”的角度考慮調度完相應任務后，此任務距離出口的時間和通信開銷。用處理器選擇值select(ni, pk)代替eft(ni, pk)，計算公式為

在同構計算環境下， r ankupd(ni, pk)和 wi,k對每個處理器而言都是相等的，不需要考慮，這也說明了E-Fairness、OWN和FDWS算法在處理器分配上也是在同構計算環境下進行的。而 s elect(ni, pk)的計算則從“向下看”和“向上看”的角度，綜合考慮調度長度和通信開銷對處理器分配的影響。

2) 插入分配法

正如圖 2(c)所示，多DAG任務調度中，可將符合插入條件的任務插入到所有因優先級約束和通信開銷造成的處理器空閑槽中，以提高處理器利用率，并能降低調度長度。插入分配過程為：

(a) 記錄每個處理器的空閑時間段，用 SLOT_SET(pk)表示pi的空閑槽集合，每個處理器都有一個空閑槽集合；

(b) 在對任務 ni進行處理器分配時，遍歷所有處理器，搜尋滿足[est(ni，pk)， eft(ni，pk) ] 屬于SLOT_SET (pk)的處理器空閑段；

為此，得出本文的多DAG處理器選擇標準：將從DAG的就緒隊列REDAY_QUEUE中選擇的任務，在考慮插入法的基礎上分配到具有最小選擇值的處理器上調度，直到 REDAY_QUEUE中的任務全部分配到相應的處理器。

4.3 公平調度算法

定義 5 DAG 通信開銷 (DOC, DAG communication overhead)。Gm中具有直接優先級約束的所有任務因沒有分配在同一個處理器而消耗的通信開銷之和，即

DAG本身可能產生的最大通信開銷則為

定義6 多DAG通信開銷率(MDCOR, multiple DAGs communication overhead ratio)。指多DAG中，所有DAG的通信開銷之和與其可能產生的最大通信開銷之和的比值。那么，由M個DAG組成的多DAG 系統 GS={G1,G1,…,Gm}調度完成所付出的通信開銷率表示為

基于4.1節提出的多DAG任務優先級排序標準和4.2節提出的多DAG處理器選擇標準，本節提出以降低調度長度和減少通信開銷為目標的，適用于異構網絡化汽車電子系統中的多DAG離線公平任務調度算法 MDOFTS(multiple DAG off-line and fairness task scheduling)。

算法1 MDOFTS算法for(DAG個數)

計算每個DAG中任務的向上排序值rankupd(ni，pk)，rankupd(ni) 與通信開銷權值 cow(ni)；

end for

計算出擁有的最大任務數的DAG，并將個數設置為n

for(var i=1∶ n)for(DAG個數)

分別從各DAG中取出一個向上排序值最大的就緒任務，放入到任務的就緒隊列 REDAY_QUEUE

end for

for(DAG個數)基于公平輪轉調度，從REDAY_QUEUE中選擇具有最小通信開銷權值cow(ni)的任務ni

獲取任務ni所在DAG為Gm

計算 ni在每個處理器上的選擇值 select(ni, pk)考慮插入法的基礎上將ni分配到選擇值select (ni, pk)最小的處理器上更新Gm的通信開銷dco(Gm)更新GS通信開銷率mdcor(GS)end for end for

MDOFTS 算法的時間復雜度為 O(n2×d×p)，其中n為擁有最多任務數的DAG所包含的任務數，d為DAG個數，p為處理器個數。

證明調度完所有DAG，遍歷任務次數的時間復雜度為O(n)，遍歷所有DAG的時間復雜度為O(d)；計算ni的select (ni，pk)需要遍歷它的前驅和各個處理器的時間復雜度為O(n×p)。所以MDOFTS總的算法時間復雜度為O(n2×d×p)，證畢。

圖2為5種算法的調度Gannt圖，表4為相應計算結果。DAG-A和DAG-B的總的通信開銷為241和35。從結果可以看出，MDOFTS算法調度長度為 78，其他算法的調度長度都在 81以上，MDOFTS算法優勢比較明顯；在通信開銷率方面，MDOFTS算法僅為0.264 5，而其他算法的通信開銷都在0.529 0以上，MDOFTS算法在減少通信開銷方面的優勢相當明顯；公平性方面，盡管MDOFTS算法的不公平性相比 OWN(off-line)和 FDWS (offline)要高一點，但是任務優先級排序結果相比這 2個算法更具有公平性。因此，實例結果顯示，MDOFTS算法在沒有提高算法時間復雜度的情況下，不僅保證了調度長度更短，而且能夠顯著減少通信開銷，還具有很好的公平性。

圖2 5種算法公平調度DAG-A和DAG-B的Gannt圖

表4 5種算法公平調度DAG結果比較

4.4 優先級調度算法

盡管公平性是需要關注的重點，但是對于混合關鍵級嵌入式系統，每個子系統都有相應的關鍵級劃分，例如底盤控制等安全關鍵子系統，有嚴格的截止期限要求，如果不能在規定的時間內完成, 執行結果也就毫無意義。因此需要優先執行安全關鍵的DAG應用，這就是DAG之間存在的混合關鍵優先級。針對上述情況，本節提出多DAG離線優先級任務調度 MDOPTS(multiple DAGs off-line and priority task scheduling)算法，調度策略如下。

1) 對于優先級高的DAG中的所有任務都要優先于優先級低的DAG中的所有任務。只有當優先級高的DAG中的所有任務分配處理器后，優先級低的DAG中的任務才能分配處理器。

2) 優先級低的DAG中的所有任務在考慮插入法的基礎上按最小選擇值分配處理器。其選擇值的計算公式需調整為式(15)。因為低優先級DAG的入口節點nentry的開始時間得到了一定的推遲，其所有后繼節點的時間計算都要做相應調整，即

算法2 MDOPTS算法

for(DAG個數) do

計算每個 DAG中任務的向上排序值rankupd(ni,pk), rankupd(ni)與通信開銷權值 cow(ni)及任務個數，并將任務放入各DAG的任務隊列

end for

對所有DAG按給定的關鍵優先級降序放入關鍵級DAG隊列

while 有DAG可以調度 do

從關鍵級DAG隊列中取出未調度完成且具有最大優先級的DAG

while當前DAG的任務隊列有任務可以調度do選擇隊列中具有最大rankupd(ni)的就緒節點ni計算 ni在每個處理器上的最早完成時間eft(ni,pk)和select(ni,pk)考慮插入法的基礎上將 ni分配到選擇值select (ni,pk)最小的處理器上

更新Gm的通信開銷dco(Gm)

更新GS通信開銷率mdcor(GS)標記ni為已調度任務

end while

標記當前DAG已調度

end while

MDOPTS算法的時間復雜度為O(n2×d×p)

證明調度完所有DAG，遍歷所有DAG的時間復雜度為O(d); 調度就緒隊列中的任務，需要遍歷一次的時間復雜度為O(n)；遍歷處理器并計算任務在每個處理器上的最早完成時間，其時間復雜度為O(n×p)。所以MDOPTS總的算法時間復雜度為O(n2×d×p)，證畢。

4.5 自適應調度算法

MDOPTS算法雖然能夠滿足實時性，但卻使低優先級的DAG沒能及時分配到處理器，從而加大了整個多DAG的調度長度，造成性能明顯下降。然而實時系統并不是必須要求優先級高的DAG中的所有任務都要優先于優先級低的DAG中的所有任務，而是只要在截止期限內調度完成優先級高的DAG中的所有任務即可。本節提出多DAG離線任務自適應調度MDOATS (multiple DAG off-line and priority task scheduling) 算法，在確保實時性的前提下，降低整個多DAG的調度長度和減少通信開銷。調度策略如下。

1) 通過MDOPTS算法保證某些DAG在截止期限內完成，通過MDOFTS算法降低多DAG的調度長度和減少通信開銷。

2) 用MDOFTS預調度多DAG系統，并判斷高優先級系統是否滿足截止期限，如果滿足，則直接用MDOFTS調度；否則，用MDOPTS調度高優先級DAG中的第一個就緒任務。如此重復，直到所有DAG全部調度完畢。即依據截止期限和公平調度結果自適應的采用MDOPTS算法和MDOFTS算法。

算法3 MDOATS調度算法for(DAG個數) do

計算每個DAG中任務的向上排序值rankupd(ni, pk)，rankupd(ni)與通信開銷權值cow(ni),，并放入各DAG的任務隊列

end for

對所有DAG按關鍵優先級降序并放入DAG隊列while 有DAG可以調度 do

從 DAG隊列中取出未調度完成且具有最大優先級的DAG為Gx，其截止期限為deadline(Gx)

用MDOFTS算法單調調度Gx，計算出其調度長度為makerspan(Gx)

if makerspan(Gx)≤deadline(Gx)while(Gx中有任務可以調度) do

用MDOFTS算法預調度多DAG系統,并更新Gx的調度長度makerspan(Gx)從Gx中取出向上排序值最大的就緒任務if makerspan(Gx)≤deadline(Gx)用MDOFTS調度算法調度此任務else用MDOPTS調度算法調度此任務end if end while else該多DAG系統不可調度,調度失敗end if

end while

MDOATS算法的時間復雜度為O(n3×d2×p)

證明調度完所有DAG，遍歷所有DAG的時間復雜度為O(d)；調度就緒隊列中的任務，需要遍歷一次的時間復雜度為 O(n)；用 MDOFTS和MDOPTS調度的算法復雜度都為 O(n2×d×p)。所以MDOATS 總的算法時間復雜度為O(n3×d2×p)，證畢。

圖 3為 DAG-B截止期限為 40的情況下，MDOFTS、MDOPTS和 MDOATS算法調度的Gannt圖，表4為相應計算結果。從結果可以看出，MDOFTS由于采用了公平輪轉調度，其多DAG的調度長度最短，但是DAG-B的截止期限要求是40，而 MDOFTS調度的結果為 41，因此不能滿足DAG-B的實時性，用此算法調度多DAG將會失敗；MDOPTS針對DAG-B的截止期限要求，優先調度DAG-B，盡管滿足了DAG-B的實時性，但由于調度公平性差，因而造成多DAG的調度長度過長，使 DAG的運行時間過長，造成性能下降；MDOATS綜合考慮MDOFTS算法和MDOPTS算法的特點，采用自適應調度策略，既能降低調度長度，又滿足截止期限，因此很適合實時系統應用。盡管MDOATS算法的時間復雜度較高，但對于同時發生的多 DAG調度屬于編譯時調度，因此并不會影響運行時性能。而且當優先級 DAG數量不多時，MDOATS非常接近于MDOFTS，因為如果采用MDOFTS能滿足所有多DAG的實時性，那么MDOATS的調度結果就是MDOFTS的調度結果。

表5 3種算法調度DAG結果比較(deadlineb=40)

圖3 3種算法調度DAG-A和DAG-B的Gannt圖(deadlineb=40)

5 實驗

5.1 評價指標

本文采用加速比(speedup)[7,11]、通信開銷率(MDCOR)、不公平性(unfairness)以及端到端最差響應時間(WCRT, worst-case response time)[19]作為評價指標。

加速比即在一個處理器上串行執行多 DAG中的調度長度最大的DAG的所有任務使用的最少時間與其實際調度長度的比值。調度算法產生的加速比越大，說明算法越高效，加速比計算公式為

多DAG的通信開銷率采用式(14)計算，通信開銷率越低，說明算法越高效。不公平性采用式(4)計算，不公平性越低，算法越高效。

在汽車電子系統中，消息集的 WCRT 定義為消息集的第一個消息所分配的 ECU觸發就緒到傳輸完畢到達最后一個消息所在 ECU節點之間的時間段，WCRT越短，算法越高效。

實驗的硬件環境為一臺具有奔騰雙核處理器(3.2 GHz/2.0 GB RAM)的Windows XP機器上，所使用的軟件工具有Java和Highcharts，DAG任務圖生成工具TGFF 3.5 (task graphs for free)[20]。根據不同參數生成各種特性不同的加權DAG。多DAG系統的DAG個數為 gs={2,4,10,20,40,60,80,100}，關鍵級 sc={1,2,3,4}，Gm的截止期限長度統一為makerspan(Gm)的90%。產生隨機DAG的參數設置為任務個數n={30,40,50,60,70,80,90,100}，最大出度β={1,2,3,4,5}，最大入度γ={1, 2, 3, 4, 5}，任務在不同處理器上執行時間的差異度 η={0.1, 0.5,1.0}。假設 wi表示任務 ni的平均計算開銷，那么ni在處理器 pk上的計算開銷可以通過公式產生而得，即

通過生成具有不同特征的大量隨機DAG，并在一個由 15個異構多處理器芯片組成的網絡計算系統中運行。

5.2 實驗結果及分析

實驗1 針對多個DAG樣本，探究加速比隨任務數和 DAG數變化的情況，每個數據點值是由2 000個實驗次數得出的平均值。從圖4和圖5得知：1)隨著系統規模增長，加速比都提高；2)MDOFTS的平均Speedup都優于其他算法，分別達20%以上，說明MDOFTS采用的公平輪轉策略能夠明顯地縮短調度長度，而且選擇處理器時綜合“向上看”和“向下看”的原則，相比其他算法僅“向下看”的原則，優勢明顯。

圖4 平均加速比隨任務數變化

圖5 平均加速比隨DAG數變化

實驗2 針對多個DAG樣本，分析通信開銷率隨任務數和DAG數變化情況，如圖6和圖7所示：1）通信開銷率隨任務數和 DAG數而提高，說明隨著系統規模和復雜性增長，通信任務大增，造成通信開銷加大；2）MDOFTS和MDOATS算法相比其他算法優勢比較明顯，通信開銷率始終保持在12%～44%之間，在最好情況超過了 50%，說明基于通信開銷權值的輪轉調度策略能夠顯著減少通信開銷，相比其他算法調度目標更加明確，性能更加優越。

圖6 平均通信開銷率比隨任務數變化

圖7 平均通信開銷率比隨DAG數變化

實驗3 分析不公平性隨任務數和DAG數變化的情況，實驗結果如圖8和圖9所示。可以看出在任務數或DAG數目較小時，MDOFTS和MDOATS算法優勢并不明顯；但隨著DAG數目的增多，相比其他算法的優勢分別達到20%以上，說明隨著系統規模和復雜性增大，各DAG包含的任務數和屬性不盡相同，使有些公平調度算法對長DAG或短DAG等造成一定的不公平性，而MDOATS的輪轉調度策略不僅滿足實時性，還具有較好的公平性。

實驗4 在真實消息集環境下分析WRCT隨消息任務數變化的情況，采用日本名古屋大學高田研究室提供的單個CAN網絡的真實消息集[19]，該實驗集包括65個消息任務，并且被分配到14個ECU之中，由于目前關于汽車電子網絡的研究都是基于單個網絡的情況，故本文將上述消息集分解為2個CAN網絡消息子集，其中，DAG_1為33個，DAG_2為32個。實驗結果如圖10～圖12所示，從結果可以看出，MDOFTS的WRCT算法最短，優于其他算法20%以上。MDOFTS和MDOATS算法的通信開銷和不公平性也都優于其他算法。

圖8 平均不公平性比隨任務數變化

圖9 平均不公平性比隨DAG數變化

圖10 WCRT隨消息數變化

圖11 平均通信開銷率隨消息數變化

圖12 平均不公平性隨消息數變化

以上4次實驗的結果表明，本文所提出的相關多DAG離線任務調度算法在調度長度、通信開銷和不公平性相比E-Fairness(off-line)、OWN(off-line)和 FDWS(off-line)等算法都要優；在真實消息集環境下，具有更好的結果，因而能夠很好地適應于異構網絡化汽車電子系統的多DAG離線任務調度。了以滿足安全關鍵DAG的多DAG離線優先級任務調度算法MDOPTS，并綜合MDOFTS和MDOPTS，提出多DAG離線自適應任務調度算法MDOATS，在滿足實時性的基礎上提高調度性能。最后利用仿真實驗將本文提出的算法與相關算法進行比較，得到本文所提出的算法在保證公平性的條件下，能夠有效降低調度長度，極大地減少通信開銷，產生更低的最差響應時間，具有更好的調度性能。

[1] BUCKL C, CAMEK A, KAINZ G , et al. The software car∶ building ICT architectures for future electric vehicles[A]. 2012 IEEE International Electric Vehicle Conference(IEVC)[C]. Kuching,Malaysia, 2012.1-8.

[2] FURST S. Challenges in the design of automotive software[A].Proceedings of the Conference on Design, Automation and Test in Europe[C]. Dresden, Germany, 2010. 256-258

[3] KONIK D. Development of the dynamic drive for the new 7series of the BMW group[J]. International Journal of Vehicle Design, 2002,28(1)∶131-149

[4] Audi A8’10 electrical and network systems[EB/OL]. http∶//www.audionlinetraining.com, 2010.

[5] BARUAH S K, BURNS A, DAVIS R I. Response-time analysis for mixed criticality systems[A]. The 32nd IEEE Real-Time Systems Symposium[C]. Vienna, Austria, 2011.34-33.

[6] ALDERISI G, CALTABIANO A, VASTA G, et al. Simulative assessments of IEEE 802.1 Ethernet AVB and time-triggered Ethernet for advanced driver assistance systems and in-car infotainment[A].Vehicular Networking Conference(VNC)[C]. Seoul, Republic of Korea,2012.187-194.

[7] TOPCUOGLU H, HARIRI S, WU M. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3)∶ 260-274.

[8] 謝勇, 李仁發, 阮華斌等. 最優的 FlexRay 靜態段配置算法[J]. 通信學報, 2012, 33(11)∶33-40.XIE Y, LI R F, RUAN H B, et al. Optimal Configuration algorithm for static segment of FlexRay[J]. Journal on Communications, 2012,33(11)∶33-40.

[9] H?NIG U, SCHIFFMANN W. A meta-algorithm for scheduling multiple DAGs in homogeneous system environments[A]. The 18th International Conference on Parallel and Distributed Computing Systems[C]. Dallas, USA, 2006.147-152.

[10] ZHAO H N, SAKELLARIOU R. Scheduling multiple DAGs onto heterogeneous systems[A]. The 20th International Parallel and Distributed Processing Symposium[C]. Rhodes Island, Greece, 2006.

[11] 田14國.忠, 肖創柏, 徐竹勝等. 異構分布式環境下多 DAG 工作流的

6 結束語

本文面向異構網絡化汽車電子系統領域進行調度問題研究，以多DAG離線任務模型為基礎，分析了現有多DAG任務調度算法；然后提出基于通信開銷權值的輪轉調度公平任務排序標準和在考慮插入法的基礎上將任務分配到具有最小選擇值的處理器上作為處理器選擇標準。綜合這2個標準提出了面向異構網絡化汽車電子系統中的多DAG離線公平任務調度MDOFTS算法；接著提出混合調度策略[J]. 軟件學報, 2012, 23(10)∶2720-2734.TIAN G Z, XIAO C B, XU Z S, et al. Hybrid scheduling strategy for multiple DAGs workflow in heterogeneous system[J]. Journal of Software, 2012, 23(10)∶2720 -2734.

[12] HSU C C, HUANG K C, WANG F J. On line scheduling of workflow applications in grid environments[J]. Future Generation Computer Systems, 2011, 27(6)∶860-870.

[13] ARABNEJAD H, BARBOSA J. Fairness resource sharing for dynamic workflow scheduling on Heterogeneous Systems[A]. 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications (ISPA)[C]. Madrid, Spain, 2012.[14] K63L3O-6B3E9D.ANZ K, KOENIG A, MUELLER W. A reconfiguration approach for fault-tolerant flexray networks[A]. Design, Automation& Test in Europe Conference & Exhibition (DATE)[C]. Grenoble,France, 2011.1-6.

[15] KLOBEDANZ K, KOENIG A, MUELLER W, et al.Self-reconfiguration for fault-tolerant flexRay networks[A]. 2011 14th IEEE International Symposium on Distributed Computing Workshops(ISORCW)[C]. Newport Beach, CA, 2011.207-216.

[16] HAGRAS T, JANE?EK J. A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems[J]. Parallel Computing, 2005, 31(7)∶653-670.

[17] LI T, BAUMBERGER D, HAHN S. Efficient and scalable multiprocessor fair scheduling using distributed weighted roundrobin[J]. ACM Sigplan Notices, 2009, 44(4)∶65.

[18] MOHANTY R, BEHERA H S, PATWARI K, et al. Priority based dynamic round robin (PBDRR) algorithm with intelligent time slice for soft real time systems[J]. International Journal of Advanced Computer Seience and Applications, 2011, 2(2)∶46-50.

[19] CHEN Y, ZENG G, RYO K, et al. Effects of queueing jitter on worst-case response times of CAN messages with offsets[A]. In Proc of the Embedded System Symposium in Japan[C]. Tokyo, Japan,2012.119-126.

[20] DICK R P, RHODES D L, WOLF W. TGFF∶ task graphs for free[A].Proceedings of the 6th International Workshop on Hardware/Software Codesign[C]. Seattle, USA, 1998.97-101.