Deterministic upperbounds of the worst-case execution times of cached programs

Proposes techniques to derive the worst-case execution time (WCET) of cached programs. We focus on the analysis of one single program run on a direct-mapped cache, where no external interference could occur. The analysis complexity of the WCET of (un)cached programs is NP-complete. For nested loops, we derive some sufficient conditions in deriving the deterministic bounds of their WCET. These sufficient conditions can be used to make trade-offs between tightness of the WCET bounds and their search time.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>