- Static Probabilistic Timing Analysis for Multi-path Programs
- 36th Real-Time Systems Symposium: RTSS 2015
- Book/source title
- Proceedings: 2015 IEEE 36th Real-Time Systems Symposium: RTSS 2015: 1-4 December 2015, San Antonio, Texas, USA
- Pages (from-to)
- Los Alamitos, CA: IEEE Computer Society
- Document type
- Conference contribution
- Faculty of Science (FNWI)
- Informatics Institute (IVI)
This paper introduces an effective Static Probabilistic Timing Analysis (SPTA) for multi-path programs. The analysis estimates the temporal contribution of an evict-on-miss, random replacement cache to the probabilistic Worst-Case Execution Time (pWCET) distribution of multi-path programs. The analysis uses a conservative join function that provides a proper overapproximation of the possible cache contents and the pWCET distribution on path convergence, irrespective of the actual path followed during execution. Simple program transformations are introduced that reduce the impact of path indeterminism while ensuring sound pWCET estimates. Evaluation shows that the proposed method is efficient at capturing locality in the cache, and substantially outperforms the only prior approach to SPTA for multi-path programs based on path merging. The evaluation results show incomparability with analysis for an equivalent deterministic system using an LRU cache.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.