实时控制系统程序模式的WCET自动分析方法

doi:10.3969/j.issn.1000-3428.2017.08.010

计算机工程

实时控制系统程序模式的WCET自动分析方法

侯小静¹,姬孟洛¹,黄辰林²,舒云星¹,阎奔¹

(1.洛阳理工学院计算机与信息工程学院,河南洛阳 471023; 2.国防科学技术大学计算机学院,长沙 410073)

收稿日期:2016-11-23 出版日期:2017-08-15 发布日期:2017-08-15
作者简介:侯小静(1975—),女,讲师、硕士,主研方向为实时系统、智能计算;姬孟洛(通信作者),教授级高级工程师、博士;黄辰林,副教授、博士;舒云星、阎奔,教授、博士。
基金资助:
国家自然科学基金“基于复合传感器阵列的多火源融合定位方法研究”(61503174);河南省基础与前沿技术研究计划项目“实时嵌入式系统WCET的精确分析研究”(152300410115);河南省科技攻关计划项目“基于PLC控制技术与SaaS云服务模式的智能运维系统关键技术研究”(162102210276);河南省科技厅国际科技合作项目“基于二维码离散视觉识别模式的物流机器人路径规划与导引的研究”(152102410053)。

Automatic WECT Analysis Method of Program Mode for Real-time Control System

HOU Xiaojing¹,JI Mengluo ¹,HUANG Chenlin ²,SHU Yunxing ¹,YAN Ben ¹

(1.School of Computer and Information Engineering,Luoyang Institute of Science and Technology,Luoyang,Henan 471023,China;2.School of Computer,National University of Defense Technology,Changsha 410073,China)

Received:2016-11-23 Online:2017-08-15 Published:2017-08-15

摘要/Abstract

摘要： 基于源程序获取实时控制系统的模式,不仅能够验证实现的模式与设计是否一致,还可使程序的最差情况执行时间(WCET)计算更为精准。为此,提出一种自动分析实时控制系统程序模式的方法。通过分析C语言源程序生成程序控制流图,对输入变量相关节点进行切片,形成依赖输入变量的控制流图(ICFG),建立ICFG每条路径的线性规划问题并求解,从而获得潜在的程序模式。在此基础上,计算指定模式下针对现代RISC处理器程序的WCET。在基准程序上的实验结果验证了该方法的可行性和有效性。

关键词: 程序模式, 最差情况执行时间分析, 实时控制系统, 控制流图, 线性规划

Abstract: Obtaining program modes of real-time control system from source codes cannot only verify the consistence of the design and implementation,but also improve the accuracy of Worst-Case Execution Time(WCET) calculation.Based on this consideration,this paper proposes an automatic analysis method for program mode of real-time control system.The Control Flow Graph(CFG) of program is generated by analyzing the C source codes,and by means of slicing input variables dependent nodes,an Input-dependent Control Flow Graph(ICFG) is formed.Linear programming problem is constructed and solved for each path of ICFG.If the problem has a solution,a potential program mode will be achieved.On this basis,the WCET of given mode for program in modern RISC processor is calculated.Experimental result for a benchmark program shows that the proposed method is feasible and effective.

Key words: program mode, Worst-Case Execution Time(WCET) analysis, real-time control system, Control Flow Graph(CFG), linear programming

中图分类号:

TP391

侯小静,姬孟洛,黄辰林,舒云星,阎奔. 实时控制系统程序模式的WCET自动分析方法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.08.010.

HOU Xiaojing,JI Mengluo,HUANG Chenlin,SHU Yunxing,YAN Ben. Automatic WECT Analysis Method of Program Mode for Real-time Control System[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.08.010.

http://www.ecice06.com/CN/Y2017/V43/I8/56

参考文献

参考文献［1］Nan Guan.Parametric Utilization Bounds［M］//Nan Guan.Techniques for Building Timing-Predictable Embedded Systems.Berlin,Germany:Springer,2016:129-155. ［2］O’Connor P,Neil D,Liu S C,et al.Realtime Classification and Sensor Fusion with a Spiking Deep Belief Network［J］.Frontiers in Neuroscience,2013,7. ［3］Reinhard W,Philipp L,Oleg P,et al.Improving the Precision of WCET Analysis by Input Constraints and Model-derived Flow Constraints［M］//Chakraborty S,Eberspcher J.Advances in Real-Time Systems.Berlin,Germany:Springer,2012:123-143. ［4］Lucas P,Parshin O,Wilhelm R.Operating Mode Specific WCET Analysis［C］//Proceedings of the 3rd Junior Researcher Workshop on Real-time Computing.Paris,France:［s.n.］,2009:15-18. (下转第68页) (上接第62页) ［5］Ji Mengluo,Wang Ji,Li Shuhao,et al.Automated Worst-Case Execution Time Analysis Based on Program Modes［J］.The Computer Journal,2009,52(5):530-544. ［6］Clément B,Julien F,Giuseppe L.Context-sensitive Parametric WCET Analysis［C］//Proceedings of the 15th International Workshop on Worst-Case Execution Time Analysis.Wadern,Germany:Dagstuhl,2015:55-64. ［7］Stefan B.Parametric WCET Analysis［D］.Vsters,Sweden:Mlardalen University,2013. ［8］单锦辉,齐治昌.面向路径的测试数据自动生成方法研究［J］.长沙:国防科学技术大学,2002. ［9］Flemming N,Hanne R,Chris H.Principles of Program Analysis［M］.Berlin,Germany:Springer,1999. ［10］姬孟洛.实时系统最差情况执行时间分析的研究［D］.长沙:国防科学技术大学,2006. ［11］Bernat G,Burns A.An Approach to Symbolic Worst-Case Execution Time Analysis［C］//Proceedings of the 25th IFAC Workshop on Real-time Programming.Oxford,UK:Pergamon Press,2000:71-76. ［12］Healy C A,Arnold R D,Mueller F,et al.Bounding Pipeline and Instruction Cache Performance［J］.IEEE Transactions on Computers,1999,48(1):53-70. ［13］Hennessy J L,Patterson D A.Computer Architecture:A Quantitative Approach［M］.2nd Edition.San Francisco,USA:Morgan Kaufmann,1996. ［14］姬孟洛,李军,王馨,等.一种基于抽象解释的WCET自动分析工具［J］.计算机工程,2006,32(14):54-56. ［15］Cousot P,Cousot R.Abstract Interpretation:A Unified 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. ［16］Harrison W H.Compiler Analysis of the Value Ranges for Variables［J］.IEEE Transactions on Software Engineering,1977,SE-3(3):243-250. ［17］Chapman R,Burns A,Wellings A.Integrated Program Proof and Worst-Case Timing Analysis of Spark Ada［C］//Pro-ceedings of ACM Workshop on Language,Compiler and Tool Support for Real-time Systems.New York,USA:ACM Press,1994:1-11. ［18］Stefan V,Sander S,Twan B,et al.Automatic Scenario Detection for Improved WCET Estimation［C］//Pro-ceedings of the 42nd ACM/IEEE Design Automation Conference.New York,USA:ACM Press,2005:101-104. ［19］Zwirchmayr J,Sotin P,Bonenfant A,et al.Identifying Relevant Parameters to Improve WCET Analysis［C］//Proceedings of the 14th International Workshop on Worst-Case Execution Time Analysis.Wadern,Germany:Dagstuhl,2014:93-102. 编辑金胡考

[1]	信文倩, 孙兵, 李超. LiCi算法的基于比特积分攻击[J]. 计算机工程, 2020, 46(7): 136-142.
[2]	朱国晖, 刘璐, 雷兰洁. 基于VNF组合的服务功能链设计及映射算法[J]. 计算机工程, 2020, 46(4): 183-188,197.
[3]	杨天, 田霖, 孙茜, 张宗帅, 王园园. 移动边缘计算中基于用户体验的计算卸载方案[J]. 计算机工程, 2020, 46(10): 33-40.
[4]	王丁玎, 丁煦, 赵冲, 石雷, 韩江洪. 带无线能量补充设备的无线传感器网络基站部署策略[J]. 计算机工程, 2020, 46(1): 164-171,178.
[5]	刘尧, 宋元斌, 李云祥. 融入逻辑关系的项目调度遗传算法[J]. 计算机工程, 2020, 46(1): 279-285.
[6]	苑乐天,李国峰. 基于业务优先级划分的虚拟网可靠性映射算法[J]. 计算机工程, 2019, 45(2): 76-81.
[7]	陈建,沈潇军,姚一杨,邢雅菲,琚小明. 基于表驱动的纯软件签名错误检测算法[J]. 计算机工程, 2018, 44(4): 187-192.
[8]	刘莹莹,邱崧,孙力,周梅,徐伟. 基于多视角自步学习的人体动作识别方法[J]. 计算机工程, 2018, 44(2): 257-263.
[9]	秦振华,牟永敏. 面向C程序的环形复杂度自动化计算方法[J]. 计算机工程, 2018, 44(12): 102-107,114.
[10]	耿海军,刘洁琦,张举. 基于不相交路径的域内路由保护方案[J]. 计算机工程, 2018, 44(12): 140-144,149.
[11]	孙贺,吴礼发,洪征,颜慧颖,张亚丰. 一种结合动态与静态分析的函数调用图提取方法[J]. 计算机工程, 2017, 43(3): 154-162.
[12]	刘珂. 基于线性规划的大规模网络故障恢复机制[J]. 计算机工程, 2016, 42(7): 104-108,116.
[13]	王磊,侯整风,向润昭,史兆鹏. 基于嵌套复杂度的控制流混淆算法[J]. 计算机工程, 2016, 42(11): 177-181,188.
[14]	李靖,乔蕊,刘志中. 结合对策论与多目标MILP的Web服务组合调度问题求解[J]. 计算机工程, 2016, 42(1): 11-17.
[15]	徐东,狄效国,孟宇龙,冯晓宁. 基于依赖图等价代换的SSDG构建算法[J]. 计算机工程, 2015, 41(12): 91-95,100.

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

选择包含的内容

实时控制系统程序模式的WCET自动分析方法

Automatic WECT Analysis Method of Program Mode for Real-time Control System

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

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

选择包含的内容

实时控制系统程序模式的WCET自动分析方法

Automatic WECT Analysis Method of Program Mode for Real-time Control System

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价