Caches in WCET Analysis Predictability, Competitiveness, Sensitivity
Jan Reineke · 2008
Embedded systems as they occur in application domains such as automotive, aeronautics, and industrial automation often have to satisfy hard real-time constraints. Safe and precise bounds on the worst-case execution time (WCET) of each task have to be derived. This thesis studies the influence of cache replacement policies on the precision and soundness of WCET analyses. We define and evaluate predictability metrics that capture how quickly may and must information can be obtained under a particular replacement policy. The metrics mark a limit on the precision of any cache analysis. We generalize the notion of competitiveness to that of relative competitiveness. Relative competitive ratios bound the performance of a policy relative to that of another policy. Constructing a quotient transition system enables us to automatically compute such competitive ratios. Competitive ratios of LRU relative to FIFO and MRU yield the first may cache analyses for the two policies. These analyses are optimal with respect to the predictability metrics. Measurement has been proposed as an alternative to static analysis in WCET analysis. To evaluate the soundness of measurement-based WCET analysis, we investigate how sensitive replacement policies are to the state they are starting in. Analysis reveals that for FIFO, MRU, and PLRU, measurement may yield WCET estimates that are dramatically wrong.