Publications in Scientific Journals:
J. Blieberger, T. Fahringer, B. Scholz:
"Symbolic Cache Analysis for Real-Time Systems";
Caches impose a major problem for predicting
execution times of real-time systems since the cache behavior
depends on the history of previous memory
references. Too pessimistic assumptions on cache hits can result in
worst-case execution time estimates that are prohibitive
for real-time systems.
This paper presents a novel approach for deriving a highly accurate
analytical cache hit function for programs at compile-time based on the assumption that no external
cache interference (e.g. process dispatching or DMA activity) occurs.
First, a symbolic tracefile of an instrumented program
is generated based on symbolic evaluation which is a
static technique to determine the dynamic behavior of programs.
Symbolic expressions and recurrences are used to describe
all memory references in a program which are then stored
chronologically in the symbolic tracefile.
Second, a cache hit function for several
cache architectures is computed based on a
novel cache evaluation technique. Our approach goes beyond
previous work by precisely modelling program control flow and program unknowns,
modelling large classes of programming languages and cache architectures, and
providing very accurate cache hit predictions.
Examples for the SPARC architecture are used to illustrate the
accuracy and effectiveness of our symbolic cache
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.