Propositions de stages 2011-2012

Y. Sorel
INRIA Rocquencourt -- 78153 Le Chesnay Cedex
Tel. : 01 39 63 52 60, Email : yves.sorel@inria.fr, Web : http://www.syndex.org

Introduction
 Les différents sujets de stages proposés auront lieu à l'INRIA Roquencourt dans l'équipe projet AOSTE (Analyse et Optimisation des Systèmes Temps réel Embarqués) dans le cadre du développement de la méthodologie AAA (Adéquation Algorithme Architecture) et du logiciel distribué gratuitement SynDEx d'aide à la conception et la réalisation de systèmes temps-réel embarqués complexes pour des algorithmes de contrôle-commande comprenant du traitement du signal et d'image s'exécutant sur des machines multicomposant (réseau de processeurs et ce circuits intégrés spécialisés).
Brièvement, SynDEx V7 est constitué :
- d'une interface graphique interactive pour saisir les graphes représentant les algorithmes (hypergraphe orienté de dépendances de données factorisé : sommet = opération de calcul, arc = dépendance de données) et les calculateurs multicomposant (graphe orienté : sommet = machine séquentielle de calcul ou de communication, arc = connexion entre machines séquentielles),
- d'heuristiques d'optimisation pour la distribution et l'ordonnancement des algorithmes sur les calculateurs (implantation optimisée),
- d'un générateur de macro-code permettant de générer des exécutifs distribués temps-réel pour l'exécution des algorithmes sur les calculateurs.

Voici les sujets de stage proposés. Ils comportent tous une partie théorique qui peut être suivie d'une partie algorithmique et éventuellement, en fonction de l'état d'avancement, d'une partie développement logiciel.

Les stages déjà attribués sont précédés d'un *.

  • Passerelle Lustre/SynDEx
     Il existe plusieurs passerelles permettant d'interfacer SynDEx avec un langage orienté métier (DSL Domain Specific Language) tel que Scilab/Scicos, Signal/Polychrony, UML/MARTE. Il s'agit d'étudier et développer une passerelle entre le langage synchrone Lustre et SynDEx. Lustre est un langage flot de données fonctionnel permettant de spécifier des applications temps réel, de vérifier des propriétés temporelles logiques, et de simuler ces applications sur une architecture monoprocesseur. Lustre est vendu sous la version commerciale Scade par Esterel-Technologies et est très utilisé dans l'industrie de l'embarqué en particulier dans l'avionique (Airbus A3X0). Une passerelle avec SynDEx permettra de respecter des contraintes temps réel et de générer du code temps réel embarqué sur des architectures multiprocesseur en garantissant les propriétés temporelles montrées avec Lustre.

  • *Distribution et ordonnancement temps réel périodique préemptif multiprocesseur
     Actuellement SynDEx offre une heuristique de distribution et d'ordonnancement temps réel périodique multiprocesseur en n'utilisant pas la préemption. Après avoir fait une analyse d'ordonnançabilité temps réel sur l'ensemble des opérations caractérisées temporellement (tâches temps réel), l'heuristique minimise le temps d'exécution total de l'application en tenant compte des coûts de communications inter-processeur. Il s'agit d'étudier et implanter une heuristique de ce type en utilisant la préemption. On choisira une approche d'ordonnancement multiprocesseur ``partitionnée'' plutôt que ``globale'' pour laquelle le coût de migration des opérations est trop important sur les processeurs actuels.

  • Optimisations pour les algorithmes réguliers
     Le formalisme de graphe utilisé pour spécifier les algorithmes permet de modéliser des algorithmes irréguliers contenant des parties régulières vues comme des sous-graphes factorisés (répétition d'un motif de graphe correspondant à du parallélisme potentiel de données). Il s'agit tout d'abord de comparer ce modèle à d'autres modèles plus classiques utilisés dans la littérature (réseau de processus de Kahn, flot de données classique, SDF synchronous data flow, etc). Il s'agit ensuite d'étudier les optimisations consistant à exploiter ces répétitions en espace ou en temps, en fonction des contraintes temps réel et/ou de la mémoire programme et donnée disponible. Cela se fera en minimisant les communications inter-processeur qui peuvent devenir très pénalisantes lorsqu'elles sont nombreuses. On étudiera tout d'abord des heuristiques gloutonnes afin d'être compatible en terme de temps d'exécution avec les heuristiques déjà existantes dans SynDEx. Il s'agit ensuite d'étendre en conséquence l'heuristique et le générateur d'exécutifs actuels.

  • Optimisation de la taille mémoire de données et de programme
     Actuellement le code généré (exécutifs distribués temps réel taillé sur mesure pour l'application) utilise de manière simpliste le modèle à assignation unique de la spécification flot de donnée de l'algorithme. Cela conduit d'une part à ne pas réutiliser une mémoire de donnée lorsque celle-ci a été précédemment utilisée et d'autre part à ne pas partager une mémoire de donnée lorsque celle-ci pourrait être utilisée en entrée et en sortie d'une opération (traitement d'une image dans laquelle seuls quelques pixels sont modifiés). Par ailleurs l'imbrication de conditionnements conduit à des duplications de If...Then...Else dans le code généré. De même la répétition d'opérations conduit à une duplication d'appels à cette opération qui pourait être remplacée par une boucle For I...Do... dans le code généré. Il s'agit d'optimiser la mémoire de données et de programme par analyse du code généré automatiquement par SynDEx, et éventuellement d'étudier si cela est faisable directement au niveau du générateur de code.

  • *Formalisation et évaluation du coût d'un ordonnanceur temps réel
     Lorsqu'on effectue des analyses d'ordonnançabilité temps réel on fait généralement l'hypothèse que le coût de l'ordonnanceur est approximé dans le WCET (pire temps d'exécution) des tâches à ordonnancer, ce qui conduit nécessairement à du gaspillage de ressources et/ou, ce qui est pire, à des comportements incorrects lors de l'exécution en temps réel. Il s'agit de réaliser une étude expérimentale de l'ordonnanceur pour quelques politiques d'ordonnancement telles que RM, EDF, et pour quelques ordonnanceurs comme celui de l'OS Linux/RTAI, RTX, etc., afin de formaliser le coût de l'ordonnanceur pour l'introduire dans les conditions d'ordonnançabilité. Il s'agit d'implanter un prototype d'ordonnanceur dont on pourra évaluer de façon précise le coût.

  • *Développement d'un train virtuel de CyCabs
     Il s'agit de participer au développement d'un train virtuel de CyCabs fondé sur un asservissement d'un CyCab automatique suiveur sur un CyCab conduit manuellement à l'aide d'un système de vision à faible coût utilisant une ou plusieurs webcams. Les algorithmes de traitement d'image permettant de faire la reconnaissance de CyCab et l'algorithme de contrôle commande effectuant l'asservissement sont spécifiés et simulés avec Scilab/Scicos, puis la passerelle Scilab/Scicos/SynDEx est utilisée pour les implanter sur l'architecture distribuée du CyCab composée de plusieurs microcontroleurs MPC555 et/ou PIC d'un PC embarqué sous Linux/RTAI communicant tous via un bus CAN. On commencera par porter la version actuelle sur Linux/Xenomai. On étudiera la possibilité d'améliorer les algorithmes de reconnaissance et de suivi de CyCab et l'intérêt d'utiliser une seconde caméra. On étudiera ensuite les différents modes de coopération (synchrone, asynchrone) entre des algorithmes de commande bas niveau des moteurs et des algorithmes de commande de plus haut niveau réalisant les asservissements simples comme dans le suivi ou plus complexes dans le cas de plannification. Cette étude sera faite relativement à au niveau de sûreté de fonctionnement visée. Cela conduira à développer dans SynDEx un nouveau type d'arc dit "asynchrone". On étudiera, avec des techniques de préemptions calculées, la possibilité d'ordonnancer des opérations ayant à la fois une grande durées et une grande période avec des opérations ayant à la fois une petites durée et une petite période.

    Les sujets sont de niveaux de difficulté différents. Ils sont parfois complémentaires. Certains sujets pourront être regroupés en fonction de la durée des stages.