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 obtain 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 C-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 C-program is generated based on  symbolic evaluation, which is a static technique to determine the dynamic behavior of programs. All memory references of a program are described by symbolic expressions and recurrences and stored in chronological order in the symbolic tracefile. Second, a cache hit function for several cache architectures is computed based on a  cache evaluation technique. Our approach goes beyond previous work by precisely modelling program control flow and program unknowns, modelling large classes of 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 prediction.
Introduction
Due to high-level integration and superscalar architectural designs the
computational capability of microprocessors has increased significantly
in the last few years. Unfortunately the gap between processor cycle
time and memory latency increases. In order to fully exploit the potential
of processors, the memory hierarchy must be efficiently utilized.
To guide scheduling for real-time systems, information about execution
times is required at compile-time. Modelling caches presents
a major obstacle towards predicting execution times for modern computer
architectures. Worst-case assumptions - e.g. every memory access
results in a cache miss 1 - can cause very poor execution time estimates.
c
Publishers. Printed in the Netherlands.
J. Blieberger, T. Fahringer, B. Scholz
The focus of this paper is on accurate cache behavior analysis. Note
that modelling caches is only one performance aspect that must be
considered in order to determine execution times. There are many other
performance characteristics (Blieberger, 1994; Blieberger and Lieger,
1996; Blieberger, 1997; Fahringer, 1996; Park, 1993; Healy et al., 1995)
to be analyzed which however are beyond the scope of this paper.
In this paper we introduce a novel approach for deriving a highly
accurate analytical function of the precise number of cache hits 2 implied
by a program. Our approach is based on symbolic evaluation
(cf. e.g. Fahringer and Scholz, 1997) which at compile-time collects
runtime properties (control and data flow information) of a given pro-
gram. The number of cache hits is described by symbolic expressions
and recurrences defined over the program's input data so as to maintain
the relationship between the cache cost function and the input data.

Figure

1 depicts an overview of our framework described in this
paper. The C-program is compiled which results in an instrumented C-
program. The source-code level instrumentation inserts code at those
points, where main memory data is referenced (read or written). Then,
the instrumented source-code is symbolically evaluated and a symbolic
tracefile is created. All memory references of a program are described
by symbolic expressions and recurrences which are stored in a symbolic
tracefile. Based on the cache parameters, which describe the cache
architecture, an analytical cache hit function is computed by symbolically
evaluating the symbolic tracefile. Note that our model strictly
separates machine specific cache parameters from the program model
which substantially alleviates portability of our approach to other cache
architectures and programming languages.
Performing a worst-case cache analysis according to our approach
can be divided into the following steps:
1. Build the symbolic tracefile based on the instrumented program
sources by using symbolic evaluation.
2. Compute an analytical cache hit function by symbolically evaluating
the symbolic tracefile.
3. Find a closed form expression for the cache hit function.
4. Determine a lower bound of the cache hit function in order to derive
the worst-case caching behavior of the program.
Steps 1 and 2 are treated in this paper. These steps guarantee a
precise description of the cache hits and misses.
Step 3 requires to solve recurrence relations. We have implemented
a recurrence solver which is described in (Fahringer and Scholz, 1997;
Symbolic Cache Analysis for Real-Time Systems 3
C-Compiler
Instrumentation
Executable
C-Files
Instrumented
C-File
Symbolic Evaluation
Symbolic
Tracefile
Parameters
Cache
Cache-Hit
Function
Symbolic Cache Evaluation

Figure

1. Overview of predicting cache performance
Fahringer and Scholz, 1999). The current implementation of our recurrence
solver handles recurrences of the following kind: linear recurrence
variables (incremented inside a loop by a symbolic expression
defined over constants and invariants), polynomial recurrence variables
(incremented by a linear symbolic expression defined over constants,
invariants and recurrence variables) and geometric recurrence variables
(incremented by a term which contains a recurrence variable multiplied
by an invariant). Our algorithm (Fahringer, 1998b) for computing lower
and upper bounds of symbolic expressions based on a set of constraints
is used to detect whether a recurrence variable monotonically increases
or decreases. Even if no closed form can be found for a recurrence
variable, monotonicity information may be useful, for instance, to determine
whether a pair of references can ever touch the same address. The
4 J. Blieberger, T. Fahringer, B. Scholz
current implementation of our symbolic evaluation framework models
assignments, GOTO, IF, simple I/O and array statements, loops and
procedures.
The result of Step 3 is a conservative approximation of the number of
exact cache hits and misses, i.e., the computed upper and lower bounds
are used to find a lower bound for the cache hit function. The output
form of Step 3 (suitably normalized) is a case-structure that possibly
comprises several cache hit functions. The conditions attached to the
different cases correspond to the original program structure and are
affected by the cache architecture.
In Step 4 we only have to determine the minimum of the cache hit
functions of the case-structure mentioned above. Note that it is not
necessary to determine the worst-case input data because the program
structure implies the worst-case cache behavior.
Steps 3 and 4 are described in detail in (Fahringer and Scholz, 1997;
Fahringer and Scholz, 1999; Fahringer, 1998b).
The rest of the paper is organized as follows. In Section 2 we discuss
our architecture model for caches. In Section 3 we describe symbolic
evaluation and outline a new model for analyzing arrays. Section 4 contains
the theoretical foundations of symbolic tracefiles and illustrates
a practical example. In Section 5 symbolic cache evaluation techniques
are presented for direct mapped and set associative caches. In Section
6 we provide experimental results. Although our approach will be
explained and experimentally examined based on the C-programming
language, it can be similarly applied to most other procedural languages
including Ada and Fortran. In Section 7 we compare our approach with
existing work. Finally, we conclude this paper in Section 8.
2. Caches
The rate at which the processor can execute instructions is limited by
the memory cycle time. This limitation has in fact been a significant
problem because of the persistent mismatch between processor and
main memory speeds. Caches - which are relatively small high-speed
memories - have been introduced in order to hold the contents of most
recently used data of main memory and to exploit the phenomenon of
locality of reference (see (Hennessy and Patterson, 1990)). The advantage
of a cache is to improve the average access time for data located
in main memory. The concept is illustrated in Figure 2.
The cache contains a small portion of main memory. A cache hit
occurs, when the CPU requests a memory reference that is found in
the cache. In this case the reference (memory word) is transmitted
Symbolic Cache Analysis for Real-Time Systems 5
CPU CACHE MEMORY
Transfer
Block
Transfer
Word

Figure

2. CPU, Cache and Main Memory
to the CPU. Otherwise, a cache miss occurs which causes a block of
memory (a fixed number of words) to be transferred from the main
memory to the cache. Consequently, the reference is transmitted from
the cache to the CPU. Commonly the CPU is stalled on a cache miss.
Clearly, memory references that cause a cache miss are significantly
more costly than if the reference is already in the cache.
In the past, various cache organizations (Hennessy and Patterson,
were introduced. Figure 3(a) depicts a general cache organization.
A cache consists of ns slots. Each slot can hold n cache lines and
one cache line contains a block of memory consisting of cls contiguous
bytes and a tag that holds the first address bits of the memory block.

Figure

3(b) shows how an address is divided into three fields to find
data in the cache: the block offset field used to select the desired data
from the block, the index field to select the slot and the tag field used
for comparison. Note that not all bits of the index are used if n ? 1.
A cache can be characterized by three major parameters. First, the
capacity of a cache determines the number of bytes of main memory it
may contain. Second, the line size cls gives the number of contiguous
bytes that are transferred from memory on a cache miss. Third, the
associativity determines the number of cache lines in a slot. If a block
of memory can reside in exactly one location, the cache is called direct
mapped and a cache set can only contain one cache line. If a block can
reside in any cache location, the cache is called fully associative and
there is only one slot. If a block can reside in exactly n locations and
n is the size of a cache set, the cache is called n-way set associative.
In case of fully associative or set associative caches, a memory block
has to be selected for replacement when the cache set of the memory
block is full and the processor requests further data. This is done according
to a replacement strategy (Smith, 1982). Common strategies
are LRU (Least Recently Used), LFU (Least Frequently Used), and
random.
Furthermore, there are two common cache policies with respect to
write accesses of the CPU. First, the write through caches write data
to memory and cache. Therefore, both memory and cache are in line.
Second, write back caches only update the cache line where the data
6 J. Blieberger, T. Fahringer, B. Scholz
Block Offset
Tag
Block
(a) Cache Organization

Figure

3. Cache Organization
item is stored. For write back caches the cache line is marked with a
dirty bit. When a different memory block replaces the modified cache
line, the cache updates the memory.
A write access of the CPU to an address that does not reside in the
cache is called a write miss. There are two common cache organizations
with respect to write misses. First, the write-allocate policy loads the
referenced memory block into the cache. This policy is generally used
for write back caches. Second, the no-write-allocate policy updates the
cache line only if the address is in cache. This policy is often used
for write through cache and has the advantages that memory always
contains up-to-date information and the elapsed time needed for a write
access is constant.
Symbolic Cache Analysis for Real-Time Systems 7
Caches can be further classified. A cache that holds only instructions
is called instruction cache. A cache that holds only data is called data
cache. A cache that can hold instructions and data is called a mixed or
unified cache.
Cache design has been extensively studied. Good surveys can be
found in (Alt et al., 1996; Mueller, 1997; Ottosson and Sjoedin, 1997; Li
et al., 1996; Li et al., 1995; Healy et al., 1995; Arnold et al., 1994; Nilsen
and Rygg, 1995; Liu and Lee, 1994; Hennessy and Patterson, 1990).
3. Symbolic Evaluation
Symbolic evaluation 3 (Cheatham et al., 1979; Ploedereder, 1980; Fah-
ringer and Scholz, 1997; Fahringer and Scholz, 1999) z is a constructive
description of the semantics of a program. Moreover, symbolic evaluation
is not merely an arbitrary alternative semantic description of a
program. As in the relationship between arithmetic and algebra the
specific (arithmetic) computations dictated by the program operators
are generalized and "delayed" using the appropriate formulas. The
dynamic behavior is precisely represented.
Symbolic evaluation satisfies a commutativity property.
Symbolic Evaluation
\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma! (z[[p]]; i)
parameters
to i
into result
Conventional Execution
\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma! z[[p]]i
If a program p is conventionally executed with the standard semantics
over a given input i, the result of the symbolically evaluated
program instantiated by i is the same. Clearly, symbolic evaluation
can be seen as a compiler, that translates a program into a different
language. Here, we use as a target language symbolic expressions and
recurrences to model the semantics of a program.
The semantic domain of our symbolic evaluation is a novel representation
called program context (Fahringer and Scholz, 1997; Fahringer
and Scholz, 1999). Every statement is associated with a program context
c that describes the variable values, assumptions regarding and
constraints between variable values and a path condition. The path
condition holds for a given input if the statement is executed. Formally,
a context c is defined by a triple [s; t; p] where s is a state, t a state
condition and p a path condition.
\Gamma The state s is described by a set of variable/value pairs fv
is a program variable and e i a symbolic
8 J. Blieberger, T. Fahringer, B. Scholz
expression describing the value of v i for 1 - i - n. For all program
variables v i there exists exactly one pair
\Gamma The state condition contains constraints on variable values such as
those implied by loops, variable declarations and user assertions.
Path condition is a predicate, which is true if and only if the
program statement is reached.
Note that all components of a context - including state information
are described as symbolic expressions and recurrences. An unconditional
sequence of statements ' j (1 - j - r) is symbolically evaluated
by [s The initial context [s
represents the context that holds before ' 1 and [s r the context
that holds after ' r . If ' i in the sequence
does not contain any side effects (implying a change of a variable
Furthermore, a context c = [s; t; p] is a logical assertion
c is a predicate over the set of program variables and the
program input which are free variables. If for all input values c i\Gamma1 holds
before executing the statement ' i then c i is the strongest post condition
(Dijkstra, 1976) and the program variables are in a state satisfying c i
after executing ' i .
For further technical details we refer the reader to (Fahringer and
Scholz, 1997; Fahringer and Scholz, 1999; Blieberger and Burgstal-
ler, 1998; Blieberger et al., 1999). In the following we discuss a novel
approach to evaluate arrays.
3.1. Arrays
Let a be a one-dimensional array with n (n - 1) array elements. Consider
the simple array assignment a[i]=v. The element with index i
is substituted by the value of v. Intuitively, we may think of an array
assignment being an array operation that is defined for an array. The
operation is applied to the array and changes its internal state. The
arguments of such an array operation are a value and an index of the
new assigned array element. A sequence of array assignments implies
a chain of operations. Formally, an array is represented as an element
of an array algebra A . The array algebra A is inductively defined as
follows.
1. If n is a symbolic expression then ? n 2 A .
2. If a 2 A and ff; fi are symbolic expressions then a \Phi (ff; fi) 2 A .
3. Nothing else is in A .
Symbolic Cache Analysis for Real-Time Systems 9
int a[100],x;

Figure

4. C-program fragment
In the state of a context, an array variable is associated with an
element of the array algebra A . Undefined array states are denoted by
is the size of the array and determines the number of
array elements. An array assignment is modelled by a \Phi-function. The
semantics of the \Phi-function is given by
a \Phi (ff;
represents the elements of array a and fi denotes
the index of the element with a new value ff. For the following general
array assignment
is the context before and [s the context after
statement ' i . The symbolic value of variable a before evaluating the
statement ' i is denoted by a. Furthermore, an element a in A with
at least one \Phi-function is a \Phi-chain. Every \Phi-chain can be written as
The length of a chain jaj is the number of \Phi-functions
in chain a.
The C-program fragment in Figure 4 illustrates the evaluation of
several array assignments. The context of statement ' j is represented
by c At the beginning of the program fragment the value of
variable x is a symbolic expression denoted by x. Array a is undefined
J. Blieberger, T. Fahringer, B. Scholz
(? 100 ). For all array assignment statements the state and path conditions
are set to true because the code fragment implies no branches.
Most program statements imply a change of only a single variable's
value. In order to avoid large lists of variable values in state descriptions
only those variables whose value changes after evaluation of the associated
statement are explicitly specified. For this reason we introduce
a function ffi,
which specifies a state s i whose variable binding is equal to that of
state s j except for variable v assigned a new
value e i .
Therefore, in the previous example, state s 1 is the same as state s 0
except for the symbolic value of array a.
After the last statement array a is symbolically described by a =
1). The left-most
\Phi-function relates to the first assignment of the example program -
the right-most one to the last statement.
Note that the last two statements overwrite the values of the first
two statements. Therefore, a simplified representation of a is given by
Although the equivalence of two symbolic expressions is undecidable
Haghighat and Polychronopoulos, 1996), a wide
class of equivalence relations can be solved in practice. The set of conditions
among the used variables in the context significantly improves
the evaluation of equivalence relation. A partial simplification operator
' is introduced to simplify \Phi-chains. Operator ' is defined as follows.
The partial simplification operator ' seeks for two equal expressions
in a \Phi-chain. If a pair exists, the result of ' will be the initial \Phi-
chain without the \Phi-function, which refers to the fi expression with
the smaller index i. If no pair exists, the operator returns the initial
\Phi-chain; the chain could not be simplified. Semantically, the right-most
expression relates to the latest assignment and overwrites the value
of the previous assignment with the same symbolic index.
The partial simplification operator ' reduces only one redundant
\Phi-function. In the previous example ' must be applied twice in order
Symbolic Cache Analysis for Real-Time Systems 11
to simplify the \Phi-chain. Moreover, each \Phi-function in the chain is a
potentially redundant one. Therefore, the chain is potentially simplified
in less than jaj applications of '. A partially complete simplification is
an iterative application of the partial simplification operator and it is
written as '   (a). If '   (a) is applied to a, further applying of ' will not
simplify a anymore: '('
In order to access elements of an array we need to model a symbolic
access function. Operator ae in a symbolic expressions e (described by a
\Phi-chain) reads an element with index i of an array a. If index i can be
found in the \Phi-chain, ae yields the corresponding symbolic expression
otherwise ae is the undefined value ?. In the latter case it is not possible
to determine whether the array element with index i was written. Let a
be an element of A and
l=1 (ff l ; fi l ). The operator ae is defined
as
ae
where i is the symbolic index of the array element to be found. In
general determining whether the symbolic index i matches with a \Phi-
function is undecidable. In practice a wide class of symbolic relations
can be solved by our techniques for comparing symbolic expressions
1998a). If our symbolic evaluation framework cannot prove
that the result of ae is fi l or ? then ae is not resolvable and remains
unchanged in symbolic expression e.
We present four examples in Figure 5, which are based on the value
of a at the end of the program fragment in Figure 4. For every example
we insert one of the following statements at the end of the code fragment
shown in Figure 4. For (1) x=a[x]; (2) x=a[x+1]; (3) x=a[x-1]; and
(4) x=a[y]; where y is a new variable with the symbolic value of y.
The figure shows the symbolic value of x after the inserted statement.
Note that in the first equation the element with index x is uniquely
determined. The second equation is resolved as well. In the third example
the index x \Gamma 1 does not exist in the \Phi-chain.
Therefore, the access returns the undefined symbol ?. In the last
equation we do not have enough information to determine a unique
value for array element with index i. Here, we distinguish between
several cases to cover all possibilities.
J. Blieberger, T. Fahringer, B. Scholz
1.
2.
3.
4.

Figure

5. Examples of ae
3.2. Array operations inside of loops
Modelling loops implies a problem with recurrence variables 4 . We will
use functions to model recurrences as follows: i(k
is the value of a scalar variable i at the end of iteration k + 1.
Our symbolic evaluation framework detects recurrence variables,
determines the recurrence system and finally tries to find closed forms
for recurrence variables at the loop exit by solving the recurrence sys-
tem. The recurrence system is given by the boundary conditions (initial
values for recurrence variables in the loop preheader), the recurrence
relations (implied by the assignments to the recurrence variables in the
loop body) and the recurrence condition (loop or exit condition).
We have implemented a recurrence solver (Scheibl et al., 1996) written
on top of Mathematica. The recurrence solver tries to determine
closed forms for recurrence variables based on their recurrence system
which is directly obtained from the program context. The implementation
of our recurrence solver is largely based on methods described in
(Gerlek et al., 1995; Lueker, 1980) and improved by our own techniques
(Fahringer and Scholz, 1997; Fahringer and Scholz, 1999).
Similar to scalar variables the array manipulation inside of loops
are described by recurrences. A recurrence system over A consists of a
boundary condition and a recurrence relation
(ff l (k); fi l (k))
where ff l (k) and fi l (k) are symbolic expressions and k is the recurrence
index with k - 0. Clearly, every instance of the recurrence is an element
of A . Without changing the semantics of an array recurrence, '   can
be applied to simplify the recurrence relation.
Symbolic Cache Analysis for Real-Time Systems 13
Operator ae needs to be extended for array recurrences, such that arrays
written inside of loops can be accessed, e.g. ae(a(z); i). The symbolic
expression z is the number of loop iterations determined by the loop
exit condition and i is the index of the accessed element. Furthermore,
the recurrence index k is bounded to 0 - k - z. To determine a possible
\Phi-function, where the accessed element is written, a potential index set
l (i) of the l-th \Phi-function is computed.
l (i) contains all possible fi l (k), z equal to the index i. If an
index set has more than one element, the array element i is written in
different loop iterations by the l-th \Phi-function. Only the last iteration
that writes array element i is of interest. Consequently, we choose the
element with the greatest index. The supremum x l (i) of an index set
l (i) is the greatest index such that
Finally, we define operator ae as follows.
ae (a(z);
ae
The maximum of the supremum indices x l (i) determines the symbolic
value ff l (x l (i)). If no supremum index exists, ae returns the access to
the value before the loop.
The example code of the program in Figure 6 shows how to symbolically
evaluate an array access. The recurrence of i(k) is resolved in
state s 3 of ' 3 . Due to the missing information about a the recurrence
of array a is not resolvable but our symbolic evaluation still models the
dynamic behavior of the example code.
4. Symbolic Tracefile
Tracing is the method of generating a sequence of instruction and data
references encountered during program execution. The trace data is
commonly stored in a tracefile and analyzed at a later point in time.
For tracing, instrumentation is needed to insert code at those points
in a program, where memory addresses are referenced. The tracefile is
created as a side-effect of execution. Tracing requires a careful analysis
of the program to ensure that the instrumentation correctly reflects the
data or code references of a program. Moreover, the instrumentation
14 J. Blieberger, T. Fahringer, B. Scholz
int
char a[100],s=0;

Figure

6. C-program fragment
can be done at the source-code level or machine code level. For our
framework we need a source-code level instrumentation. In the past a
variety of different cache profilers were introduced, e. g. MTOOL (Gold-
berg and Hennessy, 1991), PFC-Sim (Callahan et al., 1990), CPROF
(Lebeck and Wood, 1994).
The novelty of our approach is to compute the trace data symbolically
at compile-time without executing the program. A symbolic
tracefile is a constructive description for all possible memory references
in chronological order. It is represented as symbolic expressions and
recurrences.
In the following we discuss the instrumentation of the program in

Figure

6. The SPARC assembler code is listed in Figure 7. The first
part of the code is a loop preparation phase. In this portion of code
the contents of variable n is loaded into a work register. Additionally,
the address of a is built up in register %g2. Inside the loop, the storage
location of n is not referenced anymore and there are four read accesses
s, a[i], a[i], a[i+1] and two write accesses s, a[i]. Furthermore,
the variable i is held in a register. Based on this information we can
instrument the example program. In Figure 8 the instrumented program
is shown where function r ref(r,nb) denotes a read reference of
address r with the length of nb bytes. For a write reference the function
w ref() is used.
Symbolic Cache Analysis for Real-Time Systems 15
ld [%o3+%lo(n)],%g5; read &n
mov 0,%o1
add %g5,-1,%g5
cmp %o1,%g5
bge .LL3
or %g2,%lo(a),%g2
add %g2,1,%o4
ldub [%o2+%lo(s)],%g2; read &s
ldub [%o0],%g3; read &a[i]
add %g2,%g3,%g2
stb %g2,[%o2+%lo(s)]; write &s
ldub [%o0],%g2; read &a[i]
ldub [%o1+%o4],%g3; read &a[i+1]
add %g2,%g3,%g2
stb %g2,[%o0]; write &[i]
cmp %o1,%g5
bl .LL5
add %o0,1,%o0
retl

Figure

7. SPARC code of example in Figure 6
A symbolic tracefile is created by using a chain algebra. The references
are stored as a chain. A symbolic trace file t 2 T is inductively
defined as follows.
1.
2. If t 2 T and r and nb are symbolic expressions then t \Phi oe(r; nb) 2 T.
3. If t 2 T and r and nb are symbolic expressions then t \Phi -(r; nb) 2 T.
4. Nothing else is in T.
Semantically, function oe is a write reference to the memory with symbolic
address r whereby the number of referenced bytes is denoted by
nb. We have similar semantics for read references -, where r is the
address and nb is the number of referenced bytes.
For instance, a 32-bit bus between the cache and CPU can only
transfer a word references with 4 bytes. Therefore, a double data item
J. Blieberger, T. Fahringer, B. Scholz
(comprises 8 bytes) -(r; 8) must be loaded in two consecutive steps by
4). For a word reference we do not need the number of
referenced bytes anymore because it is constant. In the example above
it is legal to rewrite -(r; 8) as -(r)\Phi-(r+4). This notation is extensively
used in the examples of Section 5.
For loops we need recurrences
where - l (k) is a read or write reference (-(r l (k); nb) or -(r l (k); nb)).
Symbolic evaluation is used to automatically generate the symbolic
tracefile of a C-program. Instead of symbolically evaluating instrumentation
calls we associate w ref and r ref with specific semantics. A
pseudo variable t 2 T is added to the program. A read reference
r ref(r,nb) is translated to t \Phi -(r; nb), where t is the state of the
pseudo variable t before evaluating the instrumentation. The same is
done for write references except that - is replaced by oe.
Let us consider the example in Figure 8. Before entering the loop, t
needs to log reference r ref(&n,4). Therefore, t is equal to ?\Phi-(&n;
where &n denotes the address of variable n. Inside the loop a recurrence
is used to describe t symbolically. The boundary condition t(0) is equal
to ? \Phi -(&n; 4) and reflects the state before the loop. The recurrence
relation is given by
Note that an alternative notation of &a[k] is a a is the start
address of array a. Finally, the last value of k in the recurrence t(k) is
which is determined by the loop condition.
For the symbolic tracefile only small portions of the final program
context are needed. Therefore, we extract the necessary parts from the
final context to describe the symbolic tracefile. Here, the state condition
and symbolic value t are of relevance. For example in Figure 8 the
symbolic tracefile is given by
Symbolic Cache Analysis for Real-Time Systems 17
int
char a[100],s=0;

Figure

8. C-program fragment with symbolic tracefile
The length of the symbolic tracefile corresponds to the number of
read/write references. If either the number of reads or the number
of writes are of interest we selectively count elements (- and oe). For
instance the number of read references is jtj
the number of write references is jtj 1), and the overall
number of memory references is given by
5. Symbolic Evaluation of Caches
A symbolic tracefile of a program describes all memory references (is-
sued by the CPU) in chronological order. Based on the symbolic trace-
J. Blieberger, T. Fahringer, B. Scholz
file we can derive an analytical function over the input, which computes
the number of hits. The symbolic tracefile contains all information
to obtain the hit function. Moreover, the symbolic cache analysis is
decoupled from the original program. Thus, our approach can be used
to tailor the cache organization due to the needs of a given application.
In the following we introduce two formalisms to compute a hit function
for direct mapped and set associative data caches. To symbolically simulate
the cache hardware, hit sets are introduced. Hit sets symbolically
describe which addresses are held in the cache and keep track of the
number of hits.
5.1. Direct Mapped Caches
Direct mapped caches are the easiest cache organization to analyze.
For each item of data there is exactly one location in a direct mapped
cache where it can be placed 5 and the cache contains ns cache lines. The
size of a cache line, cls , determines the amount of data that is moved
between main memory and the cache. In the following we introduce the
cache evaluation of direct mapped caches with write through
and no-write-allocate policy. Compare Section 2.
A new cache evaluation operator fi is defined to derive a hit set
for a given tracefile t, where a hit set is a h). The
first component of H is a symbolic cache, which is element of A -
the second component represents the number of cache hits and is a
Symbolic cache C of a hit set H has ns elements and each element
corresponds to a cache line of the cache. More formally, the algebraic
operation C \Phi(r; fi) loads the memory block with start address r into the
cache whereby fi is the index of the cache line. Note that when the CPU
issues address r, the start address r of the corresponding memory block
must be selected to describe the reference. Moreover, a cache placement
function - maps a reference to an index of cache C such that the load
operation of reference r is written as C \Phi (r; -(r)). In the following we
assume that function - is a modulo operation (ns   cls).
5.1.1. Definition of the cache evaluation operator
ns ; 0) denotes the initial hit set,
the final hit set, and t the tracefile. The final hit set
H f is the analytical description of the number of cache hits and the
final state of the cache. In the following we describe the operator fi
inductively.
First, for an empty tracefile ? the hit set is
Symbolic Cache Analysis for Real-Time Systems 19
Second, if a write reference is the first reference in the tracefile, it does
not change the hit set at all and is to be removed.
(2)
where - l is either a read reference -(r l ) or write reference oe(r l ). Third,
for read references a new hit set must be computed
and
C; otherwise
Increment d is 1 if reference r is in the cache. Otherwise, d is zero and
the reference r must be loaded. For loading data item with address r
into the cache, C' is assigned the new symbolic value C \Phi (r; -(r)).
In order to symbolically describe the conditional behavior of caches
(data item is in the cache or not), we introduce a fl-function (see
(Fahringer and Scholz, 1997)).
where semantically
equivalent to (c-x
c is a conditional expression and :c the negation of c. Moreover, x i
are symbolic expressions.
Based on the definition of fl (6) we can aggregate formulas given
in (3),(4), and (5). Depending on condition ae(C; either the
number of cache hits h 0 is incremented by one or the symbolic cache is
assigned a new symbolic value C
J. Blieberger, T. Fahringer, B. Scholz
Similar to tracefiles, hit sets are written as a pair. The first component
of the pair symbolically describes the hit set. The second component
contains constraints on variable values such as conditionals and
recurrences stemming from loops.
Furthermore, for recursively-defined tracefiles we need to generalize
hit sets to hit set recurrences. Let t(k
l (k) be
the tracefile recurrence relation and H the initial hit set, the hit set
recurrence is expressed by
5.1.2. Example
For the sake of demonstration, we study our example of Figure 6 with
a cache size of 4 cache lines and each cache line comprises one byte.
The cache placement function -(r) is r mod 4. It maps the memory
addresses to slots of the cache. Moreover, all references are already
transformed to word references and references &n, &s, and &a[0] are
aligned to the first cache line. Note that in our example a word reference
can only transfer one byte from the CPU to the cache and vice versa.
The initial hit set is H 0). Based on the symbolic tracefile
given in (1) the hit set recurrence is to be derived. First of all we apply
operator fi to the hit set recurrence according to (8).
The final hit set is given by H
the highest index k of the recurrence and is determined by the loop
condition. In the following we evaluate the boundary condition of the
hit set recurrence. We successively apply the evaluation rule (7) of
operator fi to the initial hit set (? 4 ; 0).
Symbolic Cache Analysis for Real-Time Systems 21
Note that condition ae(C; of rule (7) is false for all read
references in the boundary condition. After evaluating the boundary
condition there is still no cache hit and the cache is fully loaded with
the contents of variable n. In the next step we analyze the loop iteration.
We continue to apply operator fi to the recurrence relation.
where C k and h k denote symbolic cache and number of hits in the kth
iteration of the hit set recurrence. The global variable s is mapped to
the first cache line. If the first slot of the cache contains the address
of s then a cache hit occurs and the number of hits is incremented,
otherwise the new element is loaded and the number of hits remains
the same. We further apply operator fi and obtain
In the next step we eliminate the write reference oe(&s) according to
rule (2) and further apply operator fi to -(&a[k]).
22 J. Blieberger, T. Fahringer, B. Scholz
Here, we can simplify the fl-function. The contents of symbolic cache
k at k mod 4 is k because the reference &a[k] is loaded from the step
before the previous one. Note that the write reference oe(&s) does not
destroy the reference &a[k]. In the last step the references -(&a[k
and oe(&a[k]) are evaluated. We continue with
The third fl-function can be reduced since element k+1 has never been
written before because condition ae(C 00
The hit set recurrence is still conditional. Further investigations are
necessary to derive a closed form for the number of hits. We know that
the number of cache lines is four. We consider all four modulo classes
of index k which for the given example results in an unconditional
recurrence.
0: The condition ae(C k ; &s of the first fl-function is
false since ae(C k ; 0) can be rewritten as k, if k ? 1 or ? otherwise.
The condition of second fl-function ae(C 0
is false as
well because the cache line has been loaded with the reference &s
before. For the case k mod the hit set recurrence is reduced
to an unconditional recurrence.
In the first fl-function the condition ae(C k ;
can never be true because in the previous step of the recurrence the
Symbolic Cache Analysis for Real-Time Systems 23
cache line 1 has been loaded with the contents of &a[k \Gamma 1]. Fur-
thermore, the element &a[k] has been fetched in the previous step
and, therefore, the condition of the second fl-function evaluates to
true and the hit set recurrence can be written as
3: For both cases the conditions of the
fl-functions are true. The load reference &s does not interfere with
&a[k] and &a[k 1]. The recurrence is given by
Now, we can extract the number of hits from hit sets (9), (10), (11).
The modulo classes can be rewritten such that k is replaced by 4i and
the modulo class.
The boundary conditions stem from the number of hits of H(0). The
recurrence is linear and after resolving it, we obtain
The index z of the final hit set H determined by z =
1). The analytical cache hit function h z , given by (12), can
be approximated by 9
In the example above the conditional recurrence collapsed to an
unconditional one. In general, we can obtain closed forms only for
specific - although very important - classes of conditional recurrences.
If recurrences cannot be resolved, we employ approximation techniques
as described in (Fahringer, 1998a).
J. Blieberger, T. Fahringer, B. Scholz1n-1

Figure

9. An n-way Set Associative Cache
5.2. Set Associative and Fully Associative Caches
In this section we investigate n-way set associative write through data
caches with write-allocate policy and least recently used replacement
(LRU) strategy. The organization of set-associative is more complex
than direct mapped data caches due to placing a memory block to n
possible locations in a slot (compare Section 2).
Similar to direct mapped caches we define a cache evaluation operator
fi to derive a hit set for a given tracefile t. For set associative
caches a hit set is a tuple
cache, h the number of hits, and - max is a symbolic counter that is
incremented for every read or write reference. Note that the symbolic
counter is needed to keep track of the least recently used reference
of a slot. Figure 9 illustrates the symbolic representation of C for set
associative caches. C is an array of ns slots. Each slot, denoted as S(')
ns \Gamma 1, can hold n cache lines. Array C and slots S(')
are elements of array algebra A .
More formally, algebraic operation S \Phi ((r; -); fi) loads the memory
block with start address r into set S whereby fi is the index (0 - fi ! n)
and - the current symbolic value of - max . Reading value r from S is
denoted by ae r (S; fi) while reading the time stamp is written ae - (S; fi).
A whole set is loaded into cache C via C \Phi (S; '). Note that when
the CPU issues address r, the start address r of the corresponding
memory block must be selected to describe the reference. Similar to
direct mapped caches, a cache placement function - maps a memory
reference to slot S such that the load operation of reference r is written
as C \Phi (ae(C; -(r)) \Phi ((r; -(r))) where -(r) is a function determining
Symbolic Cache Analysis for Real-Time Systems 25
the index of slot S according to the LRU strategy and is defined by
there exists a ' such that ae(S;
Note that the first case determines if there is a spare location in slot
S. If so, the first spare location is determined by -. The second case
computes the least recently used cache line of slot S.
5.2.1. Definition of the cache evaluation operator
ns ; 0; 0) denotes the initial hit set,
the final hit set, and t the tracefile. The final hit set
H f is the analytical description of the number of cache hits and the
final state of the cache. In the following we describe the operator fi
inductively.
First, for an empty tracefile ? the hit set is
Second, if a read or write operation -(r) is the first memory reference
in the tracefile, a new hit set is deduced as follows
d. The symbolic counter - max is incremented by one.
Furthermore, the slot of reference r is determined by
and increment d is given by
0; otherwise.
If there exists an element in slot S, which is equal to r, a cache hit
occurs and increment reference r must be updated with a
new time stamp.
where
Function -(r) looks up the index, where reference r is stored in slot
-(r) can be described by a recurrence. If d = 0, a cache miss occurs
and the reference is loaded into the cache
26 J. Blieberger, T. Fahringer, B. Scholz
where
We can aggregate formulas (13) - (18) with fl-functions. Depending on
condition
new element is updated with a
new time stamp or loaded into the cache.
Note that fl functions are nested in formula (19). A nested fl is recursively
expanded (compare (6)) such that the expanded boolean expression
is added to the corresponding true or false term of the higher-level
fl-function. Furthermore, for recursively-described tracefiles we need to
generalize hit sets to hit set recurrences (compare (8)).
5.2.2. Example
We symbolically evaluate the example of Figure 6 with a 2-way set
associative cache and two slots and a cache line size of one byte. For
this cache organization a word reference can transfer one byte from
the CPU to the cache and vice versa. Thus, the cache size is the same
as in Section 5.1, only the cache organization has changed. The cache
placement function -(r) is r mod 2. We assume that the references of
the symbolic tracefile are already transformed to word references and
references &n, &s, and &a[0] are aligned to the first slot.
The initial hit set is H 0). Based on the tracefile given in
(1) the hit set recurrence is to be derived. Similar to example in Section
5.1 we apply operator fi to the hit set recurrence according to (8).
For all read references in the boundary no cache hit occurred. The
cache is loaded with the contents of variable n and the number of cache
Symbolic Cache Analysis for Real-Time Systems 27
hits is zero. In the next step we evaluate the recurrence relation. We
continue to apply operator fi according to rule (19).
where C k , h k , and - k denote symbolic cache, number of hits and time
stamp counter of the kth iteration of the hit set recurrence. In order
to keep the description of hit set recurrences as small as possible we
rewrite the outer fl-function of (20) as P . We further apply operator fi
and obtain
In the next step we evaluate write reference oe(&s) and get
28 J. Blieberger, T. Fahringer, B. Scholz
Here, we can simplify the fl-function because variable s has been read
within the current iteration of the loop without being overwritten in the
cache, the condition of the outer fl-function evaluates to true. Hence,
we obtain
Similar to the previous step we can reduce both fl-functions.
Read reference &a[k produces a cache miss. Thus, the next step
can be simplified too.
Symbolic Cache Analysis for Real-Time Systems 29
In the last step the fi operator is applied to write reference &s. It is a
cache hit and we can eliminate the fl functions.
Arguments similar to those in Section 5.1 show that the conditions of
the outer fl-function in P 0 and P 00 are true for k - 1 and false for
Therefore, we can derive an unconditional recurrence relation for the
number of cache hits (k - 1).
3:
A closed form solution is given by
2:
The index z of the final hit set H determined by z =
1). Thus, the analytical cache hit function is
which shows that for our example the set associative cache performs
better than the direct mapped cache of the same size.
6. Experimental Results
In order to assess the effectiveness of our cache hit prediction we have
chosen a set of C-programs as a benchmark. We have adopted the
evaluation framework introduced in (Fahringer and Scholz,
1997; Fahringer and Scholz, 1999) for the programming language C
and the cache evaluation. The instrumentation was done by hand although
an existing tool such as CPROF (Lebeck and Wood, 1994)
could have instrumented the benchmark suite. Our symbolic evaluation
framework computed the symbolic tracefiles and symbolically evaluated
data caches. In order to compare predictions against real values we
J. Blieberger, T. Fahringer, B. Scholz
int n; char a[100];
void sum()
int

Figure

10. Benchmark Program
have measured the cache hits for a given cache and problem size. For
measuring the empirical data we used the ACS cache simulator(Hunt,
1997). The programs of the benchmark suite were amended by the
instrumentation routines of a provided library bin2pdt. The generated
tracefiles were stored as PDATS (Johnson and Ha, 1994) files and later
read by the ACS cache simulator.
The first program of the benchmark suite is example program in

Figure

10. In contrast to Section 5 we have analyzed a direct mapped
data cache with a cache line size greater than one byte. Furthermore,
the first byte of array a is aligned to the first byte of an arbitrary
cache line and the cache has more than one cache line. Our framework
computes a cache hit function, where the number of cache hits is determined
by
cls
\Upsilon
and cls is the cache line size of 4, 8 and
bytes. Intuitively, we get 2(n \Gamma 1) potential cache hits. For every new
cache line a miss is implied. Therefore, we have to subtract the number
of touched cache lines
cls
\Upsilon from the number of read references.

Table

Ia describes problem sizes n (n - first column), number of
read (R-Ref. - second column) and write (W-Ref. - third column) ref-
erences, and sum of read and write references (T-Ref. - fourth column).

Tables

measured with predicted cache hits for various
data cache configurations (capacity/cache line size). For instance, D-Cache
256/4 corresponds to a cache with 256 bytes and a cache line size
of 4 bytes. Every table comprises four columns. M-Miss tabulates the
measured cache misses, M-Hits the measured cache hits, and P-Hits
the predicted cache hits. In accordance with our accurate symbolic
cache analysis we observe that the predicted hits are identical with the
associated measurements for all cache configurations considered.
The same benchmark program was taken to derive the analytical
cache hit function for set associative data caches. Note that the result
is the same as for direct mapped caches. Even the empirical study
with two way data caches of the same capacity delivered the same
measurements given in Tables Ib - Id.
Symbolic Cache Analysis for Real-Time Systems 31

Table

ProblemSize
R-Ref. W-Ref. T-Ref.
28
1000 1999 999 2998
10000 19999 9999 29998

Table

Ib. D-Cache256/4
M-Miss M-Hit P-Hit
100 26 173 173
1000 251 1748 1748
10000 2501 17498 17498

Table

Ic. D-Cache16K/8
M-Miss M-Hit P-Hit
1000 126 1873 1873
10000 1251 18748 18748

Table

M-Miss M-Hit P-Hit
J. Blieberger, T. Fahringer, B. Scholz

Table

IIa. Experiment of mcnt
Problem Size
n\Thetam R-Ref. W-Ref. T-Ref.

Table

IIb. D-Cache 64K/16
n\Thetam M-Miss M-Hit P-Hit
100\Theta100 5000 5000 5000
100\Theta200 100000 100000 100000
The second program mcnt of the benchmark suite counts the number
of negative elements of an n \Theta m-matrix. The counter is held in
a register and does not interfere with the memory references of the
matrix. Again, we analyzed the program with three different direct
mapped cache configurations 256/4, 16K/8 and 64K/16. For the data
cache sizes 256/4 and 16K/8 the cache hit function is zero. This is due
float f[N][N], u[N][N], new[N][N];
void jacobi-relaxation()
int i,j;

Figure

11. Jacobi Relaxation
Symbolic Cache Analysis for Real-Time Systems 33

Table

IIIa. Experiment of Jacobi Relaxation
Problem Size
n\Thetan R-Ref. W-Ref. T-Ref.
90\Theta90 48020 9604 288120

Table

IIIb. D-Cache 256/4
n\Thetan M-Miss M-Hit P-Hit

Table

IIIc. D-Cache 512/4
n\Thetan M-Miss M-Hit P-Hit
50\Theta50 7102 4418 4418
90\Theta90 47672 348 348

Table

IIId. D-Cache 1K/4
n\Thetan M-Miss M-Hit P-Hit
50\Theta50 7102 4418 4418
90\Theta90
34 J. Blieberger, T. Fahringer, B. Scholz
to the usage of double elements of the matrix. Only for the 64K/16
configuration the program can benefit from a data cache and the cache
hits are given by
\Sigma n\Deltam\Upsilon
. In

Tables

IIa and IIb the analytical function is
compared to the measured results. Similar to the first benchmark the
cache hit function remains the same for set associative data caches with
the same capacity and the measurements are identical to Table IIb.
The third program jacobi relaxation in Figure 11 calculates the
Jacobi relaxation of an n \Theta n float matrix. In a doubly nested loop
the value of the resulting matrix new is computed. Both loop variables
are held in registers. Therefore, for direct mapped data caches
interference can only occur between the read references of arrays f and
u. We investigated the Jacobi relaxation code with a cache configuration
of 256/4, 512/4 and 1K/4. The number of cache hits is given by
ns
ns
ns
ns
ns - n - ns
according to Section 4 where ns is the number of cache lines. We compared
the measured cache hits with the values of the cache hit function.
The results of our experiments are shown in Tables IIIa - IIId.
The fourth program gauss jordan in Figure 12 is a linear equation
solver. Note that this program contains an if-statement inside the loop.
Variables i, ip, j, and k are held in registers. For direct mapped
data caches interference can only occur between the read references
of array a. We have analyzed the Gauss Jordan algorithm with a cache
configuration of 256/4.
We could classify three different ranges of n where the behavior of
the hit function varies.
C(n) must be described for each n in the range. Furthermore, P (n) is a
function containing 64 cases. Note that the number 64 stems from the
number of cache lines. For sake of demonstration we only enlist some
Symbolic Cache Analysis for Real-Time Systems 35
float a[N,N];
void gauss-jordan(void)
int i,ip,j,k;
if (i != j)-
(a[j,i] * a[i,k]) * a[i,i];

Figure

12. Gauss Jordan
cases.
In

Tables

IVa and IVb we compare the measured results with function
values of the hit function.
The ability to determine accurate number of cache hits depends on
the complexity of the input programs. The quality of our techniques
to resolve recurrences, analyse complex array subscript expressions,
loop bounds, branching conditions, interprocedural effects, and pointer
operations impacts the accuracy of our cache hit function. For instance,
if closed forms cannot be computed for recurrences, then we introduce
approximations such as symbolic upper and lower bounds (Fahringer,
1998a). We have provided a detailed analysis of codes that can be
handled by our symbolic evaluation in (Fahringer and Scholz, 1999).
36 J. Blieberger, T. Fahringer, B. Scholz

Table

IVa. Experiment of Gauss Jordan
Problem Size
n\Thetan R-Ref. W-Ref. T-Ref.
200\Theta200 15999600 3999900 19999500
2000\Theta2000 15999996000 3999999000 19999995000

Table

IVb. D-Cache 256/4
D-Cache 256/4
n\Thetan M-Hit P-Hit
200\Theta200 7060901 7060901
2000\Theta2000 5825464317 5825464317
7. Related Work
Traditionally, the analysis of cache behavior for worst-case execution
time estimates in real-time systems (Park, 1993; Puschner and Koza,
1989; Chapman et al., 1996) was far too complex. Recent research (Ar-
nold et al., 1994) has proposed methods to estimate tighter bounds for
WCET in systems with caches. Most of the work has been successfully
applied to instruction caches (Liu and Lee, 1994) and pipelined architectures
(Healy et al., 1995). Lim et al. (1994) extend the original timing
schemas, introduced by Puschner and Koza (1989), to handle pipelined
architectures and cached architectures. Nearly all of these methods rely
on frequency annotations of statements. If the programmer provides
wrong annotations, the quality of the prediction can be doubtful. Our
approach does not need user (programmer) interaction since it derives
all necessary information from the program's code 6 and it does not
restrict program structure such as (Ghosh et al., 1997).
A major component of the framework described in (Arnold et al.,
1994) is a static cache simulator (Mueller, 1997) realized as a data flow
analysis framework. In (Alt et al., 1996) an alternate formalization
which relies on the technique of abstract interpretation is presented.
Both of these approaches are based on data-flow analysis but do not
Symbolic Cache Analysis for Real-Time Systems 37
properly model control flow. Among others, they cannot deal with dead
paths and zero-trip loops all of which are carefully considered by our
evaluation framework (Fahringer and Scholz, 1997; Blieberger,
1997).
Implicit path enumeration (IPET) (Li et al., 1995; Li et al., 1996) allows
to express semantic dependencies as constraints on the control flow
graph by using integer linear programming models, where frequency
annotations are still required. Additionally, the problem of IPET is
that it only counts the number of hits and misses and cannot keep
track of the history of cache behavior. Only little work has been done to
introduce history variables (Ottosson and Sjoedin, 1997). While IPET
can model if-statements correctly (provided the programmer supplies
correct frequency annotations), it lacks adequate handling of loops. Our
tracefiles exactly describe the data and control flow behavior
of programs which among others enables precise modeling of loops.
In (Theiling and Ferdinand, 1998) IPET was enriched with information
of the abstract interpretation described in (Alt et al., 1996).
A graph coloring approach is used in (Rawat, 1993) to estimate
the number of cache misses for real-time programs. The approach only
supports data caches with random replacement strategy 7 . It employs
standard data-flow analysis and requires compiler support for placing
variables in memory according to the results of the presented algorithm.
Alleviating assumptions about loops and cache performance improving
transformations such as loop unrolling make their analysis less precise
than our approach. It is assumed that every memory reference that is
accessed inside of a loop at a specific loop iteration causes a cache
miss. Their analysis does not consider that a reference might have
been transmitted to the cache due to a cache miss in a previous loop
iteration.
Much research has been done to predict cache behavior in order to
support performance oriented program development. Most of these approaches
are based on estimating cache misses for loop nests. Ferrante
et al. (1991) compute an upper bound for the number of cache lines
accessed in a sequential program which allows them to guide various
code optimizations. They determine upper bounds of cache misses for
array references in innermost loops, the inner two loops, and so on. The
number of cache misses of the innermost loop that causes the cache to
overflow is multiplied by the product of the number of iterations of
the overflow loop and all its containing loops. Their approximation
technique may entail polynomial evaluations and suffers by a limited
control flow modeling (unknown loop bounds, branches, etc.
Lam et al. (1991) developed another cache cost function based on
the number of loops carrying cache reuse which can either be temporal
38 J. Blieberger, T. Fahringer, B. Scholz
(relating to the same data element) or spatial (relating to data elements
in the same cache line). They employ a reuse vector space in combination
with localized iteration space. Cross interference (elements from
different arrays displace each other from the cache) and self interferences
(interference between elements of the same array) are modeled.
Loop bounds are not considered even if they are known constants.
Temam et al. (1994) examine the source code of numerical codes for
cache misses induced by loop nests.
Fahringer (1996; 1997) implemented an analytical model that estimates
the cache behavior for sequential and data parallel Fortran
programs based on a classification of array references, control flow
modeling (loop bounds, branches, etc. are modeled by profiling), and
an analytical cache cost function.
Our approach goes beyond existing work by correctly modeling control
flow of a program even in the presence of program unknowns and
branches such as if-statements inside of loops. We cover larger classes
of programming languages and cache architectures, in particular data
caches, instruction caches and unified caches including direct mapped
caches, set associative, and fully associative caches. We can handle most
important cache replacement and write policies. Our approach accurately
computes cache hits, whereas most other methods are restricted
to approximations.
Closed form expressions and conservative approximations can be
found according to the steps described in Section 1.
Symbolic evaluation can also be used for WCET analysis without
caching (Blieberger, 1997), thereby solving the dead paths problem
of program path analysis (Park, 1993; Altenbernd, 1996). In addi-
tion, it can be used for performing "standard" compiler optimizations,
thus being an optimal framework for integrating optimizing compilers
and WCET analysis (compare Engblom et al. (1998) for a different
approach).
8. Conclusion and Future Work
In this paper we have described a novel approach for estimating cache
hits as implied by programs written in most procedural languages (in-
cluding C, Ada, and Fortran). We generate a symbolic tracefile for the
input program 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. A cache
Symbolic Cache Analysis for Real-Time Systems 39
hit function for several cache architectures is computed based on a
cache evaluation technique.
In the following we describe the contributions of our While
most other research targets upper bounds for cache misses, we focus
on deriving the accurate number of cache hits. We can automatically
determine an analytical cache hit function at compile-time without
user interaction. Symbolic evaluation enables us to represent the cache
hits as a function over program unknowns (e.g. input data). Our approach
allows a comparison of various cache organizations for a given
program with respect to cache performance. We can easily port our
techniques across different architectures by strictly separating machine
specific parameters (e.g. cache line sizes, replacement strategies, etc.)
from machine-independent parameters (e.g. loop bounds, array index
expressions, etc. A novel approach has been introduced to model
arrays as part of symbolic evaluation which maintains the history of
previous array references.
We have shown experiments that demonstrate the effectiveness of
our approach. The predicted cache behavior for our example codes
perfectly match with the measured data.
Although we have applied our techniques to direct mapped data
caches with write through and no write-allocate policy and set associative
data caches with write through and write-allocate policy, it
is possible to generalize our approach for other cache organizations
as well. Moreover, our approach is also applicable for instruction and
unified caches.
In addition our work can be extended to analyze virtual memory
architectures. A combined analysis of caching and pipelining via symbolic
evaluation will be conducted in the near future (compare Healy
et al. (1999) for a different approach).
The quality of our cache hit function depends on the complexity
(e.g. recurrences, interprocedural effects, pointers, etc.) of the input
programs. If, for instance, we cannot find closed forms for recurrences,
then we employ approximations such as upper bounds. We are currently
extending our symbolic evaluation techniques to handle larger
classes of input programs. Additionally, we are building a source-code
level instrumentation system for the SPARC processor architecture.
We investigate the applicability of our techniques for multi-level data
and instruction caches. Finally, we are in the process to conduct more
experiments with larger codes.
J. Blieberger, T. Fahringer, B. Scholz
Notes
1 A cache miss occurs if referenced data is not in cache and needs to be loaded
from main memory.
2 A cache hit occurs if referenced data is in cache.
3 Symbolic evaluation is not to be confused with symbolic execution (see e.g. (King,
1976)).
4 All variables which are written inside a loop - including the loop variable - are
called recurrence variables.
5 A slot consists of one cache line. See Section 2.
6 Clearly our approach cannot bypass undecidability.
7 Random replacement seems very questionable for real-time applications because
of its indeterministic behavior.



--R










Analyzing and Visualizing Performance of Memory Hierachies


A discipline of programming.


Kluwer Academic Publishers.













Computer Architecture - A Quantitative Approach
























His research interests include areas of analysis of algorithms and data structures
He studied Computer Science at the TU Vienna and received his doctoral degree in
Readers may contact Johann Blieberger at the Department of Computer-Aided Automation
Thomas Fahringer Thomas Fahringer received a Masters degree in
Readers may contact Fahringer at the Institute for Software Technology and Parallel Systems

Bernhard Scholz Bernhard Scholz is going to enrol a position as an Assistant Professor of Computer Science at the Dept.

Readers may contact Scholz at the Dept.
Figure 13.
Technical University Vienna

--TR

--CTR
Berhard Scholz , Johann Blieberger , Thomas Fahringer, Symbolic pointer analysis for detecting memory leaks, ACM SIGPLAN Notices, v.34 n.11, p.104-113, Nov. 1999
Thomas Fahringer , Bernhard Scholz, A Unified Symbolic Evaluation Framework for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1105-1125, November 2000
Johann Blieberger, Data-Flow Frameworks for Worst-Case Execution Time Analysis, Real-Time Systems, v.22 n.3, p.183-227, May 2002
B. B. Fraguela , R. Doallo , J. Tourio , E. L. Zapata, A compiler tool to predict memory hierarchy performance of scientific codes, Parallel Computing, v.30 n.2, p.225-248, February 2004
worst-case execution time;symbolic evaluation;cache hit prediction;static analysis