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.)
[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. |
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