Static Probabilistic Timing Analysis for Multi-path Programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 over-approximation 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.
Original languageEnglish
Title of host publicationIEEE Real-Time Systems Symposium (RTSS)
Publication statusPublished - Dec 2015
Event35th IEEE Real-Time Systems Symposium (RTSS 2015) - , United Kingdom
Duration: 1 Dec 20154 Dec 2015


Conference35th IEEE Real-Time Systems Symposium (RTSS 2015)
Country/TerritoryUnited Kingdom

Cite this