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

doi:10.3969/j.issn.1000-3428.2015.10.015

计算机工程

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

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

(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.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

摘要/Abstract

摘要： 针对现有嵌入式系统最坏执行时间(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

中图分类号:

TP393

李军义,李双,张焱,李仁发. 基于MPA与静态预估的最坏执行时间分析方法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.10.015.

LI Junyi,LI Shuang,ZHANG Yan,LI Renfa. Worst-case Execution Time Analysis Method Based on[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.10.015.

https://www.ecice06.com/CN/Y2015/V41/I10/76

参考文献

参考文献［1］Cousot P,Cousot R C P,Cousot R.Abstract Interpretation:A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints［C］//Proceedings of the 4th ACM Symposium on Principles of Programming Languages.New York,USA:ACM Press,1977:238-252. ［2］Miné A.The Octagon Abstract Domain［J］.Higher Order Symbolically Computing,2006,19(1):31-67. ［3］Cousot P,Halbwachs N.Automatic Discovery of Linear Roximation of Fixpoints［C］//Proceedings of the 5th ACM Symposium on Principles of Programming Languages.New York,USA:ACM Press,1978:84-97. ［4］Philippe G.Static Analysis of Arithmetical Con-gruences［J］.International Journal of Computer Math-ematics,1989,30(3/4):165-199. ［5］Lisper B.Fully Automatic Parametric Worst-case Execution Time Analysis［C］//Proceedings of the 3rd International Workshop on Worst-case Execution Time Analysis.Washington D.C.,USA:IEEE Press,2003:77-80. ［6］Bygde S.Static WCET Analysis Based on Abstract Interpretation and Counting of Elements［EB/OL］.(2010-03-15).http://www.mrtc.mdh.se/index.php ? choice=publications&id=2144. ［7］Feautrier P.Parametric Integer Programming［J］.Operations Research,1988,22(3):243-268. ［8］Piplib Website［EB/OL］.(2009-11-07).http://www.piplib.org/. ［9］Stefan B,Andreas E,Bjrn L.An Efficient Algorithm for Parametric WCET Calculation［J］.Journal of Systems Architecture,2011,57(6):614-624. ［10］Li Y T S,Malik S,Wolfe A.Performance Estimation of Embedded Software with Instruction Cache Model-ing［J］.ACM Transactions on Design Automation of Electronic Systems,1999,4(3):257-279. ［11］Chattopadhyay S,Kee C L,Roychoudhury A,et al.A Unified WCET Analysis Framework for Multi-core Platforms［C］//Proceedings of the 18th IEEE Inter-national Real-time and Embedded Technology and Applications Symposium.Washington D.C.,USA:IEEE Press,2012:319-329. ［12］Rosen J.Bus Access Optimization for Predictable Implementation of Real-time Applications on Multi-processor Systems-on-chip［C］//Proceedings of the 28th IEEE International Real-time Systems Symposium.Washington D.C.,USA:IEEE Press,2007. ［13］Chattopadhyay S,Roychoudhury A,Mitra T.Modeling Shared Cache and Bus in Multi Core Platforms for Timing Analysis［C］//Proceedings of SCOPES’10.Washington D.C.,USA:IEEE Press,2010:99-108. ［14］Lv Mingsong.Combining Abstract Interpretation with Model Checking for Timing Analysis of Multicore Software［C］//Proceedings of the 31st Real-time Systems Symposium.Washington D.C.,USA:IEEE Press,2010:339-349. ［15］Marco P.Hardware Support for WCET Analysis of Hard Real-time Multicore Systems［C］//Proceedings of the 36th Annual International Symposium on Computer Architecture.New York,USA:ACM Press,2009. ［16］Pellizzoni R.A Predictable Execution Model for COTS-based Embedded Systems［C］//Proceedings of the 17th Real-time and Embedded Technology and Applications Symposium.Washington D.C.,USA:IEEE Press,2011:269-279. ［17］Yan Jun,Zhang Wei.WCET Analysis for Multi-core Processors with Shared L2 Instruction Caches［C］//Proceedings of RTAS’08.Washington D.C.,USA:IEEE Press,2008:80-89. ［18］Li Yan.Timing Analysis of Concurrent Programs Running on Shared Cache Multi-cores［C］//Proceedings of RTSS’09.Washington D.C.,USA:IEEE Press,2009:57-67. ［19］孙昌爱,金茂忠,刘超.程序执行时间的静态预估与可视化分析方法［J］.软件学报,2004,4(1):69-75. ［20］Knoop J,Kovács L,Zwirchmayr J.Symbolic Loop Bound Computation for WCET Analysis［M］.Berlin,Germany:Springer,2012. 编辑陆燕菲

[1]	吴凡, 徐朝农, 邹英豪. 基于PD-NOMA的人员监控图像传输算法[J]. 计算机工程, 2024, 50(6): 266-275.
[2]	郑小敏, 李翔宇. 随机森林手势识别算法的高效嵌入式软件实现[J]. 计算机工程, 2021, 47(7): 218-225.
[3]	罗朔, 侯进, 谭光鸿, 韩雁鹏. 一种低参数的孪生卷积网络实时目标跟踪算法[J]. 计算机工程, 2021, 47(2): 84-89.
[4]	张庭芳, 黄海林, 郭劲林, 曹铭. CAN控制系统的时延分析及混合算法[J]. 计算机工程, 2020, 46(5): 305-311.
[5]	王毅然, 经小川, 贾福凯, 孙宇健, 佟轶. 基于多智能体协同强化学习的多目标追踪方法[J]. 计算机工程, 2020, 46(11): 90-96.
[6]	李春雷,高峰,颜运强. 基于Actor模型的软总线设计[J]. 计算机工程, 2019, 45(5): 77-83.
[7]	孟子琪,张倩颖,施智平,关永. 基于可信执行环境的嵌入式双操作系统架构研究[J]. 计算机工程, 2019, 45(4): 6-12.
[8]	李建鹏, 史国振, 李莉, 孙德洋, 郑戈威. 异构云环境中的实时密码服务调度策略[J]. 计算机工程, 2019, 45(10): 1-7.
[9]	任秀丽,吉鹏硕. WSN中基于分簇的模糊加权数据融合算法[J]. 计算机工程, 2018, 44(3): 109-113,118.
[10]	谭朋柳,冒苏敏,周乐. 一种事件驱动的无线CPS实时消息并行调度方法[J]. 计算机工程, 2018, 44(2): 61-67.
[11]	高峰,邓霏,陈泉根. 基于分层模型的半实物仿真测试平台设计[J]. 计算机工程, 2018, 44(1): 104-109,115.
[12]	张晶,王中正,范洪博. 基于随机Petri网的嵌入式软件能耗模型[J]. 计算机工程, 2017, 43(9): 316-321.
[13]	赵涛,郭猛,顾亚浏,章阳. 基于FPGA的多通道数据采集控制器设计与实现[J]. 计算机工程, 2017, 43(6): 241-246.
[14]	张晶,孙少杰,范洪博,付鑫,张果. 高实时性异构多核处理器任务调度算法[J]. 计算机工程, 2017, 43(5): 55-59.
[15]	李志敏,殷蓓蓓,张萍,王纪兵,王宾,张金鹏. 一种实时性缺陷定位方法及其可视化实现[J]. 计算机工程, 2017, 43(2): 111-119.

选择文件类型/文献管理软件名称

选择包含的内容

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

Worst-case Execution Time Analysis Method Based on

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Worst-case Execution Time Analysis Method Based on

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价