Analyse d’Applications Flot de Données pour la
Compilation Multiprocesseur
Les systèmes embarqués
Un système embarqué est un équipement électronique et informatique spécialisé dans une tâche précise. Il est autonome et limité en taille, en consommation électrique, et en dissipation thermique. Les premiers systèmes embarqués firent leur apparition dans les années soixante ; ils étaient particulièrement coûteux, et n’étaient utilisés que dans les domaines de l’aérospatiale et de l’armement. Par la suite, ces systèmes furent appliqués à des domaines bien plus vastes, aujourd’hui ils sont incontournables. Qu’il s’agisse d’un simple réveil-matin ou d’une automobile, d’un téléphone ou d’un téléviseur, tous ces équipements contiennent un ou plusieurs systèmes embarqués ou, plus communément, System on Chip (SoC). Un système embarqué se divise en deux parties, l’une matérielle (l’électronique), l’autre logicielle (l’informatique). Le matériel délimite les interfaces et les performances du système tandis que le logiciel définit la ou les fonctions réalisées par ce système. La complexité matérielle de ces équipements n’a cessé de croître, et les systèmes embarqués actuels comptent souvent plusieurs unités de calcul leur permettant de traiter des opérations en simultané. Ce sont des Multi-Processor System on Chip (MPSoC). La société Kalray propose notamment une architecture embarquée composée de plus de 256 cœurs de calcul et plus d’une vingtaine d’interfaces différentes. Avec une dissipation thermique proche de 5 Watt, ce processeur est alors parmi les plus performants du marché. Cependant, les outils de conception logicielle actuels ne sont pas adaptés à ces architectures multicœurs. Pour cette raison, la société Kalray a aussi fait le choix de proposer la chaîne de compilation AccessCore. Il s’agit d’un outil de conception adapté à cette architecture. Il est accompagné d’un langage de programmation dit dataflow (ou flot de données) appelé le ΣC.
La programmation dataflow
Les modèles de programmation standards sont généralement séquentiels. Ils définissent un programme par une succession d’opérations. Dans le programme de la Figure 1.1 page ci-contre, les opérations op1, op2, op3 et op4 vont ainsi se succéder infiniment. Des dépendances entre ces opérations sont induites par cet ordre d’exécution. L’exécution parallèle de ces opérations n’est donc pas naturelle. 2 1 while ( true ) { 2 out1 = op1 ( input) ; 3 out2 = op2 ( out1) ; 4 out3 = op3 ( out1) ; 5 output = op4 ( out2 , out3) ; 6 } C. La modélisation dataflow pallie ce problème de parallélisation en permettant de spécifier clairement les dépendances de données entre les différentes opérations. Un dataflow modélise une application sous forme d’un graphe dans lequel, chaque nœud est une tâche (ou un ensemble d’opérations), et les arcs sont des canaux de communication entre ces tâches. La Figure 1.2 est un exemple de dataflow. On remarque que ces différentes tâches peuvent alors s’exécuter en parallèle.Pour certains modèles dataflows, les quantités de données produites et consommées dans ces canaux sont prédéterminées : on parle de modèles statiques. Le principal intérêt de ces modèles statiques est de permettre leur analyse sans avoir à effectuer de simulation. Le langage ΣC (proposé par la société Kalray) permet de décrire des applications sous forme d’un dataflow statique particulier : le modèle Cyclo-Static Dataflow Graph (CSDFG). La chaîne de compilation AccessCore est ainsi en mesure d’évaluer a priori les performances d’un programme ou l’espace mémoire nécessaire à son exécution. Cependant, les CSDFG extraits à partir des applications ΣC sont trop grands pour nous permettre d’utiliser des techniques d’analyse exactes. La complexité de ces méthodes est trop élevée. L’objectif principal de cette thèse est d’apporter des solutions d’analyse efficaces pour la chaîne de compilation AccessCore. Compte tenu de l’ampleur de ce travail, nous avons concentré nos efforts sur trois axes distincts : – le test de vivacité, – l’évaluation du débit maximal, 3 CHAPITRE 1. INTRODUCTION – et le dimensionnement mémoire. La vivacité Lorsqu’il n’y a pas suffisamment de données pour exécuter les tâches d’un dataflow, celui-ci peut atteindre un état de blocage. Si cet état de blocage n’existe pas, on dit alors qu’une application est vivante. Nous proposons une méthode efficace pour vérifier cette propriété pour le modèle CSDFG. L’évaluation du débit maximal Si chaque tâche d’une application dataflow a une durée d’exécution maximale connue (souvent nommée le Worst Case Execution Time), il est possible d’évaluer la vitesse de fonctionnement maximale de cette application. Nous proposons une solution d’évaluation approchée de cette valeur. Le dimensionnement mémoire L’espace disponible pour faire circuler des données dans les canaux de communication d’un dataflow est en théorie infini. Ce n’est plus vrai pour de véritables applications. Nous cherchons alors à déterminer la quantité minimale de mémoire nécessaire pour qu’une application puisse fonctionner correctement et atteigne les performance attendues. Nous proposons différents algorithmes dans ce sens.
Plan de la thèse et contributions
Dans le chapitre 2, nous mettons en avant le contexte et les motivations de nos travaux. Nous y présentons l’architecture MPPA et la chaîne de compilation AccessCore, deux produits commercialisés par la société Kalray. Nous commençons par fournir une classification des différentes architectures embarquées existantes. Nous présentons ensuite les principaux outils disponibles pour programmer ces architectures. Dans un second temps, nous considérons la modélisation dataflow comme une solution efficace de la programmation parallèle, et nous énumérons quelques-uns des modèles dataflows utilisés aujourd’hui. Nous terminons alors sur la présentation de la chaîne de compilation AccessCore, et nous situons les étapes sur lesquelles portent nos contributions. Dans le chapitre 3, nous spécifions les problématiques concernées par nos travaux. Nous définissons tout d’abord des résultats d’analyse fondamentaux, puis nous énumérons un à un chaque problème étudié. Pour chacun, nous considérons les méthodes existantes pour 4 les résoudre. Nous remarquons alors que toutes les techniques d’analyse exactes appliquées aux CSDFG se basent sur un ordonnancement au plus tôt. Ce type d’ordonnancement exécute chaque tâche d’un dataflow dès qu’elle dispose de suffisamment de données en entrée. La suite de ce manuscrit s’articule en deux parties. La première partie traite de nos contributions les plus théoriques, qui portent sur l’ordonnancement des modèles dataflows. Dans la seconde partie, ces résultats sont appliqués à l’analyse des modèles CSDFG. Nous détaillons les travaux d’intégration de ces méthodes dans la chaîne de compilation AccessCore.
Première partie
Le premier chapitre de cette partie, le chapitre 4, présente une méthode polynomiale pour vérifier la faisabilité de l’ordonnancement périodique d’un CSDFG. Il s’agit d’une contribution fondamentale pour nos travaux, et pour le domaine de l’ordonnancement des modèles CSDFG. Contrairement aux ordonnancements au plus tôt, qui peuvent être de taille exponentielle, la définition d’un ordonnancement périodique est de taille polynomiale. Dans ce chapitre, nous prouvons que le calcul d’un ordonnancement périodique pour un CSDFG est un problème polynomial. Ce résultat est important ; il va nous permettre, dans la suite de nos travaux, d’appliquer les ordonnancements périodiques à l’analyse des dataflows, et de fournir des techniques approchées bien plus rapides que les méthodes exactes connues (puisque la complexité des ordonnancements périodiques est bien plus faible que celle des ordonnancements au plus tôt). La méthode d’ordonnancement précédemment proposée ne nous permet d’obtenir que des solutions d’analyse approchées. Pour améliorer nos résultats, nous étudions dans le chapitre 5 une nouvelle approche : les ordonnancements K-périodiques. Pour tout ordonnancement K-périodique, l’on doit définir un vecteur de périodicité K. Ainsi, plus les valeurs contenues dans ce vecteur sont pertinentes, plus l’ordonnancement K-périodique généré peut être précis. De cette manière, cette famille d’ordonnancement généralise les ordonnancements périodiques (avec un vecteur de périodicité minimal) et au plus tôt (avec un vecteur de taille maximale). Nous proposons une technique de calcul d’un ordonnancement K-périodique pour un vecteur périodicité fixé, et nous étudions l’impact du vecteur de périodicité sur les performances des ordonnancements obtenus. Il est important de noter que le contexte industriel de nos travaux a fortement influencé la direction de ces recherches. Les résultats théoriques d’ordonnancement obtenus ici furent donc appliqués à l’analyse des applications ΣC. La seconde partie de cette thèse est consacrée à ces applications.
Deuxième partie
Le premier chapitre de cette partie, le chapitre 6, présente les différents problèmes d’analyse traités tout au long de cette thèse. Il définit différents algorithmes, et présente les expérimentations réalisées pour évaluer leurs performances. Dans un premier temps, nous proposons un nouvel outil utilisé pour générer nos jeux de test. Puis, dans la continuité des travaux de Benazouz [11], nous proposons une solution algorithmique pour tester la vivacité d’un CSDFG. Nous proposons ensuite une méthode d’évaluation du débit d’un CSDFG ainsi qu’une méthode de dimensionnement mémoire d’un CSDFG. Ces techniques appliquent alors directement les contributions exposées dans le chapitre 4. Après le développement de ces différentes solutions d’analyse, nous avons considéré leur intégration dans la chaîne de compilation AccessCore. Le chapitre 7 porte sur cette intégration. En effet, le langage dataflow proposé par la société Kalray est en perpétuelle évolution. Bien qu’il respecte toujours les contraintes d’un modèle statique, il ne correspond plus à la définition d’un modèle CSDFG. Certaines contraintes supplémentaires sur l’exécution des tâches furent notamment ajoutées. Pour intégrer avec succès les différentes méthodes d’analyse proposées dans le chapitre précédent, il était donc nécessaire d’étendre nos méthodes à ce modèle plus expressif. Pour finir, dans le chapitre 8, nous concluons ce manuscrit et proposons différentes pistes d’amélioration. Nous envisageons également l’application de nos approches à d’autres domaines. Dans les dernières pages, nous proposons également un index des notations utilisées dans ce mémoire.
Liste des tableaux |
