Static Probabilistic Timing Analysis for Multi-path Programs

Benjamin Lesage 1 David Griffin 1 Sebastian Altmeyer 2 Robert Davis 1, 3
3 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : This paper introduces an effective Static ProbabilisticTiming 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.
Type de document :
Communication dans un congrès
RTSS 2015 - 36th Real-Time Systems Symposium., Dec 2015, San Antonio, Texas, United States
Liste complète des métadonnées

https://hal.inria.fr/hal-01231729
Contributeur : Robert Davis <>
Soumis le : vendredi 20 novembre 2015 - 15:45:10
Dernière modification le : mardi 24 novembre 2015 - 11:59:02

Identifiants

  • HAL Id : hal-01231729, version 1

Collections

Citation

Benjamin Lesage, David Griffin, Sebastian Altmeyer, Robert Davis. Static Probabilistic Timing Analysis for Multi-path Programs. RTSS 2015 - 36th Real-Time Systems Symposium., Dec 2015, San Antonio, Texas, United States. <hal-01231729>

Partager

Métriques

Consultations de la notice

99