An Accurate Worst Case Timing Analysis for RISC Processors.
An accurate and safe estimation of a tasks worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISCs pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each program construct is a simple time-bound. In our approach, associated with each program construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timingschema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. This paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach.
INTRODUCTION
In real-time computing systems, tasks have timing requirements (i.e., deadlines) that must be met
for correct operation. Thus, it is of utmost importance to guarantee that tasks finish before their
deadlines. Various scheduling techniques, both static and dynamic, have been proposed to ensure this
guarantee. These scheduling algorithms generally require that the WCET (Worst Case Execution
Time) of each task in the system be known a priori. Therefore, it is not surprising that considerable
research has focused on the estimation of the WCETs of tasks.
In a non-pipelined processor without cache memory, it is relatively easy to obtain a tight bound
on the WCET of a sequence of instructions. One simply has to sum up their individual execution
times that are usually given in a table. The WCET of a program can then be calculated by
traversing the program's syntax tree bottom-up and applying formulas for calculating the WCETs
of various language constructs. However, for RISC processors such a simple analysis may not
be appropriate because of their pipelined execution and cache memory. In RISC processors, an
instruction's execution time varies widely depending on many factors such as pipeline stalls due to
hazards and cache hits/misses. One can still obtain a safe WCET bound by assuming the worst
case execution scenario (e.g., each instruction suffers from every kind of hazard and every memory
access results in a cache miss). However, such a pessimistic approach would yield an extremely loose
WCET bound resulting in severe under-utilization of machine resources.
Our goal is to predict tight and safe WCET bounds of tasks for RISC processors. Achieving
this goal would permit RISC processors to be widely used in real-time systems. Our approach
is based on an extension of the timing schema [1]. The timing schema is a set of formulas for
computing execution time bounds of language constructs. In the original timing schema, the timing
information associated with each program construct is a simple time-bound. This choice of timing
information facilitates a simple and accurate timing analysis for processors with fixed execution
times. However, for RISC processors, such timing information is not sufficient to accurately account
for timing variations resulting from pipelined execution and cache memory.
This paper proposes extensions to the original timing schema to rectify the above problem. We
associate with each program construct what we call a (Worst Case Timing Abstraction). The
of a program construct contains timing information of every execution path that might be the
worst case execution path of the program construct. Each timing information includes information
about the factors that may affect the timing of the succeeding program construct. It also includes
the information that is needed to refine the execution time of the program construct when the
timing information of the preceding program construct becomes available at a later stage of WCET
analysis. This extension leads to a revised timing schema that accurately accounts for the timing
variation which results from the history sensitive nature of pipelined execution and cache memory.
We assume that each task is sequential and that some form of cache partitioning [2, 3] is used
to prevent tasks from affecting each other's timing behavior. Without these assumptions, it would
not be possible to eliminate the unpredictability due to task interaction. For example, consider a
real-time system in which a preemptive scheduling policy is used and the cache is not partitioned.
In such a system, a burst of cache misses usually occurs when a previously preempted task resumes
execution. Increase of the task execution time resulting from such a burst of cache misses cannot
be bounded by analyzing each task in isolation.
This paper is organized as follows. In Section II, we survey the related work. Section III focuses
on the problems associated with accurately estimating the WCETs of tasks in pipelined processors.
We then present our method for solving these problems. In Section IV, we describe an accurate
timing analysis technique for instruction cache memory and explain how this technique can be
combined with the pipeline timing analysis technique given in Section III. Section V identifies the
differences between the WCET analysis of instruction caches and that of data caches, and explains
how we address the issues resulting from these differences. In Section VI, we report on preliminary
results of WCET analyses for a RISC processor. Finally, the conclusion is given in Section VII.
II RELATED WORK
A timing prediction method for real-time systems should be able to give safe and accurate WCET
bounds of tasks. Measurement-based and analytical techniques have been used to obtain such
bounds. Measurement-based techniques are, in many cases, inadequate to produce a timing estimation
for real-time systems since their predictions are usually not guaranteed, or enormous cost
is needed. Due to these limitations, analytical approaches are becoming more popular [4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16]. Many of these analytical studies, however, consider a simple
machine model, thus largely ignoring the timing effects of pipelined execution and cache memory
[8, 12, 13, 15].
A. Timing Analysis of Pipelined Execution
The timing effects of pipelined execution have been recently studied by Harmon, Baker, and Whalley
[6], Harcourt, Mauney, and Cook [5], Narasimhan and Nilsen [11], and Choi, Lee, and Kang
[4]. In these studies, the execution time of a sequence of instructions is estimated by modeling a
pipelined processor as a set of resources and representing each instruction as a process that acquires
and consumes a subset of the resources in time. In order to mechanize the process of calculating
the execution time, they use various techniques: pattern matching [6], SCCS (Synchronous Calculus
of Communicating Systems) [5], retargetable pipeline simulation [11], and ACSR (Algebra of Communicating
Shared Resources) [4]. Although these approaches have the advantage of being formal
and machine independent, their applications are currently limited to calculating the execution time
of a sequence of instructions or a given sequence of basic blocks 1 . Therefore, they rely on ad hoc
methods to calculate the WCETs of programs.
The pipeline timing analysis technique by Zhang, Burns and Nicholson [16] can mechanically
calculate the WCETs of programs for a pipelined processor. Their analysis technique is based
on a mathematical model of the pipelined Intel 80C188 processor. This model takes into account
the overlap between instruction execution and opcode prefetching in 80C188. In their approach,
the WCET of each basic block in a program is individually calculated based on the mathematical
model. The WCET of the program is then calculated using the WCETs of the constituent basic
blocks and timing formulas for calculating the WCETs of various language constructs.
Although this approach represents significant progress over the previous schemes that did not
consider the timing effects of pipelined execution, it still suffers from two inefficiencies. First, the
pipelining effects across basic blocks are not accurately accounted for. In general, due to data
dependencies and resource conflicts within the execution pipeline, a basic block's execution time
will differ depending on what the surrounding basic blocks are. However, since their approach
requires that the WCET of each basic block be independently calculated, they make the worst
case assumption on the preceding basic block (e.g., the last instruction of every basic block that
can precede the basic block being analyzed has data memory access, which prevents the opcode
prefetching of the first instruction of the basic block being analyzed). This assumption is reasonable
for their target processor since its pipeline has only two stages. However, completely ignoring
pipelining effects across basic blocks may yield a very loose WCET estimation for more deeply
pipelined processors. Second, although their mathematical model is very effective for the Intel
80C188 processor, the model is not general enough to be applicable to other pipelined processors.
This is due to the many machine specific assumptions made in their model that are difficult to
generalize.
1 A basic block is a sequence of consecutive instructions in which flow of control enters at the beginning and leaves
at the end without halt or possibility of branching except at the end [17].
B. Timing Analysis of Cache Memory
Cache memories have been widely used to bridge the speed gap between processor and main memory.
However, designers of hard real-time systems are wary of using caches in their systems since the
performance of caches is considered to be unpredictable. This concern stems from the following
two sources: inter-task interference and intra-task interference. Inter-task interference is caused by
task preemption. When a task is preempted, most of its cache blocks 2 are displaced by the newly
scheduled task and the tasks scheduled thereafter. When the preempted task resumes execution, it
makes references to the previously displaced blocks and experiences a burst of cache misses. This
type of cache miss cannot be avoided in real-time systems with preemptive scheduling of tasks. The
result is a wide variation in task execution time. This execution time variation can be eliminated
by partitioning the cache and dedicating one or more partitions to each real-time task [2, 3]. This
cache partitioning approach eliminates the inter-task interference caused by task preemption.
Intra-task interference in caches occurs when more than one memory block of the same task
compete with each other for the same cache block. This interference results in two types of cache
miss: capacity misses and conflict misses [19]. Capacity misses are due to finite cache size. Conflict
misses, on the other hand, are caused by a limited set associativity. These types of cache miss
cannot be avoided if the cache has a limited size and/or set associativity.
Among the analytical WCET prediction schemes that we are aware of, only four schemes take
into account the timing variation resulting from intra-task cache interference (three for instruction
caches [10, 9, 7] and one for data caches [14]). The static cache simulation approach which statically
predicts hits or misses of instruction references is due to Arnold, Mueller, Whalley and Harmon [10].
In this approach, instructions are classified into the following four categories based on a data flow
analysis:
ffl always-hit: The instruction is always in the cache.
ffl always-miss: The instruction is never in the cache.
ffl first-hit: The first reference to the instruction hits in the cache. However, all the subsequent
references miss in the cache.
A block is the minimum unit of information that can be either present or not present in the cache-main memory
hierarchy [18].
.
if (cond)
elsek
Fig. 1. Sample C program fragment
ffl first-miss: The first reference to the instruction misses in the cache. However, all the subsequent
references hit in the cache.
This approach is simple but has a number of limitations. One limitation is that the analysis is too
conservative. As an example, consider the program fragment given in Fig. 1. Assume that both of
the instruction memory blocks corresponding to S i (i.e., are mapped to the same
cache block and that no other instruction memory block is mapped to that cache block. Further
assume that the execution time of S i is much longer than that of S j . Under these assumptions, the
worst case execution scenario of this program fragment is to repeatedly execute S i within the loop.
In this worst case scenario, only the first access to b i will miss in the cache and all the subsequent
accesses within the loop will hit in the cache. However, by being classified as always-miss, all the
references to b i are treated as cache misses in this approach, which leads to a loose estimation of the
loop's WCET. Another limitation of this approach is that the approach does not address the issues
regarding pipelined execution and the use of data caches, which are commonly found in most RISC
processors.
In [9], Niehaus et al. discuss the potential benefits of identifying instruction references corresponding
to always-hit and first-miss in the static cache simulation approach. However, as stated
in [10], their analysis is rather abstract and no general method for analyzing the worst case timing
behavior of programs is given.
In [7], Liu and Lee propose techniques to derive WCET bounds of a cached program based on
a transition diagram of cached states. Their WCET analysis uses an exhaustive search technique
through the state transition diagram which has an exponential time complexity. To reduce the time
complexity of this approach, they propose a number of approximate analysis methods each of which
makes a different trade-off between the analysis complexity and the tightness of the resultant WCET
bounds. Although the paper mentions that the methods are equally applicable to the data cache, the
main focus is on the instruction cache since the issues pertinent to the data cache such as handling
of write references and references with unknown addresses (cf. Section V) are not considered. Also,
it is not clear how one can incorporate the analysis of pipelined execution into the framework.
Rawat performs a static analysis for data caches [14]. His approach is similar to the graph
coloring approach to register allocation [20]. The analysis proceeds as follows. First, live ranges of
variables and those of memory blocks are computed 3 . Second, an interference graph is constructed
for each cache block. An edge in the interference graph connects two memory blocks if they are
mapped to the same cache block and their live ranges overlap with each other. Third, live ranges
of memory blocks are split until they do not overlap with each other. If a live range of a memory
block does not overlap with that of any other memory block, the memory block never gets replaced
from the cache during execution within the live range. Therefore, the number of cache misses due
to a memory block can be calculated from the frequency counts of its live ranges (i.e., how many
times the program control flows into the live ranges). Finally, the total number of data cache misses
is estimated by summing up the frequencies of all the live ranges of all the memory blocks used in
the program.
Although this analysis method is a step forward from the analysis methods in which every data
reference is treated as a cache miss, it still suffers from the following three limitations. First, the
analysis does not allow function calls and global variables, which severely limits its applicability.
Second, the analysis leads to an overestimation of data cache misses resulting from the assumption
that every possible execution path can be the worst case execution path. This limitation is similar
to the first limitation of the static cache simulation approach. The third limitation of this approach
is that it does not address the issues of locating the worst case execution path and of calculating
the WCET, again limiting its applicability.
3 A live range of a variable (memory block) is a set of basic blocks during whose execution the variable (memory
potentially resides in the cache [14].
RD
IF
ALU
MD
mult $25, $24
nop
lw $24, 16($22)
nop
lw $25, 16($23)
Fig. 2. Sample MIPS assembly code and the corresponding reservation table
III PIPELINING EFFECTS
In pipelined processors, various execution steps of instructions are simultaneously overlapped. Due
to this overlapped execution, an instruction's execution time will differ depending on what the
surrounding instructions are. However, this timing variation could not be accurately accounted for
in the original timing schema since the timing information associated with each program construct
is a simple time-bound. In this section, we extend the timing schema to rectify this problem.
In our extended timing schema, the timing information of each program construct is a set of
reservation tables rather than a time-bound. The reservation table was originally proposed to describe
and analyze the activities within a pipeline [21]. In a reservation table, the vertical dimension
represents the stages in the pipeline and the horizontal dimension represents time. Fig. 2 shows a
sample basic block in the MIPS assembly language [22] and the corresponding reservation table. In
the figure, each x in the reservation table specifies the use of the corresponding stage for the indicated
time slot. In the proposed approach, we analyze the timing interactions among instructions
within a basic block by building its reservation table. In the reservation table, not only the conflicts
in the use of pipeline stages but also data dependencies among instructions are considered.
A program construct such as an if statement may have more than one execution path. Moreover,
in pipelined processors, it is not always possible to determine which one of the execution paths is
the worst case execution path by analyzing the program construct alone. As an example, suppose
that an if statement has two execution paths corresponding to the two reservation tables shown in
Fig. 3. The worst case execution path here depends on the instructions in the preceding program
constructs. For example, if one of the instructions near the end of the preceding program construct
uses the MD stage, the execution path corresponding to R 1 will become the worst case execution
path. On the other hand, if there is an instruction using the DIV stage instead, the execution path
corresponding to R 2 will become the worst case execution path. Therefore, we should keep both
ALU
RD
IF
MD
Fig. 3. Two reservation tables with equal
struct pipeline timing information f
time t max;
reservation table head[ffi head ];
reservation table tail[ffi tail ];
d
d
MD
RD
head
tail
Fig. 4. Reservation table data structure
reservation tables until the timing information of the preceding program constructs is known.
Fig. 4 shows the data structure for a reservation table used in our approach in both textual
and graphical form. In the data structure, t max is the worst case execution time of the reservation
table, which is determined by the number of columns in the reservation table. In implementation,
not all the columns in the reservation table are maintained. Instead, we maintain only a first few
(i.e., columns and a last few (i.e., ffi tail ) columns. The larger ffi head and ffi tail are, the tighter
the resulting WCET estimation is since more execution overlap between program constructs can be
modeled as we will see later. corresponds to the case where the full reservation
table is maintained.
As explained earlier, we associate with each program construct a set of reservation tables where
each reservation table contains the timing information of an execution path that might be the worst
case execution path of the program construct. We call this set the WCTA (Worst Case Timing
Abstraction) of the program construct. This WCTA corresponds to the time-bound in the original
timing schema and each element in the WCTA is denoted by (t
With this framework, the timing schema can be extended so that the timing interactions across
ALU
RD
MD
IF
ALU
RD
IF
MD
ALU
RD
IF
MD
Fig. 5. Example application of \Phi operation
program constructs can be accurately accounted for. In the extended timing schema, the timing
formula of a sequential statement S:
are the WCTAs of S, S 1 and S 2 , respectively. The operation
between two WCTAs is defined as
are reservation tables and the \Phi operation concatenates two reservation tables
resulting in another reservation table. This concatenation operation models the pipelined execution
of a sequence of instructions followed by another sequence of instructions. The semantics of this
operation for a target processor can be deduced from its data book. Fig. 5 shows an application of
the \Phi operation. From the figure, one can note that as more columns are maintained in head and
tail, more overlap between adjacent program constructs can be modeled and, therefore, a tighter
WCET estimation can be obtained.
The above timing formula for S: effectively enumerates all the possible candidates for
the worst case execution path of S 1 However, during each instantiation of this timing formula,
a check is made to see whether the resulting WCTA can be pruned. An element in a WCTA can be
removed from the WCTA if we can guarantee that that element's WCET in the worst case scenario is
shorter than the best case scenario WCET of some other element in the same WCTA. This pruning
condition can be more formally specified as follows:
A reservation table w in a WCTA W can be pruned without affecting the prediction for
the worst case timing behavior of W if
In this condition, w:t max is w's execution time when we assume the worst case scenario for w (i.e.,
when no part of w's head and tail is overlapped with the surrounding program constructs). On
the other hand, w tail is the execution time of w 0 when we assume the best case
scenario for w 0 (i.e., when its head is completely overlapped with the tail of the preceding program
construct and its tail is completely overlapped with the head of the succeeding program construct).
The timing formula of an if statement S: if (exp) then S 1 else S 2 is given by
are the WCTAs of S, exp, S 1 and S 2 , respectively and
S is the set union operation. As in the previous timing formula, pruning is performed during each
instantiation of this timing formula.
Function calls are processed like sequential statements. In our approach, functions are processed
in a reverse topological order in the call graph 4 since the WCTA of a function should be calculated
before the functions that call it are processed.
4 A call graph contains the information on how functions call each other [23]. For example, if f calls g, then an arc
connects f 's vertex to that of g in their call graph.
Finally, the timing formula of a loop statement S: while (exp) S 1 is given by
where N is a loop bound that is provided by some external means (e.g., from user input). This timing
formula effectively enumerates all the possible candidates for the worst case execution scenario of
the loop statement. This approach is exact but is computationally intractable for a large N . In the
following, we provide approximate methods for loop timing analysis.
Approximate Loop Timing Analysis The problem of finding the worst case execution scenario
for a loop statement with loop bound N can be formulated as a problem to find the longest
weighted path (not necessarily simple) containing exactly N arcs in a weighted directed graph. Thus,
the approximate loop timing analysis method is explained using a graph theoretic formulation.
be a weighted directed graph where is the set of the
execution paths in the loop body that might be the worst case execution path (i.e., those in
associated with each arc is weight w ij which is the execution time of path
its execution is immediately preceded by path p i . Define D ';i;j as the weight of the longest
path (not necessarily simple) from p i to p j in G containing exactly ' arcs. With this definition, the
t max of the loop's worst case execution scenario that starts with path p i and ends with path p j is
given by p i :t max +DN \Gamma1;i;j where p i :t max is t max of path p i . The WCTA of this worst case execution
scenario inherits p i 's head since it starts with p i . Likewise, it inherits p j 's tail. From these, the
of the loop's worst case execution scenario that starts with path p i and ends with path p j ,
which is denoted by wcta(wp N
ij ), is given by (p i :t Since the actual
worst case execution scenario of the loop depends on the program constructs surrounding the loop
statement, we do not know with which paths the actual worst case execution scenario starts and
ends when we analyze the loop statement. Therefore, one has to consider all the possibilities. The
corresponding WCTA of the loop statement is given by (
(exp). The
only remaining problem is to determine DN \Gamma1;i;j . We determine the value by solving the following
equations.
pk 2P
Computation of D ';i;j for all using dynamic programming takes O(N \ThetajP
time. For a large N , this time complexity is still unacceptable. In the following, we describe a faster
technique that gives a very tight upper bound for D ';i;j . This technique is based on the calculation
of the maximum cycle mean of G.
The maximum cycle mean of a weighted directed graph G is
ranges over all directed cycles in G and m(c) is the mean weight of c. The maximum cycle mean
can be calculated in O(jP j \Theta jAj) time, which is independent of N , using an algorithm due to
Karp [24]. Let m be the maximum cycle mean of G, then D ';i;j can safely be approximated as
We prove this in the following proposition.
Proposition 1 If D ';i;j is the maximum weight of a path (not necessarily simple) from p i to p j
containing exactly ' arcs in a complete weighted directed graph and m is the maximum
cycle mean of G, then D ';i;j - D 0
Proof . Assume for the sake of contradiction that D ';i;j is greater than ' \Theta m+ (m \Gamma w ji ). Then we
can construct a cycle containing by adding the arc from p j to p i to the path from which
D ';i;j is calculated. The arc should exist since G is a complete graph. The resulting cycle has a
mean weight greater than m since D ';i;j +w ji
m. This implies an existence of
a cycle in G whose mean weight is greater than m. This contradicts our hypothesis that m is the
maximum cycle mean of G and thus D ';i;j - ' \Theta m
Moreover, it has been shown that D 0 ';i;j \Gamma D ';i;j , which indicates the looseness of the approx-
imation, is bounded above by 3 \Theta (m \Gamma wmin ) where wmin is the minimum weight of an arc in A
[25]. We can expect this bound to be very tight since m ' wmin . (Remember that P consists of the
paths in W (exp)
that cannot be pruned by each other.)
Interference Up to now, we have assumed that tasks execute without preemption. However,
bb
contents
cache
cache
cache
Fig. 6. Sample instruction block references from a program construct
in real systems, tasks may be preempted for various reasons: preemptive scheduling, external inter-
rupts, resource contention, and so on. For a task, these preemptions are interference that breaks
in the task's execution flow. The problem regarding interference is that of adjusting the prediction
made under the assumption of no interference such that the prediction is applicable in an environment
with interference. Fortunately, the additional per-preemption delay introduced by pipelined
execution is bounded by the maximum number of cycles for which an instruction remains in the
pipeline (in MIPS R3000 it is 36 cycles in the case of the div instruction). Once this information is
available, adjusting the predictions to reflect interference can be done using the techniques explained
in [26].
IV INSTRUCTION CACHING EFFECTS
For a processor with an instruction cache, the execution time of a program construct will differ
depending on which execution path was taken prior to the program construct. This is a result of
the history sensitive nature of the instruction cache. As an example, consider a program construct
that accesses instruction blocks 5 (b 2 , b 3 , b 2 , b 4 ) in the sequence given (cf. Fig. 6). Assume that
the instruction cache has only two blocks and is direct-mapped. In a direct-mapped cache, each
instruction block can be placed exactly in one cache block whose index is given by instruction block
number modulo number of blocks in the cache.
In this example, the second reference to b 2 will always hit in the cache because the first reference
to b 2 will bring b 2 into the cache and this cache block will not be replaced in the mean time. On
5 We regard a sequence of consecutive references to an instruction block as a single reference to the instruction
block without any loss of accuracy in the analysis.
struct pipeline cache timing information f
time t max;
reservation table head[ffi head ];
reservation table tail[ffi tail ];
block address first reference[n block ];
block address last reference[n block ];
Fig. 7. Structure of an element in a
the other hand, the reference to b 4 will always miss in the cache even when b 4 was previously in the
cache prior to this program construct because the first reference to b 2 will replace b 4 's copy in the
cache. (Note that b 2 and b 4 are mapped to the same cache block in the assumed cache configuration.)
Unlike the above two references whose hits or misses can be determined by local analysis, the hit or
miss of the first reference to b 2 cannot be determined locally and is dependent on the cache contents
immediately before executing this program construct. Similarly, the hit or miss of the reference
to b 3 will depend on the previous cache contents. The hits or misses of these two references will
affect the (worst case) execution time of this program construct. Moreover, the cache contents after
executing this program construct will, in turn, affect the execution time of the succeeding program
construct in a similar way. These timing variations, again, cannot be accurately represented by a
simple time-bound of the original timing schema.
This situation is similar to the case of pipelined execution discussed in the previous section
and, therefore, we adopt the same strategy; we simply extend the timing information of elements
in the WCTA leaving the timing formulas intact. Each element in the WCTA now has two sets
of instruction block addresses in addition to t max , head, and tail used for the timing analysis of
pipelined execution. Fig. 7 gives the data structure for an element in the WCTA in this new setting
where n block denotes the number of blocks in the cache.
In the given data structure, the first set of instruction block addresses (i.e., first reference)
maintains the instruction block addresses of the references whose hits or misses depend on the
cache contents prior to the program construct. In other words, this set maintains for each cache
block the instruction block address of the first reference to the cache block. The second set (i.e.,
last reference) maintains the addresses of the instruction blocks that will remain in the cache
after the execution of the program construct. In other words, this set maintains for each cache block
head
tail
bb
first-reference
last-referenceX X
ALU
RD
IF
MD
RD
ALU
MD
Fig. 8. Contents of the element corresponding to the example in Fig. 6
the instruction block address of the last reference to the cache block. These are the cache contents
that will determine the hits or misses of the instruction block references in the first reference
of the succeeding program construct. In calculating t max , we accurately account for the hits and
misses that can be locally determined such as the second reference to b 2 and the reference to b 4 in the
previous example. However, the instruction block references whose hits or misses are not known (i.e.,
those in first reference) are conservatively assumed to miss in the cache in the initial estimate of
t max . This initial estimate is later refined as the information on the hits or misses of those references
becomes available at a later stage of the analysis. Fig. 8 shows the timing information maintained
for the program construct given in the previous example.
With this extension, the timing formula of S:
This timing formula is structurally identical to the one given in the previous section for the sequential
statement. The differences are in the structure of the elements in the WCTAs and in the semantics
of the \Phi operation. The revised semantics of the \Phi operation is procedurally defined in Fig. 9.
The function concatenate given in the figure concatenates two input elements
puts the result into w 3 , thus implementing the \Phi operation. In lines 9-12 of function concatenate,
first reference if the corresponding cache block is accessed in w 1 . If the cache
block is not accessed in w 1 , the first reference to the cache block in w 1 \Phi w 2 is from w 2 . Therefore,
struct pipeline cache timing information
concatenate(struct pipeline cache timing information w 1 ,
3 struct pipeline cache timing information w 2 )
struct pipeline cache timing information w 3 ;
8 for
9 if (w 1
.first reference[i] == NULL)
.first reference[i];
else
.first reference[i];
.last reference[i] == NULL)
.last reference[i];
else
.last
.last reference[i];
.last reference[i] == w 2 .first reference[i])
.head
22 w 3
26 g
Fig. 9. Semantics of the \Phi operation
would inherit w 2 's first reference. Likewise, in lines 13-16, w 3 inherits w 2 's last reference
if the corresponding cache block is accessed in w 2 or w 1 's last reference otherwise. By comparing
first reference with w 1 's last reference, lines 17-18 determine how many of the memory
references in w 2 's first reference will hit in the cache. These cache hits are used to refine w 3 's
(Remember that all the memory references in w 2 's first reference were previously assumed
to miss in the cache in the initial estimate of w 2 's t max .) In lines 20-21, w 3 inherits w 1 's head and
taking into account the pipelined execution across w 1
and w 2 and the cache hits determined in lines 17-18. In this calculation, the \Phi pipeline operation is
the \Phi operation defined in the previous section for the timing analysis of pipelined execution and
miss penalty is the time needed to service a cache miss.
As before, an element in a WCTA can safely be eliminated (i.e., pruned) from the WCTA if we
can guarantee that the element's WCET is always shorter than that of some other element in the
same regardless of what the surrounding program constructs are. This condition for pruning
is procedurally specified in Fig. 10. The function prune given in the figure checks whether either one
struct pipeline cache timing information
prune(struct pipeline cache timing information w 1 ,
3 struct pipeline cache timing information w 2 )
7 for
8 if (w 1 .first reference[i] != w 2 .first reference[i])
9 n diff ++;
.last reference[i] != w 2 .last reference[i])
else
else
19 return NULL;
Fig. 10. Semantics of pruning operation
of the two execution paths corresponding to the two input elements can be pruned and
returns the pruned element if the pruning is successful and null if neither of them can be pruned.
In the function prune, lines 6-12 determine how many entries in w 1 's first reference and
last reference are different from the corresponding entries in w 2 's first reference and
last reference. The difference bounds the cache memory related execution time variation between
checks whether w 2 can be pruned by w 1 . Pruning of w 2 by w 1 can be
made if w 2 's WCET assuming the worst case scenario for w 2 is shorter than w 1 's WCET assuming
best case scenario. Likewise, line 16 checks whether w 1 can be pruned by w 2 .
Again as before, the timing formula of S: if (exp) then S 1 else S 2 is given by
As in the previous section, the problem of calculating W (S) for a loop statement S: while (exp)
S 1 can be formulated as a graph theoretic problem. Here, wcta(wp N
ij ) is given by
:first reference; p j :last reference)
After calculating wcta(wp N
can be computed as follows:
The loop timing analysis discussed in the previous section assumes that each loop iteration benefits
only from the immediately preceding loop iteration. This is because in the calculation of w ij , we only
consider the execution time reduction of p j due to the execution overlap with p i . This assumption
holds in the case of pipelined execution since the execution time of an iteration's head is affected
only by the tail of the immediately preceding iteration. In the case of cache memory, however,
the assumption does not hold in general. For example, an instruction memory reference may hit to
a cache block that was loaded into the cache in an iteration other than the immediately preceding
one. Nevertheless, since the assumption is conservative, the resulting worst case timing analysis is
safe in the sense that the result does not underestimate the WCET of the loop statement. The
degradation of accuracy resulting from this conservative assumption can be reduced by analyzing a
sequence of k (k ? 1) iterations at the same time rather than just one iteration [25]. In this case,
each vertex represents an execution of a sequence of k iterations and w ij is the execution time of
sequence j when its execution is immediately preceded by an execution of sequence i . This analysis
corresponds to the analysis of the loop unrolled k times and trades increased analysis complexity
for more accurate
a) Set associative caches: Up to now we have considered only the simplest cache organization
called the direct-mapped cache in which each instruction block can be placed exactly in one cache
block. In a more general cache organization called the n-way set associative cache, each instruction
block can be placed in any one of the n blocks in the mapped set 6 . Set associative caches need a
policy that decides which block to replace among the blocks in the set to make room for a block
fetched on a cache miss. The LRU (Least Recently Used) policy is typically used for that purpose.
Once this replacement policy is given (assuming that it is not random), it is straightforward to
implement \Phi and prune operations needed in our analysis method.
6 In a set associative cache, the index of the mapped set is given by instruction block number modulo number of
sets in the cache.
The timing analysis of data caches is analogous to that of instruction caches. However, the former
differs from the latter in several important ways. First, unlike instruction references, the actual
addresses of some data references are not known at compile-time. This complicates the timing
analysis of data caches since the calculation of first reference and last reference, which is
the most important aspect of our cache timing analysis, assumes that the actual address of every
memory reference is known at compile-time. This complication, however, can be avoided completely
if a simple hardware support in the form of one bit in each load/store instruction is available. This
bit, called allocate bit, decides whether the memory block fetched on a miss will be loaded into
the cache. For a data reference whose address cannot be determined at compile-time, the allocate
bit is set to zero preventing the memory block fetched on a miss from being loaded into the cache.
For other references, this bit is set to one allowing the fetched block to be loaded into the cache.
With this hardware support, the worst case timing analysis of data caches can be performed very
much like that of instruction caches, i.e. treating the references whose addresses are not known at
compile-time as misses and completely ignoring them in the calculation of first reference and
last reference. Even when such hardware support is not available, the worst case timing analysis
of data caches is still possible by taking two cache miss penalties for each data reference whose
address cannot be determined at compile-time, and then ignoring the reference in the analysis [27].
The one cache miss penalty is due to the fact that the reference may miss in the cache. The other
is due to the fact that the reference may replace a cache block that contributes a cache hit in our
analysis.
The second difference stems from accesses to local variables. In general, data area for local
variables of a function, called the activation record of the function, is pushed and popped on a
runtime stack as the associated function is called and returned. In most implementations, a specially
designated register, called sp (Stack Pointer), marks the top of the stack and each local variable
is addressed by an offset relative to sp. The offsets of local variables are determined at compile-
time. However, the sp value of a function differs depending on from where the function is called.
However, the number of distinct sp values a function may have is bounded. Therefore, the
of a function can be computed for each sp value the function may have. Such sp values can be
calculated from the activation record sizes of functions and the call graph.
The final difference is due to write accesses. Unlike instruction references, which are read-only,
data references may both read from and write to memory. In data caches, either write-through or
write-back policy is used to handle write accesses [18]. In the write-through policy, the effect of each
write is reflected on both the block in the cache and the block in main memory. On the other hand,
in the write-back policy, the effect is reflected only on the block in the cache and a dirty bit is set
to indicate that the block has been modified. When a block whose dirty bit is set is replaced from
the cache, the block's contents are written back to main memory.
The timing analysis of data caches with the write-through policy is relatively simple. One simply
has to add a delay to each write access to account for the accompanying write access to main memory.
However, the timing analysis of data caches with the write-back policy is slightly more complicated.
In a write-back cache, a sequence of write accesses to a cached memory block without a replacement
in-between, which we call a write run, requires only one write-back to main memory. We attribute
this write-back overhead (i.e., delay) to the last write in the write run, which we call the tail of
the write run. With this setting, one has to determine whether a given write access can be a tail
to accurately estimate the delay due to write-backs. In some cases, local analysis can determine
whether a write access is a tail or not as in the case of hit/miss analysis for a memory reference.
However, local analysis is not sufficient to determine whether a write access is a tail in every case.
Hence, when this is not possible, we conservatively assume that the write access is a tail and add a
write-back delay to t max . However, if later analysis over the program syntax tree reveals that the
write access is not a tail, we subtract the incorrectly attributed write-back delay from t max . This
global analysis can be performed by providing a few bits to each block in first reference and
last reference and augmenting the \Phi and pruning operations [27].
VI EXPERIMENTAL RESULTS
We tested whether our extended timing schema approach could produce useful WCET bounds by
building a timing tool based on the approach and comparing the WCET bounds predicted by the
timing tool to the measured times. Our timing tool consists of a compiler and a timing analyzer (cf.
Fig. 11). The compiler is a modified version of an ANSI C compiler called lcc [28]. The modified
compiler accepts a C source program and generates the assembly code along with the program syntax
information and the call graph. The timing analyzer uses the assembly code and the program syntax
WCET
WCEP
Modified
Information
User-provided
Graph
Call
Information
Program
Code
Assembly
Program Analyzer
Timing
Fig. 11. Overview of the timing tool
information along with user-provided information (e.g., loop bound) to compute the WCET of the
program.
We chose an IDT7RS383 board as the timing tool's target machine. The target machine's CPU is
a 20 MHz R3000 processor which is a typical RISC processor. The R3000 processor has a five-stage
integer pipeline and an interface for off-chip instruction and data caches. It also has an interface for
an off-chip Floating-Point Unit (FPU).
The IDT7RS383 board contains instruction and data caches of 16 Kbytes each. Both caches are
direct-mapped and have block sizes of 4 bytes. The data cache uses the write-through policy and has
a one-entry deep write buffer. The cache miss service times of both the instruction and data caches
are 4 cycles. The FPU used in the board is a MIPS R3010. Although the board has a timer chip that
provides user-programmable timers, their resolutions are too low for our measurement purposes. To
facilitate the measurement of program execution times in machine cycles, we built a daughter board
that consists of simple decoding circuits and counter chips, and provides one user-programmerable
timer. The timer starts and stops by writing to specific memory locations and has a resolution of
one machine cycle (50 ns).
Three simple benchmark programs were chosen: Clock, Sort and MM. The Clock benchmark is a
program used to implement a periodic timer. The program periodically checks 20 linked-listed timers
and, if any of them expires, calls the corresponding handler function. The Sort benchmark sorts an
array of 20 integer numbers and the MM program multiplies two 5 \Theta 5 floating-point matrices.

Table

1 compares the WCET bounds predicted by the timing tool and the measured execution
times for the three benchmark programs. In all three cases, the tool gives fairly tight WCET bounds
(within a maximum of about 30% overestimation). A closer inspection of the results revealed that
Clock Sort MM
Predicted
Measured 2768 11471 6346
(unit: machine cycles)

Table

1. Predicted and measured execution times of the benchmark programs
more than 90% of the overestimation is due to data references whose addresses are not known at
compile-time. (Remember that we have to account for two cache miss penalties for each such data
reference.)
Program execution time is heavily dependent on the program execution path, and the logic of
most programs severely limits the set of possible execution paths. However, we intentionally chose
benchmark programs that do not suffer from overestimation due to infeasible paths. The rationale
behind this selection is that predicting tighter WCET bounds by eliminating infeasible paths using
dynamic path analysis is an issue orthogonal to our approach and that this analysis can be introduced
into the existing timing tool without modifying the extended timing schema framework. In fact, a
method for analyzing dynamic program behavior to eliminate infeasible paths of a program within
the original timing schema framework is given in [29] and we feel that our timing tool will equally
benefit from the proposed method.
We view our experimental work reported here as an initial step toward validating our extended
timing schema approach. Clearly, much experimental work, especially with programs used in real
systems, need to follow to demonstrate that our approach is practical for realistic systems.
VII CONCLUSION
In this paper, we described a technique that aims at accurately estimating the WCETs of tasks
for RISC processors. In the proposed technique, two kinds of timing information are associated
with each program construct. The first type of information is about the factors that may affect the
timing of the succeeding program construct. The second type of information is about the factors
that are needed to refine the execution time of the program construct when the first type of timing
information of the preceding program construct becomes available at a later stage of WCET analysis.
We extended the existing timing schema using these two kinds of timing information so that we can
accurately account for the timing variations resulting from the history sensitive nature of pipelined
execution and cache memory. We also described an optimization that minimizes the overhead of
the proposed technique by pruning the timing information associated with an execution path that
cannot be part of the worst case execution path.
We also built a timing analyzer based on the proposed technique and compared the WCET
bounds of sample programs predicted by the timing analyzer to their measured execution times.
The timing analyzer gave fairly tight predictions (within a maximum of about 30% overestimation)
for the benchmark programs we used and the sources of the overestimation were identified.
The proposed technique has the following advantages. First, the proposed technique makes
possible an accurate analysis of combined timing effects of pipelined execution and cache memory,
which, previously, was not possible. Second, the timing analysis using the proposed technique is
more accurate than that of any other technique we are aware of. Third, the proposed technique
is applicable to most RISC processors with in-order issue and single-level cache memory. Finally,
the proposed technique is extensible in that its general rule may be used to model other machine
features that have history sensitive timing behavior. For example, we used the underlying general
rule to model the timing variation due to write buffers [27].
One direction for future research is to investigate whether or not the proposed technique applies
to more advanced processors with out-of-order issue [30] and/or multi-level cache hierarchies
[18]. Another research direction is in the development of theory and methods for the design of a
retargetable timing analyzer. Our initial investigation on this issue was made in [31]. The results
indicated that the machine-dependent components of our timing analyzer such as the routines that
implement the concatenation and pruning operations of the extended timing schema can be automatically
generated from an architecture description of the target processor. The details of the
approach are not repeated here and interested readers are referred to [31].



--R

"Reasoning About Time in Higher-Level Language Software,"
"SMART (Strategic Memory Allocation for Real-Time) Cache Design,"
"Software-Based Cache Partitioning for Real-time Applications,"
"Timing Analysis of Superscalar Processor Programs Using ACSR,"
"High-Level Timing Specification of Instruction-Level Parallel Processors,"
"A Retargetable Technique for Predicting Execution Time,"
"Deterministic Upperbounds of the Worst-Case Execution Times of Cached Programs,"
"Evaluating Tight Execution Time Bounds of Programs by Annotations,"
"Predictable Real-Time Caching in the Spring System,"
"Bounding Worst-Case Instruction Cache Performance,"
"Portable Execution Time Analysis for RISC Processors,"
"Experiments with a Program Timing Tool Based on Source-Level Timing Schema,"
"Calculating the MaximumExecution Time of Real-Time Programs,"
"Static Analysis of Cache Performance for Real-Time Programming,"

"Pipelined Processors and Worst-Case Execution Times,"

Computer Architecture: A Quantitative Approach.
Aspects of Cache Memory and Instruction Buffer Performance.
"Register Allocation by Priority-based Coloring,"
The Architecture of Pipelined Computers.
Englewood Cliffs
Crafting a Compiler with C.
"A Characterization of the Minimum Cycle Mean in a Digraph,"
"Instruction Cache and Pipelining Analysis Technique for Real-Time Systems,"
Predicting Deterministic Execution Times of Real-Time Programs
"Data Cache Analysis Techniques for Real-Time Systems,"
"A Code Generation Interface for ANSI C,"
"Predicting Program Execution Times by Analyzing Static and Dynamic Program Paths,"
"Look-ahead Processors,"
"Retargetable Timing Analyzer for RISC Processors,"
--TR

--CTR
Hassan Aljifri , Alexander Pons , Moiez Tapia, The estimation of the WCET in super-scalar real-time system, Real-time system security, Nova Science Publishers, Inc., Commack, NY,
Jan Staschulat , Rolf Ernst, Scalable precision cache analysis for preemptive scheduling, ACM SIGPLAN Notices, v.40 n.7, July 2005
Minsoo Ryu , Jungkeun Park , Kimoon Kim , Yangmin Seo , Seongsoo Hong, Performance re-engineering of embedded real-time systems, ACM SIGPLAN Notices, v.34 n.7, p.80-86, July 1999
Dongkun Shin , Jihong Kim , Seongsoo Lee, Low-energy intra-task voltage scheduling using static timing analysis, Proceedings of the 38th conference on Design automation, p.438-443, June 2001, Las Vegas, Nevada, United States
Xianfeng Li , Abhik Roychoudhury , Tulika Mitra, Modeling out-of-order processors for WCET analysis, Real-Time Systems, v.34 n.3, p.195-227, November  2006
Jurgen Schnerr , Oliver Bringmann , Wolfgang Rosenstiel, Cycle Accurate Binary Translation for Simulation Acceleration in Rapid Prototyping of SoCs, Proceedings of the conference on Design, Automation and Test in Europe, p.792-797, March 07-11, 2005
Dongkun Shin , Jihong Kim , Seongsoo Lee, Intra-Task Voltage Scheduling for Low-Energy, Hard Real-Time Applications, IEEE Design & Test, v.18 n.2, p.20-30, March 2001
Jrn Schneider , Christian Ferdinand, Pipeline behavior prediction for superscalar processors by abstract interpretation, ACM SIGPLAN Notices, v.34 n.7, p.35-44, July 1999
Sheayun Lee , Sang Lyul Min , Chong Sang Kim , Chang-Gun Lee , Minsuk Lee, Cache-Conscious Limited Preemptive Scheduling, Real-Time Systems, v.17 n.2-3, p.257-282, Nov. 1999
Henrik Theiling, Generating Decision Trees for Decoding Binaries, ACM SIGPLAN Notices, v.36 n.8, p.112-120, Aug. 2001
Joosun Hahn , Rhan Ha , Sang Lyul Min , Jane W.-S. Liu, Analysis of Worst Case DMA Response Time in a Fixed-Priority Bus Arbitration Protocol, Real-Time Systems, v.23 n.3, p.209-238, November 2002
Tobias Schuele , Klaus Schneider, Abstraction of assembler programs for symbolic worst case execution time analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
Thomas Lundqvist , Per Stenstrm, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999
Daniel Kstner , Stephan Thesing, Cache Aware Pre-Runtime Scheduling, Real-Time Systems, v.17 n.2-3, p.235-256, Nov. 1999
Colin Fidge , Peter Kearney , Mark Utting, A Formal Method for Building Concurrent Real-Time Software, IEEE Software, v.14 n.2, p.99-106, March 1997
Henrik Theiling , Christian Ferdinand , Reinhard Wilhelm, Fast and Precise WCET Prediction by Separated Cache andPath Analyses, Real-Time Systems, v.18 n.2-3, p.157-179, May 2000
Joan Krone , William F. Ogden , Murali Sitaraman, Performance analysis based upon complete profiles, Proceedings of the 2006 conference on Specification and verification of component-based systems, November 10-11, 2006, Portland, Oregon
Jungkeun Park , Minsoo Ryu , Seongsoo Hong , Lucia Lo Bello, Rapid performance re-engineering of distributed embedded systems via latency analysis and k-level diagonal search, Journal of Parallel and Distributed Computing, v.66 n.1, p.19-31, January 2006
Andreas Ermedahl , Friedhelm Stappert , Jakob Engblom, Clustered Worst-Case Execution-Time Calculation, IEEE Transactions on Computers, v.54 n.9, p.1104-1122, September 2005
Xianfeng Li , Tulika Mitra , Abhik Roychoudhury, Modeling control speculation for timing analysis, Real-Time Systems, v.29 n.1, p.27-58, January 2005
Friedhelm Stappert , Andreas Ermedahl , Jakob Engblom, Efficient longest executable path search for programs with complex flows and pipeline effects, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA
Andreas Ermedahl , Friedhelm Stappert , Jakob Engblom, Clustered calculation of worst-case execution times, Proceedings of the international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA
Sheayun Lee , Jaejin Lee , Chang Yun Park , Sang Lyul Min, Selective code transformation for dual instruction set processors, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.2, p.10-es, May 2007
Gustavo Gmez , Yanhong A. Liu, Automatic time-bound analysis for a higher-order language, ACM SIGPLAN Notices, v.37 n.3, p.75-86, March 2002
Ian J. Hayes, Procedures and parameters in the real-time program refinement calculus, Science of Computer Programming, v.64 n.3, p.286-311, February, 2007
Karl Lermer , Colin J. Fidge , Ian J. Hayes, A theory for execution-time derivation in real-time programs, Theoretical Computer Science, v.346 n.1, p.3-27, 23 November 2005
Y. A. Liu , G. Gmez, Automatic Accurate Cost-Bound Analysis for High-Level Languages, IEEE Transactions on Computers, v.50 n.12, p.1295-1309, December 2001
C. J. Fidge, Real-Time Schedulability Tests for Preemptive Multitasking, Real-Time Systems, v.14 n.1, p.61-93, Jan. 1998
Christian Ferdinand , Reinhard Wilhelm, Efficient and Precise Cache Behavior Prediction for Real-TimeSystems, Real-Time Systems, v.17 n.2-3, p.131-181, Nov. 1999
Vasanth Venkatachalam , Michael Franz, Power reduction techniques for microprocessor systems, ACM Computing Surveys (CSUR), v.37 n.3, p.195-237, September 2005
pipelined execution;cache memory;worst case execution time;real-time system;RISC processor