Result: Compositional static instruction cache simulation

Scheduling in hard real-time systems requires a priori knowledge of worst-case execution times (WCET). Obtaining the WCET of a task is a difficult problem. Static timing analysis techniques approach this problem via path analysis, pipeline simulation and cache simulation to derive safe WCET bounds. But such analysis has traditionally been constrained to only small programs due to the complexity of simulation, most notably the complexity of static cache simulation, which requires inter-procedural analysis. This paper describes a novel approach of compositional static cache simulation that alleviates the complexity problem, thereby making static timing analysis feasible for much larger programs than in the past. Specifically, a framework is contributed that facilitates static cache analysis by splitting it into two steps, a module-level analysis and a compositional phase, thus addressing the issue of complexity of inter-procedural analysis for an entire program. The module-level analysis parameterizes the data-flow information in terms of potential evictions from cache due to calls containing conflicting references. The compositional analysis stage uses the result of the parameterized data-flow for each module. Thus, the emphasis here is on handling most of the complexity in the module-level analysis and performing as little analysis as possible at the compositional level. The experimental results for direct-mapped instruction caches show that the compositional analysis framework outperforms prior analysis methods for larger programs by one to two orders of magnitude, depending on the reference for comparison, while providing equally accurate predictions. This novel approach to static cache analysis provides a promising solution to the complexity problem in timing analysis, which, for the first time, makes the analysis of larger programs feasible.