多核汽車電子系統(tǒng)中關鍵級感知的任務分配算法

劉樑驕，李仁發(fā)，謝 勇，楊 柳，謝國琪

(1．湖南大學 a．信息科學與工程學院;b．嵌入式與網(wǎng)絡計算湖南省重點實驗室，長沙410082;2．廈門理工學院 a．計算機與信息工程學院;b．福建省高校物聯(lián)網(wǎng)應用技術重點實驗室，福建廈門361024;3．湖南省發(fā)展和改革委員會，長沙410004)

1 概述

近年來，人們在安全、智能、節(jié)能和環(huán)保等方面對汽車提出越來越高的要求，使得汽車電子系統(tǒng)的復雜性驟增。如奔馳S級等豪華轎車車內(nèi)包含的電子功能達800多個、ECU達100多個，車內(nèi)的代碼量達上千萬行［1］。系統(tǒng)復雜性給汽車電子系統(tǒng)設計在滿足尺寸、重量和功率(Size，Weight and Power，SWaP)屬性方面提出嚴格要求，成本節(jié)約等方面面臨嚴峻挑戰(zhàn)。為應對上述挑戰(zhàn)，集成化正成為汽車電子系統(tǒng)發(fā)展的重要趨勢［2］，汽車電子系統(tǒng)正逐漸演變?yōu)榛旌详P鍵級系統(tǒng)［3］。

混合關鍵級系統(tǒng)的同一硬件平臺上同時集成了多個關鍵級功能，如安全關鍵性功能、任務關鍵性功能和非關鍵性功能等。面向汽車工業(yè)的功能安全標準ISO 26262［4］將車內(nèi)電子功能劃分為4個安全完整性等級(Safety Integrity Level，SIL)，并定義不同關鍵級功能在可靠性方面具有不同的要求，如最高關鍵級(SIL=4)功能對應的可靠性要求為每小時失效率小于10－8，最低關鍵級(SIL=1)功能對應的可靠性要求為每小時失效率小于10－6。部分工作關注關鍵級與任務執(zhí)行時間之間的對應關系，但是本文主要關注關鍵級與可靠性之間的對應關系，文獻［5］對關鍵級的不同定義和模型等進行綜述。為了保障功能滿足可靠性方面的特定要求，關鍵級越高的功能在開發(fā)和認證方面需要付出更高的成本。但是高關鍵級功能可通過SIL分解來降低其開發(fā)和認證成本［6-7］，ISO 26262規(guī)范對高關鍵級功能的分解方案進行了詳細闡述。可是SIL分解在實現(xiàn)系統(tǒng)成本縮減的同時將帶來額外的資源開銷(包括CPU利用率和通信時延的增長等)，因此混合關鍵級系統(tǒng)的實現(xiàn)需在成本和資源開銷之間取得平衡。

本文主要研究混合關鍵級汽車電子系統(tǒng)的功能實現(xiàn)中任務到多核處理器的分配問題，即當給定多核的系統(tǒng)結構和汽車電子功能(包括功能的拓撲結構，功能包含任務、消息的屬性)的前提下，研究如何實現(xiàn)任務到節(jié)點的優(yōu)化分配，使得實現(xiàn)后的系統(tǒng)可調(diào)度、系統(tǒng)成本得到優(yōu)化，以及系統(tǒng)資源得到高效使用。多核處理器調(diào)度中的任務分配問題是典型的強NP難問題［8］，本文在保證滿足系統(tǒng)可調(diào)度的前提下，以成本和資源開銷的聯(lián)合優(yōu)化為目標，提出一個基于模擬退伙算法的啟發(fā)式分配算法關鍵級感知的任務分配(Criticality-aware Task Allocation，CTA)算法。

2 相關工作

任務分配問題是多核處理器調(diào)度研究中的關鍵問題，它是一個典型的NP難問題，現(xiàn)有的研究成果從不同角度提出了多種解決方案，包括基于binpacking 的啟發(fā)式算法(如 first-fit，best-fit，next-fit等)、基于整數(shù)線性規(guī)劃的最優(yōu)化算法、基于線性規(guī)劃、動態(tài)編程的算法等［8-9］。但是上述研究均未考慮汽車電子系統(tǒng)的混合關鍵級特性，并且在多核共享資源開銷方面的考慮較少，多核混合關鍵級系統(tǒng)中的任務分配問題具有更高的復雜性。

在多核混合關鍵級系統(tǒng)的調(diào)度研究方面，文獻［10］提出多處理器混合關鍵級系統(tǒng)中基于正方向時間分割和關鍵因子優(yōu)先的調(diào)度算法，以提高低關鍵級任務的可調(diào)度性。文獻［11］研究基于劃分的多核混合關鍵級系統(tǒng)調(diào)度問題，允許任務在不同模式下分配到不同的處理節(jié)點之中進行處理，以提高系統(tǒng)資源的利用率。但是本文未考慮核間通信，僅實現(xiàn)了系統(tǒng)資源的優(yōu)化。文獻［12］對基于劃分的多核混合關鍵級系統(tǒng)中的任務分配問題進行了研究，考慮了關鍵級與任務執(zhí)行時間、內(nèi)存開銷之間的關系建模，提出基于模擬退火的啟發(fā)式算法以實現(xiàn)任務反應時間的優(yōu)化和內(nèi)存資源的高效使用。文獻［13］對多核混合關鍵級系統(tǒng)中容錯感知的任務分配問題進行了研究，考慮了關鍵級與可靠性和任務執(zhí)行時間之間的關系建模，提出的基于遺傳算法的啟發(fā)式算法在滿足可靠性要求的前提下可實現(xiàn)任務反應時間的優(yōu)化。上述研究未考慮關鍵級與成本之間的關系建模，在系統(tǒng)資源方面未考慮多核處理器中存在的多層通信時延模型。文獻［6，14］對分布式混合關鍵級系統(tǒng)中的任務分配問題和靜態(tài)劃分調(diào)度問題進行了研究，并就成本與關鍵級之間的關系進行了建模。但是上述研究主要面向基于單核的分布式系統(tǒng)，以成本和系統(tǒng)可調(diào)度性的聯(lián)合優(yōu)化為目標，而本文的研究面向多核處理器系統(tǒng)，在系統(tǒng)結構、資源模型和優(yōu)化目標方面不同。

3 系統(tǒng)模型和假設前提

3．1 系統(tǒng)結構

本文假設混合關鍵級汽車電子系統(tǒng)采用如圖1所示的雙核處理器架構。該多核處理器采用兩級通信模型，同一個核內(nèi)的任務之間通過Cache進行通信，不同核內(nèi)的任務之間通過共享內(nèi)存進行通信。該兩層通信模型可以容易地擴展到三級或者更復雜的通信模型。

圖1 多核混合關鍵級系統(tǒng)的系統(tǒng)結構

3．2 任務和消息模型

如圖2(a)所示，采用有向非循環(huán)圖(Directed Acyclic Graph，DAG)對汽車電子功能進行建模，每個節(jié)點表示一個任務，每條邊表示2個任務之間的通信消息。圖2(b)～圖2(d)分別給出了事例功能包含高關鍵級任務T2和T4的SIL分解方案。任務可通過如下五元組進行描述:

Ti= ＜ Ci，Pi，SILi，Di，Wi＞

分別表示任務的執(zhí)行時間、周期、SIL、最終期限和開發(fā)成本，i∈R+，且 i的值屬于［1，2，…，TN］。SILi的值越大，關鍵級越高。

圖2 汽車電子功能及其包含任務的SIL分解方案

消息可通過如下三元組進行描述:

mi= ＜ SOUi，DESi，DLYi(x)＞，x={cache，mem}

分別表示消息的源任務、目的任務和消息對應的通信時延，i∈R+，且 i的值屬于［1，2，…，MN］。當消息的源任務和目的任務分配到同一個核的時候，mi通過Cache進行實現(xiàn)(x=cache);當消息的源任務和目的任務分配到不同核的時候，mi通過共享內(nèi)存進行實現(xiàn)(x=mem)。根據(jù)多核通信的相關研究成果，后一種通信機制對應的通信時延與前一種通信機制對應的通信時延呈2個數(shù)量級的倍數(shù)關系［15］，本文假設已知 DLYi(cache)和DLYi(mem)的值。因此系統(tǒng)整體的通信時延可按照式(1)進行計算:

汽車電子功能的實現(xiàn)包括任務到核的分配和核內(nèi)任務調(diào)度2個方面。本文主要研究任務到核的分配問題，假設核內(nèi)的任務采取固定優(yōu)先級調(diào)度算法進行調(diào)度執(zhí)行，任務的優(yōu)先級采用Audsley算法進行分配［16］，任務的反應時間分析按照文獻［17］中給出的方法進行分析。

3．3 成本模型

本文主要從系統(tǒng)的安全性認證和功能開發(fā)2個方面對系統(tǒng)成本進行建模和分析，由于本文主要關注多核混合關鍵級系統(tǒng)中任務分配問題在資源開銷和成本之間的權衡問題，因此成本分析方面僅參照文獻［6］給出的成本模型，軟件成本的精確估計和分析可參照相關標準和研究成果［18-19］。

多核處理器每個核中包含的任務需進行同一認證，其認證成本依賴于所包含任務的最高關鍵級。核一級的認證成本COk可按照式(2)進行計算:

其中，SIL_COST()函數(shù)對應處理器核在不同關鍵級上的認證成本，本文假設該成本已知。

由于處理器核一級的認證成本依賴于所包含任務的最高關鍵級，因此系統(tǒng)的認證成本很高。為降低系統(tǒng)的認證成本，ISO 26262規(guī)范指出可對高關鍵級任務進行SIL分解來降低處理器核一級的認證成本。

根據(jù)ISO 26262規(guī)范，表1以圖2中的功能為例給出了高關鍵級任務的SIL分解方案庫。

表2給出了汽車電子功能實例包含任務的相關屬性。如功能2中的T4對應2種SIL分解方案:方案1將其分解為T11，T122個任務，并且它們通過I/O任務T10和T13與功能中的其他任務進行通信，該方案將T4的開發(fā)成本由28降至9。方案2將其分解為T16，T17和T193個任務，并且它們通過I/O任務T14，T15，T18和T20與功能中的其他任務進行通信，該方案將T4的開發(fā)成本由28降至12。圖3(a)給出了圖2(a)中汽車電子功能的分配方案，此時核1和核2的SIL分別為3和4，如果按照圖2(b)～圖2(d)給出的SIL分解方案對T2和T4進行分解，那么核1和核2的SIL都可將至2。另2種分配方案如圖3(b)、圖3(c)所示。汽車電子功能實例根據(jù)FSA和C-FSA分配方案得到的任務分配結果如圖4所示。

表2 汽車電子功能實例包含任務的相關屬性

圖3 汽車電子功能實例對應的3種任務分配方案

圖4 任務分配結果

根據(jù)上述分析，系統(tǒng)的成本包括處理器核一級的認證成本和任務的開發(fā)成本2個組成部分，系統(tǒng)成本可按照式(3)進行計算:

4 關鍵級感知的任務分配算法

模擬退火算法在任務分配問題的相關研究中展現(xiàn)了其有效性［8，12］，本文亦采用其來實現(xiàn)多核混合關鍵級系統(tǒng)中任務分配在成本和資源開銷之間的聯(lián)合優(yōu)化。提出的關鍵級感知的任務分配(Criticalityaware Task Allocation，CTA)算法具體描述如下:

算法 Criticality_aware_Task_Allocation()

輸入 多核處理器的系統(tǒng)架構，汽車電子功能集

輸出 任務到核的映射關系χ，系統(tǒng)的成本和資源開銷情況Opt_Obj

該啟發(fā)式算法的初始值為“以功能為單位進行任務分配后得到的系統(tǒng)實現(xiàn)方案”(第 1行)，圖3(a)給出了實例功能根據(jù)該初始化方案分配后得到的任務分配結果。該分配方案亦對應資源開銷最小化的分配方案(CPU利用率最低、通信時延最少)。第2行對初始化的任務分配方案對應的系統(tǒng)成本和資源開銷情況進行分析，以作為后續(xù)啟發(fā)式搜索步驟的起點。本文主要關注成本和系統(tǒng)資源開銷之間的聯(lián)合優(yōu)化問題，因此按照線性加權的方式設定CTA的目標函數(shù)。該目標函數(shù)的具體定義如式(4)所示。

其中，WHT1，WHT2和WHT3分別表示系統(tǒng)成本、CPU利用率和通信時延在該聯(lián)合優(yōu)化方案中的權重，該權重的設置可參照文獻［20］等相關研究。

CTA共包括4個啟發(fā)式搜索步驟:SIL分解(SIL Decomposition)，SIL 聚合(SIL Composition)，核間的任務交換(Task Exchange)，核間的任務遷移(Task Migration)(第4行～第11行)。其中，SIL聚合指與SIL分解相反的操作，即將原來通過SIL分解后得到的多個低關鍵級任務聚合為一個高關鍵級任務。對當前的任務分配方案進行啟發(fā)式調(diào)整后，首先對調(diào)整后的系統(tǒng)可調(diào)度性進行分析(第12行)。僅當任務分配調(diào)整后的系統(tǒng)可調(diào)度的前提下，再嘗試對新的分配方案對應的目標值進行分析(第13行)。當啟發(fā)式步驟獲得目標優(yōu)化時，接受該步驟對應的任務分配調(diào)整方案(第14行～第16行);當啟發(fā)式步驟未獲得目標優(yōu)化時，以概率P接受該步驟對應的任務分配調(diào)整方案(第17行～第20行)。當啟發(fā)式搜索次數(shù)達到設定的M1或者啟發(fā)式搜索對應的目標值連續(xù)M2次未獲得優(yōu)化時，終止該算法(第23行～第25行)。由于CTA的啟發(fā)式特性，不能對其時間復雜性進行準確估計，因此本文主要通過算法的運行時間來代表其復雜性。

5 實驗與結果分析

為了證明本文提出算法的有效性，以文獻［6］中給出的真實汽車電子功能到雙核處理器的分配為例展開實驗，該功能集的相關情況如圖5所示。該功能集共包括引擎控制、懸掛控制等6個功能，其中，2個SIL4功能;2個SIL3功能，1個SIL2功能和1個SIL1功能。上述功能的初始實現(xiàn)共包括31個任務、19個消息。SIL4的功能包含任務的周期等于25 ms，SIL3的功能包含任務的周期等于50 ms，SIL2的功能包含任務的周期等于100 ms，SIL1的功能包含任務的周期等于200 ms，任務的執(zhí)行時間在0．2 ms～4 ms之間，功能集對應的CPU利用率為1．37。為實現(xiàn)系統(tǒng)成本的縮減，該功能集中的高關鍵級任務采用表1給出的SIL分解方案進行分解，分解后得到的任務集CPU利用率的最大值為1．496。

圖5 真實的汽車電子功能集

本文在Matlab 2010環(huán)境下對提出的關鍵級感知的任務分配算法CTA進行了實現(xiàn)，其中實驗運行的 PC 的配置如下:Intel(R)Core(TM)2 2．13 GHz，2 GB RAM。CTA算法的配置如下:WHT1=1，WHT2=800，WHT3=12，M1=10 000 000，M2=100，DLY(cache)=0．05 ms，DLY(mem)=1 ms。根據(jù)該配置，CTA運行的時間大約為9 min。

由于現(xiàn)有相關研究與本文的系統(tǒng)模型存在較大差別，因此分別從分配方案和優(yōu)化目標2個方面出發(fā)實現(xiàn)了另外4種算法，并與CTA進行對比分析，以驗證其有效性。在分配方案方面，實現(xiàn)了另外2種可行的任務分配算法(FSA和C-FSA)。其中，F(xiàn)SA表示在不考慮SIL分解的前提下以功能為單位進行任務分配的直觀方案，該方案對應的CPU利用率和通信時延較低(圖4(a)給出了實例功能按照FSA方案進行任務分配后得到的系統(tǒng)實現(xiàn)情況)。C-SFA表示在考慮關鍵級的前提下進行的任務分配方案，該方案將所有高關鍵級任務分配到一個核，其他低關鍵級任務分配到另一個核(圖4(b)給出了實例功能按照FSA方案進行任務分配后得到的系統(tǒng)實現(xiàn)情況)。在優(yōu)化目標方面，本文分別以成本最小化和資源開銷(CPU和通信時延)最小化為目標實現(xiàn)了2種分配方案Min Cost和Min Res。圖3(a)和圖3(b)分別給出了實例功能按照Min Res和Min Cost方案進行任務分配后得到的系統(tǒng)實現(xiàn)情況。上述5種任務分配方案對應的目標優(yōu)化情況如圖6所示，另外表3對5種任務分配方案對應系統(tǒng)實現(xiàn)所需的成本和資源開銷進行了描述，表4對5種任務分配方案對應系統(tǒng)實現(xiàn)的兩核CPU利用率之和以及通信情況進行了描述。

圖6 5種任務分配方案對應的目標情況

表3 任務分配方案對應的成本和資源開銷

表4 分配方案對應的CPU利用率和通信開銷情況

通過對以上實驗數(shù)據(jù)進行分析后可知:與Min Res方案相比，CTA僅通過增加0．96%的CPU利用率和4個通信消息(3個核內(nèi)消息、1個核間消息)即可獲得30．13%的成本縮減。與 Min Cost方案相比，雖然成本增加了504，但是CPU利用率降低了11．44%，通信消息降低了50個(42個核內(nèi)消息、8個核間消息)。與FSA相比，雖然CPU利用率增加了0．96%，但是通信時延降低了81．6%、成本降低了30．13%。C-FSA在任務分配時也考慮了關鍵級，但是CTA在沒有增加成本的前提下(成本縮減0．5%)，以0．96%的 CPU利用率開銷獲得了45%的整體資源開銷縮減(包括81．6%的通信時延縮減)。

圖7、表5和表6給出了表2中給出的模擬數(shù)據(jù)集對應的實驗結果。同樣，從該實驗結果也可以看出CTA算法在實現(xiàn)成本和系統(tǒng)資源開銷聯(lián)合優(yōu)化方面的優(yōu)勢。

圖7 模擬功能實例的目標值情況

表5 模擬功能集的成本和資源開銷情況

表6 模擬功能實例的CPU利用率和通信開銷情況

6 結束語

為解決多核混合關鍵級系統(tǒng)實現(xiàn)在成本和資源開銷兩方面的權衡，本文提出了一個基于模擬退火算法的啟發(fā)式任務分配算法CTA。該算法同時對CPU資源和多核中的兩層通信時延進行考慮，通過SIL分解實現(xiàn)成本和資源開銷的聯(lián)合優(yōu)化。對比實驗證明CTA算法在實現(xiàn)成本和資源的權衡優(yōu)化方面具有一定優(yōu)勢。

［1］ Buckl C，Camek A，Kainz G，et al．The Software Car:Building ICT Architectures for Future Electric Vehicles［C］//Proceedings of IEEE International Electric Vehicle Conference．Washington D．C．，USA:IEEE Press，2012:4-8．

［2］ Di Natale M，Sangiovanni-Vincentelli A L．Moving from Federated to Integrated Architectures in Automotive:The Role of Standards，Methods and Tools［J］．Proceedings of the IEEE，2010，98(4):603-620．

［3］ Barhorst J，Belote T，Martin L，et al．A Research Agenda for Mixed-criticality Systems［EB/OL］．(2009-04-16)．http://www．cse．wustl．edu/～cdgill/CPSWEEK09_MCAR．

［4］ ISO．ISO 26262-2009 Road Vehicles Functional Safety［S］．2009．

［5］ Alan B，Davis R．Mixed Criticality Systems——A Review［EB/OL］．(2014-07-31)．http://www-users．cs．york．a(chǎn)c．uk/burns/review．pdf．

［6］ Gan Junhe．Tradeoff Analysis for Dependable Real-time Embedded Systems During the Early Design Phase［D］．Copenhagen，Denmark:Technical University of Denmark，2014．

［7］ Parker D，WalkerM．Automatic Decomposition and Allocation of Safety Integrity Levels Using a Penalty-based Genetic Algorithm ［C］//Proceedings of the 26th International Conference on Industrial，Engineering and OtherApplications ofApplied IntelligentSystems．Amsterdam，the Netherlands:［s．n．］，2013:449-459．

［8］ Davis R I，BurnsA．A Survey ofHard Real-time Scheduling for Multiprocessor Systems［J］．ACM Computing Surveys，2011，43(4):1-44．

［9］ 賀毅輝，潘明聰，徐 偉，等．基于概率推理的不確定性任務分配評價方法［J］．計算機工程，2015，41(2):31-35．

［10］ 朱怡安，黃姝娟，段俊花，等．新的混合關鍵任務調(diào)度算法的研究［J］．電子科技大學學報，2014，43(2):268-271．

［11］ 谷傳才，關 楠，于金銘，等．多處理器混合關鍵性系統(tǒng)中的劃分調(diào)度策略［J］．軟件學報，2014，25(2):284-297．

［12］ Giannopoulou G，Stoimenov N．Mapping Mixed-criticality Applications on Multi-core Architectures［C］//Proceedings of Conference on Design Automation and Test in Europe．Washington D．C．，USA:IEEE Press，2014．

［13］ Kang S H，Yang H．Static Mapping of Mixed-critical Applications for Fault-tolerant MPSoCs［C］//Proceedings of Design Automation Conference．Washington D．C．，USA:IEEE Press，2014．

［14］ Tamas-Selicean D，Pop P．Design Optimization of Mixedcriticality Real-time Applications on Cost-constrained Partitioned Architectures［C］//Proceedings of the 32nd Real-time Systems Symposium．Washington D．C．，USA:IEEE Press，2011:24-33．

［15］ Intel．Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors［EB/OL］．(2013-06-21)．http://software．intel．com/sites/products/coll-ateral/hpc/vtune/performanceanalysisguide．pdf．

［16］ Audsley N．On Priority Assignment in Fixed Priority Scheduling［J］．Information Processing Letters，2001，79(1):39-44．

［17］ Davis R I，Burns A．Robust Priority Assignment for Fixed Priority Real-time Systems［C］//Proceedings of the 28th IEEE Real-time Systems Symposium．Washington D．C．，USA:IEEE Press，2007:3-14．

［18］ Jorgensen M，Shepperd M．A SystematicReview of Software Development Cost Estimation Studies［J］．IEEE Transactions on Software Engineering，2007，33(1):33-53．

［19］ IBM．DO-178B Compliance:Turn an Overhead Expense into a Competitive Advantage［EB/OL］．(2012-10-06)．ftp://public．dhe．ibm．com/common/ssi/ecm/en/raw 14249usen/RAW14249USEN．PDF．

［20］ Polzlbauer F，Bate I，Brenner E．On Extensible Networks for Embedded Systems［C］//Proceedings of the 20th Annual International Conference on the Engineering of Computer Based Systems．Washington D．C．，USA:IEEE Press，2013:69-77．