实时程序WCET分析模型与算法

论文摘要

近年来,嵌入式系统在交通、工业控制、移动通信、家用电器等领域的运用需求迅猛增加。嵌入式系统,特别是嵌入式实时系统,逐步从传统的航天、军用武器等高端运用领域走进了人们的日常生活。在一个大的系统中,嵌入式实时系统往往作为核心的控制部件,控制着整个系统的运行。因此,嵌入式实时系统自身的正确性,对整个系统的安全运行起着关键性的作用。时间可预测性是实时系统的重要特征。实时系统时间可预测性一定程度上依赖于实时任务在最坏情况下的执行时间WCET(Worst Case Execution Time)的估计。在系统设计阶段,实时任务的WCET决定着系统硬件在吞吐能力指标上的选择。在系统运行阶段,实时任务的WCET决定着任务是否可调度以及将如何被调度。不正确的WCET估计,可能会导致实时系统失败,甚至带来灾难性的后果。实时程序的WCET与程序的输入参数、实现程序所采用的算法以及程序运行的目标环境相关。控制流分析从程序的源代码或目标代码出发,通过分析程序逻辑结构、语法、语义等来获取程序可能的执行路径信息,找出最长路径。底层分析主要考虑处理器体系结构对程序执行时间的影响,如何对缓存(Cache)、流水线(Pipelines)、分支预测(Branch Prediction)等特性进行建模来提高WCET估计的精度。WCET计算主要研究如何在控制流分析、底层分析的基础上对程序WCET进行估计的算法。在对实时程序WCET分析的相关模型和算法进行了分析的基础上,结合嵌入式实时系统开发的特点,讨论了实时系统开发过程中的时间分析流程、实时程序的WCET分析框架、模型与算法。在GCC编译器的基础上,对静态WCET分析的模型与算法进行了实验。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 嵌入式实时系统
• 1.2 WCET 分析国内外研究现状
• 1.3 论文主要结构
• 2 实时程序WCET 分析的框架
• 2.1 实时系统的时间分析
• 2.2 实时程序WCET 分析框架
• 2.3 小结
• 3 程序控制流分析
• 3.1 基本块（BASIC BLOCK）
• 3.2 控制流图（CONTROL FLOW GRAPH）
• 3.3 时间树（TIMING TREE）
• 3.4 循环上界估计
• 3.5 不可行路径分析
• 3.6 小结
• 4 WCET 计算算法
• 4.1 基于路径的算法
• 4.2 基于树的算法
• 4.3 两种算法比较
• 4.4 小结
• 5 实验
• 6 结束语
• 致谢
• 参考文献