<  Back to the Polytechnique Montréal portal

An adaptive Markov model for the timing analysis of probabilistic caches

Chao Chen and Giovanni Beltrame

Article (2017)

Accepted Version
Terms of Use: Tous droits réservés.
Download (1MB)
Cite this document: Chen, C. & Beltrame, G. (2017). An adaptive Markov model for the timing analysis of probabilistic caches. ACM Transactions on Design Automation of Electronic Systems, 23(1), p. 1-24. doi:10.1145/3123877
Show abstract Hide abstract


Accurate timing prediction for real-time embedded software execution is becoming a problem due to the increasing complexity of computer architecture, and the presence of mixed-criticality workloads. Probabilistic caches were proposed to set bounds to Worst Case Execution Time (WCET) estimates and help designers improve real-time embedded system resource use. Static Probabilistic Timing Analysis (SPTA) for probabilis- tic caches is nevertheless difficult to perform, because cache accesses depend on execution history, and the computational complexity of SPTA makes it intractable for calculation as the number of accesses increases. In this paper, we explore and improve SPTA for caches with evict-on-miss random replacement policy using a state space modeling technique. A nonhomogeneous Markov model is employed for single-path programs in discrete-time finite state space representation. To make this Markov model tractable, we limit the number of states and use an adaptive method for state modification. Experiments show that compared to the state-of-the-art methodology, the proposed adaptive Markov chain approach provides better results at the occurrence probability of 10^−15: in terms of accuracy, the state-of-the-art SPTA results are more conservative, by 11% more on average. In terms of computation time, our approach is not significantly different from the state-of-the-art SPTA.

Uncontrolled Keywords

Theory of computation, Probabilistic computation, Design and analysis of algorithms, Probabilistic, Real-time systems, Cache

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2713 Algorithmes
2700 Technologie de l'information > 2714 Mathématiques de l'informatique
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Date Deposited: 02 Oct 2017 11:43
Last Modified: 08 Apr 2021 10:43
PolyPublie URL: https://publications.polymtl.ca/2777/
Document issued by the official publisher
Journal Title: ACM Transactions on Design Automation of Electronic Systems (vol. 23, no. 1)
Publisher: ACM
Official URL: https://doi.org/10.1145/3123877


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only