Bounding worst-case data cache performance
Randall T. White · 1997
Tightly predicting worst-case execution times (WCETs) of programs on real-time systems with caches is difficult. Whether or not a particular reference is in cache depends on the program's previous dynamic behavior. While much progress has been accomplished recently on predicting instruction cache performance of programs, bounding worst-case data cache performance is significantly more challenging. Unlike instruction caching, many of the data addresses referenced by load and store instructions can change during the execution of a program. This dissertation describes an automatic tool-based approach for statically bounding the worst-case data cache performance of large code segments. It also presents the work done to verify the validity of the computed bounds. The given approach works on fully optimized code, performs the analysis over the entire control flow of a program, detects and exploits both spatial and temporal locality within data references, produces results typically within a few seconds, and produces, on average, 30% tighter WCET bounds than can be predicted without analyzing data cache behavior. The given method of timing analysis involves several steps. First, data flow analysis within an optimizing compiler is used to determine the bounded range of addresses of each data reference relative to a global symbol or activation record. Second, virtual address ranges are calculated from the relative address ranges by examining the order of the assembly data declarations and the call graph of the entire program. Third, the control flow of the program is analyzed to statically categorize the caching behavior of each data reference. Fourth, these categorizations are used when calculating the pipeline performance of sequences of instructions representing paths within the program. Finally, the pipeline path analysis is used to estimate the worst-case execution performance of each loop and function in the program. Overall, this dissertation presents a comprehensive report on methods and results of worst-case timing analysis of data cache behavior and shows that such an analysis can lead to a significantly tighter worst-case performance prediction. The given approach is unique and provides a considerable step towards realistic worst-case execution time prediction of contemporary architectures and its use in schedulability analysis for real-time systems.