嵌入式实时系统的最坏情况执行时间（WCET）分析

论文题目: 嵌入式实时系统的最坏情况执行时间（WCET）分析

论文类型: 硕士论文

论文专业: 电路与系统

作者: 许杰

导师: 时龙兴

关键词: 嵌入式实时系统,程序最坏情况执行时间,高层分析,底层建模,整数线性规划

文献来源: 东南大学

发表年度: 2005

论文摘要: 嵌入式实时系统的正确性不仅取决于系统的逻辑计算结果,还和产生结果所花费的时间有关,系统必须保证在一个可预测的时间段内对外部事件做出反应。程序最坏情况执行时间(Worst Case Execution Time)是指程序在运行过程中所花费的最大执行时间。它在操作系统实时调度、任务优先级仲裁、资源冲突仲裁、任务间通信以及软硬件划分等研究领域中有着很重要的作用。本文主要针对特定的硬件平台(ARM7TDMI微处理器),对Garfield系统MP3解码程序的最坏情况执行时间(WCET)进行评估,对MP3解码程序的优化给出客观的评判,同时也为MP3子模块的软硬件划分提供重要的依据。程序最坏情况执行时间(WCET)的计算主要涉及到两个方面:高层分析(High-Level Analysis)和底层建模(Low-Level Modeling)。高层分析主要是在高级语言环境中分析程序结构,找出最坏情况下的指令序列,而底层建模是在汇编环境中建立硬件模型,得到已知指令序列的最坏情况执行时间。WCET计算的复杂性限制了被分析程序的大小和计算的准确性。本文详细介绍了一种有效计算最坏情况执行时间(WCET)的方法,并开发了路径分析工具CRYINGCAT。该路径分析工具从底层模型中得到指令执行时间,将其反标到由高层分析提取出来的控制流图(Control Flow Graph)上,然后利用含有执行时间信息的控制流图来建立整数线性规划模型,最后通过求解整数线性规划模型来得到程序的最坏情况执行时间(WCET)。本文使用路径分析工具CRYINGCAT对Garfield系统MP3解码程序的最坏情况执行时间进行计算和分析,以实例验证了路径分析工具CRYINGCAT的有效性和准确性。实验结果显示,在一定数量测试向量的前提下,对于Garfield系统MP3解码程序中已优化的函数,计算所得到的WCET和模拟器仿真所得到的值相差只有1%,而对于结构复杂的函数或者是未经优化的函数,计算所得WCET值和不同测试向量集下的ARMulator模拟器仿真值相差5%至30%。这说明模拟器仿真要么不能找到最长执行时间的路径,要么需要数目庞大的测试向量集。由上面的分析可见,路径分析工具CRYINGCAT可以有效简便地计算出MP3解码程序(C语言程序)的最坏情况执行时间(WCET)。

论文目录:

摘要

ABSTRACT

第一章绪论

1.1 课题选题背景及意义

1.2 所作工作

1.3 本文结构

第二章嵌入式系统WCET分析

2.1 程序路径分析

2.2 硬件结构分析

2.2.1 Cache存储器

2.2.2 ARM7TDMI流水线策略

2.3 硬件结构模型

2.3.1 Cache存储器模型

2.3.2 PipeLine模型

第三章 C语言词法和语法分析

3.1 词法分析原理

3.2 语法分析原理

3.3 词法分析器的生成

3.4 语法解析器的生成

第四章MP3 解码程序分析

4.1 MP3 解码程序CFG图的提取

4.2 CFG图结点信息的采集

4.3 CFG图结点信息的反标

4.4 网络流图分析

第五章 WCET和模拟器仿真之间的比较分析

第六章总结和展望

致谢

参考文献

在校期间发表的论文清单

发布时间: 2007-06-11

参考文献

[1].基于抽象分析的最坏执行时间分析技术[D]. 黎嘉翰.电子科技大学2013
[2].面向对象程序的最坏执行时间分析研究[D]. 李张.大连理工大学2008
[3].程序最差执行时间的混合估算方法研究[D]. 韩同欢.哈尔滨工业大学2016
[4].实时程序WCET分析模型与算法[D]. 江华.华中科技大学2008
[5].μC/OS-Ⅱ实时内核最坏情况执行时间的研究[D]. 陈蕊.东北大学2009
[6].基于抽象解释的实时软件WCET研究[D]. 赵修伟.大连理工大学2009
[7].基于WCET分析技术的程序实时性模型检验方法研究[D]. 张曦.国防科学技术大学2011
[8].基于极值统计的实时软件WCET估计研究[D]. 王海瑞.大连理工大学2007
[9].基于执行时间评估的Spark任务调度技术研究[D]. 刘思宇.北京工业大学2017
[10].多核集群环境下并行地理计算执行时间预测技术研究[D]. 张思乾.国防科学技术大学2011

嵌入式实时系统的最坏情况执行时间（WCET）分析

猜你喜欢