多核汽车电子系统中关键级感知的任务分配算法

刘樑骄，李仁发，谢 勇，杨 柳，谢国琪

(1．湖南大学 a．信息科学与工程学院;b．嵌入式与网络计算湖南省重点实验室，长沙410082;2．厦门理工学院 a．计算机与信息工程学院;b．福建省高校物联网应用技术重点实验室，福建厦门361024;3．湖南省发展和改革委员会，长沙410004)

1 概述

近年来，人们在安全、智能、节能和环保等方面对汽车提出越来越高的要求，使得汽车电子系统的复杂性骤增。如奔驰S级等豪华轿车车内包含的电子功能达800多个、ECU达100多个，车内的代码量达上千万行［1］。系统复杂性给汽车电子系统设计在满足尺寸、重量和功率(Size，Weight and Power，SWaP)属性方面提出严格要求，成本节约等方面面临严峻挑战。为应对上述挑战，集成化正成为汽车电子系统发展的重要趋势［2］，汽车电子系统正逐渐演变为混合关键级系统［3］。

混合关键级系统的同一硬件平台上同时集成了多个关键级功能，如安全关键性功能、任务关键性功能和非关键性功能等。面向汽车工业的功能安全标准ISO 26262［4］将车内电子功能划分为4个安全完整性等级(Safety Integrity Level，SIL)，并定义不同关键级功能在可靠性方面具有不同的要求，如最高关键级(SIL=4)功能对应的可靠性要求为每小时失效率小于10－8，最低关键级(SIL=1)功能对应的可靠性要求为每小时失效率小于10－6。部分工作关注关键级与任务执行时间之间的对应关系，但是本文主要关注关键级与可靠性之间的对应关系，文献［5］对关键级的不同定义和模型等进行综述。为了保障功能满足可靠性方面的特定要求，关键级越高的功能在开发和认证方面需要付出更高的成本。但是高关键级功能可通过SIL分解来降低其开发和认证成本［6-7］，ISO 26262规范对高关键级功能的分解方案进行了详细阐述。可是SIL分解在实现系统成本缩减的同时将带来额外的资源开销(包括CPU利用率和通信时延的增长等)，因此混合关键级系统的实现需在成本和资源开销之间取得平衡。

本文主要研究混合关键级汽车电子系统的功能实现中任务到多核处理器的分配问题，即当给定多核的系统结构和汽车电子功能(包括功能的拓扑结构，功能包含任务、消息的属性)的前提下，研究如何实现任务到节点的优化分配，使得实现后的系统可调度、系统成本得到优化，以及系统资源得到高效使用。多核处理器调度中的任务分配问题是典型的强NP难问题［8］，本文在保证满足系统可调度的前提下，以成本和资源开销的联合优化为目标，提出一个基于模拟退伙算法的启发式分配算法关键级感知的任务分配(Criticality-aware Task Allocation，CTA)算法。

2 相关工作

任务分配问题是多核处理器调度研究中的关键问题，它是一个典型的NP难问题，现有的研究成果从不同角度提出了多种解决方案，包括基于binpacking 的启发式算法(如 first-fit，best-fit，next-fit等)、基于整数线性规划的最优化算法、基于线性规划、动态编程的算法等［8-9］。但是上述研究均未考虑汽车电子系统的混合关键级特性，并且在多核共享资源开销方面的考虑较少，多核混合关键级系统中的任务分配问题具有更高的复杂性。

在多核混合关键级系统的调度研究方面，文献［10］提出多处理器混合关键级系统中基于正方向时间分割和关键因子优先的调度算法，以提高低关键级任务的可调度性。文献［11］研究基于划分的多核混合关键级系统调度问题，允许任务在不同模式下分配到不同的处理节点之中进行处理，以提高系统资源的利用率。但是本文未考虑核间通信，仅实现了系统资源的优化。文献［12］对基于划分的多核混合关键级系统中的任务分配问题进行了研究，考虑了关键级与任务执行时间、内存开销之间的关系建模，提出基于模拟退火的启发式算法以实现任务反应时间的优化和内存资源的高效使用。文献［13］对多核混合关键级系统中容错感知的任务分配问题进行了研究，考虑了关键级与可靠性和任务执行时间之间的关系建模，提出的基于遗传算法的启发式算法在满足可靠性要求的前提下可实现任务反应时间的优化。上述研究未考虑关键级与成本之间的关系建模，在系统资源方面未考虑多核处理器中存在的多层通信时延模型。文献［6，14］对分布式混合关键级系统中的任务分配问题和静态划分调度问题进行了研究，并就成本与关键级之间的关系进行了建模。但是上述研究主要面向基于单核的分布式系统，以成本和系统可调度性的联合优化为目标，而本文的研究面向多核处理器系统，在系统结构、资源模型和优化目标方面不同。

3 系统模型和假设前提

3．1 系统结构

本文假设混合关键级汽车电子系统采用如图1所示的双核处理器架构。该多核处理器采用两级通信模型，同一个核内的任务之间通过Cache进行通信，不同核内的任务之间通过共享内存进行通信。该两层通信模型可以容易地扩展到三级或者更复杂的通信模型。

图1 多核混合关键级系统的系统结构

3．2 任务和消息模型

如图2(a)所示，采用有向非循环图(Directed Acyclic Graph，DAG)对汽车电子功能进行建模，每个节点表示一个任务，每条边表示2个任务之间的通信消息。图2(b)～图2(d)分别给出了事例功能包含高关键级任务T2和T4的SIL分解方案。任务可通过如下五元组进行描述:

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

分别表示任务的执行时间、周期、SIL、最终期限和开发成本，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进行实现(x=cache);当消息的源任务和目的任务分配到不同核的时候，mi通过共享内存进行实现(x=mem)。根据多核通信的相关研究成果，后一种通信机制对应的通信时延与前一种通信机制对应的通信时延呈2个数量级的倍数关系［15］，本文假设已知 DLYi(cache)和DLYi(mem)的值。因此系统整体的通信时延可按照式(1)进行计算:

汽车电子功能的实现包括任务到核的分配和核内任务调度2个方面。本文主要研究任务到核的分配问题，假设核内的任务采取固定优先级调度算法进行调度执行，任务的优先级采用Audsley算法进行分配［16］，任务的反应时间分析按照文献［17］中给出的方法进行分析。

3．3 成本模型

本文主要从系统的安全性认证和功能开发2个方面对系统成本进行建模和分析，由于本文主要关注多核混合关键级系统中任务分配问题在资源开销和成本之间的权衡问题，因此成本分析方面仅参照文献［6］给出的成本模型，软件成本的精确估计和分析可参照相关标准和研究成果［18-19］。

多核处理器每个核中包含的任务需进行同一认证，其认证成本依赖于所包含任务的最高关键级。核一级的认证成本COk可按照式(2)进行计算:

其中，SIL_COST()函数对应处理器核在不同关键级上的认证成本，本文假设该成本已知。

由于处理器核一级的认证成本依赖于所包含任务的最高关键级，因此系统的认证成本很高。为降低系统的认证成本，ISO 26262规范指出可对高关键级任务进行SIL分解来降低处理器核一级的认证成本。

根据ISO 26262规范，表1以图2中的功能为例给出了高关键级任务的SIL分解方案库。

表2给出了汽车电子功能实例包含任务的相关属性。如功能2中的T4对应2种SIL分解方案:方案1将其分解为T11，T122个任务，并且它们通过I/O任务T10和T13与功能中的其他任务进行通信，该方案将T4的开发成本由28降至9。方案2将其分解为T16，T17和T193个任务，并且它们通过I/O任务T14，T15，T18和T20与功能中的其他任务进行通信，该方案将T4的开发成本由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)所示。汽车电子功能实例根据FSA和C-FSA分配方案得到的任务分配结果如图4所示。

表2 汽车电子功能实例包含任务的相关属性

图3 汽车电子功能实例对应的3种任务分配方案

图4 任务分配结果

根据上述分析，系统的成本包括处理器核一级的认证成本和任务的开发成本2个组成部分，系统成本可按照式(3)进行计算:

4 关键级感知的任务分配算法

模拟退火算法在任务分配问题的相关研究中展现了其有效性［8，12］，本文亦采用其来实现多核混合关键级系统中任务分配在成本和资源开销之间的联合优化。提出的关键级感知的任务分配(Criticalityaware Task Allocation，CTA)算法具体描述如下:

算法 Criticality_aware_Task_Allocation()

输入 多核处理器的系统架构，汽车电子功能集

输出 任务到核的映射关系χ，系统的成本和资源开销情况Opt_Obj

该启发式算法的初始值为“以功能为单位进行任务分配后得到的系统实现方案”(第 1行)，图3(a)给出了实例功能根据该初始化方案分配后得到的任务分配结果。该分配方案亦对应资源开销最小化的分配方案(CPU利用率最低、通信时延最少)。第2行对初始化的任务分配方案对应的系统成本和资源开销情况进行分析，以作为后续启发式搜索步骤的起点。本文主要关注成本和系统资源开销之间的联合优化问题，因此按照线性加权的方式设定CTA的目标函数。该目标函数的具体定义如式(4)所示。

其中，WHT1，WHT2和WHT3分别表示系统成本、CPU利用率和通信时延在该联合优化方案中的权重，该权重的设置可参照文献［20］等相关研究。

CTA共包括4个启发式搜索步骤:SIL分解(SIL Decomposition)，SIL 聚合(SIL Composition)，核间的任务交换(Task Exchange)，核间的任务迁移(Task Migration)(第4行～第11行)。其中，SIL聚合指与SIL分解相反的操作，即将原来通过SIL分解后得到的多个低关键级任务聚合为一个高关键级任务。对当前的任务分配方案进行启发式调整后，首先对调整后的系统可调度性进行分析(第12行)。仅当任务分配调整后的系统可调度的前提下，再尝试对新的分配方案对应的目标值进行分析(第13行)。当启发式步骤获得目标优化时，接受该步骤对应的任务分配调整方案(第14行～第16行);当启发式步骤未获得目标优化时，以概率P接受该步骤对应的任务分配调整方案(第17行～第20行)。当启发式搜索次数达到设定的M1或者启发式搜索对应的目标值连续M2次未获得优化时，终止该算法(第23行～第25行)。由于CTA的启发式特性，不能对其时间复杂性进行准确估计，因此本文主要通过算法的运行时间来代表其复杂性。

5 实验与结果分析

为了证明本文提出算法的有效性，以文献［6］中给出的真实汽车电子功能到双核处理器的分配为例展开实验，该功能集的相关情况如图5所示。该功能集共包括引擎控制、悬挂控制等6个功能，其中，2个SIL4功能;2个SIL3功能，1个SIL2功能和1个SIL1功能。上述功能的初始实现共包括31个任务、19个消息。SIL4的功能包含任务的周期等于25 ms，SIL3的功能包含任务的周期等于50 ms，SIL2的功能包含任务的周期等于100 ms，SIL1的功能包含任务的周期等于200 ms，任务的执行时间在0．2 ms～4 ms之间，功能集对应的CPU利用率为1．37。为实现系统成本的缩减，该功能集中的高关键级任务采用表1给出的SIL分解方案进行分解，分解后得到的任务集CPU利用率的最大值为1．496。

图5 真实的汽车电子功能集

本文在Matlab 2010环境下对提出的关键级感知的任务分配算法CTA进行了实现，其中实验运行的 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。根据该配置，CTA运行的时间大约为9 min。

由于现有相关研究与本文的系统模型存在较大差别，因此分别从分配方案和优化目标2个方面出发实现了另外4种算法，并与CTA进行对比分析，以验证其有效性。在分配方案方面，实现了另外2种可行的任务分配算法(FSA和C-FSA)。其中，FSA表示在不考虑SIL分解的前提下以功能为单位进行任务分配的直观方案，该方案对应的CPU利用率和通信时延较低(图4(a)给出了实例功能按照FSA方案进行任务分配后得到的系统实现情况)。C-SFA表示在考虑关键级的前提下进行的任务分配方案，该方案将所有高关键级任务分配到一个核，其他低关键级任务分配到另一个核(图4(b)给出了实例功能按照FSA方案进行任务分配后得到的系统实现情况)。在优化目标方面，本文分别以成本最小化和资源开销(CPU和通信时延)最小化为目标实现了2种分配方案Min Cost和Min Res。图3(a)和图3(b)分别给出了实例功能按照Min Res和Min Cost方案进行任务分配后得到的系统实现情况。上述5种任务分配方案对应的目标优化情况如图6所示，另外表3对5种任务分配方案对应系统实现所需的成本和资源开销进行了描述，表4对5种任务分配方案对应系统实现的两核CPU利用率之和以及通信情况进行了描述。

图6 5种任务分配方案对应的目标情况

表3 任务分配方案对应的成本和资源开销

表4 分配方案对应的CPU利用率和通信开销情况

通过对以上实验数据进行分析后可知:与Min Res方案相比，CTA仅通过增加0．96%的CPU利用率和4个通信消息(3个核内消息、1个核间消息)即可获得30．13%的成本缩减。与 Min Cost方案相比，虽然成本增加了504，但是CPU利用率降低了11．44%，通信消息降低了50个(42个核内消息、8个核间消息)。与FSA相比，虽然CPU利用率增加了0．96%，但是通信时延降低了81．6%、成本降低了30．13%。C-FSA在任务分配时也考虑了关键级，但是CTA在没有增加成本的前提下(成本缩减0．5%)，以0．96%的 CPU利用率开销获得了45%的整体资源开销缩减(包括81．6%的通信时延缩减)。

图7、表5和表6给出了表2中给出的模拟数据集对应的实验结果。同样，从该实验结果也可以看出CTA算法在实现成本和系统资源开销联合优化方面的优势。

图7 模拟功能实例的目标值情况

表5 模拟功能集的成本和资源开销情况

表6 模拟功能实例的CPU利用率和通信开销情况

6 结束语

为解决多核混合关键级系统实现在成本和资源开销两方面的权衡，本文提出了一个基于模拟退火算法的启发式任务分配算法CTA。该算法同时对CPU资源和多核中的两层通信时延进行考虑，通过SIL分解实现成本和资源开销的联合优化。对比实验证明CTA算法在实现成本和资源的权衡优化方面具有一定优势。

［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．ac．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］ 朱怡安，黄姝娟，段俊花，等．新的混合关键任务调度算法的研究［J］．电子科技大学学报，2014，43(2):268-271．

［11］ 谷传才，关 楠，于金铭，等．多处理器混合关键性系统中的划分调度策略［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．