实时嵌入式系统的WCET分析与预测研究综述

摘要/Abstract

摘要： 在实时嵌入式系统设计中,为了保证系统的安全运行,需要验证系统是否满足时限,即任务必须在截止期之前完成,否则实时系统将失败。目前衡量实时嵌入式系统实时性的重要指标是任务的最坏情况执行时间(Worst Case Execution Time,WCET)。文章首先综述了WCET分析以及研究WCET分析的主要方法。分析了在当前多核平台上、复杂处理器架构下WCET分析存在的主要问题,并根据当前WCET分析存在的问题展开讨论,分别针对时序分析、微系统结构分析和多核多任务调度策略等方面分析了国内外的研究进展。最后提出了一种基于深度学习的自适应实时DVFS算法,该算法可以进行动态电压和频率调节(DVFS),以达到节能的目的;同时还能够动态修正程序的WCET值,为未来嵌入式系统中的WCET分析与预测提供指导方法。

关键词: 调度策略, 动态电压和频率调节, 模型检验, 时序分析, 最坏情况执行时间

Abstract: For the safe operation of real-time embedded system,verifying whether the system meet the duration limitation is necessary.That means the task must be completed before the deadline,otherwise the real-time system will fail.At present,the worst-case execution time (WCET) is one of the important indicators to measure the real-time embedded system.This paper firstly introduces WCET analysis itself and main methods for this analysis.Secondly,the main problems of WCET analysis under complex processor architecture on current multi-core platforms are investigated.Thirdly,the research progress in WCET analysis is discussed for timing analysis,micro-system structure analysis and multi-core and multi-task scheduling strategy based on the current problems.Finally,adaptive real-time DVFS algorithm based on deep learning is proposed,which can perform dynamic voltage and frequency adjustment (DVFS),achieve the target for energy saving,and dynamically correct the WCET value of the program to provide guidance for the analysis and prediction of WCET in future embedded systems.

Key words: Dynamic voltage and frequency scaling (DVFS), Model verification, Scheduling strategy, Timing analysis, Worst case execution time (WCET)

中图分类号:

TP311

王颖洁, 周宽久, 李明楚. 实时嵌入式系统的WCET分析与预测研究综述[J]. 计算机科学, 2019, 46(6A): 16-22. https://doi.org/

WANG Ying-jie, ZHOU Kuan-jiu, LI Ming-chu. Survey of WCET Analysis and Prediction for Real-time Embedded Systems[J]. Computer Science, 2019, 46(6A): 16-22. https://doi.org/

参考文献

[1]吕鸣松,关楠,王义.面向WCET估计的Cache分析研究综述[J].软件学报,2014,25(2):179-199.
[2]姬孟洛.实时系统最差情况执行时间分析的研究[D].长沙:国防科学技术大学,2006.
[3]吕鸣松.实时系统最坏情况执行时间分析技术的研究[D].沈阳:东北大学,2010.
[4]王海瑞.基于极值统计的实时软件WCET估计研究[D].大连:大连理工大学,2007.
[5]江华.实时程序WCET分析模型与算法[D].武汉:华中科技大学,2008.
[6]陈芳园.基于多核处理器平台的实时系统WCET分析研究[D].长沙:国防科学技术大学,2011.
[7]WILHELM R,GRUND D.How Much Time Does It Take to Calculate? [J].ACM通信,2014,57(2):94-103.
[8]姬孟洛,李书浩,秦杰,等.WCET分析中面向对象程序多态性问题的解决方法[J].计算机科学,2006,33(11):249-255.
[9]张曦.基于WCET分析技术的程序实时性模型检验方法研究[D].长沙:国防科学技术大学,2011.
[10]WU L,ZHANG W.Bounding Worst-Case Execution Time for Multicore Processors through Model Checking[C]∥Proc.16th IEEE Real-Time and Embedded Technology and Applications Symposium(RTAS’10).Work-in-Progress Session,2010:17-20.
[11]VALERO.Hardware support for WCET analysis of hard real-time multicore systems[C]∥Proc.36th International Sympo-sium on Computer Architecture(ISCA 2009).2009:57-68.
[12]王馨,姬孟洛,王戟,等.基于WCET分析的实时系统轨迹获取技术[J].软件学报,2006,17(5):1232-1240.
[13]LESAGE B,GRIFFIN D,ALTMEYER S,et al.On the analysis of random replacement caches using static probabilistic timing methods for multi-path programs[J].Real-Time Systems,2017(2):1-82.
[14]CHATTOPADHYAY S,ROYCHOUDHURY A,MITRA T. Modeling shared cache and bus in multi-cores for timing analysis[C]∥International Workshop on Software & Compilers for Embedded Systems.ACM,2010.
[15]DAVIS R I,ALTMEYER S,INDRUSIAK L S,et al.An extensible framework for multicore response time analysis[J].Real-Time Systems,2017(5):1-55.
[16]姬孟洛,齐治昌,王怀民.包含依赖输入分支程序的符号化WCET分析[J].软件学报,2006,17(3):628-637.
[17]BALLABRIGA C,FORGET J,LIPARI G.Symbolic WCET Computation[J].ACM Transactions on Embedded Computing Systems(TECS),2017,17(2):1-26.
[18]陈芳园,丁亚军,张冬松,等.面向WCET分析的实时多核体系结构研究[J].计算机工程与科学,2014,36(3):393-398.
[19]PAOLIERI M,CAZORLA F J,BERNAT G,et al.Hardware support for WCET analysis of hard real-time multicore systems[C]∥International Symposium on Computer Architecture.ACM,2009:57-68.
[20]甘志华,古志民,安立奎,等.基于WCET的多核共享资源冲突分析与约束研究[J].计算机科学,2014,41(8):19-24.
[21]陈芳园,张冬松,王志英.多核实时线程间干扰分析及WCET估值[J].电子学报,2012,40(7):1372-1378.
[22]LIU T,XUE C J.Instruction cache locking for multi-task real-time embedded systems[J].Real-Time Systems,2012,48(2):166-197.
[23]张吉赞,古志民.多核共享缓存bank冲突分析及其延迟最小化[J].计算机学报,2016,39(9):1883-1899.
[24]NAGAR K,SRIKANT Y N.Refining Cache Behavior Prediction Using Cache Miss Paths[J].Acm Transactions on Embedded Computing Systems,2017,16(4):1-26.
[25]杨志斌,赵永望,黄志球,等.同步语言的时间可预测多线程代码生成方法[J].软件学报,2016,27(3):611-632.
[26]安立奎,古志民,付引霞,等.支持软件预取的缓存WCET分析[J].北京理工大学学报,2015,35(7):730-736.
[27]王恩东,倪璠,陈继承,等.一种面向实时系统的程序基本块指令预取技术[J].软件学报,2016,27(9):2426-2442.
[28]PUFFITSCH W.Persistence-based branch misprediction bounds for WCET analysis[C]∥ACM Symposium on Applied Computing.ACM,2015:1898-1905.
[29]CARMINATI A,STARKE R A,OLIVEIRA R S D.On the use of static branch prediction to reduce the worst-case execution time of real-time applications[J].Real-Time Systems,2018:1-25.
[30]MANGEAN A,BÉCHENNEC J L,BRIDAY M,et al.WCET Analysis by Model Checking for a Processor with Dynamic Branch Prediction[M]∥Verification and Evaluation of Compu-ter and Communication Systems.2017:64-78.
[31]SU X,WU H,YANG Q.An Efficient WCET-Aware Hybrid Global Branch Prediction Approach[C]∥IEEE,International Conference on Embedded and Real-Time Computing Systems and Applications.IEEE,2016:195-201.
[32]张冬松.多核多处理器系统的节能实时调度技术研究[D].长沙:国防科学技术大学,2012.
[33]姚鑫骅.数控实时系统调度理论及应用研究[D].杭州:浙江大学,2006.
[34]王磊,刘道福,陈云霁,等.片上多核处理器共享资源分配与调度策略研究综述[J].计算机研究与发展,2013,50(10):2212-2227.
[35]刘轶,张昕,李鹤,等.一种面向多核处理器并行系统的启发式任务分配算法[J].计算机研究与发展,2009,46(6):1058-1064.
[36]耿晓中.基于多核分布式环境下的任务调度关键技术研究[D].长春:吉林大学,2013.
[37]赵林祥.基于多核处理器任务复制的分簇调度算法研究[D].长沙:湖南大学,2012.
[38]LIU Y,ZHANG X,LI H,et al.Allocating Tasks in Multi-core Processor based Parallel Systems[C]∥2007 IFIP International Conference on Network and Parallel Computing Workshops(NPC2007),2007.
[39]LEE L T,CHANG H Y,CHAO S W.A Hybrid Task Scheduling for Multi-Core Platform[C]∥2008 Second International Conference on Future Generation Communication and Networking Symposia.2008:40-45.
[40]HATANAKA K,BAGHERZADEH N.Scheduling Techniques for Multi-Core Architectures[C]∥2009 Sixth International Conference on Information Technology:New Generations.2009:865-870.
[41]冯华,卢凯,王小平.面向多核处理器的实时优化技术:基于独立实时域的实时优化方法[J].计算机科学,2013,40(9):159-162.
[42]张忆文,郭锐锋,刘娴,等.基于平均空闲时间分配的低功耗调度算法[J].小型微型计算机系统,2015,36(8):1907-1910.
[43]郭锐锋,吴昊天,邓昌义,等.一种WCET比例空闲时间分配的周期任务低功耗算法[J].小型微型计算机系统,2017,38(8):1856-1860.
[44]黄丽达,李龙,李仁发,等.混合关键级多任务调度中低关键级任务的积极处理[J].计算机工程与科学,2014,36(1):6-11.
[45]刘樑骄,谢国琪,李仁发,等.通信竞争的混合关键级系统多DAG动态调度策略[J].计算机研究与发展,2015,52(11):2608-2621.
[46]黄丽达,李仁发.事件触发关键级提升的实时任务可调度性分析[J].计算机研究与发展,2017,54(1):184-191.
[47]赵庆玲.混合关键度CPS系统中的资源共享协议和设计优化[D].杭州:浙江大学,2015.
[48]黄丽达.混合关键级调度的若干关键问题研究[D].长沙:湖南大学,2016.
[49]PILLAI P,SHIN K G.Real-time dynamic voltage scaling for low-power embedded operating systems[J].Acm Sigops Opera-ting Systems Review,2001,35(5):89-102.
[50]NAIK B V,DAS S,KAPOOR H K.RT-DVS for Power Optimization in Multiprocessor Real-Time Systems[C]∥International Conference on Information Technology.IEEE,2015:24-29.
[51]WANG W,RANKA S,MISHRA P.Energy-aware dynamic slack allocation for real-time multitasking systems[J].Sustainable Computing Informatics & Systems,2012,2(3):128-137.

相关文章 15

[1]	杨林, 王永杰, 张俊. FAWA:一种异构执行体的负反馈动态调度算法 FAWA:A Negative Feedback Dynamic Scheduling Algorithm for Heterogeneous Executor 计算机科学, 2021, 48(8): 284-290. https://doi.org/10.11896/jsjkx.200900059
[2]	李运筹,尹平. 模型检验在航天测控软件上的应用研究 Research of Model Checking Application on Aerospace TT&C Software 计算机科学, 2018, 45(6A): 523-526.
[3]	杜红光,雷州,陈圣波. 共享集群基于HDFS的数据块密度调度策略 Data Block Density Scheduling Strategy Based on HDFS in Shared Cluster 计算机科学, 2017, 44(Z11): 510-515. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.108
[4]	刘斌斌,刘万伟,毛晓光,董威. 无人驾驶汽车决策系统的规则正确性验证 Correctness Verification of Rules for Unmanned Vehicles’ Decision System 计算机科学, 2017, 44(4): 72-74. https://doi.org/10.11896/j.issn.1002-137X.2017.04.015
[5]	朱振宇,张仕,蒋建民,吴亚洲,杨启帆. 并发系统中基于优先级的调度分析 Analyzing Scheduling Based on Priority in Concurrent Systems 计算机科学, 2016, 43(Z11): 523-528. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.118
[6]	张岩庆,陆余良,杨国正. 基于时序距离的AS级Internet动态性测量方法 Measurement of AS-level Internet Evolution Based on Temporal Distance 计算机科学, 2016, 43(8): 118-122. https://doi.org/10.11896/j.issn.1002-137X.2016.08.025
[7]	陈光颖,黄志球,陈哲,阚双龙. 面向DO-333的襟缝翼控制单元安全性分析 Safety Analysis of Slat and Flap Control Unit for DO-333 计算机科学, 2016, 43(5): 150-156. https://doi.org/10.11896/j.issn.1002-137X.2016.05.028
[8]	朱利鲁,李智. 问题框架中问题领域因果行为的形式化验证 Formal Validation of Causal Behaviors of Problem Domains in Problem Frames Approach 计算机科学, 2015, 42(12): 136-142.
[9]	开金宇,缪淮扣,高洪皓. Web服务计算组合流程QoS验证 Verification QoS of Web Services Compositional Processes 计算机科学, 2015, 42(12): 120-123.
[10]	王飞,沈国华,黄志球,马琳,刘畅,李海峰,廖莉莉. 一种结合线性时序逻辑和故障树的软件安全验证方法 Method Combining Linear Temporal Logic and Fault Tree for Software Safety Verification 计算机科学, 2015, 42(12): 71-75.
[11]	王蓁蓁. 模型检验综述 Survey of Model Checking 计算机科学, 2013, 40(Z6): 1-14.
[12]	陈利,张利,姚轶崭,胡卫华. 基于时序分析的木马控制行为识别方法 Trojans Control Behavior Detection Approach Based on Timing Analysis 计算机科学, 2013, 40(Z6): 337-339.
[13]	张媛，于冠龙，李仁见. 一种基于模型检验的缓冲区溢出检测方法 Buffer Overflow Detection Method Based on Model Checking 计算机科学, 2012, 39(Z6): 31-34.
[14]	郑逢斌，张哲，余涛，赖积保，徐辉，张谦. 一种支持多任务高效处理的遥感产品生产线架构研究 Architecture of Remote Sensing Producing Line for Supporting Multi-task Parallel Proceeding 计算机科学, 2012, 39(Z11): 181-184.
[15]	李晋文,胡军,曹跃胜史林森肖立权. DDR3时序分析与设计 Timing Analysis and Design for DDR3 System 计算机科学, 2012, 39(4): 293-295.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed