计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

基于MPA与静态预估的最坏执行时间分析方法

李军义1,2,李双1,2,张焱1,2,李仁发1,2   

  1. (1.湖南大学信息科学与工程学院,长沙 411000; 2.湖南省嵌入式与网络计算重点实验室,长沙 411000)
  • 收稿日期:2014-09-28 出版日期:2015-10-15 发布日期:2015-10-15
  • 作者简介:李军义(1970-),男,副教授、博士,主研方向:嵌入式软件,软件测试;李双、张焱,硕士研究生;李仁发,教授、博士生导师。
  • 基金项目:
    广东省产学研合作重大专项基金资助项目(2012-391)。

Worst-case Execution Time Analysis Method Based on

LI Junyi  1,2,LI Shuang  1,2,ZHANG Yan  1,2,LI Renfa  1,2   

  1. (1.College of Information Science and Engineering,Hunan University,Changsha 411000,China; 2.Key Laboratory for Embedded and Network Computing of Hunan Province,Changsha 411000,China)
  • Received:2014-09-28 Online:2015-10-15 Published:2015-10-15

摘要: 针对现有嵌入式系统最坏执行时间(WCET)的静态分析方法效率低下问题,利用最小传播算法对程序流进行分析,获得程序中每一个基本块的最小树约束,通过象征性循环上界约束对所求函数中的内部循环变量进行再次约束,并结合最小树约束获得程序的WCET表达式。使用静态预估分析方法对每一个基本块的底层指令周期进行绝对估值,将底层指令周期代入WCET表达式计算出程序最终的WCET值。实验结果表明,与基于程序控制流程图的程序执行时间静态分析方法相比,该方法在保证程序分析精度的同时,大幅提高了分析效率。

关键词: 嵌入式软件, 实时性, 最坏执行时间, 最小传播算法, 静态预估分析

Abstract: Aiming at the problem of low efficiency for embedded system Worst-case Execution Time(WCET) static analysis methods,this paper uses Minimum Propagation Algorithm(MPA) to analyze the program flow and obtain the min-tree of each code block.Then it gets more strict constraints through the analysis of inner loop variables of function by symbolic loop bounds computation,and gets a WCET expression through constraints of min-tree and the loop bounds.Finally,it uses static prediction method to solve the WCET by absolute valuation of underlying instruction cycle of each basic block,and calculates the final WCET value.Experimental results show that this method increases the analysis efficiency as well as ensures accuracy compared with program execution time static analysis method based on process control flow diagram.

Key words: embedded software, real-time, Worst-case Execution Time(WCET), Minimum Propagation Algorithm(MPA), static prediction analysis

中图分类号: