Soutenance mémoire
Mesure du temps d’exécution, méthodes dynamiques
En théorie, étant données une architecture hôte et une tâche, son profil temporel exact peut être obtenu en effectuant une mesure pour chacune des valeurs de données d’entrée et toutes les configurations environnementales, bref pour toute combinaison possible de facteurs de variation. Des méthodes génétiques [101] ont été proposées pour diriger la recherche d’une configuration optimale, maximisant le temps d’exécution de la tâche étudiée. L’algorithme génétique [29] travaille sur une population composée de jeux d’entrées pour une tâche donnée. Cette population subit de façon itérative des évolutions avec l’objectif de converger vers une solution produisant le pire temps d’exécution. Toutefois, un tel algorithme peut se retrouver piégé autour d’un minima local, dans une zone restreinte de l’espace des solutions, quand un minimum global est requis pour satisfaire à la propriété de sûreté de la solution. Un autre axe de recherche est l’exploration et la mesure du temps d’exécution sur la totalité des chemins possibles de l’application cible [105]. Pour réduire le nombre de cas explorés, des conditions de validité sur l’ensemble des chemins évalués ont été proposées, p. ex. « chaque instruction est exécutée au moins une fois par un des chemins de l’ensemble » Mais des conditions trop précises posent un problème de complexité vis-à-vis du nombre de configurations à explorer. Si les méthodes dynamiques en reproduisant un environnement d’exécution répondent à la contrainte de précision, le pire cas peut toujours éluder la mesure en cas d’exploration non exhaustive des configurations possibles [102] ; pour des systèmes réalistes, le nombre de configurations à considérer est souvent trop important pour qu’une exploration exhaustive soit applicable [79]. Ces méthodes conviennent pour la validation de systèmes temps-réel souples où un comportement divergent de celui estimé met seulement en jeu la qualité de service. Elles s’avèrent aussi utiles pour une estimation rapide du comportement temporel d’applications. Il est à noter que les mesures peuvent être difficiles à réaliser car requérant le matériel hôte et un mécanisme d’observation ne perturbant pas les résultats obtenus (probe effect [28]).
Méthodes à base d’arbres syntaxiques
Les méthodes à base d’arbres [79, 18] représentent le flot du programme sous la forme d’un arbre de syntaxe abstraite extrait le plus souvent depuis le code source. Les nœuds de cet arbre représentent les différentes structures de contrôle du langage source, notamment boucles et branchements conditionnels. Par extension, les feuilles de l’arbre sont des blocs de base. Ceux-ci sont pondérés par leur pire temps d’exécution obtenu par l’analyse de bas niveau. Le pire temps d’une application est calculé lors d’un parcours de bas en haut de l’arbre correspondant. Pour obtenir le poids d’un nœud, une règle de combinaison dépendante de son type est utilisée. Dans l’exemple 1.1, le poids de la structure conditionnelle if est le poids de la plus lourde de ses branches, while ou BB4, sommé à celui de l’évaluation de sa condition BB1. Les méthodes à base d’arbres ont l’avantage de la simplicité et de la rapidité de calcul. Leur proximité de la structure du programme permet l’identification des structures sensibles et coûteuses. Cette même proximité implique la restriction de la représentation à des programmes correctement formés [82], pour lesquels une relation hiérarchique entre les blocs de base est définie. Ceci est un inconvénient
Exemple 1.1 – Représentation de programmes
Un simple programme est ici présenté conjointement à sa représentation sous la forme d’un arbre syntaxique et d’un graphe de flot de contrôle. Ce code est composé d’une boucle imbriquée dans une conditionnelle, elle-même suivi d’une séquence d’instructions. Cinq blocs de base ont été identifiés correspondant respectivement : 1 à l’évaluation de la condition, 2 à la tête de la boucle, 3 au corps de la boucle, 4 à la branche else de la conditionnelle, et 5 à des instructions consécutives à la conditionnelle.
Analyse multi-niveau de caches de données
Le comportement temporel pire cas d’une instruction vis-à-vis de la hiérarchie mémoire dépend des latences qu’elle subit et donc des niveaux de cache auxquels cette dernière accède. L’estimation de ce comportement d’accès requiert la connaissance du comportement succès ou défaut de l’instruction pour chaque niveau. À son tour, cette connaissance repose sur une estimation du contenu à l’exécution des caches de la hiérarchie. Une fois obtenue, la contribution temporelle de l’instruction est intégrée dans une analyse de haut niveau visant à calculer un pire chemin d’exécution. Les méthodes mentionnées par la suite travaillent à la granularité des références mémoire de l’application analysée. Une référence mémoire est la distinction d’une instruction mémoire dans un contexte d’appel connu. La plage d’adresses ciblée par chaque référence mémoire est estimée statiquement au cours d’une phase d’analyse d’adresses non détaillée dans ce document. Cette plage d’adresses peut, pour des raisons de sûreté, inclure plusieurs blocs mémoire quand la cible exacte d’une référence n’est pas connue statiquement. De plus, les méthodes présentées sont ici introduites pour des hiérarchies de caches associatifs par ensemble. Celles-ci sont gérées selon une politique de type mostly-inclusive pour lesquelles ni l’inclusion ni l’exclusion des contenus de caches de niveaux différents ne sont maintenues ; une requête mémoire traverse la hiérarchie jusqu’à trouver la donnée accédée et la charge dans tous les niveaux traversés. Les caches analysés mettent en œuvre une politique de remplacement lru favorisée pour sa prédictibilité. Les écritures en cache sont supposées propagées à tous les niveaux de la hiérarchie (write-through) sans allocation en cache en cas de défaut (write-no-allocate).
Heuristiques pour le bypass
Pour une instruction, le choix de court-circuiter ou non un niveau de cache n’est pas anodin. Cette décision entraîne des répercussions sur le comportement des références mémoire suivantes. Certaines peuvent devenir des défauts si elles utilisaient le bloc inséré par l’instruction. Mais à l’inverse, si l’instruction en courtcircuit participait à l’éviction d’un bloc utile, certaines références mémoire peuvent se résoudre en succès suite au bypass. Explorer l’ensemble des configuration de bypass de chacune des instructions du programme, pour sélectionner la meilleure, est toutefois trop complexe. En lieu et place, nous définissons des heuristiques permettant d’atteindre pour un niveau de cache donné une décision locale à chaque instruction de chargement mémoire. Les deux premières heuristiques reposent sur l’estimation de la réutilisation des blocs chargés par l’instruction. La troisième heuristique repose sur les résultats de l’analyse d’adresses et la nature des structures accédées. Pour une heuristique x, la décision de bypass pour l’instruction inst et le niveau de cache L est formalisée par Bypassx(inst, L). Bypassx(inst, L) est true (vrai) si l’instruction inst court-circuite le niveau de cache L selon l’heuristique x. À l’inverse, Bypassx(inst, L) = f alse si l’instruction inst ne court-circuite pas le niveau de cache L.
|
Table des matières
Introduction 1
1 État de l’art sur l’estimation du comportement temporel pire-cas de la hiérarchie mémoire
1.1 Estimation de pire temps d’exécution
1.1.1 Mesure du temps d’exécution, méthodes dynamiques
1.1.2 Méthodes d’analyse statique
1.1.3 Méthodes hybrides pour analyse temporelle
1.2 Analyse bas niveau, comportement temporel des caches
1.2.1 Architecture et propriétés des caches
1.2.2 Analyse statique du comportement temporel au pire cas d’un cache
1.2.3 Améliorer la prédictibilité des caches
1.3 Discussion
2 Comportement pire-cas des caches de données partagés en contexte multi-cœur
2.1 Analyse multi-niveau de caches de données
2.1.1 Analyse d’un niveau de cache
2.1.2 Classification d’accès au cache (cac)
2.1.3 Estimation de la contribution temporelle au pire cas des caches
2.2 Impact des interférences sur les analyses de caches de données
2.2.1 Estimation des conflits de cache inter-tâches
2.2.2 Prise en compte des conflits durant l’analyse des caches
2.2.3 Classification des accès aux données partagées
2.3 Réduction des conflits pour les caches partagés, utilisation du bypass
2.3.1 Calcul des réutilisations entre accès mémoire
2.3.2 Heuristiques pour le bypass
2.3.3 Analyse de statique caches de données avec du bypass
2.4 Expérimentations
2.4.1 Conditions expérimentales
2.4.2 Caches de données en environnement uni-cœur
2.4.3 Caches de données en environnement multi-cœur
3 PRETI : Caches partitionnés pour environnements temps-réel
3.1 Fondements de la politique de partitionnement preti
3.1.1 Politiques d’accès et de mise à jour du cache
3.1.2 Implémentation du partitionnement
3.1.3 Analyse de caches partitionnés avec preti
3.2 Expérimentations
3.2.1 Conditions expérimentales
3.2.2 Impact de preti sur l’ordonnançabilité des systèmes
3.2.3 Impact de preti sur les performances mesurées des tâches
3.3 Étendre le comportement des caches preti
3.3.1 Restriction des accès aux données partagées
3.3.2 Contrôle de la croissance des partitions
3.3.3 Extensions à d’autres politiques de remplacement, au delà du lru
Conclusion
Télécharger le rapport complet
