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

Abstract

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)

CLC Number:

TP311

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.

References

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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Survey of WCET Analysis and Prediction for Real-time Embedded Systems

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 8

Metrics

Comments

Recommended 0

[1]	YANG Lin, WANG Yong-jie, ZHANG Jun. FAWA:A Negative Feedback Dynamic Scheduling Algorithm for Heterogeneous Executor [J]. Computer Science, 2021, 48(8): 284-290.
[2]	DU Hong-guang, LEI Zhou and CHEN Sheng-bo. Data Block Density Scheduling Strategy Based on HDFS in Shared Cluster [J]. Computer Science, 2017, 44(Z11): 510-515.
[3]	GAN Zhi-hua,GU Zhi-min,AN Li-kui and ZHAO Xin. Research on Constraint Conflicts and Analysis of Shared Resources in CMP Based on WCET [J]. Computer Science, 2014, 41(8): 19-24.
[4]	SUN Tao and YE Xin-ming. Verification Method on CP-nets Concurrent Model [J]. Computer Science, 2014, 41(7): 135-139.
[5]	CHEN Li,ZHANG Li,YAO Yi-zhan and HU Wei-hua. Trojans Control Behavior Detection Approach Based on Timing Analysis [J]. Computer Science, 2013, 40(Z6): 337-339.
[6]	. Architecture of Remote Sensing Producing Line for Supporting Multi-task Parallel Proceeding [J]. Computer Science, 2012, 39(Z11): 181-184.
[7]	DONG Nan-nan, LU Yan,SONG Bao-yan. Adaptive Query Optimum Scheduling Strategy on Data Streams [J]. Computer Science, 2011, 38(5): 142-144.
[8]	WU Chun xue GUO Xian-hui （School of Computer and Electrical Engineering, Shanghai University of Science and Technology, Shanghai 200093,China）. [J]. Computer Science, 2009, 36(5): 56-59.