Je présente tout d'abord mes activités de recherche passées, et notamment les travaux effectués pendant ma thèse en évaluation de performances. J'ai travaillé sur le formalisme des réseaux d'automates stochastiques et développé de nouvelles méthodes et algorithmes pour évaluer les performances de systèmes informatiques à grand espace d'états. La section 2.2 expose mes travaux actuels. J'effectue un post-doctorat à l'université d'Edimbourg, et le projet porte sur l'évaluation des performances d'applications parallèles haut niveau pour les grilles informatiques. Mon projet de recherche est présenté en section 2.3, et la liste de mes publications se trouve en section 2.4.
Les références chiffrées se réfèrent à la liste de mes publications, alors que les références de la forme [Aut05] correspondent à des publications diverses présentes en fin de document (bibliographie).
Je décris les travaux de recherche menés pendant ma thèse, effectuée
au laboratoire Informatique et Distribution (CNRS, INPG, INRIA, UJF) à
Grenoble sur les méthodes et algorithmes pour l'évaluation des
performances de systèmes informatiques à grand espace d'états. Ces
travaux ont été encadrés par Brigitte Plateau, et ont été menés depuis
octobre 2000 jusqu'à ma soutenance de thèse en juin 2003. Ces travaux
ont été récompensés par le prix de thèse de l'INPG en février 2005.
Tout d'abord je présente le contexte de ces travaux avant de détailler
les contributions apportées. Enfin, je présente rapidement les
responsabilités que j'ai eu durant ma thèse (encadrement de
projet, ...).
Les chaînes de Markov, que ce soit à temps continu ou à temps discret, facilitent l'analyse des performances des systèmes dynamiques dans de nombreux domaines d'application [Ste94], et elles sont particulièrement bien adaptées à l'étude de systèmes parallèles et distribués. Cependant, lorsque le nombre d'états est important (de l'ordre du million d'états), il est quasiment impossible d'envisager une modélisation à plat, d'une part au niveau de la représentation du système, et d'autre part en prévision des techniques d'analyse que nous désirons appliquer pour calculer des indices de performances sur le système.
Pour cela, un formalisme de haut niveau structuré est souvent défini, et le modèle sous-jacent est une chaîne de Markov. Un logiciel est alors utilisé pour générer l'espace d'états et le générateur infinitésimal de la chaîne de Markov, ainsi que pour calculer les solutions stationnaires et transitoires. Plusieurs formalismes de haut niveau ont été proposés pour permettre la modélisation des chaînes de Markov très grandes et très complexes de façon compacte et structurée. Parmi ceux largement utilisés dans divers domaines d'application, nous citons notamment les réseaux d'automates stochastiques (SAN) [Pla84,Fer98], les réseaux de files d'attente [GP98], les réseaux de Petri stochastiques généralisés [MBC$^+$95], et les algèbres de processus [Hil96].
La principale difficulté rencontrée dans le développement de logiciels traitant les chaînes de Markov réside dans l'explosion du nombre d'états qui se produit couramment lorsque l'on modélise des systèmes à grande échelle. La chaîne de Markov sous-jacente possède alors un grand nombre d'états, et des algorithmes sophistiqués sont nécessaires pour traiter de telles structures. Pour obtenir des résultats en un temps raisonnable, il faut analyser finement à la fois la mémoire utilisée et le temps mis pour générer la chaîne de Markov et calculer des indices de performances à partir du formalisme de haut niveau utilisé. Ainsi, les méthodes numériques dites directes, comme la méthode de Gauss [LT94], ne sont pas utilisables pour des modèles de grande taille. En effet, les besoins en espace mémoire sont trop importants. Les méthodes itératives sont mieux adaptées à l'étude des grands systèmes puisqu'elles permettent de tirer avantage des techniques de stockage structurées du générateur de la chaîne de Markov. Cependant, là aussi, les besoins en mémoire peuvent devenir trop élevés pour les modèles à échelle réelle.
La première partie de mes travaux de thèse cible le formalisme des réseaux d'automates stochastiques. J'ai proposé un nouveau formalisme de modélisation de réseaux d'automates stochastiques (SAN) à temps discret, ainsi que des techniques d'agrégation visant à réduire l'espace d'états afin de pallier au problème de l'explosion du nombre d'états évoqué précédemment. Je me suis également intéressé à la résolution numérique des modèles SAN, et j'ai ainsi proposé de nouvelles techniques adaptées aux systèmes à grand espace d'états. Je détaille maintenant ces différentes contributions.
Réseaux d'automates stochastiques à temps discret [12,14]
Dans les modèles à temps discret, le temps est regroupé en intervalles. Ceci permet de réduire la complexité du système (par rapport à l'approche temps continu), car on ne regarde plus le détail de tout ce qui se passe à chaque instant, mais l'ensemble de tout ce qui s'est passé dans un intervalle de temps donné. Cependant, les modèles à temps discret sont plus difficiles à représenter justement du fait que plusieurs événements puissent avoir lieu pendant une même unité de temps (événements concurrents). Nous trouvons donc beaucoup moins de travaux sur de tels modèles dans la littérature que pour le temps continu.
J'ai proposé un formalisme de réseaux d'automates stochastiques à temps discret en détaillant explicitement comment agir dans le cas d'événements concurrents. Pour cela, une priorité est associée à chaque événement et permet de déterminer comment agir en cas de conflit. De plus, j'ai proposé un algorithme de génération de la chaîne de Markov, qui détecte les événements concurrents et agit en conséquence.
Agrégation de réseaux d'automates stochastiques avec réplication [1,10]
Pour pallier au problème de l'explosion du nombre d'états dans le cas de systèmes à grand espace d'états, nous cherchons à réduire la complexité de la chaîne de Markov étudiée. Heureusement, de nombreux systèmes contiennent un grand nombre de composants identiques. On peut alors exploiter ces réplications de composants pour générer une chaîne de Markov réduite, en effectuant une agrégation exacte [KS60] sur l'espace d'états de la chaîne de Markov.
Dans le cadre des SAN à temps continu, j'ai introduit le concept de réseaux d'automates stochastiques avec réplication, en tenant compte du fait que, la plupart du temps, un système est constitué de plusieurs entités identiques. J'ai donc défini la notion d'automates répliqués dans un SAN, et proposé une agrégation exacte sur de tels modèles. J'ai également donné une expression tensorielle de la matrice de la chaîne de Markov agrégée, ce qui permet d'avoir un modèle stocké de façon compacte, et des méthodes de résolution efficaces sur ce modèle.
Résolution numérique de modèles SAN [2,3,9,11,23]
Pour calculer des indices de performances pour des systèmes à grand espace d'états, ce sont des méthodes de résolution itératives qui sont utilisées. Or, ces méthodes ont souvent besoin d'effectuer la multiplication d'un vecteur de probabilités par le générateur de la chaîne de Markov un grand nombre de fois. Pour les systèmes étudiés, il est difficile de stocker le vecteur et le générateur, et surtout l'efficacité de la multiplication dépend directement de ce stockage.
Les réseaux d'automates stochastiques permettent de diminuer les besoins en mémoire pour stocker le générateur par leur approche structurée, basée sur une formule tensorielle. J'ai proposé une amélioration de l'algorithme de multiplication classique utilisé pour multiplier un vecteur par un générateur stocké sous forme tensorielle (appelé aussi descripteur). Le nouvel algorithme tient compte du fait que dans de nombreux modèles, la proportion d'états accessibles est faible. Ainsi, il utilise uniquement des structures réduites (de la taille de l'état accessible), ce qui permet un gain en mémoire et en temps d'exécution important lorsque la proportion d'états accessibles est effectivement faible.
J'ai implanté cet algorithme dans le logiciel PEPS (Performance Evaluation of Parallel Systems) [FLP88] et des résultats numériques prouvant son efficacité ont été obtenus sur divers exemples d'application (réseaux, files d'attente, ...)
Durant ma thèse, j'ai eu l'occasion d'encadrer un stage de maîtrise et de participer à l'encadrement d'un stage de DEA. De plus, j'ai été coordinatrice d'une tâche dans le projet DECORE (Dimensionnement Et COmmande de REseaux de communication) de l'IMAG (Informatique et Mathématiques Appliquées de Grenoble).
La tâche concerne l'exploitation des symétries dans les modèles des réseaux. La construction de protocoles de communication repose sur le fait que les sites exécutent les mêmes codes, avec éventuellement des paramètres différents. L'objectif de cette tâche est de développer des méthodes permettant d'intégrer les hypothèses de symétries dans les modèles et les méthodes de résolution. Les travaux effectués correspondant sont ceux concernant l'agrégation des réseaux d'automates stochastiques avec réplication. J'ai encadré un stage de maîtrise sur ce sujet, qui a aboutit à la publication d'un article [10]. Ces travaux font également parti du rapport d'activité du projet DECORE.
J'ai également participé à l'encadrement d'un stage de DEA concernant la traduction de modèles UML (Unified Modeling Language) en réseaux d'automates stochastiques, dans le but de combiner à la fois la vérification du système et l'évaluation de ses performances dans un logiciel unique.
Depuis septembre 2003, je suis en post-doctorat à l'université d'Edimbourg, et je travaille avec Murray Cole, Jane Hillston et Stephen Gilmore sur le projet Enhance (Enhancing the Performance Predictability of Grid Applications with Patterns and Process Algebras). Je présente tout d'abord le contexte et les objectifs du projet avant de détailler les contributions apportées jusqu'à présent.
Une grille informatique est un ensemble de ressources (calcul et stockage) reliées par un réseau haut débit, accessible à une communauté d'utilisateurs par l'intermédiaire d'un logiciel de partage (middleware). Les grilles de calcul ont été l'objet de nombreuses recherches en informatique ces dix dernières années. Elles permettent en effet d'exploiter au mieux la puissance de calcul d'un ensemble d'ordinateurs hétérogènes distribués [FK98]. Cependant, concevoir une application pour une grille d'ordinateurs soulève des problèmes d'allocation de ressources et d'ordonnancement (comment décider quel ordinateur exécute quelle tâche, quand, et comment les différents ordinateurs intéragissent). Ces problèmes sont rendus d'autant plus complexes que les performances des ressources et leur disponibilité sont difficiles à prévoir dans ce contexte de grille. Par exemple, un super-ordinateur peut être réquisitionné pour une autre application plus prioritaire, ou bien les connections Internet utilisées par l'application peuvent être très chargées.
Dans ce contexte de programmation pour une grille, la programmation à base de squelettes [Col89,RG02] exploite le fait que de nombreuses applications utilisent les mêmes schémas de programmation bien connus. Cette approche de haut niveau permet ainsi de structurer aisément les programmes parallèles en fournissant à l'utilisateur une bibliothèque de squelettes (routines génériques) prédéfinis. Cela permet en outre de raisonner plus facilement sur les programmes afin de supprimer les éventuelles erreurs de programmation. La bibliothèque de squelettes eSkel [Col02] a été développée à l'université d'Edimbourg pour les machines multiprocesseurs et les clusters, en utilisant MPI (Message Passing Interface). Une nouvelle version axée grilles est en cours de développement. Cette dernière utilise des versions de MPI adaptées à ce nouveau contexte, comme MPICH-G2 [KTF03].
L'utilisation d'un squelette particulier génère de nombreuses informations sur les dépendances impliquées lors de l'ordonnancement de l'application. Dans le projet Enhance, nous proposons de modéliser ces squelettes à l'aide d'algèbres de processus [Hil96]. En introduisant dans ces modèles les aspects d'incertitude propres à la programmation pour les grilles, nous pensons pouvoir obtenir des résultats permettant de prendre de meilleures décisions d'ordonnancement sur la grille que les approches moins sophistiquées. De plus, les techniques développées sur les grilles permettent d'obtenir les performances des ressources utilisées de façon dynamique, ce qui permettra un réordonnancement dynamique de l'application, pour s'adapter aux conditions changeantes.
Les travaux déjà effectués sur l'évaluation des performances pour les applications grilles ne présentent pas de réels modèles de performances, et ne sont pas axés sur une approche haut niveau à base de squelettes algorithmiques. Je détaille maintenant l'avancée du projet à l'aide des résultats déjà obtenus.
A l'université d'Edimbourg, nous développons une bibliothèque de squelettes permettant une programmation parallèle structurée. J'ai contribué largement au développement de cette bibliothèque eSkel [Col02], et pour cela j'ai été amenée à réfléchir aux implications de la programmation structurée, et aux moyens nécessaires pour la mettre en oeuvre. J'ai tout d'abord réfléchi aux concepts sous-jacents [6] à la programmation parallèle à base de squelettes algorithmiques, puis implémenté ces concepts dans une nouvelle version de la librairie eSkel disponible sur http://homepages.inf.ed.ac.uk/abenoit1/eSkel, et expliqué dans [24].
J'ai particulièrement porté attention aux squelettes Pipeline [4,8] et Deal [5]. Le pipeline est un schéma de parallélisme classique qui consiste à traiter un flot de données à travers une série d'étapes. Le parallélisme est introduit car les différentes étapes peuvent traiter différentes données en même temps. Le goulot d'étranglement est alors l'étape la plus longue, et pour accélérer l'application on peut alors utiliser un deal sur cette étape, ce qui consiste à répliquer l'étape pour pouvoir traiter plusieurs données en même temps.
Le coeur du projet consiste à définir des modèles de performances pour ces squelettes, ce qui permet de trouver le meilleur scheduling possible pour l'application lorsqu'on se trouve dans un contexte d'application pour la grille, avec des ressources hétérogènes et un environnement changeant dynamiquement de configuration.
J'ai ainsi élaboré un modèle de ces squelettes en algèbre de processus
PEPA (Performance Evaluation Process Algebra) [Hil96]. Chaque
modèle est décomposé en plusieurs sous-modèles :
- l'application elle-même, à savoir l'enchaînement logique des
différentes étapes du pipeline et le détail des étapes étant un
squelette deal ;
- les ressources disponibles, à savoir les différents processeurs sur
lesquels l'application va s'exécuter, et leur puissance de calcul
disponible pour notre application, en précisant quelle partie de
l'application s'exécute sur quelle ressource ;
- le réseau, qui précise l'efficacité des connections reliant les
différentes ressources.
Les informations de performance sur les ressources et le réseau sont obtenues en partie grâce à un service de monitoring de ressources, le Network Weather Service [WSH99]. Avec ces informations et la connaissance du scheduling de l'application sur les ressources, nous pouvons en déduire les paramètres qui définissent le modèle ([5]).
Des résultats numériques peuvent alors être obtenus à l'aide du logiciel PEPA Workbench [GH94]. L'indice de performance qui nous intéresse dans le cadre du pipeline est le débit. J'ai ainsi été amenée à rajouter une fonctionnalité dans le PEPA Workbench pour pouvoir calculer directement de tels indices. Pour cela, il suffit de rajouter une description du résultat voulu dans le fichier décrivant le modèle. Ensuite, une simple ligne de commande permet de résoudre le modèle et d'obtenir le résultat voulu.
Enfin, pour pouvoir améliorer les performances des applications étudiées, j'ai également développé un outil qui génère automatiquement un ensemble de modèles de performances (dans le cas du pipeline et du deal uniquement), puis qui résout automatiquement tous ces modèles dans le but de fournir à l'application des résultats significatifs pour améliorer ses performances. Dans sa forme actuelle, l'outil est un prototype indépendant de l'application. Plus tard, il sera intégré à l'application, et permettra d'adapter la correspondance de l'application sur les ressources dynamiquement, en fonction des modifications de la disponibilité et des performances des ressources. L'outil dans sa forme actuelle nous a permis d'obtenir cependant des premiers résultats significatifs prouvant l'intérêt de ces recherches.
Je m'intéresse également à des applications concrètes pour valoriser ces recherches~[25,26], et récemment j'applique ces méthodes sur une application qui associe différentes vues d'une même image pour obtenir une image en trois dimensions~[25]. Cette application peut être décrite à l'aide de pipeline et de deal, et les modèles de performances permettent d'optimiser son exécution.
Dans des travaux connexes, j'ai développé un simulateur en Objective Caml qui permet de déboguer les modèles PEPA pas à pas ([13]), ce qui peut être utilisé notamment sur les modèles de squelettes algorithmiques évoqués précédemment.
J'ai également appliqué ces techniques pour l'analyse de clusters, comme présenté dans [7].
Mes activités de recherche durant ma thèse puis mon post-doctorat sont axées sur une approche "évaluation des performances", avec une forte connexion avec la programmation parallèle et distribuée et les réseaux. Ce champ de recherche est très vaste et permet d'aborder différents domaines d'applications.
Comme projet de recherche, je souhaite mettre à profit mes connaissances en évaluation de performance, notamment pour le développement de méthodes efficaces de programmation parallèle. Je désire associer ces travaux avec mon expérience en programmation parallèle structurée, dans le but de développer des environnements de programmation parallèle pour la haute performance.
Évaluation des performances
J'ai eu l'occasion de travailler avec différents formalismes de modélisation, et notamment les réseaux d'automates stochastiques et les algèbres de processus. Ces deux formalismes ont des caractéristiques qui les rendent plus ou moins adaptés à la modélisation d'un système particulier, c'est pourquoi il est intéressant de s'intéresser à plusieurs formalismes ayant des caractéristiques différentes. Ainsi, lorsqu'on est confronté à un système présentant des problèmes de performances, on peut choisir la façon la plus adéquate d'obtenir des indices de performances en vue de résoudre le problème. L'utilisation d'autres formalismes de modélisation permettrait d'élargir encore mon savoir sur les techniques d'évaluation de performances.
Les techniques de résolution deviennent de plus en plus sophistiquées pour pallier au problème de l'explosion du nombre d'états. En effet, les systèmes étudiés sont de plus en plus complexes et il est difficile de les traiter par des méthodes traditionnelles et parfois naïves. Ainsi, de nombreux travaux restent à faire sur chaque formalisme pour satisfaire aux exigences de tels systèmes. Les techniques utilisées d'un formalisme à un autre ont souvent de nombreux points similaires, d'où l'intérêt de s'intéresser à plusieurs formalismes plutôt que de se borner à l'étude d'un unique formalisme.
Programmation parallèle structurée
Un des buts principaux de l'évaluation de performances est de résoudre des problèmes de performances sur des applications réelles. Il est donc tout naturel de se tourner vers des applications lorsqu'on s'intéresse à l'évaluation des performances, car cela peut d'une part donner des pistes pour améliorer les techniques existantes, et d'autre part résoudre des problèmes pour l'application. Lors de mes études, j'ai découvert différents aspects de la programmation parallèle et distribuée, et étudié les réseaux. J'ai également utilisé ces connaissances de façon concrète pendant des projets et des stages.
Depuis septembre 2003, je m'intéresse plus spécifiquement aux environnements de programmation parallèle structurée, qui permettent de développer plus facilement des applications parallèles, et d'assurer de bonnes performances. Mon intérêt actuel se porte ainsi sur les applications pour la grille informatique, très en vogue en ce moment, et particulièrement propices à une étude de performances. Je m'intéresse notamment aux applications parallèles structurées et contraintes par des schémas de parallélisme prédéfinis (squelettes algorithmiques).
Bilan
Je suis ouverte à tout sujet de recherche, ayant trait à la programmation parallèle et distribuée. Les différentes techniques d'évaluation de performances que j'ai étudiées sont particulièrement adaptées à ce domaine de recherche. Je pense que je peux également apprendre beaucoup en travaillant sur des domaines voisins, et je désire surtout partager mes connaissances acquises ces dernières années, à la fois en programmation parallèle structurée et en évaluation des performances.