362
W. Chang et al.
This technique starts from a control flow graph (CFG) and then sets up the
equations to compute the reaching cache states (RCS) and live cache states (LCS) of
each node, based on which the fixed-point computation is performed. Afterwards,
the guaranteed WCET reduction can be calculated [3, 4]. We will begin our
discussion with some basics.
In the two-level memory hierarchy shown in Fig. 7.1, there are N c cache lines,
denoted as CL =
c 0 , c 1 , . . . , c N c −1
and the flash main memory has N m blocks,
denoted as M =
m 0 , m 1 , . . . , m N m −1
. Each memory block is mapped to a fixed
cache line. A basic block is a straight-line sequence of code with only one entry
point and one exit point. This restriction makes a basic block highly amenable for
program analysis. There are three key terms in memory analysis that are described
as follows:
• Cache states: A cache state cs is described as a vector of N c elements. Each
element cs[i], where i ∈ {0, 1, . . . , N c − 1}, represents the memory block in
the cache line c i . When the cache line c i holds the memory block m j , where
j ∈ {0, 1, . . . , N m − 1}, cs[i] = m j . If c i is empty, it is denoted as cs[i] = ⊥. If the
memory block is unknown, it is denoted as cs[i] = . CS is the set of all possible
cache states.
• Reaching cache states: RCS of a basic block b k , denoted as F CS b k , is the set of
all possible cache states when b k is reached via any incoming path.
• Live cache states: LCS of a basic block b k , denoted as LCS b k , is the set of all
possible first memory references to cache lines at b k via any outgoing path.
Since the focus is on WCET reduction between two consecutive executions of
C i , e.g., C i (1) and C i (2), it is necessary to compute the RCS of the exit point in
C i (1) and the LCS of the entry point in C i (2). By comparing all possible pairs of
cache states, the guaranteed number of cache hits and thus WCET reduction can
be calculated. Conceptually, the program RCS is the set of all possible cache states
after the program finishes execution by any execution path, and the program LCS
is the set of all cache states, where each cache state contains memory blocks that
may be firstly referenced after the program starts execution, for any execution path
to follow. Both the RCS and LCS could contain multiple cache states. Each pair
with one cache state cs from the program RCS and one cache state cs
from the
program LCS represents one possible execution path between the two consecutive
executions. For any cache line c i in a pair, if cs[i] is equal to cs
[i] and they are not
equal to , then there is certainly a hit and thus WCET reduction.
As discussed in the introduction, CPS often run TT OS due to the safety-critical
nature. We will take OSEK/VDX OS, which is a class of RTOS widely used
in the automotive industry, as an example. In general, OSEK/VDX OS supports
preemptive fixed-priority scheduling. That is, priorities are assigned to applications
and at any point in time, the task with the highest priority among all active ones
is executed. Tasks can be triggered by events (e.g., interrupts, alarms, etc.) or by
time. In the TT scheme, each application gets released and is allowed to access
the processor periodically. There are various periods of release times and each
W. Chang et al.
This technique starts from a control flow graph (CFG) and then sets up the
equations to compute the reaching cache states (RCS) and live cache states (LCS) of
each node, based on which the fixed-point computation is performed. Afterwards,
the guaranteed WCET reduction can be calculated [3, 4]. We will begin our
discussion with some basics.
In the two-level memory hierarchy shown in Fig. 7.1, there are N c cache lines,
denoted as CL =
c 0 , c 1 , . . . , c N c −1
and the flash main memory has N m blocks,
denoted as M =
m 0 , m 1 , . . . , m N m −1
. Each memory block is mapped to a fixed
cache line. A basic block is a straight-line sequence of code with only one entry
point and one exit point. This restriction makes a basic block highly amenable for
program analysis. There are three key terms in memory analysis that are described
as follows:
• Cache states: A cache state cs is described as a vector of N c elements. Each
element cs[i], where i ∈ {0, 1, . . . , N c − 1}, represents the memory block in
the cache line c i . When the cache line c i holds the memory block m j , where
j ∈ {0, 1, . . . , N m − 1}, cs[i] = m j . If c i is empty, it is denoted as cs[i] = ⊥. If the
memory block is unknown, it is denoted as cs[i] = . CS is the set of all possible
cache states.
• Reaching cache states: RCS of a basic block b k , denoted as F CS b k , is the set of
all possible cache states when b k is reached via any incoming path.
• Live cache states: LCS of a basic block b k , denoted as LCS b k , is the set of all
possible first memory references to cache lines at b k via any outgoing path.
Since the focus is on WCET reduction between two consecutive executions of
C i , e.g., C i (1) and C i (2), it is necessary to compute the RCS of the exit point in
C i (1) and the LCS of the entry point in C i (2). By comparing all possible pairs of
cache states, the guaranteed number of cache hits and thus WCET reduction can
be calculated. Conceptually, the program RCS is the set of all possible cache states
after the program finishes execution by any execution path, and the program LCS
is the set of all cache states, where each cache state contains memory blocks that
may be firstly referenced after the program starts execution, for any execution path
to follow. Both the RCS and LCS could contain multiple cache states. Each pair
with one cache state cs from the program RCS and one cache state cs
from the
program LCS represents one possible execution path between the two consecutive
executions. For any cache line c i in a pair, if cs[i] is equal to cs
[i] and they are not
equal to , then there is certainly a hit and thus WCET reduction.
As discussed in the introduction, CPS often run TT OS due to the safety-critical
nature. We will take OSEK/VDX OS, which is a class of RTOS widely used
in the automotive industry, as an example. In general, OSEK/VDX OS supports
preemptive fixed-priority scheduling. That is, priorities are assigned to applications
and at any point in time, the task with the highest priority among all active ones
is executed. Tasks can be triggered by events (e.g., interrupts, alarms, etc.) or by
time. In the TT scheme, each application gets released and is allowed to access
the processor periodically. There are various periods of release times and each