By the same authors

From the same journal

From the same journal

Static probabilistic timing analysis for real-time systems using random replacement caches

Research output: Contribution to journalArticlepeer-review

Author(s)

Department/unit(s)

Publication details

JournalReal-Time Systems
DateE-pub ahead of print - 13 Jan 2015
Issue number1
Volume51
Number of pages40
Pages (from-to)77-123
Original languageEnglish

Abstract

In this paper, we investigate static probabilistic timing analysis (SPTA) for single processor real-time 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 different approaches to SPTA for random replacement caches. We prove that one of the previously published formulae for the probability of a cache hit is optimal with respect to the limited information (reuse distance and cache associativity) that it uses. We derive an alternative formulation that makes use of additional information in the form of the number of distinct memory blocks accessed (the stack distance). This provides a complementary lower bound that can be used together with previously published formula to obtain more accurate analysis. We improve upon this joint approach 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. 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 complexity. The performance of the various approaches are compared on benchmark programs. We also make comparisons against deterministic analysis of the least recently used replacement policy.

    Research areas

  • worst-case execution time (WCET) analysis, probabilistic analysis, REAL-TIME, cache memories, random replacement

Discover related content

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

View graph of relations