硬件成本縮減的異構分布式嵌入式系統調度算法*

邢紅星,魏葉華,樂 懿

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

1 引言

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

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

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

2 相關工作

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

3 模型

3.1 系統架構

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

調度過程中，任務或消息會占據ECU和總線BUS的時間槽(即ECU或BUS可被占用的最小單位)。令E={ECU1,ECU2,…,ECUe,…,ECUNOE}表示異構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種狀態屬性[1]。當ECU處于工作狀態時，參與任務的正常執行與消息傳遞；但當ECU處于睡眠狀態時，其不接受任何任務的登記。假如一個ECU在調度過程中處于睡眠狀態，即認為該ECU是可以被取消的。

3.2 功能模型

Figure 1 Function examples

Figure 2 Scheduling based on the task attributes

3.3 簡單案例

以圖1所示的2個功能為例進行調度，其中pg1=10 ms，dg1=9 ms，pg2=20 ms，dg2=16 ms。考慮在超周期內完成功能集合的調度，超周期為所有功能周期的最小公倍數。任務屬性如表1所示，其中，n1、n3和n5是周期性任務，任務的映射信息表示功能在開發階段的最佳映射信息。

Table 1 Task attributes

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

Table 2 Task execution cost

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

Figure 3 設置ECU4為睡眠狀態

4 基于整數線性規劃的硬件成本縮減算法

4.1 算法描述

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

Figure 4 Flowchart of IHCR algorithm

4.2 功能整合

Figure 5 Functions integration

4.3 成本縮減方案

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

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

為設計初始方案，本文采用2個指標對所有ECU進行評價：ECU可映射任務數NECUe和可映射任務的總執行開銷ωECUe。為提升方案搜索效率，在設計成本縮減方案時會優先考慮可映射任務數較小的ECU，若映射任務數量相同，則優先考慮可映射任務的總執行開銷較小的ECU。

(2)根據成功方案執行結果產生新的成本縮減方案集。

當方案集搜索完畢，根據搜索結果生產ECU睡眠數量加1的方案集。當成功方案數量大于1時，以成功的方案為基礎，添加在其他成功方案中其不包含的ECU；當成功方案數量等于1時，以該方案為基礎，逐個添加該方案中未有的ECU；否則，結束新方案的建立。

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

Figure 6 Setting ECU3 and ECU4 to sleep state

4.4 優化目標

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

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

4.5 約束表達

(1)

(2)

(3)

(4)

針對任務的不同實例的觸發時間呈現嚴格周期性的特點，需對所有周期性任務添加約束：

(8)

(9)

對功能gm的初始偏移值的約束，需添加對應約束：

(10)

5 仿真和評估

5.1 仿真設置

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

Table 3 Function and task instances date

5.2 性能驗證

實驗以每組參數組合的5次執行為基礎，性能指標有2個：平均ECU縮減數量和ECU使用率提升百分比，分別表示IHCR算法執行結果的平均值。

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

Figure 7 Reduced number of ECU

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

Figure 8 Simulation of ECU usage improvement

6 結束語

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