车载异构嵌入式系统多功能的调度问题探究

1、车载异构嵌入式系统多功能的调度问题探究摘 要车辆是嵌入式系统的主要应用场所之一，新一代车载异构嵌入式系 统 正 逐 步 发 展 成 为 车 载 物 理 信 息 融 合 系 统(AutomotiveCyberPhysicalSystem, ACPS)，考虑到人员和车辆的安全，需提出高性能、强实时、低成本的调度算法，在设计阶段完成任务到资源的合理分配。因此，围绕可调度性和成本缩减开展基于车载异构嵌入式系统的调度问题研究是十分必要的。本文主要工作和创新点如下。（1）基于时间触发策略的混合周期性功能集合的调度研究。以增强可调度性为目标，考虑了任务和消息的整体调度，提出了最大容忍性后移调度(Maximu

2、m Tolerant Backshift Scheduling, MTBS)算法。算法基于插入策略，有选择性地释放满足实时性约束下被已完成调度的任务和消息所占据的资源以满足任务执行时间，减少整体调度时的资源冲突，合理地利用了零星资源，在调度复杂功能集合时能保证较高的调度成功率。（2）基于整数线性规划模型的车载电子系统硬件成本缩减方案研究。基于已找到的调度表，以硬件成本缩减为目标，尝试在保证功能的响应时间约束的前提下，取消尽可能多的处理器，提出了基于整数线性规划的硬件成本缩减(ILP based Hardware Cost Reduction, IHCR)算法。算法通过对任务与处理器之间的映射关

3、系、执行开销进行分析，建立硬件成本缩减方案，通过建立整数线性规划模型确认可行性，并根据执行结果产生新方案，寻找最优解。综上，本文针对车载异构嵌入式系统多功能的调度问题展开探索和研究，基于响应时间约束、时间触发策略、功能混合周期性、系统成本敏感的特性，从任务到资源的合理分配角度考虑了整体调度，并对调度表进行了硬件成本的缩减研究，为车载异构嵌入式系统的早期设计阶段的调度问题提供性能更高的优化方法，具有一定理论意义和应用价值。关键词：异构嵌入式系统；多功能调度；时间触发策略；混合周期性；硬件成本缩减。ABSTRACTVehicles are one of themain applications o

4、fembedded systems, and thenewgenerationofvehicle-basedembeddedsystemsisgradually developing into Automotive Cyber Physical System (ACPS).Considering the safety of people and vehicles, its need to propose high performance and strongreal-time,low-costschedulingalgorithmtocompletethe assignmentrational

5、oftaskstoresourcesinthedesignstage. Therefore, itsnecessarytoresearchonschedulingproblemsbasedonschedulability and cost reduction. The main work and innovations are as follows.(1) Research on scheduling mixed periodic function set based on time trigger strategy. In order to enhance schedulability, c

6、onsidering the holistic schedulingoftaskandmessageinstances,MaximumTolerantBackshift Scheduling (MTBS) algorithm is proposed. Under the real-time constraint, thealgorithm selectivelyreleases theallocated resourcesto meet the task executiontime,makesreasonableuseofsporadicresources,andcan guarantee a

7、 high scheduling success rate when scheduling complex function sets;(2) Research on hardware cost reduction scheme in vehicle electronic systembasedonintegerlinearprogrammingmodel. Aimingatreducing hardwarecostand eliminatingasmanyprocessorsaspossibleonthe premiseofensuringthesecurityandintegrityoff

8、unctions,ILPbased HardwareCostReduction(IHCR)algorithmwasproposed. Accordingto theexecutionofthetask,thealgorithmestablishesahardwarecost reductionscheme,establishesintegerlinearprogrammingmodelstoconfirmthefeasibility,andgeneratesnewschemesaccordingtothe execution result to find the optimal solutio

9、n as much as possible step by step.Insummary,thisarticlestudiesthemulti-functionalintegrated scheduling problem of vehicle heterogeneous embedded systems. Based on response time constraints, task and message time triggering methods, mixed periodicity of functions, and hardware cost sensitive, from t

10、he perspective of rational allocation of tasks to resources and the hardware cost reduction was studied for the scheduling. It is theoretical significance and application valuetoprovideahigherperformanceoptimizationmethodforthe scheduling problem in the early design stage of the vehicle heterogeneou

11、s embedded system.Keywords:heterogeneous embedded system; multi-functionsscheduling; time-triggered strategy; mixed periodicity; hardware cost reductio。第1章绪论1.1、 研究背景和意义。异构嵌入式体系结构广泛应用于航空航天、国防、工业自动化、健康医疗设备、重大基础设施、道路交通等主要领域1。车辆是异构嵌入式系统的主要应用场所之一，其内部的汽车电子系统已发展成为成熟的异构分布嵌入式计算系统。从计算机系统的角度看，异构嵌入式系统由计算单元、控制器

12、单元、执行器单元以及网络系统构成。随着智能传感、云计算、大数据和5G网络等信息技术的发展和其技术逐步在车异构嵌入式系统上的应用，使得无人驾驶、先进的辅助驾驶等智能化的车辆新功能有机会面向大众，被国内外专家学者认为是下一代智能系统的信息物理系统(Cyber-PhysicalSystems,CPS)2, 3被应用于汽车行业，形成汽车网络物理系统(AutomobileCPS)，具有发展潜力。ACPS主要通过集成于其上的功能实现车辆控制，据统计，车载嵌入式异构系统的相关成本已经占到汽车总成本的30%-40%4，汽车工业相关创新中的90%都依赖于电子化和软件的驱动，软件总容量已达到230MB，车内的代码

13、量达到上千万行5, 6。因此，车载嵌入式系统必须利用有限的资源完成对所有汽车功能的资源部署。现代车载系统体系结构日益复杂，图1.1所示为车载系统实例。其中处理设备包含各类异构电子控制单元(Electronic Control Unit, ECU)7集群、执行器、传感器、网关等物理设备，其收集和传输物理信息，通过异构网络总线连接起来的多个的相互作用、反馈和协调来实现多个功能(Function)，遍布车内的ECU数量达到了100多个8。系统异构性特征明显，表现在ECU计算效率的不同，ECU集成了不同指令集的CPU、数字信号处理器、FPGA和其他专门定制的芯片，对于相同的计算任务，不同的ECU耗时不

14、同。基于多核处理器架构的车载嵌入式系统，在硬件层次上大幅地提升了处理器的性能和系统对复杂功能的承载力，但车辆功能由不同的团队开发和测试，并在后期被整合9，在对功能集合进行整合和资源部署的时候，必须同时满足功能对系统硬件的要求，这使得ACPS异构性被动提升10。例如，在汽车辅助驾驶功能中，引入图像信息采集系统和对应算法运行的ECU；在主动刹车功能中，需要引入速度、转向等信息的采集和控制系统及其对应算法运行的ECU。因此，系统中引入了大量具有专门功能的ECU以适应功能的部署，否则任务在其他ECU执行会浪费大量时间以致最终违背功能的响应时间约束甚至酿成惨祸。由于主动功能、X-by-wire技术11等

15、的引入，对ACPS的带宽、预测性、可靠性等提出了高要求。为保证车辆的服务质量(Quality of Service, Qo S)，Flex Ray12、TT-CAN13等总线协议以其具有基于时间触发的工作特性，显现出了优势，因此，需在基于时间触发的系统上完成对功能集合的调度和资源分配。同时，车载功能主要通过传感器感知物理环境14，包括距离传感器、温度传感器、压力传感器等，传感器的工作方式一般是周期性的，并且传感器类型和工作频率不尽相同，使得系统对有传感器参与的功能的实时性要求也不同，并且某些任务在不同周期内的开始时间呈现严格周期性，导致功能集合呈现混合周期性。汽车开放系统架构(Automoti

16、ve Open System Architecture, AUTOSAR)15规范指出需从功能级别的角度对车载计算系统和网络系统进行集成设计。同时，2011年颁布的道路安全-功能安全(Road Vehicle-Function Safety)标准规范ISO 2626216中提出，确保汽车电子系统的安全功能在各种严酷条件下保持正常运作，确保驾乘人员及行人的安全，是现代汽车电子系统设计的核心任务16。与传统汽车电子产品相比，现代汽车更强调智能性和整体性，更强调基于异构总线的ECU的协调工作，这对这一基于安全保障的产品提出了挑战。因此，在考虑对种类繁多的车载功能集成的时候，安全是首要目标，即必须保证

17、功能集合的整体调度17。随着车载功能规模的不断增长，所需的处理器硬件成本也相应增加。当前，用于CAN(Controller Area Networks,标准控制器局域网)接口的处理器的单价从25美元到110美元18，大幅提升了系统硬件成本。车辆是大批量生产的工业产品，对成本敏感，必须在安全前提下考虑硬件成本缩减，因此需要对车载嵌入式系统做硬件成本缩减分析19，从而获得高利润。尽管分布式体系结构已大大降低了线束的硬件成本，但执行车载功能所需的处理器数量仍然会产生大量的硬件成本20。因此，通过调度算法减少处理器数量来降低硬件成本具有重大工业意义。1.2、调度问题研究进展.1.2.1、异构嵌入式系统

18、中的功能调度1.2.2、硬件成本缩减进展.1.2.3、研究进展小结1.3、本文主要工作1.4、本文组织结构第2章系统模型和调度问题简介2.1、异构嵌入式系统调度模型.2.1.1、嵌入式系统模型2.1.2、功能的DAG抽象模型2.1.3 、异构嵌入式系统的多DAG抽象模型2.2、面向异构嵌入式系统的调度问题.2.2.1、基于时间约束和功能完整的调度问题2.2.2、嵌入式系统网络协议触发方式2.2.3、功能混合周期性2.2.4、系统处理器高异构性和成本敏感2.3、本章小结.第3章时间触发车载网络中混合周期功能的调度3.1、引言1.2、调度问题研究进展.1.2.1、异构嵌入式系统中的功能调度1.2.

19、2、硬件成本缩减进展.1.2.3、研究进展小结1.3、本文主要工作1.4、本文组织结构第2章系统模型和调度问题简介2.1、异构嵌入式系统调度模型.2.1.1、嵌入式系统模型2.1.2、功能的DAG抽象模型2.1.3、 异构嵌入式系统的多DAG抽象模型2.2、面向异构嵌入式系统的调度问题.2.2.1、基于时间约束和功能完整的调度问题2.2.2、嵌入式系统网络协议触发方式2.2.3、功能混合周期性2.2.4、系统处理器高异构性和成本敏感2.3、本章小结.第3章时间触发车载网络中混合周期功能的调度3.1、引言第4章基于整数线性规划的硬件成本缩减调度4.1、 引言.4.2、调度模型与问题描述4.2.1

20、、调度模型4.2.2、问题描述与简单案例4.3、基于整数线性规划的硬件成本缩减算法4.3.1、算法简介4.3.2、功能整合4.3.3、建立成本缩减方案.4.3.4、整数线性规划公式4.4、实验和评估4.4.1、实验环境与指标4.4.2、RTGG仿真实验4.5、本章小结.总结新一代车载异构嵌入式系统是典型的物理信息融合系统(AutomotiveCyberPhysical System, ACPS)，其通过车内异构总线将大量的电子控制单元(ECU)、执行器、处理器互相连通，尤其是先进辅助驾驶、无人驾驶、主动安全功能等技术的引入和部署，使得其具有物理环境、网络信息、控制部件结合紧密的特点。系统的安全

21、性是重要的设计指标，实现所有车载功能的资源部署是系统安全的前提，其对车载系统的可靠性和可预测性提出了较高的要求，基于时间触发策略的总线协议和调度算法有更强的适应性，所以本文面向新一代车载异构嵌入式系统，开展基于时间触发策略和功能混合周期性的调度问题与算法的研究，以高性能、硬实时和低硬件成本为目标，将车载功能抽象成多个有向无环图，围绕可调度性和硬件成本缩减开展研究，取得了一定的研究成果。主要工作内容总结如下。(1)面向时间触发策略、高异构性、功能集合混合周期性的调度问题展开研究。1）基于任务与ECU的映射关系固定的特点，提出了基于关键路径任务优先排序(Critical Path Task Fir

22、st Based Sorting, CPTFBS)算法，获得具有最小调度长度的单功能任务和消息排序；采用基于功能的周期、端到端截止时间、最小调度长度、功能周期率四维属性的功能计算功能优先级并排序，旨在同步水平对所有功能的调度难度做客观评价。2）基于时间触发策略和功能混合周期性，考虑了任务和消息的整体调度，提出了最大容忍性后移调度(Maximum Tolerant Backshift Scheduling, MTBS)算法，提升了调度成功率。该算法在一个超周期内寻找功能的所有任务和消息实例的触发时间，提出最佳释放时间寻找(Optimal Release-time Finding, ORF)方法避

23、开资源冲突，引入回溯提升优先级(Backtracking and Priority Promotion, BPP)方法重新对功能进行排序从而扩大对解空间的搜寻。3）基于功能的伸展性，提出了寻找任务和消息实例的触发时间的整体后移(Overall-Movement, OM)算法。该算法考虑在资源冲突时，有选择性地释放满足实时性约束下被已完成调度的任务和消息所占据的资源以满足任务执行时间，减少整体调度时的资源冲突，合理地利用了零星资源；4）利用仿真实验将MTBS与现有的算法进行了对比，基于RTGG产生的随机DAG集合，得到该算法在应对混合周期性的功能集合时，在满足时序约束的基础上，提升了调度成功率，

24、找到了在超周期中所有任务和消息实例的触发时间。（2）面向时间触发策略、硬件成本优化、功能集合混合周期性的调度问题的研究。1）基于功能的周期值不同，为了整体考虑对所有功能的调度，考虑在一个超周期内，构建将所有功能实例包含在内的Big DAG，通过添加虚拟入口任务、虚拟出口任务、同一功能不同实例之间的虚拟信息，添加了所有任务之间的强线性约束，建立起不同功能之间的约束关系；2）基于所有任务对ECU的需求程度，提出了基于整数线性规划的硬件成本缩减(ILP based Hardware Cost Reduction, IHCR)算法，通过对任务与ECU之间的映射关系、执行开销进行分析，根据需求程度建立包

25、括了设置睡眠状态的ECU的数量和编号的硬件成本缩减方案，然后根据调度模型和线性公式，建立整数线性规划模型，确认成本缩减方案的可行性，并根据方案执行结果产生设置睡眠状态的ECU的数量递增的新方案，最终找到满足功能安全条件下的成本最优解。3）利用仿真实验将IHCR与MTBS找到的调度表进行对比，基于RTGG产生的随机DAG集合和任务的执行开销集，得到在应对ECU数量缩减从而减少硬件成本时，在硬实时约束条件下，减少了调度模型中的ECU数量，提升了ECU的使用率。ACPS具有异构、交互和分布式的特点，新一代智能网联汽车的安全运行将更依赖感知、计算、控制和网络四者的协同，所以在系统设计过程需要考虑动态性、并行性、实时