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

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



Publication details

Title of host publicationDesign Automation and Test Europe (DATE 2014)
DatePublished - Mar 2014
Number of pages6
Original languageEnglish
ISBN (Print)9781479932979


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.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations