1. Static probabilistic timing analysis for real-time systems using random replacement caches
- Author
-
Robert I. Davis, Sebastian Altmeyer, Liliana Cucu-Grosjean, System and Network Engineering (IVI, FNWI), University of Luxembourg [Luxembourg], Models and methods of analysis and optimization for systems with real-time and embedding constraints (AOSTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), University of York [York, UK], BGLE Departs, LEOC Capacites, European Project: 611085,EC:FP7:ICT,FP7-ICT-2013-10,PROXIMA(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
- Subjects
Control and Optimization ,Correctness ,Computer Networks and Communications ,Computer science ,Real-time computing ,Probabilistic logic ,Parallel computing ,Reuse ,Upper and lower bounds ,Computer Science Applications ,Control and Systems Engineering ,Simple (abstract algebra) ,Modeling and Simulation ,Benchmark (computing) ,[INFO.INFO-ES]Computer Science [cs]/Embedded Systems ,Cache ,Electrical and Electronic Engineering ,ddc:004 ,Cache algorithms - Abstract
International audience; 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.
- Published
- 2015
- Full Text
- View/download PDF