On the Correctness, Optimality and Precision of Static Probabilistic Timing Analysis

Sebastian Altmeyer, Robert Ian Davis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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)
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 languageEnglish
Title of host publicationDesign Automation and Test Europe (DATE 2014)
Number of pages6
ISBN (Print)9781479932979
Publication statusPublished - Mar 2014

Cite this