硬件成本缩减的异构分布式嵌入式系统调度算法*

邢红星,魏叶华,乐 懿

(湖南师范大学信息科学与工程学院，湖南 长沙 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的使用率。