Generalizing timing predictions to set-associative caches

Hard realtime systems rely on the assumption that the deadlines of tasks can be met otherwise the safety of the controlled system is jeopardized Several scheduling paradigms have been developed to support the analysis of a task sets and determine if a schedule is feasible These scheduling paradigms rely on the assumption that the worstcase execution time WCET of hard realtime tasks be known apriori In the past years research in the static prediction of WCET has been extended from unoptimized programs on simple CISC processors to optimized programs on pipelined RISC processors and from un cached architectures to directmapped instruction caches The work presented here goes one step beyond the previous research by introducing the rst framework to handle WCET prediction for setassociative caches Generalizing the work of static cache simulation of directmapped caches to setassociative caches a formalization of the new method is given and the operational characteristics are presented and discussed by example Furthermore WCET predictions for several programs are presented by combining the static cache analysis for setassociative caches with a timing analysis tool This approach has the advantage that cache conguration details are handled by static cache simulation but remain transparent to the timing analyzer Overall this work lls another gap between realistic WCET prediction of contemporary cache