article IA

Reliable and precise WCET Determination for a real-life processor

WCET : Worst Case Execution Time


I Introduction

Garantir des contraintes de temps fortes dans les système temps réel -> timing validation

Toutes les techniques d'analyse d'ordonnancement repose sur la connaissance du WCET de toutes les tâches avant l'exécution. Ces estimations doivent être sûres (ne jamais sous-estimer le temps réel d'exécution) et les plus fines possibles (la surestimation doît être faible possible).

Pour les processeurs ayant pour chacune de leurs instructions un temps d'exécution fixe, des méthodes existent déjà pour calculer des WCET précis.

Dans les architectures de processeurs modernes, les caches et les pipelines sont les principales technologies pour améliorer les performances.

Caches -> permettent de passer outre la lenteur de la mémoire vive par rapport à la vitesse de calcul des processeurs.

Pieplines -> permettent le chevauchement de plusieurs instructions.

De ce fait, il n'est plus possible d'analyser séparément l'exécution des instructions puisque l'ordre d'exécution entre en compte.

Les approches classiques d'estimation par WCET ne sont pas directement applicables ou produisent des résultats dépassant le temps réel d'exécution BY OVER 9000 (by orders of magnitude), ce qui n'est acceptable.

II The USES approach to WCET computation

Aspects principaux : 

- Modularité.
- choix de méthode appropriées.
- généricité

Phases de la détermination du WCET : 

- Calcul des plages d'adresse pour les instructions accédant à la mémoire par une analyse des valeurs.
- Classification des références mémoires en cache hit / cache miss (analyse de cache).
- Prédiction du comportement du programme dans le pipeline du processeur (analyse de pipeline).
- Détermination du chemin du WCET (analyse de chemin).

Ces taches sont complexes pour les processeurs modernes et les DSPs (microprocesseur optimisé pour les calculs), les combiner en une seule analyse renforce encore la complexité.

On séquencera donc les analyses:

analyse des valeurs (IA) -> analyse des caches (IA) -> analyse des pipelines (IA) -> analyse des chemins (integer linear programmation).

Sérialisation des sous-tâches : ok si pas de dépendances  cycliques, peut entraîner des pertes de précision, en partie dûes à l'utilisation de l'analyse statique de programme (inévitable avec les méthodes statiques).