Timing Anomalies as a Challenge for Precise Worst-Case Execution Time Analysis

Raimund Kirner, Albrecht Kadlec, and Peter Puschner

Vienna University of Technology, Vienna, Austria
 

Timing anomalies add to the complexity of WCET analysis and make it hard to apply divide-and-conquer strategies to simplify the WCET assessment [2]. So far, timing anomalies have been described as a problem that occurs when the WCET of a control-flow graph is computed from the WCETs of its subgraphs, i.e., from a series decomposition. As one of the research contributions within the project ``Compiler-Support for Timing Analysis'' (COSTA) we extend the state of the art by (i) showing that timing anomalies can as well occur in a paral lel decomposition of the WCET problem, i.e., when complexity is reduced by splitting the hardware state space and performing a separate WCET analysis for hardware components that work in parallel, (ii) proving that the potential occurrence of parallel timing anomalies makes the parallel decomposition technique unsafe (i.e., one cannot guarantee that the calculated WCET bound does not underestimate the WCET), and (iii) identifying special cases of parallel timing anomalies for which the parallel decomposition technique is safe. The latter provides an important hint to hardware designers on their way to constructing predictable hardware components [1].

(The research leading to these results has received funding from the Austrian Science Fund (Fonds zur Förderung der wissenschaftlichen Forschung) within the research project "Sustaining Entire Code-Coverage on Code Optimization" (SECCO) under contract P20944-N13 and by the Austrian Science Fund (Fonds zur Förderung der wissenschaftlichen Forschung) within the research project "Compiler-Support for Timing Analysis" (CoSTA) under contract P18925-N13.)  

References:

[1]     Raimund Kirner, Albrecht Kadlec, and Peter Puschner. Precise worst-case execution time analysis for processors with timing anomalies. In Proc. 21st Euromicro Conference on Real-Time Systems, Dublin, Ireland, July 2009. IEEE. To appear.
[2]     Raimund Kirner and Peter Puschner. Obstacles in worst-cases execution time analysis. In Proc. 11th IEEE International Symposium on Object-oriented Real-time distributed Computing, pages 333-339, Orlando, Florida, May 2008.
 

Biography:

Univ. Assistent Dr. Raimund Kirner received his Master's degree and his PhD degree at the Vienna University of Technology (TU Vienna) in 2000 respectively 2003. During this time he has been working as a research and teaching assistant at the Institut für Technische Informatik at TU Vienna. The main focus of Kirner's research is worst-case execution time analysis of real-time programs, including compiler support and design methodologies to make systems predictable. He has published several papers on WCET analysis and was involved in two projects funded by the European Commission (SETTA, NEXT TTA). From 2003-2005 Raimund Kirner has worked on the FIT-IT project MoDECS, and from 2005-2007 he worked on the FIT-IT project TeDES, both funded by the Federal Ministry of Transport, Innovation, and Technology (BMVIT). Currently, Raimund Kirner is principal investigator of the following projects: "Compiler-Support for Timing Analysis" (COSTA), "Formal Timing Analysis Suite" (FORTAS), and "Sustaining Entire Code-Coverage on Code Optimization" (SECCO). He is a member of the IEEE Computer Society, the ACM, and the Austrian Computer Society (OCG).

Albrecht Kadlec holds a MSc Degree in automation and compilers from TU Vienna. He has been working for seven years in the embedded compiler industry. In 2007 he left Mentor Graphics to join the CoSTA (Compiler Support for Timing Analysis) team as a PhD research assistant.

Peter Puschner is a professor in computer science at Vienna University of Technology. His main research interest is on hard real-time systems for safety-critical applications, with a focus on the worst-case execution time (WCET) analysis of real-time programs and software/hardware architectures for time-predictable computing. He has published more than 80 refereed conference and journal papers and was a guest editor for the special issue on WCET analysis of the Kluwer (now Springer) International Journal on Real-Time Systems in 2000. P. Puschner chaired the PC of ISORC 2003 and ECRST 2004 and was the general chair of the Euromicro Conference on Real-Time Systems 2002 and ISORC 2004. He is in charge of the steering committees of the workshop series on worst-case execution-time analysis (WCET) and the International Workshop on Software Technologies for Future Embedded and Ubiquitous Computing Systems (SEUS). P. Puschner is a member of the IEEE Computer Society, IFIP working group 10.2 on Embedded Systems, Euromicro, the OCG (Austrian Computer Society), and the Marie-Curie Fellowship Association.

Contact Raimund, Albrecht, and Peter at:

Dr. Raimund Kirner
Institute of Computer Engineering
Vienna University of Technology
A-1040 Vienna, Austria
raimund at vmars.tuwien.ac.at
https://ti.tuwien.ac.at/rts/people/kirner/view

Dipl.-Ing. Albrecht Kadlec
Institute of Computer Engineering
Vienna University of Technology
A-1040 Vienna, Austria
albrecht at vmars.tuwien.ac.at
https://ti.tuwien.ac.at/rts

Prof. Peter Puschner
Institute of Computer Engineering
Vienna University of Technology
A-1040 Vienna, Austria
peter at vmars.tuwien.ac.at
https://ti.tuwien.ac.at/rts