Abstract
In this paper, we investigate Static Probabilistic
Timing Analysis (SPTA) for single processor systems that use a
cache with an evict-on-miss random replacement policy. We show
that previously published formulae for the probability of a cache
hit can produce results that are optimistic and unsound when used
to compute probabilistic Worst-Case Execution Time (pWCET)
distributions.
We investigate the correctness, optimality, and precision of
dierent approaches to SPTA. We prove that one of the previously
published formulae for the probability of a cache hit is optimal
with respect to the limited information that it uses. We improve
upon this formulation by using extra information about cache
contention. To investigate the precision of various approaches to
SPTA, we introduce a simple exhaustive method that computes
a precise pWCET distribution, albeit at the cost of exponential
complexity. Further, we integrate this precise approach, applied
to small numbers of frequently accessed memory blocks, with
imprecise analysis of other memory blocks, to form a combined
approach that improves precision, without significantly increasing
its complexity. The performance of the various approaches are
compared on benchmark programs.
Timing Analysis (SPTA) for single processor systems that use a
cache with an evict-on-miss random replacement policy. We show
that previously published formulae for the probability of a cache
hit can produce results that are optimistic and unsound when used
to compute probabilistic Worst-Case Execution Time (pWCET)
distributions.
We investigate the correctness, optimality, and precision of
dierent approaches to SPTA. We prove that one of the previously
published formulae for the probability of a cache hit is optimal
with respect to the limited information that it uses. We improve
upon this formulation by using extra information about cache
contention. To investigate the precision of various approaches to
SPTA, we introduce a simple exhaustive method that computes
a precise pWCET distribution, albeit at the cost of exponential
complexity. Further, we integrate this precise approach, applied
to small numbers of frequently accessed memory blocks, with
imprecise analysis of other memory blocks, to form a combined
approach that improves precision, without significantly increasing
its complexity. The performance of the various approaches are
compared on benchmark programs.
| Original language | English |
|---|---|
| Title of host publication | Design Automation and Test Europe (DATE 2014) |
| Publisher | IEEE |
| Pages | 117-122 |
| Number of pages | 6 |
| ISBN (Print) | 9781479932979 |
| Publication status | Published - Mar 2014 |