rusted/article IA

## 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 aussi faible que 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
=================================================

Technique largement utilisée pour déterminer les propriétés d'exécution d'un programme sans avoir à l'exécuter réellement.


Interprétation abstraite : théorie d'approximation de la sémantique de programmes informatiques, afin de prouver des critères de correction et de terminaison.
Une analyse de programme est considéré comme une abstraction de la sémantique du langage de programmation.

La sémantique d'un langage est donné par un domaine concret de donnée et un ensemble de fonctions décrivant comment les instructions du langage modifie les données.

La sémantique abstraite consiste en un domaine abstrait plus simple, et un ensemble de fonctions de transfert, pour évaluer les instructions dans le domaine abstrait.

le domaine abstrait est obtenu en abstrayant autant que nécessaire les caractéristiques du domaine réel, en sachant que les domaines sont principalement des treillis de valeurs avec un ordre partiel.
Dans cet article l'ordre correspond à la précision, moins une donnée est précise, plus elle est élevée dans l'ordre. (Dans le cours, T = Top, la plus haute valeur, borne supérieure, ici notée U page 6)

3.1 Value analysis p6
=====================

Pour chaque registre du processeur, on a un intervale des valeurs possibles (comme dans simpleai avec range)

Pour fusionner 2 registres abstraits, on fait comme dans range, [l1,u1] U [l2,u2] = [min(l1,L2),max(u1,u2)]

Ensuite définition de l'addition, si pas d'overflow, add classique, si overflow -> val inconnue.

Cette analyse permet parfois de détecter des chemins impossibles dans le programme, en répérant des branches toujours / jamais prises. Ces infos sont fournies aux analyses du cache et du pipeline pour améliorer la qualité de l'analyse.

3.2 Cache analysis p6
=====================

2 analyses créées et implémentées de différentes façons pour correspondre aux caches existants. Un totalement associatif avec un remplacement LRU (least recently used).

Must analysis : fourni un ensemble de blocs mémoires qui sont dans le cache à un point donné du programme quand l'exéc l'atteint.

May analysis : détermine tous les blocs mém qui peuvent être dans le cache à ce point donné.

Ces 2 analyses permettent de savoir si un bloc n'est pas dans le cache.
On peut donc définir 3 cat de réf mémoire :

ah : always hit
am : always miss
nc : not classified

TODO : RESUME de MAY ET MUST ANALYSIS P7 P8

TODO : RESUME DE LOOP ET RECURSIVE PROCEDURE P8

3.3 Pipeline analysis

Encore de l'interprétation abstraite, on représente un pipeline abstrait, reflétant de manière pessimiste, afin d'avoir un WCET safe, les spécifications non documentées du pipeline.
La fonction de mise à jour du pipeline réalise l'avancement étape par étape, et prend en compte l'ensemble des états du pipeline, la file de prefetch, le groupement des instructions et la classification des réfs mémoires (cache hit/miss).

microcontroleur coldfire : Motorola M68K architecture.

Cache
=====
Cache unifié données/instructions de 8 Ko => 128 ensembles de 4 lignes de 16 octets.

algorithme de remplacement :
-si une ligne de l'ensemble contient des données invalides, on les remplace par les données demandées. Si plusieurs lignes matchent le critère, on prend celle de plus faible numéro.
-si toutes les lignes contiennent des données valides, un compteur global de remplacement est utilisé pour donner le numéro de ligne dont les données seront remplacées. Le compteur est incrémenté de 1.
-Les accès "hit" au cache ne provoquent aucune mofication du cache ou du compteur.
=> espèce de round robin
Cette politique de remplacement plutot naze fait que lors de l'interprétation abstraite, on peut seulement dire que la ligne sera présente jusqu'au prochain accès dans son ensemble.
Rien ne peut être dit sur les lignes qui peuvent être dans le cache, on ne peut pas assurer que la ligne qui peut être dans le cache a été supprimé et donc plus dans celui-ci.

Pipeline
========

2 pipelines couplés, un fetche les instructions depuis la mémoire, les décode partiellement, fait la prédiction de branche et les place dans un buffer d'instruction, une FIFO pouvant contenir 8 instructions.
Le pipeline d'exécutions est composé de 2 étages, qui fetch l'instruction complète depuis le buffer d'instructions, la décode puis l'exécute.

Le pipeline de fetching scanne l'instruction, et redirige s'il trouve un branchement inconditionel ou une branche arrière.

De ce fait, le comportement de la mémoire est très dépendant de celui du pipeline, car une prédiction de branchement incorrect conduit à des accès mémoires différents.

Le pipeline abstrait est un ensemble d'états du pipeline concret, donnant une estimation safe de l'ensemble de tous les états possibles du pipeline qui peuvent se produire à un instant donné du programme.
A partir de là on peut calculer une borne sup du nombre de cycles nécessaires pour exécuter les instructions dans le pire des cas.

2 types de signaux : immédiat -> cancel, delayed -> cycle suivant.
étage SST : stall, quand on a 2 write consécutifs, jusqu'à 2 cycles de latence.
la granularité est le cycle du pipeline.

Valeur de sortie ==> nombre de cycle qu'un bloc de base prend pour être exécuté, pour chaque context, résultats transmis à l'analyse de chemin pour obtenir le WCET de tout le programme
***ENFIN le résultat... 23h33***

4.3 Experiments
===============


Benchmark fourni par Airbus, hard real-time, fait pour ressembler à un cas réel de logiciels d'avionique => boucle infinie qui réagit à des évènements externes en activant une des 12 taches indépendantes.
Les taches sont indépendantes, chaque tache est extraite du programme principal et analysée à part, et doît tenir des contrainte de temps fortes.

Value analysis : 90+% des accès peuvent être résolus exactement + ~4% de good (moins de 16 lignes de cache) ! 1 min de calcul et 25 mo de ram sur une bécane de 14-18, Athlon 1,2 GHz.

Cache and pipeline analysis :

110 mo de ram en pointe, entre 4 et 10 min par tache, ça roxxe les licornes arc en ciel.
On a pas les nombres de cycles p/r au réel, donc ça doit être pourrave comme analyse ^^.

Conclusion
==========

Fonce, sur un malentendu, ça peut marcher.

Ce bousin est utilisé par l'usine Airbus Toulouse, les experts roxxors ont dit que ça pownait grave, et sont en train de décider s'ils vont l'utiliser pour la validation du temps d'exéc des logiciels d'avionique!

Merci, questions, non nous ne signons pas d'autographes, pas de photos.
	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 aussi faible que 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
	=================================================

	Technique largement utilisée pour déterminer les propriétés d'exécution d'un programme sans avoir à l'exécuter réellement.



	Interprétation abstraite : théorie d'approximation de la sémantique de programmes informatiques, afin de prouver des critères de correction et de terminaison.
	Une analyse de programme est considéré comme une abstraction de la sémantique du langage de programmation.

	La sémantique d'un langage est donné par un domaine concret de donnée et un ensemble de fonctions décrivant comment les instructions du langage modifie les données.

	La sémantique abstraite consiste en un domaine abstrait plus simple, et un ensemble de fonctions de transfert, pour évaluer les instructions dans le domaine abstrait.

	le domaine abstrait est obtenu en abstrayant autant que nécessaire les caractéristiques du domaine réel, en sachant que les domaines sont principalement des treillis de valeurs avec un ordre partiel.
	Dans cet article l'ordre correspond à la précision, moins une donnée est précise, plus elle est élevée dans l'ordre. (Dans le cours, T = Top, la plus haute valeur, borne supérieure, ici notée U page 6)

	3.1 Value analysis p6
	=====================

	Pour chaque registre du processeur, on a un intervale des valeurs possibles (comme dans simpleai avec range)

	Pour fusionner 2 registres abstraits, on fait comme dans range, [l1,u1] U [l2,u2] = [min(l1,L2),max(u1,u2)]

	Ensuite définition de l'addition, si pas d'overflow, add classique, si overflow -> val inconnue.

	Cette analyse permet parfois de détecter des chemins impossibles dans le programme, en répérant des branches toujours / jamais prises. Ces infos sont fournies aux analyses du cache et du pipeline pour améliorer la qualité de l'analyse.

	3.2 Cache analysis p6
	=====================

	2 analyses créées et implémentées de différentes façons pour correspondre aux caches existants. Un totalement associatif avec un remplacement LRU (least recently used).

	Must analysis : fourni un ensemble de blocs mémoires qui sont dans le cache à un point donné du programme quand l'exéc l'atteint.

	May analysis : détermine tous les blocs mém qui peuvent être dans le cache à ce point donné.

	Ces 2 analyses permettent de savoir si un bloc n'est pas dans le cache.
	On peut donc définir 3 cat de réf mémoire :

	ah : always hit
	am : always miss
	nc : not classified

	TODO : RESUME de MAY ET MUST ANALYSIS P7 P8

	TODO : RESUME DE LOOP ET RECURSIVE PROCEDURE P8

	3.3 Pipeline analysis

	Encore de l'interprétation abstraite, on représente un pipeline abstrait, reflétant de manière pessimiste, afin d'avoir un WCET safe, les spécifications non documentées du pipeline.
	La fonction de mise à jour du pipeline réalise l'avancement étape par étape, et prend en compte l'ensemble des états du pipeline, la file de prefetch, le groupement des instructions et la classification des réfs mémoires (cache hit/miss).

	microcontroleur coldfire : Motorola M68K architecture.

	Cache
	=====
	Cache unifié données/instructions de 8 Ko => 128 ensembles de 4 lignes de 16 octets.

	algorithme de remplacement :
	-si une ligne de l'ensemble contient des données invalides, on les remplace par les données demandées. Si plusieurs lignes matchent le critère, on prend celle de plus faible numéro.
	-si toutes les lignes contiennent des données valides, un compteur global de remplacement est utilisé pour donner le numéro de ligne dont les données seront remplacées. Le compteur est incrémenté de 1.
	-Les accès "hit" au cache ne provoquent aucune mofication du cache ou du compteur.
	=> espèce de round robin
	Cette politique de remplacement plutot naze fait que lors de l'interprétation abstraite, on peut seulement dire que la ligne sera présente jusqu'au prochain accès dans son ensemble.
	Rien ne peut être dit sur les lignes qui peuvent être dans le cache, on ne peut pas assurer que la ligne qui peut être dans le cache a été supprimé et donc plus dans celui-ci.

	Pipeline
	========

	2 pipelines couplés, un fetche les instructions depuis la mémoire, les décode partiellement, fait la prédiction de branche et les place dans un buffer d'instruction, une FIFO pouvant contenir 8 instructions.
	Le pipeline d'exécutions est composé de 2 étages, qui fetch l'instruction complète depuis le buffer d'instructions, la décode puis l'exécute.

	Le pipeline de fetching scanne l'instruction, et redirige s'il trouve un branchement inconditionel ou une branche arrière.

	De ce fait, le comportement de la mémoire est très dépendant de celui du pipeline, car une prédiction de branchement incorrect conduit à des accès mémoires différents.

	Le pipeline abstrait est un ensemble d'états du pipeline concret, donnant une estimation safe de l'ensemble de tous les états possibles du pipeline qui peuvent se produire à un instant donné du programme.
	A partir de là on peut calculer une borne sup du nombre de cycles nécessaires pour exécuter les instructions dans le pire des cas.

	2 types de signaux : immédiat -> cancel, delayed -> cycle suivant.
	étage SST : stall, quand on a 2 write consécutifs, jusqu'à 2 cycles de latence.
	la granularité est le cycle du pipeline.

	Valeur de sortie ==> nombre de cycle qu'un bloc de base prend pour être exécuté, pour chaque context, résultats transmis à l'analyse de chemin pour obtenir le WCET de tout le programme
	*ENFIN le résultat... 23h33*

	4.3 Experiments
	===============


	Benchmark fourni par Airbus, hard real-time, fait pour ressembler à un cas réel de logiciels d'avionique => boucle infinie qui réagit à des évènements externes en activant une des 12 taches indépendantes.
	Les taches sont indépendantes, chaque tache est extraite du programme principal et analysée à part, et doît tenir des contrainte de temps fortes.

	Value analysis : 90+% des accès peuvent être résolus exactement + ~4% de good (moins de 16 lignes de cache) ! 1 min de calcul et 25 mo de ram sur une bécane de 14-18, Athlon 1,2 GHz.

	Cache and pipeline analysis :

	110 mo de ram en pointe, entre 4 et 10 min par tache, ça roxxe les licornes arc en ciel.
	On a pas les nombres de cycles p/r au réel, donc ça doit être pourrave comme analyse ^^.

	Conclusion
	==========

	Fonce, sur un malentendu, ça peut marcher.

	Ce bousin est utilisé par l'usine Airbus Toulouse, les experts roxxors ont dit que ça pownait grave, et sont en train de décider s'ils vont l'utiliser pour la validation du temps d'exéc des logiciels d'avionique!

	Merci, questions, non nous ne signons pas d'autographes, pas de photos.