Pour l'année 2000/2001, les séminaires du LIP auront lieu le mardi après-midi à 13h30 deux fois par mois avec en alternance un exposé d'un intervenant local / un exposé d'un intervenant extérieur. La durée est de 45 minutes plus 10 à 15 minutes de questions (des modifications peuvent être envisagées si elles sont demandées à l'avance).
Delaunay refinement is a technique for generating unstructured meshes of triangles or tetrahedra suitable for use in such applications as
In this talk, I discuss the algorithmic underpinnings and current state of the art of Delaunay refinement methods. Popularized by the engineering community in the mid-1980s, Delaunay refinement operates by maintaining a Delaunay triangulation or Delaunay tetrahedralization, which is refined by the insertion of additional vertices. The placement of these vertices is chosen to force the mesh to conform to an object's boundaries, and to improve its quality as a grid for interpolation.
I present a new three-dimensional Delaunay refinement algorithm, which builds on the pioneering two-dimensional work by L. Paul Chew and Jim Ruppert. My algorithm produces tetrahedral meshes that are nicely graded (in a provable sense) and whose tetrahedra have circumradius-to-shortest edge ratios bounded below 1.63. This theoretical guarantee ensures that all poor quality tetrahedra except slivers (a particular type of poor tetrahedron) are removed. The slivers that remain are easily removed in practice, although there is no theoretical guarantee.
L'ensemble des pavages d'un zonotope est connexe Les zonotopes sont des objets géométriques définis dans une dimension d quelconque par un ensemble de vecteurs. A partir de ces vecteurs, on définit de façon standard un ensemble de tuiles de dimension d, et le problème du pavage du zonotope est de "remplir" l'intérieur du zonotope par des copies translatées de ces tuiles, de façon à ce qu'il n'y ait ni trous ni recouvrement de tuiles.
Les pavages de zonotopes ont une grande importance en physique, où ils modélisent les quasicristaux, et en combinatoire où ils posent de nombreux problèmes d'énumeration. Ils sont aussi fortement reliés à la théorie des matroïdes, et de nombreux problèmes s'expriment naturellement en termes de pavages de zonotopes.
Il est possible de définir une opération locale sur les pavages de zonotope qui transforme un pavage du zonotope en un autre pavage du même zonotope. Une question fondamentale de cette théorie est de savoir si on peut obtenir TOUS les pavages d'un zonotope donné en itérant cette opération. Kenyon a prouvé que la réponse est positive en dimension 2, et nous introduisons un nouvel objet combinatoire permettant de montrer que la réponse reste positive en n'importe quelle dimension.
Les possibilités maintenant disponibles en matière de calcul réparti et de réseau à très haut débit permettent d'envisager que des applications scientifiques soient portées sur des grilles de calcul.
Des initiatives nationales et européennes visent à mettre en place des prototypes de grande dimension et à en faire bénéficier quelques secteurs scientifiques fortement demandeurs de puissance de calcul : la physique des hautes énergies, la biologie et les sciences de la terre.
Il s'agit d'organiser un transfert de ces technologies des laboratoires de recherche en informatique vers des utilisateurs et, en retour, à enrichir la recherche conduite par les 'informaticiens' de l'expérience de ces applications pilote.
Au cours du séminaire, Christian Michau présentera en particulier le projet européen Datagrid : la logique du projet, les applications concernées, les développements logiciels engagés sur la couche Globus et des plateformes expérimentales qui se construisent. Il parlera également des coopérations qui s'organisent en France dans ce domaine entre les centres de recherche et les industriels.
Christian Michau est le directeur de l'Unité Réseaux du CNRS et le secrétaire du comité d'orientation des moyens informatiques du CNRS. Il est l'un des acteurs du projet Datagrid. Le LIP et l'UREC construisent un partenariat sur ces activités.
La fourmi de Langton est un système dynamique introduit par C. Langton qui essayait de montrer que des règles automatiques simples peuvent donner lieu à des comportements aussi complexes que ceux des organismes vivants. En effet, la fourmi de Langton a une dynamique très imprévisible et étonnante. Elle a été étudiée par plusieurs chercheurs dans les contextes dynamique, physique, combinatoire et informatique. Plusieurs propriétés ont été prouvées, mais sa caractéristique la plus remarquable est encore un problème ouvert.
Langton a défini la fourmi sur la grille carrée, mais je vais donner ici une définition plus générale sur un graphe planaire quelconque : à chaque sommet du graphe on associe un état ( à-gauche ou à-droite), que seule la fourmi peut changer; la fourmi peut être interprétée comme une flèche, qui est sur une des arêtes du graphe et qui pointe sur un sommet; à chaque pas, elle tourne à gauche ou à droite selon l'état de ce sommet, et elle en change l'état. D'un certain point de vue, la fourmi est une machine de Turing bi-dimensionnelle.
Le comportement de la fourmi varie selon le graphe sous-jacent, certaines propriétés étant communes à une large classe de graphes. Dans une première partie de l'exposé, on montrera les propriétés les plus importantes et les plus générales de la fourmi sur les graphes bi-réguliers Gamma(k,d).
En suite, comme une preuve de sa complexité, on montrera que ce système est universel dans la mesure où il existe une configuration initiale du système telle que suivant une machine de Turing et un mot d'entrée donnés, il suffit de modifier la configuration initiale dans un nombre fini de sommets, et la fourmi simule la machine de Turing. On montrera comment construire cette configuration initiale à travers la simulation de portes et circuits logiques.
Les réseaux ad-hoc se caractérisent par une absence d'infrastructure et des noeuds mobiles. Plusieurs protocoles de routage sont proposés pour ce type de réseaux. Nous verrons une analyse de la surcharge de trafic apportée par les protocoles eux-mêmes. Il existe deux classes de protocoles : les pro-actifs qui maintiennent des informations de topologie en continu et les réactifs qui découvrent la route au moment où on en a besoin. Nous comparerons la surcharge due au trafic de contrôle dans ces deux classes, et nous analyserons la surcharge due à la non-optimalité des routes pour les protocoles réactifs.
L'automate cellulaire du Tas de sable est apparu dans la fin des années 80 comme étant le modèle le plus simple permettant derendre compte de phénomènes physi ques complexes comme les tremblements de terre.
En 1990, à la suite d'un article de Dhar et al., apparait une formulation plus mathématique et algorithmique de ce problème. Ainsi, je présenterai dans un premier temps l'automate du Tas de Sable que l'on peut définir sur un graphe quelconque. Nous en étudierons certaines configurations dites récurrentes sur des familles de graphes très étudiées en combinatoire. Grâce au formalisme de Dhar, on peut montrer que ces configurations forment un groupe abélien fini. Je présenterai ainsi dans un second temps quelques parallèles entre des objets combinatoires ou algébriques connus et le groupe du Tas de Sable.
In the last few years, molecular biology has generated a huge amount of data, mainly in the form of sequences of DNA/RNA (over a four-bases alphabet) and of proteins (over an alphabet of 20 aminoacids). For computational biologists, the main challenge is now to provide efficient tools for the analysis and the comparison of the sequences. In the lecture, the main problems will be briefly discussed, ad an algorithm that finds repeated substrings in a DNA sequence will be presented. The occurrences of the substrings can be approximated, i.e. can differ up to a given number of mismatches. The algorithm has been successfully implemented on a cluster of workstations.
Frustrated by the NP-hardness of many combinatorial optimization problems, researchers have in the last decade turned their attention away from exact algorithms, to approximation algorithms. Of particular interest are approximation schemes, which construct a solution whose cost is arbitrarily close to the optimal solution cost. Rounding is a powerful tool for this. We will give several examples of rounding techniques: rounding followed by exhaustive search (example: planar max cut), by linear programming (examples: bin-packing, strip packing), or by dynamic programming.
Pour satisfaire les besoins actuels de qualité de service dans les réseaux de télécommunication, il faut rajouter de l'intelligence dans leurs noeuds. Cependant, l'utilisation de plusieurs moyens de transport de l'information dans un même réseau (fibre optique, lien satellite, cable,...) contraint souvent le concepteur à placer cette intelligence dans les points d'accès. Dans cet exposé, nous montrons que sous des hypothèses assez faibles sur la topologie et sur le comportement des commutateurs internes d'un réseau, on peut faire du contrôle optimal des entrées afin de minimiser la charge globale ou le délai de communication.
La méthode présentée formalise le principe général selon lequel, à débit donné, un trafic par rafale se comporte moins bien qu'un trafic plus régulier. Elle utilise des outils mathématiques assez variés: l'analyse convexe (avec l'introduction d'une notion de convexité discrète), les probabilités (pour modéliser le comportement global du réseau), les réseaux de Petri stochastiques, l'algèbre (max,plus) et la combinatoire des mots (en particulier les mots de Sturm).
Ces concepts et les théorèmes généraux qu'ils induisent, ainsi que plusieurs exemples d'applications (optimisation du parcours des robots d'un site de recherche sur le Web, routage dans deux files déterministes, comparaisons entre politiques de routage) seront montrés durant l'exposé.
L'exposé commencera par présenter les différents types de matériel réseau pour les architectures de type «grappes». A partir de là on montrera que l'interface entre les noeuds de calcul et le réseau est une donnée toujours cruciale dans les performances du système de communication. Nous présenterons les diverses techniques systèmes permettant d'obtenir faibles latences et haut débit (accès en mode utilisateur à la carte réseau, transfert à zéro copie-mémoire, élimination des interruptions). Et nous présenterons la problématique d'implémentation d'un protocole asynchrone entre les différents niveaux de l'architecture (code sur processeur principal, logiciel embarqué, implémentation matérielle), en expliquant les problèmes d'interaction entre ces niveaux.
Le partitionnement maximalement prédictif sous contrainte d'ordre total est une méthode de classification qui cherche à partager des séquences d'objets qualitatifs en segments homogènes. L'homogénéité est définie selon un critère basé sur la notion de prédiction. Pour un problème donné, on se munit d'un ensemble fini de prédicteurs possibles. A chaque prédicteur, on associe une fonction - la prédiction - à valeurs réelles sur les objets de la séquence. Un segment est évalué par la somme des prédictions de tous ses éléments par un même prédicteur ad hoc. L'évaluation est ainsi un critère d'homogénéité. Une partition de la séquence est évaluée par la somme des prédictions sur ses segments. Sur la base de cette évaluation on veut pouvoir, grâce au prédicteur de chaque segment d'une partition, disposer d'un résumé de la séquence qui mette en relief une éventuelle structure de cette séquence. Il faut alors estimer le nombre de segments en lequel il est le plus judicieux d'opérer cette partition.
Je présente un algorithme qui, sur la donnée d'une séquence, d'un ensemble de prédicteurs et d'un entier k, construit l'ensemble des partitions optimales en i segments de la séquence pour tout i entre 1 et k. C'est ce que j'appelle un partitionnement. Ceci permet aussi d'observer l'évolution des partitions en fonction de leurs nombres de classes.
L'algorithme présenté a une complexité en temps linéaire avec la longueur de la séquence, la taille de l'ensemble des prédicteurs et le nombre maximum de segments. On peut alors partitionner de très grandes séquences, et les séquences biologiques en constituent un domaine naturel d'expérimentation. Je présenterai ainsi entre autres une méthode de détection des origines de réplication de génomes bactériens.
La basse consommation d'énergie est une contrainte de conception de plus en plus forte pour les circuits intégrés. Avec le développement actuel des appareils portables, les circuits intégrés doivent effectuer des tâches complexes tout en ne consommant que très peu d'énergie. Même dans les processeurs de bureau, la consommation d'énergie peut être critique (problème de dissipation, densité de courant élevée, écologie, bruits...).
Cet exposé sera décomposé en deux grandes parties. Dans la première, nous allons regarder pourquoi les circuits intégrés consomment et quelles sont les techniques classiques pour réduire la consommation. En particulier, nous allons voir que la basse consommation peut être abordée depuis le niveau algorithmique jusqu'au plus bas niveau électrique. Dans la seconde partie de l'exposé, nous regarderons le cas de quelques opérateurs arithmétiques matériels simples (addition et multiplication essentiellement).
CompoVis est une architecture logicielle distribuée offrant à un utilisateur connecté par Internet un ensemble de services de calcul exécutés sur une grille de calcul. Les principales caractéristiques de l'architecture sont son extensibilité, sa portabilité, la mobilité des services, et son intégration avec les technologies Internet, entre autres les bases de données. Le coeur de notre système repose sur la technologie Corba et des composants logiciels, facilement interopérables. Créé au départ dans le but de créer un service de visualisation sur Internet, un prototype aujourd'hui opérationnel de l'architecture met en jeu des technologies comme les Applets Java, les Servlets, une base de donnée MySQL, et le bus Corba de Visibroker pour de simples services de calculs. Toutefois son extension vers les services de visualisation est en cours actuellement. Dans mon intervention, je m'attacherai plus particulièrement à montrer la motivation de notre approche, la modèlisation que nous proposons du problème et les choix techniques adoptés.
Incomplete information may make the benefit of some program transformations unknown at compile-time. However, it is still possible at compile-time to produce parameterized performance formulas which can be used at runtime to choose which variant of the program to execute. We describe our system, the Modal Model of Memory, which was built to explore this approach for locality transformations.
This is joint work with Nick Mitchell, currently at IBM T.J. Watson Research Center, and Larry Carter.
In contrast to traditinal networking, active networking allows routers themselves to play an active role by executing application-dependent services on incoming packets. The talk with first present the current status of Internet networks and then the enhancements active networking could bring to this communication infrastructure. After describing what active networking is (and is not), the talk will move on describing one particular application: active reliable multicast. Recently, the use of active network concepts have been proposed in the multicast research community. Reliable multicast protocols have gained popularity with active services contribution where routers implement additional functionalities. Contributing mainly to feedback implosion problems, retransmission scoping and cache of data, these active protocols open new perspectives for achieving high throughput and low latencies on wide-area networks. The talk will present the general strategies behind active reliable multicast protocols, some performance results and some insights on dimensioning active networks.
Quelques données internes sur notre séminaire (accès LIP uniquement).
Last modified: Mon Jun 11 10:12:16 CEST 2001
Isabelle Guérin Lassous