There are two general contributions of this paper. First, an approach for bounding the worst-case data caching performance is introduced. It uses data flow analysis within a compiler to determine a bounded range of relative addresses for each data reference. An address calculator converts these relative ranges to virtual address ranges by examining the order of data declarations and the call graph of the program. Categorizations of the data references are produced by a static simulator. A timing analyzer uses the categorizations when performing pipeline path analysis to predict the worst-case performance for each loop and function in the program. The results so far indicate that the approach is valid and can result in significantly tighter worst-case performance predictions.
Second, a report on an implementation of timing predictions for set-associative caches is given. A formal method and the corresponding operational framework for simulating set-associative caches is described. This method of static cache simulation for set-associative caches is shown to yield adequate results to enable tight predictions of the WCET by the timing analyzer, regardless of the degree of cache associativity. The cache simulation overhead scales linearly with increasing associativity.
Overall, this paper contributes a comprehensive report on methods and results of worst-case timing analysis for data caches and set-associative caches. The analysis occurred on code generated with all compiler optimizations enabled and requires no user-specified information. The approach taken is unique and provides a considerable step toward realistic worst-case execution time prediction of contemporary architectures and its use in schedulability analysis for real-time systems.