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

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

摘要/Abstract

摘要： 在实时软件系统中,软件时间性能的分析与评估技术是一个重要的课题,然而随着CPU的结构越来越复杂,采用传统的模拟底层硬件执行的方法越来越困难。而基于分布函数的最坏执行时间(Worst Case Execution Time,WCET)估计方法从概率角度出发,可以绕过复杂的底层硬件建模,估计程序的最坏执行时间。首先对TI TMS320C6713 DSP汇编代码进行基本块的划分,以基本块为结点构建程序流图；然后用贝塔分布模拟每条指令的运行时间并采用改进的计划评审技术(Program Evaluation and Review Technique,PERT)确定贝塔分布相关参数,指令叠加后用正态分布模拟每个基本块的执行时间；最后利用基于路径的方法得到整个程序的最坏执行时间。实验结果表明此方法是可行的和合理的。

关键词: WCET,DSP,PERT,实时软件

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

周国昌,郭宝龙,高翔,王健,闫允一. 基于分布函数的WCET快速估计[J]. 计算机科学, 2016, 43(5): 157-161. https://doi.org/10.11896/j.issn.1002-137X.2016.05.029

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. https://doi.org/10.11896/j.issn.1002-137X.2016.05.029

参考文献

[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