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

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

(湖南大學(xué) 嵌入式與網(wǎng)絡(luò)計(jì)算湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410082)

1 引言

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

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

2 調(diào)度模型

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

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

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

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

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

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

圖1 2個(gè)DAG任務(wù)模型實(shí)例

3 相關(guān)研究與理論知識(shí)

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

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

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

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

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

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

其中，ftown(ni)表示 ni單獨(dú)調(diào)度的完成時(shí)間，ftmulti(ni)表示ni在多DAG中調(diào)度的完成時(shí)間。如此重復(fù)，直到列表中沒(méi)有未調(diào)度完成的DAG為止。同時(shí)文獻(xiàn)[10]也提出了評(píng)價(jià)DAG不公平性的具體方法，首先計(jì)算某個(gè)DAG的slowdown值，其計(jì)算公式為

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

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

表1 DAG-A和DAG-B中各任務(wù)在處理器上的計(jì)算開(kāi)銷(xiāo)

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

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

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

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

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

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

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

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

4 調(diào)度算法

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

4.1 任務(wù)優(yōu)先級(jí)排序

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

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

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

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

2) 多DAG任務(wù)公平性?xún)?yōu)先級(jí)排序

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

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

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

(a) 計(jì)算每個(gè) DAG中每個(gè)任務(wù)的向上排序值rankupd(ni)；

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

(c) 基于通信開(kāi)銷(xiāo)權(quán)值，對(duì)REDAY_QUEUE升序排序；

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

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

4.2 處理器選擇

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

1) 處理器選擇值

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

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

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

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

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

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

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

2) 插入分配法

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

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

(b) 在對(duì)任務(wù) ni進(jìn)行處理器分配時(shí)，遍歷所有處理器，搜尋滿(mǎn)足[est(ni，pk)， eft(ni，pk) ] 屬于SLOT_SET (pk)的處理器空閑段；

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

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

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

定義 5 DAG 通信開(kāi)銷(xiāo) (DOC, DAG communication overhead)。Gm中具有直接優(yōu)先級(jí)約束的所有任務(wù)因沒(méi)有分配在同一個(gè)處理器而消耗的通信開(kāi)銷(xiāo)之和，即

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

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

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

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

計(jì)算每個(gè)DAG中任務(wù)的向上排序值rankupd(ni，pk)，rankupd(ni) 與通信開(kāi)銷(xiāo)權(quán)值 cow(ni)；

end for

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

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

分別從各DAG中取出一個(gè)向上排序值最大的就緒任務(wù)，放入到任務(wù)的就緒隊(duì)列 REDAY_QUEUE

end for

for(DAG個(gè)數(shù))基于公平輪轉(zhuǎn)調(diào)度，從REDAY_QUEUE中選擇具有最小通信開(kāi)銷(xiāo)權(quán)值cow(ni)的任務(wù)ni

獲取任務(wù)ni所在DAG為Gm

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

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

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

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

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

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

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

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

1) 對(duì)于優(yōu)先級(jí)高的DAG中的所有任務(wù)都要優(yōu)先于優(yōu)先級(jí)低的DAG中的所有任務(wù)。只有當(dāng)優(yōu)先級(jí)高的DAG中的所有任務(wù)分配處理器后，優(yōu)先級(jí)低的DAG中的任務(wù)才能分配處理器。

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

算法2 MDOPTS算法

for(DAG個(gè)數(shù)) do

計(jì)算每個(gè) DAG中任務(wù)的向上排序值rankupd(ni,pk), rankupd(ni)與通信開(kāi)銷(xiāo)權(quán)值 cow(ni)及任務(wù)個(gè)數(shù)，并將任務(wù)放入各DAG的任務(wù)隊(duì)列

end for

對(duì)所有DAG按給定的關(guān)鍵優(yōu)先級(jí)降序放入關(guān)鍵級(jí)DAG隊(duì)列

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

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

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

更新Gm的通信開(kāi)銷(xiāo)dco(Gm)

更新GS通信開(kāi)銷(xiāo)率mdcor(GS)標(biāo)記ni為已調(diào)度任務(wù)

end while

標(biāo)記當(dāng)前DAG已調(diào)度

end while

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

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

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

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

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

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

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

計(jì)算每個(gè)DAG中任務(wù)的向上排序值rankupd(ni, pk)，rankupd(ni)與通信開(kāi)銷(xiāo)權(quán)值cow(ni),，并放入各DAG的任務(wù)隊(duì)列

end for

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

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

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

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

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

end while

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

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

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

5.1 評(píng)價(jià)指標(biāo)

本文采用加速比(speedup)[7,11]、通信開(kāi)銷(xiāo)率(MDCOR)、不公平性(unfairness)以及端到端最差響應(yīng)時(shí)間(WCRT, worst-case response time)[19]作為評(píng)價(jià)指標(biāo)。

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

多DAG的通信開(kāi)銷(xiāo)率采用式(14)計(jì)算，通信開(kāi)銷(xiāo)率越低，說(shuō)明算法越高效。不公平性采用式(4)計(jì)算，不公平性越低，算法越高效。

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

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

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

5.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

圖6 平均通信開(kāi)銷(xiāo)率比隨任務(wù)數(shù)變化

圖7 平均通信開(kāi)銷(xiāo)率比隨DAG數(shù)變化

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

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

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

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

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

圖11 平均通信開(kāi)銷(xiāo)率隨消息數(shù)變化

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

以上4次實(shí)驗(yàn)的結(jié)果表明，本文所提出的相關(guān)多DAG離線(xiàn)任務(wù)調(diào)度算法在調(diào)度長(zhǎng)度、通信開(kāi)銷(xiāo)和不公平性相比E-Fairness(off-line)、OWN(off-line)和 FDWS(off-line)等算法都要優(yōu)；在真實(shí)消息集環(huán)境下，具有更好的結(jié)果，因而能夠很好地適應(yīng)于異構(gòu)網(wǎng)絡(luò)化汽車(chē)電子系統(tǒng)的多DAG離線(xiàn)任務(wù)調(diào)度。了以滿(mǎn)足安全關(guān)鍵DAG的多DAG離線(xiàn)優(yōu)先級(jí)任務(wù)調(diào)度算法MDOPTS，并綜合MDOFTS和MDOPTS，提出多DAG離線(xiàn)自適應(yīng)任務(wù)調(diào)度算法MDOATS，在滿(mǎn)足實(shí)時(shí)性的基礎(chǔ)上提高調(diào)度性能。最后利用仿真實(shí)驗(yàn)將本文提出的算法與相關(guān)算法進(jìn)行比較，得到本文所提出的算法在保證公平性的條件下，能夠有效降低調(diào)度長(zhǎng)度，極大地減少通信開(kāi)銷(xiāo)，產(chǎn)生更低的最差響應(yīng)時(shí)間，具有更好的調(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]. 通信學(xué)報(bào), 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國(guó).忠, 肖創(chuàng)柏, 徐竹勝等. 異構(gòu)分布式環(huán)境下多 DAG 工作流的

6 結(jié)束語(yǔ)

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