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

Altmeyer Sebastian 1 Liliana Cucu-Grosjean 2 Robert Davis 2, 3
2 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper, we investigate Static Probabilistic Timing Analysis (SPTA) for sin- gle 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 dis- tance 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 preci- sion 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 ap- proaches are compared on benchmark programs. We also make comparisons against deter- ministic analysis of the Least Recently Used (LRU) replacement policy.
Type de document :
Article dans une revue
Real-Time Systems, Springer Verlag, 2015, 51 (1), pp.77-123. <10.1007/s11241-014-9218-4>


https://hal.inria.fr/hal-01244349
Contributeur : Liliana Cucu <>
Soumis le : mardi 15 décembre 2015 - 16:14:34
Dernière modification le : mardi 5 janvier 2016 - 14:45:20

Identifiants

Collections

Citation

Altmeyer Sebastian, Liliana Cucu-Grosjean, Robert Davis. Static probabilistic timing analysis for real-time systems using random replacement caches . Real-Time Systems, Springer Verlag, 2015, 51 (1), pp.77-123. <10.1007/s11241-014-9218-4>. <hal-01244349>

Partager

Métriques

Consultations de la notice

91