<  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)

Open Access document in PolyPublie
Open Access to the full text of this document
Accepted Version
Terms of Use: Tous droits réservés
Download (831kB)
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

Subjects: 2700 Information technology > 2713 Algorithms
2700 Information technology > 2714 Mathematics of computing
Department: Department of Computer Engineering and Software Engineering
PolyPublie URL: https://publications.polymtl.ca/2777/
Journal Title: ACM Transactions on Design Automation of Electronic Systems (vol. 23, no. 1)
Publisher: ACM
DOI: 10.1145/3123877
Official URL: https://doi.org/10.1145/3123877
Date Deposited: 02 Oct 2017 11:43
Last Modified: 08 Apr 2024 02:37
Cite in APA 7: 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), 1-24. https://doi.org/10.1145/3123877


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item