Timing anomalies in dynamically scheduled microprocessors

Previous timing analysis methods have assumed that the worst-case instruction execution time necessarily cor-responds 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. We first provide necessary conditions when timing anomalies can show up and identify what architectural fea-tures that may cause such anomalies. We also show that an-alyzing the effect of these anomalies with known techniques results in prohibitive computational complexities. Instead, we propose some simple code modification techniques to make it impossible for any anomalies to occur. These modi-fications make it possible to estimate WCET by known tech-niques. 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. 1