Ernst Althaus
Sebastian Altmeyer
ABSTRACT
Hard real-time systems require tasks to finish in time. To guarantee the timeliness of such a system, static timing analyses derive upper bounds on the worst-case execution time (WCET) of tasks. There are two types of timing analyses: numeric and parametric. A numeric analysis derives a numeric timing bound and, to this end, assumes all information such as loop bounds to be given a priori. If these bounds are unknown during analysis time, a parametric analysis can compute a timing formula parametric in these variables. A performance bottleneck of timing analyses, numeric and especially parametric, is the so-called path analysis, which determines the path in the analyzed task with the longest execution time bound.
In this paper, we present a new approach to path analysis. This approach exploits the often rather regular structure of software for hard real-time and safety-critical systems. As we show in the evaluation of this paper, we strongly improve upon former techniques in terms of precision and runtime in the parametric case. Even in the numeric case, the approach competes with state-of-the-art techniques and may be an alternative to commercial tools employed for path analysis.
- E. Althaus, S. Altmeyer, and R. Naujoks. A new combinatorial approach to parametric path analysis. Reports of SFB/TR 14 AVACS 58, SFB/TR 14 AVACS, to appear.Google Scholar
- S. Altmeyer, C. Hüumbert, B. Lisper, and R. Wilhelm. Parametric timing analyis for complex architectures. In Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'08), pages 367--376. IEEE Computer Society, August 2008. Google ScholarDigital Library
- G. Bernat and A. Burns. An approach to symbolic worst-case execution time analysis. In 25th IFAC Workshop on Real-Time Programming. Palma (Spain)., May 2000.Google ScholarCross Ref
- S. Bygde, A. Ermedahl, and B. Lisper. An efficient algorithm for parametric wcet calculation. In Proceedings of the 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'09), pages 13--21. IEEE Computer Society, August 2009. Google ScholarDigital Library
- R. Chapman, A. Burns, and A.Wellings. Combining static worst-case timing analysis and program proof. Real-Time Syst., 11(2):145--171, 1996. Google ScholarDigital Library
- J. Coffman, C. A. Healy, F. Mueller, and D. B. Whalley. Generalizing parametric timing analysis. In Proceedings of the 7th ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems (LCTES '07), pages 152--154, 2007. Google ScholarDigital Library
- G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963.Google ScholarDigital Library
- P. Feautrier. The parametric integer programming's home http: \www.piplib.org.Google Scholar
- R. E. Gomory. An algorithm for integer solutions to linear programming. In R. L. Graves and P.Wolfe, editors, Recent Advances in Mathematical Programming, pages 269--302, New York, 1969. McGraw- Hill.Google Scholar
- R. Heckmann and C. Ferdinand. Worst-case execution time prediction by static program analysis. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04), pages 26--30. IEEE Computer Society, 2004.Google Scholar
- Y.-T. S. Li and S. Malik. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the 32nd annual ACM/IEEE Design Automation Conference (DAC '95), pages 456-- 461. ACM, 1995. Google ScholarDigital Library
- B. Lisper. Fully automatic, parametric worst-case execution time analysis. In Proceedings of the Third Internation Workshop on Worst- Case Execution Time Analysis (WCET 03), pages 77--80, July 2003.Google Scholar
- P. Puschner and C. Koza. Calculating the maximum, execution time of real-time programs. Real-Time Syst., 1(2):159--176, 1989. Google ScholarDigital Library
- H. Theiling. ILP-based Interprocedural Path Analysis. In Proceedings of the Workshop on Embedded Software, Grenoble, France, October 2002. Google ScholarDigital Library
- E. Vivancos, C. Healy, F. Mueller, and D. Whalley. Parametric timing analysis. In Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems (LCTES '01), pages 88--93. ACM Press, 2001 Google ScholarDigital Library
Index Terms
- Precise and efficient parametric path analysis
Recommendations
Precise and efficient parametric path analysis
LCTES '10Hard real-time systems require tasks to finish in time. To guarantee the timeliness of such a system, static timing analyses derive upper bounds on the worst-case execution time (WCET) of tasks. There are two types of timing analyses: numeric and ...
Generalizing parametric timing analysis
Proceedings of the 2007 LCTES conferenceIn the design of real-time and embedded systems, it is important to establish a bound on the worst-case execution time (WCET) of programs to assure via schedulability analysis that deadlines are not missed. Static WCET analysis is performed by a timing ...
Generalizing parametric timing analysis
LCTES '07: Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systemsIn the design of real-time and embedded systems, it is important to establish a bound on the worst-case execution time (WCET) of programs to assure via schedulability analysis that deadlines are not missed. Static WCET analysis is performed by a timing ...
Comments