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 p2
========================================

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).

Des caractéristiques architecturales peuvent réduire à néant la dépendance unidirectionelle en l'analyse du cache et l'analyse du pipeline : Motorola Coldfire -> 2 pipelines, 1 fetch et 1 execution couplés par un buffer d'instruction, l'ordre des réfs mémoire et les effets sur le cache dépendent du comportement du pipeline, qui lui dépend du nombre d'instructions préfetchées dans le buffer.

Generic and generative methods p3
==============================

méthode générique : méthode avec des paramètres formels non spécifiés.
approche générative : si l'implém est générée à partir d'une spécification par précalcul.


L'analyse de cache peut être implémenter génériquement en abstrayant les params taille, associativité, taille des lignes et stratégie de remplacement.

Ex : analyse de cache générique générée à partir d'une spécif générique du domaine des états de cache abstraits et d'une spécification de sémantique abstraite des fonctions.

Approche générative à l'avantage de permettre de séparer la spécification de l'implém, les spécifs étant plus facilement compréhensible que les analyses faites à la main (hand coded).

Underlying framework p4
=======================

CRL : Control flow Representation Language
ILP : integer linear programming : programmation linéaire en nombres entiers (optimisation linéaire)
Etapes : 

un parseur lit la sortie du compilateur et reconstruit le flot de contrôle, ce qui nécessite des infos sur le hardware (branchements/appels).

Ce graphe de flot de contrôle annoté est utilisé comme entrée pour l'analyse de l'archi.

L'analyse des valeurs détermine l'intervale des valeurs dans les registres et peut ainsi résoudre des accès mémoires indirects à la mémoire.
L'analyse du cache classe les accès à la mémoire centrale pour savoir si les données demandées sont dans le cache ou non.
L'analyse du pipeline modélise le comportement du pipeline pour déterminer les temps d'exéc pour une suite séquentielle d'instructions. 
==> résultat : un tps d'exécution pour chaque instruction dans chaque contexte d'exécution (??? pourquoi plusieurs contextes d'exéc ?)

Après l'analyse de la microarchitecture, l'analyse du chemin détermine une estimation sûre du WCET.
- un générateur d'ILP modélise le flot de contrôle du prog à l'aide d'un prog d'analyse linéaire, et un mapping nom de variable <=> bloc de base
- l'ILP est résolu par lp_solve
- la solution de l'ILP est évalué avec le mapping calculé plus haut, la valeur obtenue est le WCET.

III Program analysis to predict Run-time behavior
=================================================

Interprétation abstraite :