異構(gòu)網(wǎng)絡化汽車電子系統(tǒng)中多DAG離線任務調(diào)度

謝國琪，李仁發(fā)，楊帆，黃衛(wèi)紅

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

1 引言

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

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

2 調(diào)度模型

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

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

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

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

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

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

圖1 2個DAG任務模型實例

3 相關研究與理論知識

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

3.1 多DAG任務調(diào)度的公平性

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

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

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

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

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

其中，makespanown(Gm)表示 Gm單獨調(diào)度的調(diào)度長度，makespanmulti(Gm)表示 Gm在多 DAG中調(diào)度的調(diào)度長度?；趕lowdown(Gm)計算多DAG系統(tǒng)調(diào)度的不公平性，其計算公式為

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

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

3.2 多DAG任務調(diào)度中的輪轉(zhuǎn)調(diào)度

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

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

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

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

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

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

表2 4種多DAG任務調(diào)度算法比較

4 調(diào)度算法

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

4.1 任務優(yōu)先級排序

1)DAG內(nèi)的任務優(yōu)先級排序

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

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

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

2) 多DAG任務公平性優(yōu)先級排序

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

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

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

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

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

(c) 基于通信開銷權(quán)值，對REDAY_QUEUE升序排序；

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

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

4.2 處理器選擇

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

1) 處理器選擇值

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

其中，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執(zhí)行，由此公式可知當ni為出口任務時，a f t(nk)為DAG

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

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

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

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

2) 插入分配法

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

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

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

(c) 如果只存在唯一的空閑段，則直接插入的；如果存在多個處理器的空閑段，則選擇選擇值最小處理器插入，并更新相應的SLOT_SET。

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

4.3 公平調(diào)度算法

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

DAG本身可能產(chǎn)生的最大通信開銷則為

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

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

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

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

end for

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

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

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

end for

for(DAG個數(shù))基于公平輪轉(zhuǎn)調(diào)度，從REDAY_QUEUE中選擇具有最小通信開銷權(quán)值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為擁有最多任務數(shù)的DAG所包含的任務數(shù)，d為DAG個數(shù)，p為處理器個數(shù)。

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

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

圖2 5種算法公平調(diào)度DAG-A和DAG-B的Gannt圖

表4 5種算法公平調(diào)度DAG結(jié)果比較

4.4 優(yōu)先級調(diào)度算法

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

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

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

算法2 MDOPTS算法

for(DAG個數(shù)) do

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

end for

對所有DAG按給定的關鍵優(yōu)先級降序放入關鍵級DAG隊列

while 有DAG可以調(diào)度 do

從關鍵級DAG隊列中取出未調(diào)度完成且具有最大優(yōu)先級的DAG

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

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

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

end while

標記當前DAG已調(diào)度

end while

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

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

4.5 自適應調(diào)度算法

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

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

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

算法3 MDOATS調(diào)度算法for(DAG個數(shù)) do

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

end for

對所有DAG按關鍵優(yōu)先級降序并放入DAG隊列while 有DAG可以調(diào)度 do

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

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

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

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

end while

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

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

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

表5 3種算法調(diào)度DAG結(jié)果比較(deadlineb=40)

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

5 實驗

5.1 評價指標

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

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

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

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

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

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

5.2 實驗結(jié)果及分析

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

圖4 平均加速比隨任務數(shù)變化

圖5 平均加速比隨DAG數(shù)變化

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

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

圖7 平均通信開銷率比隨DAG數(shù)變化

實驗3 分析不公平性隨任務數(shù)和DAG數(shù)變化的情況，實驗結(jié)果如圖8和圖9所示?？梢钥闯鲈谌蝿諗?shù)或DAG數(shù)目較小時，MDOFTS和MDOATS算法優(yōu)勢并不明顯；但隨著DAG數(shù)目的增多，相比其他算法的優(yōu)勢分別達到20%以上，說明隨著系統(tǒng)規(guī)模和復雜性增大，各DAG包含的任務數(shù)和屬性不盡相同，使有些公平調(diào)度算法對長DAG或短DAG等造成一定的不公平性，而MDOATS的輪轉(zhuǎn)調(diào)度策略不僅滿足實時性，還具有較好的公平性。

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

圖8 平均不公平性比隨任務數(shù)變化

圖9 平均不公平性比隨DAG數(shù)變化

圖10 WCRT隨消息數(shù)變化

圖11 平均通信開銷率隨消息數(shù)變化

圖12 平均不公平性隨消息數(shù)變化

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

[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] 謝勇, 李仁發(fā), 阮華斌等. 最優(yōu)的 FlexRay 靜態(tài)段配置算法[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國.忠, 肖創(chuàng)柏, 徐竹勝等. 異構(gòu)分布式環(huán)境下多 DAG 工作流的

6 結(jié)束語

本文面向異構(gòu)網(wǎng)絡化汽車電子系統(tǒng)領域進行調(diào)度問題研究，以多DAG離線任務模型為基礎，分析了現(xiàn)有多DAG任務調(diào)度算法；然后提出基于通信開銷權(quán)值的輪轉(zhuǎn)調(diào)度公平任務排序標準和在考慮插入法的基礎上將任務分配到具有最小選擇值的處理器上作為處理器選擇標準。綜合這2個標準提出了面向異構(gòu)網(wǎng)絡化汽車電子系統(tǒng)中的多DAG離線公平任務調(diào)度MDOFTS算法；接著提出混合調(diào)度策略[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.