Chao Chen and Giovanni Beltrame
Article (2017)
|
Open Access to the full text of this document Accepted Version Terms of Use: Tous droits réservés Download (831kB) |
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: | 27 Sep 2024 07:20 |
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 |
---|---|
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions