基于分布函数的WCET快速估计

doi:10.11896/j.issn.1002-137X.2016.05.029

Abstract

Abstract: In the real-time software systems,the software-time performance analysis and evaluation techniques are important.But with the structure of CPU being more and more complex,traditional methods based on underlying hardware simulations are becoming increasingly difficult.Based on distribution function,the worst-case execution time(WCET) estimation method that is from a probabilistic perspective,can bypass the complex underlying hardware modeling and estimate the worst-case execution time.This article first divided TI TMS320C6713 DSP assembly code into basic blocks to build the program flow diagram.Then the run time of each instruction was simulated based on beta distribution whose parameters are determined according to the improved program evaluation and review technique(PERT).The instruction execution time was superimposed based on normal distribution to simulate the run time of each basic block.Finally, the worst execution time of the whole program was gotten by using a path based approach.Experimental results show that this method is feasible and reasonable.

Key words: WCET,DSP,PERT,Real-time software

ZHOU Guo-chang, GUO Bao-long, GAO Xiang, WANG Jian and YAN Yun-yi. Fast Estimation of WCET Based on Distribution Function[J].Computer Science, 2016, 43(5): 157-161.

References

[1] Puschner P,Burns A.A review of worst-case execution time analysis[J].Real-Time Systems,2000,18(2/3):115-128
[2] Wilhelm R,Engblom J,Ermedahl A,et al.The worst-case execution-time problem-overview of methods and survey of tools[J].ACM Transactions on Embedded Computing Systems,2008,7(3):1-53
[3] Lv M,Guan N,Zhang Y,et al.A Survey of WCET Analysis of Real-Time Operating Systems[C]∥Proceedings of the 2009 International Conference on Embedded Software and Systems.2009:65-72
[4] Metzlaff S,Ungerer T.Impact of Instruction Cache and Diffe-rent Instruction Scratchpads on the WCET Estimate[C]∥2011 IEEE 14th International Conference on High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems(HPCC-ICESS).2012:1442-1449
[5] Ni F,Long X,Wan H,et al.Using Basic Block Based Instruction Prefetching to Optimize WCET Analysis for Real-Time Applications[C]∥Proceedings of the 2012 13th International Confe-rence on Parallel and Distributed Computing,Applications and Technologies.2012:459-466
[6] Yoo J,Lee J,Hong S.Petri Net-Based FTL Architecture forParametric WCET Estimation via FTL Operation Sequence Deri-vation[J].IEEE Transactions on Computers,2013,62(11):2238-2251
[7] Puschner P,Prokesch D,Huber B,et al.The T-CREST ap-proach of compiler and WCET-analysis integration[C]∥2013 IEEE 16th International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing(ISORC).2013:1-8
[8] Ji Meng-luo,Qi Zhi-chang.An Overview of Worst Case Execution Time(WCET) Analysis[J].Computer Science,2006,33(10):238-241(in Chinese) 姬孟洛,齐治昌.实时系统程序最差情况执行时间(WCET)的分析[J].计算机科学,2006,33(10):238-241
[9] Zhang Bao-min,Wu Guo-wei,Yao Lin.Program worst-case execution time extreme value statistics estimation method[J].Computer Engineering and Applications,2010,46(26):67-71(in Chinese) 张保民,吴国伟,姚琳.程序最坏执行时间极值统计方法 [J].计算机工程与应用,2010,46(26):67-71
[10] Marref A,Betts A.Accurate Measurement-Based WCET Analysis in the Absence of Source and Binary Code[C]∥Proceedings of the 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing.2011:127-135
[11] Hu Ming-hua,Tang Ming-duan.Worst case execution time estimation based on distribution function[J].Computer Engineering and Design,2006,27(16):3045-3047(in Chinese) 胡明华,汤铭端.基于分布函数的程序执行时间的静态预估 [J].计算机工程与设计,2006,27(16):3045-3047
[12] Lisper B,Santos M.Model Identification for WCET Analysis[C]∥Proceedings of the 2009 15th IEEE Symposium on Real-Time and Embedded Technology and Applications.2009:55-64
[13] Bygde S,Ermedahl A,Lisper B.An Efficient Algorithm for Pa-rametric WCET Calculation[C]∥Proceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.2009:13-21
[14] Leveque T,Borde E,Marref A,et al.Hierarchical Composition of Parametric WCET in a Component Based Approach[C]∥Proceedings of the 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Com-puting.2011:261-268
[15] Lv Ming-song,Guan Nan,Wang Yi.Survey of Cache Analysis for Worst-Case Execution Time Estimation[J].Journal of Software,2014,25(2):179-199(in Chinese) 吕鸣松,关楠,王义.面向WCET估计的Cache分析研究综述 [J].软件学报,2014,25(2):179-199
[16] Wu Guo-wei,Li Zhang.Precise program worst-case executiontime analysis method[J].Computer Engineering and Applications,2010,46(18):60-64(in Chinese) 吴国伟,李张.一种精确程序最坏执行时间分析方法[J].计算机工程与应用,2010,46(18):60-64
[17] Bernat G,Colin A,Petters S.pWCET:a Tool for ProbabilisticWorst-Case Execution Time Analysis of Real-Time Systems:YCS-2003-353[R].England,UK:University of York,2003
[18] Petters SM.How much worst case is needed in wcet estimation[C]∥International Workshop on Worst Case Execution Time Analysis.2002
[19] http://wiki.mbalib.com/wiki/PERT
[20] Aho V A,Sethi R,Ullman J D.编译原理[M].北京:机械工业出版社,2008
[21] T.I.TMS320C6000 CPU and instruction set reference guide[Z].2000
[22] Wu Su,Luo Yan-sheng.Application of a New Module of PERT in Project Management[J].Construction Technology,2007,36(12):50-53(in Chinese) 吴苏,罗延生.一种新PERT模型在项目管理中的应用[J].施工技术,2007,36(12):50-53

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Fast Estimation of WCET Based on Distribution Function

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 0

Metrics

Comments

Recommended 0