PLEA: Parametric loop bound estimation in WCET analysis

Worst-case execution time (WCET) analysis of a program is important to verify the temporal correctness of real-time systems. Parametric WCET analysis represents the WCET of the program as a formula, where the unknown values affecting the WCET are parameterized. Many issues usually affect the WCET of a program, including the loop bound. In parametric timing analysis, instead of determining a constant upper bound for a loop, a symbolic formula represents the loop bound. In this paper, a new method is presented for the parametric loop bound analysis based on path analysis. Instead of considering the basic bocks on their own and independent of the rest, the execution paths within the loop body have to be analyzed. There are certain situations in which the execution of certain statements of an execution path affects the number of executions of all the basic blocks along the execution path. Therefore, more accurate estimation of the number of loop iterations is provided. The results of analysis on the M¨alardalen benchmark suite reveal the accuracy of the proposed method.

PDF

___

[1] Vivancos E, Healy C, Mueller F, Whalley D. Parametric timing analysis. In: Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems; 2001; Snowbird, UT, USA. pp. 88-93.
[2] Bygde S, Ermedahl A, Lisper B. An efficient algorithm for parametric WCET calculation. J Syst Architect 2011; 57: 614-624.
[3] Marref A. Evolutionary techniques for parametric WCET analysis. In: 12th International Workshop on Worst-Case Execution Time Analysis; 2012; Pisa, Italy. pp. 103-115.
[4] Huber B, Prokesch D, Puschner PP. A formal framework for precise parametric WCET formulas. In: 12th International Workshop on Worst-Case Execution Time Analysis; 2012; Pisa, Italy. pp. 91-102.
[5] Bernat G, Burns A. An approach to symbolic worst-case execution time analysis. In: Proceedings of the 25th Workshop on Real-Time Programming; 2000; Palma, Spain.
[6] Coffman J, Healy C, Mueller F, Whalley D. Generalizing parametric timing analysis. In: Proceedings of the 2007 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools; 2007; New York, NY, USA. pp. 152-154.
[7] Altmeyer S, H¨umbert C, Lisper B, Wilhelm R. Parametric timing analysis for complex architectures. In: Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications; 2008; Kaohsiung, Taiwan. pp. 367-376.
[8] Lisper B. Fully automatic, parametric worst-case execution time analysis. In: Proceedings of the 3rd International Workshop on Worst-Case Execution Time Analysis; 2003; Porto, Portugal. pp. 77-80.
[9] Li YTS, Malik S. Performance analysis of embedded software using implicit path enumeration. In: Proceedings of the 32nd Design Automation Conference; 1995. pp. 456-461.
[10] Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley D, Bernat G, Ferdinand C, Heckmann R, Mitra T et al. The worst-case execution time problem overview of methods and survey of tools. ACM T Embedded Comput Syst 2008; 7: 1-53.
[11] Verdoolaege S, Seghir R, Beyls K, Loechner V, Bruynooghe M. Counting integer points in parametric polytopes using Barvinoks rational functions. Algorithmica 2007; 48: 37-66.
[12] Feautrier P. Parametric integer programming. RAIRO Recherche Op´erationnelle 1998; 22: 243-268.
[13] Parsa S, Sakhaei-nia M. Modeling flow information of loops using compositional condition of controls. The journal of supercomputing. 2015; Feb 1; 71(2): 506-36.
[14] Bayardo RJ, Pehoushek JD. Counting models using connected components. In: 17th International Conference on Artificial Intelligence; 2000. pp. 157-162.
[15] Clauss P, Loechner V. Parametric analysis of polyhedral iteration spaces. J VLSI Signal Process 1998; 19: 179-194.
[16] Loechner V, Meister B, Clauss P. Precise data locality optimization of nested loops. J Supercomput 2002; 21: 37-76.
[17] Beyls K, DHollander E. Generating cache hints for improved program efficiency. J Syst Architect 2005; 51: 223-250.
[18] van Engelen RA, Gallivan KA, Walsh B. Parametric timing estimation with Newton-Gregory formulae. Concur Comp-Pract E 2006; 18: 1435-1463.
[19] Engblom J. Static properties of commercial embedded real-time programs, and their implication for worst-case execution time analysis. In: Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium; 1999; Vancouver, Canada. pp. 46-55.
[20] Gustafsson J, Betts A, Ermedahl A, Lisper B. The M¨alardalen WCET benchmarks past, present and future. In: Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis; 2010; Brussels, Belgium. pp. 137-147.
[21] Lisper B. Fully Automatic, Parametric Worst-Case Execution Time Analysis. MRTC Report. V¨aster˚as, Sweden: M¨alardalen Real-Time Research Centre of M¨alardalen University, 2003.
[22] Chen T, Mitra T, Roychoudhury A, Suhendra V. Exploiting branch constraints without exhaustive path enumeration. In: 5th International Workshop on Worst-Case Execution Time Analysis; 2005.