硬件成本縮減的異構(gòu)分布式嵌入式系統(tǒng)調(diào)度算法*

邢紅星,魏葉華,樂 懿

(湖南師范大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410081)

1 引言

異構(gòu)嵌入式體系結(jié)構(gòu)被廣泛應(yīng)用于汽車、航空航天、工業(yè)自動化和健康醫(yī)療設(shè)備等高端工業(yè)，其已具備成熟的異構(gòu)分布嵌入式計算系統(tǒng)的特征[1]。在異構(gòu)分布式系統(tǒng)中，功能并行程度得到了提升，并且功能中的任務(wù)表現(xiàn)出明顯的數(shù)據(jù)依賴性和優(yōu)先級約束。系統(tǒng)通過集成于其上的功能實現(xiàn)控制，功能安全已成為工業(yè)嵌入式系統(tǒng)發(fā)展的優(yōu)先方向，其指不存在由于系統(tǒng)故障和隨機(jī)硬件故障而引起的不合理風(fēng)險[2]。安全關(guān)鍵嵌入式功能必須符合相關(guān)的功能安全標(biāo)準(zhǔn)[3]，例如汽車系統(tǒng)的ISO 26262[4]、航空電子系統(tǒng)的DO-178B和各種工業(yè)嵌入式系統(tǒng)的IEC 61508[5]。執(zhí)行異常和錯過最后期限被認(rèn)為是典型的隨機(jī)硬件和系統(tǒng)故障。

汽車電子系統(tǒng)中任務(wù)調(diào)度更強調(diào)智能性和整體性。智能化發(fā)展過程中，系統(tǒng)主要通過智能傳感器感知物理環(huán)境，其信號一般是周期性的，這使得在有傳感器參與的功能中，某些任務(wù)也是周期性觸發(fā)，即任務(wù)的不同實例的開始時間呈現(xiàn)嚴(yán)格周期性，而其他任務(wù)則只需要滿足功能內(nèi)部的時序約束。同時，由于傳感器工作頻率不盡相同，功能執(zhí)行的周期也不同，使得功能的實時性要求也不同，導(dǎo)致功能集合呈現(xiàn)混合周期性[6]。盡管多核處理器架構(gòu)在硬件層次上大幅地提升了處理器的性能和對復(fù)雜功能的承載力，但功能由不同的團(tuán)隊開發(fā)和測試，并在后期被整合[7]，因此需基于混合周期性考慮對功能集合的整體調(diào)度[6,8]，找到所有任務(wù)和消息的觸發(fā)時間。

工業(yè)嵌入式系統(tǒng)的開發(fā)通常是成本敏感的，因為它們是批量生產(chǎn)的工業(yè)產(chǎn)品。降低硬件成本可以大大節(jié)省工業(yè)生產(chǎn)成本，從而獲得高利潤。據(jù)統(tǒng)計，車載嵌入式異構(gòu)系統(tǒng)的相關(guān)成本已經(jīng)占到產(chǎn)品總成本的30%～40%[9,10]。隨著功能規(guī)模的不斷擴(kuò)大，所需的處理器硬件成本也相應(yīng)增加。當(dāng)前，用于標(biāo)準(zhǔn)控制器局域網(wǎng)CAN(Controller Area Networks)接口的處理器的單價從25美元上漲到110美元[1]，大幅增加了系統(tǒng)硬件成本，因此對車載嵌入式系統(tǒng)做硬件成本縮減分析，通過調(diào)度算法減少處理器數(shù)量，具有重大工業(yè)意義。

2 相關(guān)工作

工業(yè)嵌入式系統(tǒng)成本敏感，可以通過減少處理器數(shù)量來縮減硬件成本，前提是不影響功能的正確執(zhí)行和實時約束。文獻(xiàn)[1]從功能安全角度出發(fā)，針對功能安全至關(guān)重要的并行功能集合，提出了探索性硬件成本優(yōu)化EHCO(Explorative Hardware Cost Optimization)算法，通過迭代地移除處理器來實現(xiàn)，在滿足功能安全性要求的前提下，可以產(chǎn)生較低的硬件成本。文獻(xiàn)[11]為增強信息安全，采用FPGA或ASIC形式的硬件協(xié)處理器從電子控制單元ECU(Electronic Control Unit)卸載計算密集型加密算法，提出了一系列混合整數(shù)線性規(guī)劃MILP(Mixed-Integer Linear Programming)公式，以滿足安全性和期限要求，同時最大程度地減少了系統(tǒng)中所需的硬件協(xié)處理器的數(shù)量；文獻(xiàn)[12]提出了一種基于遺傳算法的方法來解決在設(shè)計階段車載系統(tǒng)性能、能量和可靠性之間的平衡問題，保證了實時功能的可調(diào)度性，將整體開發(fā)和產(chǎn)品單位成本降至最低；文獻(xiàn)[13]以節(jié)能效果和保持服務(wù)質(zhì)量為目標(biāo)，提出了一種支持動態(tài)電壓頻率調(diào)整DVFS(Dynamic Voltage and Frequency Scaling)的節(jié)能工作流任務(wù)調(diào)度DEWTS(DVFS-enabled Efficient energy Workflow Task Scheduling)算法，通過回收閑置時間來合并效率相對較低的處理器，實現(xiàn)系統(tǒng)能量降低和硬件成本縮減；文獻(xiàn)[14]從完全異構(gòu)的模型角度出發(fā)，提出一種基于拉格朗日理論的功率分配和負(fù)載均衡策略，使用任務(wù)到達(dá)率和核心速度之間的擬合數(shù)據(jù)方法來確定每個核心的合適速度，有效地解決了負(fù)載均衡和功率分配的聯(lián)合優(yōu)化問題；文獻(xiàn)[15]以能耗為出發(fā)點，提出了一種通過在不等分配中選擇一個相對中間的值來為每個任務(wù)分配相同的能耗算法，在能耗限制下實現(xiàn)了并行功能調(diào)度長度的最小化。

3 模型

3.1 系統(tǒng)架構(gòu)

在汽車電子系統(tǒng)中，一個中央網(wǎng)關(guān)[16]連接多條異構(gòu)總線，每條總線直接連接多個異構(gòu)電子控制單元ECU。每個ECU可以同時連接多個傳感器和執(zhí)行器或者不連接。當(dāng)滿足任務(wù)預(yù)定觸發(fā)時間，即可觸發(fā)任務(wù)在ECU上的執(zhí)行、執(zhí)行器執(zhí)行動作等。車內(nèi)網(wǎng)絡(luò)支持時間觸發(fā)方式的FlexRay協(xié)議、TT-CAN(Time Triggered-CAN)協(xié)議等，因具備傳輸速率高、實時性高、可靠性強、可預(yù)測性強、靈活性大的特點，得到了廣泛的研究和應(yīng)用，因此本文基于系統(tǒng)時間觸發(fā)方式展開研究。

調(diào)度過程中，任務(wù)或消息會占據(jù)ECU和總線BUS的時間槽(即ECU或BUS可被占用的最小單位)。令E={ECU1,ECU2,…,ECUe,…,ECUNOE}表示異構(gòu)ECU集合，NOE(Number Of ECU)表示集合E的大??；ECUe={slot1,slot2,…,slott,…,slotNOS}、B={slot1,slot2,…,slott,…,slotNOS}分別表示單個ECUe和BUS的時間槽，slott表示固定大小的時間槽，NOS(Number Of Slot)表示集合ECUe和B的大小。

ECU包括工作和睡眠2種狀態(tài)屬性[1]。當(dāng)ECU處于工作狀態(tài)時，參與任務(wù)的正常執(zhí)行與消息傳遞；但當(dāng)ECU處于睡眠狀態(tài)時，其不接受任何任務(wù)的登記。假如一個ECU在調(diào)度過程中處于睡眠狀態(tài)，即認(rèn)為該ECU是可以被取消的。

3.2 功能模型

Figure 1 Function examples

Figure 2 Scheduling based on the task attributes

3.3 簡單案例

以圖1所示的2個功能為例進(jìn)行調(diào)度，其中pg1=10 ms，dg1=9 ms，pg2=20 ms，dg2=16 ms?？紤]在超周期內(nèi)完成功能集合的調(diào)度，超周期為所有功能周期的最小公倍數(shù)。任務(wù)屬性如表1所示，其中，n1、n3和n5是周期性任務(wù)，任務(wù)的映射信息表示功能在開發(fā)階段的最佳映射信息。

Table 1 Task attributes

在功能集成階段，由于系統(tǒng)中集成了大量ECU，功能g1與g2的任務(wù)可以分配到某些ECU上，其執(zhí)行開銷情況如表2所示。

Table 2 Task execution cost

表2中，數(shù)值表示任務(wù)ni在處理器上的執(zhí)行開銷，因ECU的類型不同，其執(zhí)行時間也不同，表格中的“×”表示禁止任務(wù)到該ECU的映射。通過對表2進(jìn)行簡單的分析可以知道：(1)任務(wù)n1與n6分別只能在ECU1和ECU2上運行，因此在調(diào)度過程中ECU1和ECU2不能被設(shè)置為睡眠狀態(tài)；(2)針對g1與g2的整體調(diào)度的硬件成本縮減問題，其最優(yōu)解是同時取消ECU3和ECU4；(3)各個任務(wù)對ECU4的“需要程度”最低，這里可以理解為，ECU4最有可能被設(shè)置為睡眠狀態(tài)以探索成本縮減方案的可行性。因此，通過調(diào)度將ECU4設(shè)置為睡眠狀態(tài)的調(diào)度過程，如圖3所示，其保證了在超周期中任務(wù)n1和n32個任務(wù)實例觸發(fā)時間的嚴(yán)格周期性。與圖2相比，將任務(wù)n4的2個任務(wù)實例分別轉(zhuǎn)移至ECU3和ECU2,任務(wù)n7轉(zhuǎn)移至ECU2，使各個功能實例都能在截止期前執(zhí)行完畢，保證了功能的運行完整性。

Figure 3 設(shè)置ECU4為睡眠狀態(tài)

4 基于整數(shù)線性規(guī)劃的硬件成本縮減算法

4.1 算法描述

基于系統(tǒng)中功能任務(wù)與處理器的映射關(guān)系和執(zhí)行開銷的復(fù)雜情況，為了找到包含所有任務(wù)和消息實例觸發(fā)時間的功能集合調(diào)度表，本文提出了基于整數(shù)線性規(guī)劃的硬件成本縮減IHCR(ILP based Hardware Cost Reduction)算法，算法流程如圖4所示。功能集合G、處理器集合E和總線資源B作為算法輸入，輸出為包含所有任務(wù)和消息實例的觸發(fā)時間和調(diào)度表。

Figure 4 Flowchart of IHCR algorithm

4.2 功能整合

Figure 5 Functions integration

4.3 成本縮減方案

成本縮減方案分為2種情況：

(1)初始成本縮減方案集。

為設(shè)計初始方案，本文采用2個指標(biāo)對所有ECU進(jìn)行評價：ECU可映射任務(wù)數(shù)NECUe和可映射任務(wù)的總執(zhí)行開銷ωECUe。為提升方案搜索效率，在設(shè)計成本縮減方案時會優(yōu)先考慮可映射任務(wù)數(shù)較小的ECU，若映射任務(wù)數(shù)量相同，則優(yōu)先考慮可映射任務(wù)的總執(zhí)行開銷較小的ECU。

(2)根據(jù)成功方案執(zhí)行結(jié)果產(chǎn)生新的成本縮減方案集。

當(dāng)方案集搜索完畢，根據(jù)搜索結(jié)果生產(chǎn)ECU睡眠數(shù)量加1的方案集。當(dāng)成功方案數(shù)量大于1時，以成功的方案為基礎(chǔ)，添加在其他成功方案中其不包含的ECU；當(dāng)成功方案數(shù)量等于1時，以該方案為基礎(chǔ)，逐個添加該方案中未有的ECU；否則，結(jié)束新方案的建立。

基于圖3所示成功方案，考慮將ECU3和ECU4同時設(shè)置為睡眠模式，通過整數(shù)線性規(guī)劃模型可以搜索到完整的調(diào)度表。完整調(diào)度過程如圖6所示，該方案已是最佳解。

Figure 6 Setting ECU3 and ECU4 to sleep state

4.4 優(yōu)化目標(biāo)

由于研究目標(biāo)是實現(xiàn)基于時間觸發(fā)的系統(tǒng)上的整體調(diào)度，并實現(xiàn)ECU數(shù)量最小化和ECU負(fù)載均衡，通過對成本縮減方案進(jìn)行整數(shù)線性規(guī)劃模型求解，對解空間進(jìn)行篩選時，以負(fù)載均衡為整數(shù)線性規(guī)劃模型的優(yōu)化目標(biāo)函數(shù)。由于該模型的約束條件中不能出現(xiàn)變量的乘積，本文采用所有ECU時間槽占用率的平均絕對誤差作為目標(biāo)函數(shù)：

其中，uECUe表示在通過整數(shù)線性模型求得的解中，ECUe的使用率；ε表示ECU的數(shù)量；Average.uE表示該解中除去設(shè)置為睡眠狀態(tài)的所有ECU的使用率的平均值；求和部分表示所有ECU的絕對誤差和。

4.5 約束表達(dá)

(1)

(2)

(3)

(4)

針對任務(wù)的不同實例的觸發(fā)時間呈現(xiàn)嚴(yán)格周期性的特點，需對所有周期性任務(wù)添加約束：

(8)

(9)

對功能gm的初始偏移值的約束，需添加對應(yīng)約束：

(10)

5 仿真和評估

5.1 仿真設(shè)置

為評估所提出IHCR算法的有效性，本節(jié)將功能集成階段與設(shè)計階段的調(diào)度表進(jìn)行對比。采用隨機(jī)任務(wù)生成器生成隨機(jī)功能集合，功能的周期從[5,10,20,40]中隨機(jī)選擇。在每組實驗中，功能的數(shù)量分別為[4,6,8]，每個功能的平均任務(wù)數(shù)為15個，任務(wù)平均執(zhí)行成本為0.5。采用CPLEX軟件構(gòu)建整數(shù)線性規(guī)劃模型，為滿足模型的運行要求，以數(shù)值屬性的10倍進(jìn)行計算，但實驗指標(biāo)以原數(shù)值計算。為研究硬件成本縮減與功能周期率的關(guān)系，周期率分別設(shè)置為[0.2,0.5,0.8]。任務(wù)的執(zhí)行成本以RTGG模型為基礎(chǔ)，隨機(jī)產(chǎn)生初始映射關(guān)系，并將執(zhí)行成本低于初始映射關(guān)系的ECU設(shè)置為禁止映射。功能情況如表3所示，表中給出了功能實例數(shù)與所合成BigDAG的任務(wù)實例數(shù)與消息實例數(shù)，其值為每組實驗中數(shù)據(jù)的平均值。

Table 3 Function and task instances date

5.2 性能驗證

實驗以每組參數(shù)組合的5次執(zhí)行為基礎(chǔ)，性能指標(biāo)有2個：平均ECU縮減數(shù)量和ECU使用率提升百分比，分別表示IHCR算法執(zhí)行結(jié)果的平均值。

在功能開發(fā)階段，所有任務(wù)只能映射到一個ECU上，且將ECU的數(shù)量設(shè)置為功能數(shù)量的2倍[6,7]。圖7展示了IHCR算法對ECU的縮減數(shù)量。其中，每一組柱狀圖分別代表功能周期率為0.2,0.5,0.8時縮減數(shù)量的變化趨勢。當(dāng)功能周期率較低時，算法表現(xiàn)出最優(yōu)性能，當(dāng)其值從0.2開始逐漸增加時，縮減數(shù)量下降。原因是隨著功能周期率的增加，周期性任務(wù)的數(shù)量增加，使得對任務(wù)各個實例的觸發(fā)時間的要求更加嚴(yán)格，將ECU資源劃分為情況復(fù)雜的間隙，降低了ECU對任務(wù)的承載能力，導(dǎo)致違背整數(shù)線性規(guī)劃的公式，使得該方案失?。划?dāng)周期率固定而功能數(shù)量逐漸增加時，ECU縮減數(shù)量增幅下降。當(dāng)功能數(shù)量分別為4,6,8時，原始模型中的ECU數(shù)量分別為8,12,16，在實際ECU縮減方案中，所有實驗中平均縮減數(shù)量為2.9,3.4,3.7，說明隨著功能數(shù)量增加，ECU縮減變得困難，一方面是因為任務(wù)的數(shù)量增多，使得任務(wù)觸發(fā)時間的約束公式數(shù)量大幅增加，增加了整體調(diào)度的難度；另一方面是因為該系統(tǒng)架構(gòu)是基于單總線的，盡管IPL模型會最大程度地尋找最優(yōu)解，但消息實例的數(shù)量會逐漸接近總線對消息的承載極限，最終導(dǎo)致總線資源成為限制ECU數(shù)量縮減的最大約束。

Figure 7 Reduced number of ECU

圖8是IHCR算法在縮減ECU數(shù)量的同時，對ECU使用率提升情況的三維數(shù)據(jù)圖。圖8中不同周期率時最左一列表示功能模型在開發(fā)階段的ECU使用率，雖然隨著功能數(shù)量的增加，系統(tǒng)中ECU的數(shù)量也會增加，但使用率隨之提升表示功能集合的增長更加劇烈。在IHCR模擬實驗中，隨著周期率的增加，ECU使用率會下降5%以內(nèi)，而相對初始調(diào)度方案，使用率的提升最小值是7.1%(功能數(shù)量為8，周期率為0.8)，最大值是15.9%(功能數(shù)量為4，周期率為0.2)，與圖7的變化趨勢相似，這是由于功能集合的集成難度與功能數(shù)量、功能周期率成正比，當(dāng)減少ECU數(shù)量時體現(xiàn)相同的趨勢。當(dāng)功能數(shù)量一定，ECU使用率提升隨著周期率的增加而下降，這是因為周期率越高，周期性任務(wù)的時間約束越強，各個任務(wù)實例雖然可能會映射到不同的ECU上，但其仍會對ECU資源產(chǎn)生不規(guī)則的分配，導(dǎo)致對調(diào)度的承載力的下降。IHCR算法可使ECU使用率提升到[35.6,40.2]，且功能數(shù)量增多，使用率增加的幅度有所下降，原因是ECU使用率的提升存在上限，特別是功能實例逐漸增加，盡管任務(wù)映射關(guān)系的變化有可能會減少消息實例的數(shù)量，但相比于任務(wù)實例數(shù)量，消息實例的增加更劇烈，越來越接近系統(tǒng)總線的承載力。

Figure 8 Simulation of ECU usage improvement

6 結(jié)束語

針對異構(gòu)嵌入式系統(tǒng)的硬件成本縮減問題，本文基于所有任務(wù)與ECU的映射關(guān)系與執(zhí)行開銷，在保證功能的安全性和完整性的前提下，提出了基于整數(shù)線性規(guī)劃的硬件成本縮減算法IHCR，通過約束公式構(gòu)建約束模型，為通過減少ECU數(shù)量降低成本提供了新思路。通過與開發(fā)階段單一映射關(guān)系的調(diào)度表進(jìn)行對比，該算法可以有效地減少ECU數(shù)量，提高ECU的使用率。