![]() |
Séminaire du LaBRI 2001-2002Le jeudi, à 14h, amphithéâtre du LaBRI. |
L'évolution des techniques et des outils de compilation logicielle et de synthèse automatique de matériels permet maintenant de concevoir de manière conjointe (Codesign) des systèmes électroniques intégrés sur une seule puce de silicium, appelés Systems on Chips. Ces systèmes dans leurs versions embarquées doivent répondre à des contraintes spécifiques de place, de vitesse et de consommation. De plus, les capacités sans cesse croissantes de ces systèmes permettent aujourd'hui de développer des applications complexes comme les applications multimédia et les communications par réseaux. Les applications multimédia génèrent de gros besoins en place mémoire et des transferts de données volumineux. Il faut donc se concentrer sur l'optimisation de la mémoire lors de la conception de telles applications dans le monde de l'embarqué. Deux moyens d'action sont généralement mis en oeuvre: le choix des architectures (hiérarchies mémoire et mémoires caches) et l'adéquation du code décrivant l'application avec l'architecture générée. Je développerai ce second axe d'optimisation de la mémoire et comment transformer automatiquement le code de l'application, en particulier les boucles, pour minimiser les transferts de données (grands consommateurs d'énergie) et la place mémoire (grande utilisatrice de surface et d'énergie).
Le programme de modélisation des plantes du CIRAD travaille depuis une dizaine d'années à montrer l'importance fondamentale de l'architecture dans l'étude de la croissance des plantes. C'est dans la logique de cette approche que nous avons abordé les méthodes informatiques et mathématiques nous permettant de quantifier certains événements macroscopiques intervenant dans l'édification des plantes. Pour prendre en compte de façon précise l'ensemble de la structure topologique de la plante, les représentations de type arborescent sont couramment utilisées (Godin et al. 2000). Pour assurer une plus grande généralité dans la description de l'architecture des plantes, Godin et Caraglio ont défini une structure arborescente multi-échelles, basée sur la notion de graphe quotienté.
Dans la logique de cette approche nous présenterons lors de ce séminaire un algorithme de comparaison entre arborescences et ses extensions. Nous étudierons alors leurs applications dans les domaines de la biologie végétale. Ce type d'algorithmes s'appuie sur la généralisation des méthodes de calcul de distance entre séquences utilisées, par exemple, pour la comparaison du génome. Leur principe général consiste à reconstruire un graphe cible en appliquant à un graphe initial différentes opérations structurelles, appelées opérations d'édition. Ayant attribué un coût à chaque opération, on recherche alors une suite d'opérations d'édition dont la somme des coûts est minimale. L'étude de la combinatoire de tels problèmes se ramène à la recherche d'une solution optimale dans un espace qui croît exponentiellement avec la taille des données. Les méthodes de résolution de ces problèmes réduisent la complexité de l'espace de recherche, pour la plupart, en utilisant les techniques du principe de programmation dynamique.
Après avoir proposé un point de vue unifié de différentes distances entre arborescences, nous donnerons deux extensions permettant d'envisager le calcul d'une mesure de ressemblance entre arborescences multi-échelles. Nous montrerons, en outre, comment de telles distances peuvent être utilisées pour quantifier le degré d'autosimilarité de structures arborescentes. Nous illustrerons cette méthodologie sur des inflorescences de lilas comme cas d'étude.
Cet exposé présentera quelques travaux récents (effectués au sein du projet ReMaP) s'intéressant à l'étude de mécanismes permettant d'améliorer les performances au sein de supports exécutifs parallèles portables. Les architectures visées étant de type ``grappe de noeuds multiprocesseurs (SMP)'', nos recherches se sont naturellement focalisées sur les supports exécutifs multithreads distribués qui sont particulièrement adaptés à l'exploitation efficace de ce type de configuration. Cette quête du temps perdu revêt donc une certaine coloration multithread que nous justifierons en rappelant plusieurs vertus méconnues du multithreading. Dans cet exposé, nous nous concentrerons sur deux axes de recherche particuliers.
En premier lieu, nous présenterons une nouvelle interface de communication (Madeleine) capable d'exploiter efficacement de multiples protocoles pour réseaux rapides (BIP, SISCI, etc.) en contexte multithread. L'originalité de Madeleine est de permettre une sélection dynamique d'optimisations de transmission des données en fonction des contraintes exprimées par l'application. Cette ``programmation par contrat'' est la clé permettant de garantir la portabilité des performances sur un vaste éventail de protocoles. Récemment, nous avons étendu ces travaux aux architectures de type ``grappe de grappes'' exhibant des réseaux d'interconnexion hétérogènes.
La seconde partie de l'exposé sera consacrée à nos travaux sur l'ordonnancement de threads sur machines multiprocesseurs. Ces travaux nous ont conduit non seulement à proposer de nouvelles optimisations rendues possibles en s'écartant (un peu) de la norme POSIX Threads, mais aussi et surtout à proposer des mécanismes permettant d'améliorer le déroulement des opérations d'entrées/sorties (en particulier les communications) sur le plan de la réactivité des threads applicatifs. Nous avons ainsi revisité le modèle des ``Scheduler Activations'' afin d'augmenter la réactivité aux événements d'E/S. Ce modèle a été implanté sous la forme d'une extension au noyau Linux (LinuxActivations) et d'une adaptation de l'ordonnanceur de threads Marcel. Nous avons en outre dégagé une interface générale pour la récupération d'événements d'E/S (par scrutation et par interruptions) fondée sur un support spécifique de l'ordonnanceur de threads.
Le modèle des réseaux de Petri est largement répandu dans la spécification des systèmes à événements discrets (SED). Ceci est dû principalement à la diversité des méthodes de vérification, à la possibilité d'y associer des domaines sémantiques différents (SED, systèmes temporisés, processus stochastiques) et à la capacité de vérifier des systèmes à nombre infini d'états.
Dans cet exposé, nous discuterons des limites du pouvoir d'expression des réseaux de Petri vis à vis de certains types de comportement. Puis nous introduirons une extension des réseaux de Petri, les réseaux de Petri récursifs (RdPR). Nous illustrerons comment ce modèle pallie les insuffisances décrites précédemment. Nous nous pencherons ensuite sur la vérification des propriétés standard telles que l'accessibilité et le caractère borné qui restent décidables pour les RdPR. Enfin nous étudierons la vérification de formules de logique temporelle linéaire événementielle (décidable pour les réseaux de Petri) qui devient indécidable dans le cadre des RdPR. Ceci nous conduira à présenter une restriction de ce modèle, le modèle des RdPR séquentiels pour lequel cette vérification reste décidable.
La réalité virtuelle a commencé par proposer des expériences personnelles (un casque de visualisation donc une personne), puis assez rapidement les utilisateurs ont souhaité dépasser cet aspect " privé " pour pouvoir réaliser des travaux collectifs où par exemple une équipe d'ingénieurs peut travailler en commun sur la conception d'un produit.
Aujourd'hui ce souhait peut être exaucé grâce à l'arrivée de nouveaux dispositifs d'affichage de type salle de projection immersive. Il s'agit d'une pièce où sont projetées, sur les murs ou sur des écrans, les images calculées interactivement par des calculateurs spécialisés en fonction des actions des utilisateurs. La surface de projection (jusqu'à plusieurs dizaines de m²) permet de visualiser la plupart des produits en conception à l'échelle 1 concrétisant ainsi la notion de maquette numérique.
Bordeaux 1 s'est récemment doté d'un tel équipement au sein d'un centre baptisé Hémicyclia que je présenterai, d'abord d'un point de vue matériel, puis au travers de nos activités de recherche et de quelques exemples de collaborations extérieures. L'exposé sera suivi de visites/démos sur le site.
Les techniques d'acquisition d'images volumiques s'affinant rapidement, l'image 3D devient une modalité très utilisée lors de l'analyse de comportements ou de propriétés physiques d'objets réels. A l'origine, ces techniques prédominaient dans le domaine médical avec des méthodes d'acquisition telles que l'imagerie par résonance magnétique ou encore le scanner X. Cependant, le champ d'applications de ce modèle est en constante expansion. Par exemple, Météo-France l'utilise dans le cadre d'une analyse d'échantillons de neige en vue d'une paramètrisation de plate-forme de modélisation d'avalanches.
En ce qui concerne l'analyse de ces images discrètes, de nombreux outils du modèle discret sont utilisés pour extraire de l'information. Parmi ces outils, les opérateurs de type différentiels (dérivée, courbure...) sont des descripteurs de forme privilégiés. L'utilisation de ces opérateurs, venant des mathématiques du continu, peut se faire suivant deux approches possibles :