Timing Anomalies in Dynamically Scheduled Microprocessors

Abstract

Safe and tight estimations of the worst-case execution time (WCET) of programs run on processors employing pipelining and caching is important when constructing high-performance real-time systems. Previous timing analysis methods have assumed that the worst-case instruction execution time necessarily corresponds to the worst-case behavior. We show that this assumption is wrong in dynamically scheduled processors. A cache miss, for example, can in some cases result in a shorter execution time than a cache hit. Many examples of such timing anomalies are provided.

A first contribution of this paper is to provide necessary conditions for when timing anomalies may show up and identification of what architectural features that may cause such anomalies. We also show that analyzing the effect of these anomalies with known techniques would result in prohibitive computational complexities. Instead we propose some simple code modification techniques to make it impossible for any anomalies to occur. These modifications make it possible to estimate WCET by known techniques. We use an existing WCET analyzer to evaluate how much pessimism the code transformations impose on some benchmarks. Our evaluation shows that the pessimism imposed by these techniques is fairly limited; it is less than 27 % for the programs in our benchmark suite.

This is a preliminary version of the conference paper with the same name.

A copy can also be found in my licentiate thesis.