Static Probabilistic Timing Analysis for Multi-path Programs

TY - GEN

T1 - Static Probabilistic Timing Analysis for Multi-path Programs

AU - Lesage, Benjamin Michael Jean-Rene

AU - Griffin, David Jack

AU - Altmeyer, Sebastian

AU - Davis, Robert Ian

PY - 2015/12

Y1 - 2015/12

N2 - 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 ExecutionTime (pWCET) distribution of multi-path programs. The analysisuses 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 whileensuring sound pWCET estimates. Evaluation shows that theproposed method is efficient at capturing locality in the cache,and substantially outperforms the only prior approach to SPTAfor multi-path programs based on path merging. The evaluationresults show incomparability with analysis for an equivalent deterministic system using an LRU cache.

AB - 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 ExecutionTime (pWCET) distribution of multi-path programs. The analysisuses 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 whileensuring sound pWCET estimates. Evaluation shows that theproposed method is efficient at capturing locality in the cache,and substantially outperforms the only prior approach to SPTAfor multi-path programs based on path merging. The evaluationresults show incomparability with analysis for an equivalent deterministic system using an LRU cache.

M3 - Conference contribution

BT - IEEE Real-Time Systems Symposium (RTSS)

T2 - 35th IEEE Real-Time Systems Symposium (RTSS 2015)

Y2 - 1 December 2015 through 4 December 2015

ER -