Avoiding Timing Anomalies using Prefetch Window Padding

Albrecht Kadlec

Vienna University of Technology, Vienna, Austria

So called timing anomalies are phenomena in processors where changes of the local worst-case execution time (WCET) do not correspond to changes of the global WCET. Timing anomalies are problematic for timing analysis, since they make it challenging to use abstract hardware models that still lead to safe and tight WCET bounds. In this paper, we refine and categorize the conditions for timing anomalies, distinguishing between triggers and amplifiers, which communicate via processor state only. We use that distinction to present the theoretical approaches for countermeasures against timing anomalies. Then we establish a sufficient condition to avoid timing anomalies from pipeline scheduling decisions. Based on this condition, we modify a standard postpass instruction scheduler to avoid the accumulation of timing effects. This modified scheduler is evaluated for several experimental out-of-order architectures using the Mälardalen WCET benchmark suite. The results are promising.  


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.

Contact Albrecht at:

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