关键词:
信息物理系统
嵌入式系统
任务映射
可靠性
摘要:
通过无线网络将协同工作的物理设施互连以达到功能更复杂、性能更高效目标的信息物理系统(Cyber-Physical System,CPS),目前已应用在人类生活的各个领域。同时,嵌入式系统因其体积小、成本低、功耗小、易定制且具备数据采集、信息处理、无线通信等多种功能的优势已逐步成为CPS不可或缺的元件。另外,通常可以将系统应用描述为多个子任务的协同工作,任务之间的数据相关性用有向无环图表示,然后通过将这些子任务映射到嵌入式节点上并以合适的电压/频率执行可以提高系统性能。此外,任务执行过程中的可靠性是影响系统性能的关键因素,节点在网络环境下工作也会面临数据传输和数据处理过程中的可靠性问题,这可以通过提高节点频率或者任务复制(Task Duplication)来改善。与此同时,系统能耗和时间延迟也是衡量系统性能的重要指标,这可以通过动态电压/频率调整(Dynamic Voltage/Frequency Scaling,DVFS)与任务映射(Task Mapping)来调整。本文主要研究嵌入式节点能耗、时延和可靠性联合优化的任务映射问题,在保证可靠性和实时性得到满足的前提下优化能量,主要工作如下:1)针对嵌入式CPS中具有相关性任务的映射问题,考虑在保证实时性和可靠性前提下的能量优化。为了提高任务执行可靠性,引入任务复制机制,当任务可靠性低于某一标准时,可采用任务复制或者DVFS的方式来提高其可靠性。将任务映射问题构建为整数非线性规划(Integer Non-Linear Programming,INLP)问题后通过变量替换的方法将其线性化以求得最优解。同时,为了适应实际应用中问题规模较大导致求最优解十分耗时的情况,提出了能够快速求解的启发式算法,仿真验证了算法能大大缩减求解时间,同时保证求得的解与最优解之间的差距在可接受范围内。2)由于在实际应用中节点间可以通过多条路径路由,本文研究了基于多路径路由的嵌入式节点任务映射可靠性问题。构建了在实时性、可靠性约束下,基于多路径路由的任务映射能量优化问题。同时,本文为此优化问题提出了两种求解方法:一种是将任务映射INLP问题转化为整数线性规划问题后利用优化求解器(如Gurobi等)得到最优解,另一种是设计求近似解的启发式算法。仿真验证了在问题可行性与解的质量方面,基于多路径路由的任务映射问题均比单路径情况更优。另外,在求解时间方面,本文提出的启发式算法(Heuristic Algorithm)非常省时,特别是在问题规模很大时,也能保证迅速求解。3)嵌入式多核体系发展迅速,本文还研究了基于同构多核处理器的嵌入式CPS系统任务映射可靠性问题,在实时性和可靠性的约束下尽可能均衡各节点上的能耗。另外,为了避免任务冲突(Task Non-preemption),在任务映射的同时需要确定任务执行开始时间,且本文考虑影响任务执行开始时间的因素有两个:1)映射到同一核上的任务的执行结束时间;2)来自具有相关性的任务的数据传输结束时间。此外,本文为多核嵌入式CPS系统的任务映射可靠性问题设计了基于任务图分层的启发式算法以减少求解时间。仿真实验表明,基于多核处理器的任务映射问题在可行性和解的质量方面明显优于单核处理器情况。