Accurate timing analysis by modeling caches, speculation and their interaction

Schedulability analysis of real-time embedded systems re-quires worst case timing guarantees of embedded software performance. This involves not only language level program analysis, but also modeling the effects of complex micro-architectural features in modern processors. Speculative ex-ecution and caching are very common in current processors. Hence one needs to model the effects of these features on the Worst Case Execution Time (WCET) of a program. Even though the individual effects of these features have been studied recently, their combined effects have not been inves-tigated. We do so in this paper. This is a non-trivial task be-cause speculative execution can indirectly affect cache per-formance (e.g., speculatively executed blocks can cause ad-ditional cache misses). Our technique starts from the con-trol flow graph of the embedded program, and uses integer linear programming to estimate the program’s WCET. The accuracy of our modeling is illustrated by tight estimates obtained on realistic benchmarks. Categories and Subject Descriptor