摘 要
车辆是嵌入式系统的主要应用场所之一，新一代车载异构嵌入式系 统 正 逐 步 发 展 成 为 车 载 物 理 信 息 融 合 系 统(Automotive CyberPhysical System, ACPS)，考虑到人员和车辆的安全，需提出高性能、强实时、低成本的调度算法，在设计阶段完成任务到资源的合理分配。因此，围绕可调度性和成本缩减开展基于车载异构嵌入式系统的调度问题研究是十分必要的。本文主要工作和创新点如下。
（1）基于时间触发策略的混合周期性功能集合的调度研究。以增强可调度性为目标，考虑了任务和消息的整体调度，提出了最大容忍性后移调度(Maximum Tolerant Backshift Scheduling, MTBS)算法。算法基于插入策略，有选择性地释放满足实时性约束下被已完成调度的任务和消息所占据的资源以满足任务执行时间，减少整体调度时的资源冲突，合理地利用了零星资源，在调度复杂功能集合时能保证较高的调度成功率。
（2）基于整数线性规划模型的车载电子系统硬件成本缩减方案研究。基于已找到的调度表，以硬件成本缩减为目标，尝试在保证功能的响应时间约束的前提下，取消尽可能多的处理器，提出了基于整数线性规划的硬件成本缩减(ILP based Hardware Cost Reduction, IHCR)算法。算法通过对任务与处理器之间的映射关系、执行开销进行分析，建立硬件成本缩减方案，通过建立整数线性规划模型确认可行性，并根据执行结果产生新方案，寻找最优解。
综上，本文针对车载异构嵌入式系统多功能的调度问题展开探索和研究，基于响应时间约束、时间触发策略、功能混合周期性、系统成本敏感的特性，从任务到资源的合理分配角度考虑了整体调度，并对调度表进行了硬件成本的缩减研究，为车载异构嵌入式系统的早期设计阶段的调度问题提供性能更高的优化方法，具有一定理论意义和应用价值。
关键词： 异构嵌入式系统；多功能调度；时间触发策略；混合周期性；硬件成本缩减。
ABSTRACT
Vehicles are one of the main applications of embedded systems, and the new generation of vehicle-based embedded systems is gradually developing into Automotive Cyber Physical System (ACPS). Considering the safety of people and vehicles, its need to propose high performance and strong real-time, low-cost scheduling algorithm to complete the assignment rational of tasks to resources in the design stage. Therefore, its necessary to research on scheduling problems based on schedulability 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, considering the holistic scheduling of task and message instances, Maximum Tolerant Backshift Scheduling (MTBS) algorithm is proposed. Under the real-time constraint, the algorithm selectively releases the allocated resources to meet the task execution time, makes reasonable use of sporadic resources, and can guarantee a high scheduling success rate when scheduling complex function sets;(2) Research on hardware cost reduction scheme in vehicle electronic system based on integer linear programming model. Aiming at reducing hardware cost and eliminating as many processors as possible on the premise of ensuring the security and integrity of functions, ILP based Hardware Cost Reduction (IHCR) algorithm was proposed. According to the execution of the task, the algorithm establishes a hardware cost reduction scheme, establishes integer linear programming models toconfirm the feasibility, and generates new schemes according to the execution result to find the optimal solution as much as possible step by step.
In summary, this article studies the multi-functional integrated 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 the perspective of rational allocation of tasks to resources and the hardware cost reduction was studied for the scheduling. It is theoretical significance and application value to provide a higher performance optimization method for the scheduling problem in the early design stage of the vehicle heterogeneous embedded system.
Keywords: heterogeneous embedded system; multi-functions scheduling; time-triggered strategy; mixed periodicity; hardware cost reductio。
第1章 绪论
1.1、 研究背景和意义。
异构嵌入式体系结构广泛应用于航空航天、国防、工业自动化、健康医疗设备、重大基础设施、道路交通等主要领域[1]。车辆是异构嵌入式系统的主要应用场所之一，其内部的汽车电子系统已发展成为成熟的异构分布嵌入式计算系统。从计算机系统的角度看，异构嵌入式系统由计算单元、控制器单元、执行器单元以及网络系统构成。随着智能传感、云计算、大数据和5G网络等信息技术的发展和其技术逐步在车异构嵌入式系统上的应用，使得无人驾驶、先进的辅助驾驶等智能化的车辆新功能有机会面向大众，被国内外专家学者认为是下一代智能系统的信息物理系统(Cyber-Physical Systems, CPS)[2, 3]被应用于汽车行业，形成汽车网络物理系统(Automobile CPS)，具有发展潜力。
ACPS主要通过集成于其上的功能实现车辆控制，据统计，车载嵌入式异构系统的相关成本已经占到汽车总成本的30%-40%[4]，汽车工业相关创新中的90%都依赖于电子化和软件的驱动，软件总容量已达到230MB，车内的代码量达到上千万行[5, 6]。因此，车载嵌入式系统必须利用有限的资源完成对所有汽车功能的资源部署。
现代车载系统体系结构日益复杂，图1.1所示为车载系统实例。其中处理设备包含各类异构电子控制单元(Electronic Control Unit, ECU)[7]集群、执行器、传感器、网关等物理设备，其收集和传输物理信息，通过异构网络总线连接起来的多个的相互作用、反馈和协调来实现多个功能(Function)，遍布车内的ECU数量达到了100多个[8]。系统异构性特征明显，表现在ECU计算效率的不同，ECU集成了不同指令集的CPU、数字信号处理器、FPGA和其他专门定制的芯片，对于相同的计算任务，不同的ECU耗时不同。
基于多核处理器架构的车载嵌入式系统，在硬件层次上大幅地提升了处理器的性能和系统对复杂功能的承载力，但车辆功能由不同的团队开发和测试，并在后期被整合[9]，在对功能集合进行整合和资源部署的时候，必须同时满足功能对系统硬件的要求，这使得ACPS异构性被动提升[10]。例如，在汽车辅助驾驶功能中，引入图像信息采集系统和对应算法运行的ECU；在主动刹车功能中，需要引入速度、转向等信息的采集和控制系统及其对应算法运行的ECU。因此，系统中引入了大量具有专门功能的ECU以适应功能的部署，否则任务在其他ECU执行会浪费大量时间以致最终违背功能的响应时间约束甚至酿成惨祸。
由于主动功能、X-by-wire技术[11]等的引入，对ACPS的带宽、预测性、可靠性等提出了高要求。为保证车辆的服务质量(Quality of Service, Qo S)，Flex Ray[12]、TT-CAN[13]等总线协议以其具有基于时间触发的工作特性，显现出了优势，因此，需在基于时间触发的系统上完成对功能集合的调度和资源分配。同时，车载功能主要通过传感器感知物理环境[14]，包括距离传感器、温度传感器、压力传感器等，传感器的工作方式一般是周期性的，并且传感器类型和工作频率不尽相同，使得系统对有传感器参与的功能的实时性要求也不同，并且某些任务在不同周期内的开始时间呈现严格周期性，导致功能集合呈现混合周期性。
汽车开放系统架构(Automotive Open System Architecture, AUTOSAR)[15]规范指出需从功能级别的角度对车载计算系统和网络系统进行集成设计。同时，2011年颁布的道路安全-功能安全(Road Vehicle-Function Safety)标准规范ISO 26262[16]中提出，确保汽车电子系统的安全功能在各种严酷条件下保持正常运作，确保驾乘人员及行人的安全，是现代汽车电子系统设计的核心任务[16]。与传统汽车电子产品相比，现代汽车更强调智能性和整体性，更强调基于异构总线的ECU的协调工作，这对这一基于安全保障的产品提出了挑战。因此，在考虑对种类繁多的车载功能集成的时候，安全是首要目标，即必须保证功能集合的整体调度[17]。
随着车载功能规模的不断增长，所需的处理器硬件成本也相应增加。当前，用于CAN(Controller Area Networks,标准控制器局域网)接口的处理器的单价从25美元到110美元[18]，大幅提升了系统硬件成本。车辆是大批量生产的工业产品，对成本敏感，必须在安全前提下考虑硬件成本缩减，因此需要对车载嵌入式系统做硬件成本缩减分析[19]，从而获得高利润。尽管分布式体系结构已大大降低了线束的硬件成本，但执行车载功能所需的处理器数量仍然会产生大量的硬件成本[20]。因此，通过调度算法减少处理器数量来降低硬件成本具有重大工业意义。
【由于本篇文章为硕士论文，如需全文请点击底部下载全文链接】
1.2、调度问题研究进展.
1.2.1、异构嵌入式系统中的功能调度
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.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、调度模型
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、本章小结.
总 结
新一代车载异构嵌入式系统是典型的物理信息融合系统(Automotive CyberPhysical System, ACPS)，其通过车内异构总线将大量的电子控制单元(ECU)、执行器、处理器互相连通，尤其是先进辅助驾驶、无人驾驶、主动安全功能等技术的引入和部署，使得其具有物理环境、网络信息、控制部件结合紧密的特点。系统的安全性是重要的设计指标，实现所有车载功能的资源部署是系统安全的前提，其对车载系统的可靠性和可预测性提出了较高的要求，基于时间触发策略的总线协议和调度算法有更强的适应性，所以本文面向新一代车载异构嵌入式系统，开展基于时间触发策略和功能混合周期性的调度问题与算法的研究，以高性能、硬实时和低硬件成本为目标，将车载功能抽象成多个有向无环图，围绕可调度性和硬件成本缩减开展研究，取得了一定的研究成果。主要工作内容总结如下。
(1)面向时间触发策略、高异构性、功能集合混合周期性的调度问题展开研究。
1）基于任务与ECU的映射关系固定的特点，提出了基于关键路径任务优先排序(Critical Path Task First Based Sorting, CPTFBS)算法，获得具有最小调度长度的单功能任务和消息排序；采用基于功能的周期、端到端截止时间、最小调度长度、功能周期率四维属性的功能计算功能优先级并排序，旨在同步水平对所有功能的调度难度做客观评价。
2）基于时间触发策略和功能混合周期性，考虑了任务和消息的整体调度，提出了最大容忍性后移调度(Maximum Tolerant Backshift Scheduling, MTBS)算法，提升了调度成功率。该算法在一个超周期内寻找功能的所有任务和消息实例的触发时间，提出最佳释放时间寻找(Optimal Release-time Finding, ORF)方法避开资源冲突，引入回溯提升优先级(Backtracking and Priority Promotion, BPP)方法重新对功能进行排序从而扩大对解空间的搜寻。
3）基于功能的伸展性，提出了寻找任务和消息实例的触发时间的整体后移(Overall-Movement, OM)算法。该算法考虑在资源冲突时，有选择性地释放满足实时性约束下被已完成调度的任务和消息所占据的资源以满足任务执行时间，减少整体调度时的资源冲突，合理地利用了零星资源；4）利用仿真实验将MTBS与现有的算法进行了对比，基于RTGG产生的随机DAG集合，得到该算法在应对混合周期性的功能集合时，在满足时序约束的基础上，提升了调度成功率，找到了在超周期中所有任务和消息实例的触发时间。
（2）面向时间触发策略、硬件成本优化、功能集合混合周期性的调度问题的研究。
1）基于功能的周期值不同，为了整体考虑对所有功能的调度，考虑在一个超周期内，构建将所有功能实例包含在内的Big DAG，通过添加虚拟入口任务、虚拟出口任务、同一功能不同实例之间的虚拟信息，添加了所有任务之间的强线性约束，建立起不同功能之间的约束关系；2）基于所有任务对ECU的需求程度，提出了基于整数线性规划的硬件成本缩减(ILP based Hardware Cost Reduction, IHCR)算法，通过对任务与ECU之间的映射关系、执行开销进行分析，根据需求程度建立包括了设置睡眠状态的ECU的数量和编号的硬件成本缩减方案，然后根据调度模型和线性公式，建立整数线性规划模型，确认成本缩减方案的可行性，并根据方案执行结果产生设置睡眠状态的ECU的数量递增的新方案，最终找到满足功能安全条件下的成本最优解。
3）利用仿真实验将IHCR与MTBS找到的调度表进行对比，基于RTGG产生的随机DAG集合和任务的执行开销集，得到在应对ECU数量缩减从而减少硬件成本时，在硬实时约束条件下，减少了调度模型中的ECU数量，提升了ECU的使用率。
ACPS具有异构、交互和分布式的特点，新一代智能网联汽车的安全运行将更依赖感知、计算、控制和网络四者的协同，所以在系统设计过程需要考虑动态性、并行性、实时性和可靠性等挑战。本文主要针对设计开发阶段车载功能集合的实时性调度问题展开了研究，提出了解决方案和优化算法，并利用仿真实验验证了其有效性。以本调度模型为基础，可从以下几个方面开展进一步研究。
（1）面向车载网络信息安全的调度问题研究。
新一代汽车异构嵌入式系统网络有联通网络的需求，针对车辆处理任务到边缘计算服务器的卸载也是当下研究热门，在提升车辆性能的同时，也增加了车载网络因暴露而被攻击产生严重的功能安全威胁。例如，中国腾讯科恩实验室攻破特斯拉汽车电子系统网络，实现了对汽车的远程完全控制。随着通信接口的集成，保护敏感通信信息的需求变得至关重要。因此，可以通过消息加密的方式保证汽车电子系统的信息安全，在提升网络总线中的消息的安全级别、最小化系统暴露的漏洞和资源约束的限制下，实现信息安全最大化，强化信息安全。
（2）面向可靠性增强的车载嵌入式异构系统的调度问题研究。
车载系统是可靠性关键的嵌入式系统，在ECU硬件性能和数量得到大幅提升的同时，却引起系统的故障率不断增加。车载系统是多个不同类型的子系统相互作用的综合体，若某个子系统发生错误，极易将风险传播至其他子系统甚至威胁总体安全，同时车辆在行驶过程中也会因电磁干扰使ECU和通信网络出现瞬时故障、因硬件温度较高使运行出现瞬时故障等偶发情况，导致系统可靠性显着降低。因此，从可靠性角度出发考虑混合周期性功能集合在时间触发策略下的调度问题是十分必要的，未来可根据标准规范IS0 26262定义的功能的可靠性概率需求，研究实时性约束条件下的车载系统可靠性增强，降低车载功能运行故障率，为车辆安全提供保障；（3）面向车载功能强实时性约束的混合时间/事件触发的调度问题。
本文提出的调度策略和算法是在设计阶段对多DAG的静态调度，但实际中的车载功能部分是基于时间触发策略，部分是基于事件触发策略，因此多DAG的时间触发策略的调度不一定能完全满足于现实需要，有必要考虑实时性约束前提下的混合时间/事件触发方式的调度问题。
参考文献
