Séminaire des Elèves 2005-2006


Note aux orateurs
Contact et renseignements : Anne Benoit
Tous les séminaires ont lieu le mercredi à 18h00 dans l'amphi B de l'ENS Lyon

Programme des séminaires

 
Date : mercredi Orateur Titre
 28 septembre
2005 
 Frédéric Loulergue (LIFO, Orléans)  Programmation Parallèle BSP fonctionnelle
 12 octobre
2005 
 Jean-Marc Vincent (Laboratoire ID-IMAG, Grenoble)
 Simulation parfaite de réseaux de files d'attente :
application aux politiques de routage à base d'index

 26 octobre
2005 
 Nicolas Schabanel (ENS Lyon)
 Algorithmes d'approximation :
de la théorie à la pratique

 9 novembre
2005 
 Jacques Mazoyer (ENS Lyon)
 Classification des automates cellulaires
 23 novembre
2005 
 Grégory Mounié (Laboratoire ID-IMAG, Grenoble)
 Ordonnancement pour le calcul parallèle : fondamentaux et autres trucs rigolos
 7 décembre
2005 
 Sacha Bourgeois-Gironde (ENS LSH Lyon)
 Problèmes philosophiques sous-tendant la représentation de la connaissance
 8 février
2006 
 Aurélien Bouteiller (ENS Lyon)
 Tolérance aux défaillances dans les systèmes hautes-performances
 22 février
2006 
 Jérôme Durand-Lose (LIFO, Orléans)
 Calculer géométriquement sur le plan
 15 mars
2006 
 Thomas Colcombet (IRISA, Rennes)
 Expressions omega-régulières et extensions
 29 mars
2006 
 Marco Aldinucci (ISTI CNR, Pise, Italie)
 From high-level parallel programming to high-level grid programming
 12 avril
2006 
 Michel Morvan
 Conférence-débat à l'ENS, 16h-20h [Programme]
 3 mai
2006 
 
 Visite des L3 à l'INRIA Sophia Antipolis



À voir également


L'historique


Résumés des séminaires


 

Programmation Parallèle BSP Fonctionnelle



Date
28 septembre 2005 - 18h00

Orateur
Frédéric Loulergue

Résumé
De nombreux problèmes comme la simulation de phénomènes physiques ou la manipulation de bases de données de grandes tailles nécessitent des performances que seuls les ordinateurs massivement parallèles, voire les méta-ordinateurs, peuvent fournir. Nos travaux concernent la conception de langages pour la programmation parallèle de haut niveau qui facilite leur usage.
Notre méthode a été de partir d'un modèle de parallélisme structuré possédant un modèle de prévision de performances (Bulk Synchronous Parallel ou BSP) puis de concevoir un ensemble d'opérations universelles qui permet la programmation de n'importe quel algorithme de ce modèle. Une approche opérationnelle nous a amené à définir des extensions du lambda-calcul par des primitives BSP.
Une bibliothèque basée sur ces calculs, la bibliothèque BSML a été développée pour le langage fonctionnel Objective Caml. La programmation BSML s'appuie sur une structure de données parallèle polymorphe. Les programmes sont des fonctions Objective Caml usuelles mais manipulent cette structure de données parallèle à l'aide d'un petit ensemble d'opérations dédiées. BSML suit le modèle BSP et est donc garanti sans inter-blocage. La confluence des calculs garantit quant à elle le déterminisme de BSML. La prévision de performances selon le modèle BSP a été vérifiée.
L'exposé comprendra une présentation du contexte de ces travaux, du modèle BSP et enfin de la bibliothèque BSML et de son utilisation.


Transparents
pdf


 

Simulation parfaite de réseaux de files d'attente :
application aux politiques de routage à base d'index



Date
12 octobre 2005 - 18h00

Orateur
Jean-Marc Vincent (laboratoire ID-IMAG, Grenoble)

Résumé
Plan de l'exposé :
  1. Réseaux de files d'attente : modélisation de systèmes et de réseaux
  2. Chaînes de Markov en temps continu (quelques éléments)
  3. Simulation parfaite : monotonie et accélération de simulation
  4. Routage à base d'index : un cadre général pour l'allocation dynamique de clients


Transparents
pdf


 

Algorithmes d'approximation : de la théorie à la pratique



Date
26 octobre 2005 - 18h00

Orateur
Nicolas Schabanel (ENS Lyon)

Résumé
La plupart des problèmes d'optimisation rencontrés dans la nature des projets industriels sont NP-difficiles. Pourtant, il faut bien les résoudre (p.ex., allouer les fréquences radio aux émetteurs GSM). La première approche naïve consiste à se dire que puisque le problème est NP-complet, il suffit de développer des heuristiques sans garantie autre que des courbes sur des exemples adhoc. Cependant un travail d'algorithmique est toujours possible et conduit à des résultats d'une grande richesse. Nous allons faire un tour sur des exemples de ce domaine de recherche, l'un des plus actifs en algorithmique actuellement.
Tout d'abord du point de vue constructif, des méthodes ont été développées pour permettre d'estimer la valeur des solution optimales, même si le problème est NP-difficile (et donc même si cette valeur n'est pas calculable en temps polyonomial), en se ramenant à un problème polynomial quitte à perdre un peu sur la qualité de la solution. Tout l'art de l'algorithmique d'approximation consiste à borner cette perte et à démontrer que la solution qu'on produit ainsi n'est qu'à un facteur raisonnable de l'optimum. Outre la conception d'un algorithme dont l'efficacité est prouvée, le résultat le plus important de ce type de travail est cette estimation de la valeur de l'optimum. Il s'agit la plupart du temps d'un minorant du coût optimal (pour un problème de minimisation), dont on peut se servir par la suite pour comparer des heuristiques ad hoc entre elles, permettant ainsi une analyse concrète et générique de leurs performances relatives, à l'aide d'une estimation absolue de l'optimum (contrairement aux comparaisons peu informatives des heuristiques entre elles sur des exemples adhoc). Le plus intéressant est qu'une fois que les paradigmes sont connus, il est maintenant relativement aisé de développer ces bornes inférieures qui permettent de plus des analyses pertinentes des performances des heurisitiques développées en pratiques.
Du point de vue des résultats d'impossibilité, ces travaux (années 1980-1990) ont démontré qu'il était possible de raffiner la notion brutale de NP-difficulté en la décomposant en différentes classes d'inapproximabilité croissante (à epsilon près, à une constante près, à un facteur polylog, à un facteur polynomial, à un facteur exponentiel,...) et qu'il existe des problèmes complets pour chacune de ces classes. Encore une fois, maintenant que ces problèmes complets sont connus, il suffit comme précédemment pour la NP-difficulté, d'effectuer la bonne réduction polynomiale du problème étudié au problème complet le plus proche pour obtenir un résultat bien plus informatif que la simple NP-difficulté, par exemple, de savoir s'il est possible d'approcher à epsilon près la solution optimale.


Transparents
pdf


 

Classification des automates cellulaires



Date
9 novembre 2005 - 18h00

Orateur
Jacques Mazoyer (ENS Lyon)

Résumé
Nous considérons ici les automates cellulaires comme un système simple servant à modéliser des phénomènes réels.Classifier les automates cellulaires consiste à en définir des classes en fonction des phénomènes qu'on veut comprendre.
Nous présenterons la problématique et l'historique de la classification en nous attachant à deux classifications. La première est historiquement de nature topologique et concerne la notion de chaos. Nous montrerons qu'il existe plusieurs classification de ce type dépendant de ce qu'on entend par chaos. La seconde de nature algébrique concerne l'apparition de particules (ou de concentration de l'information). Cette approche permet d'appréhender la notion d'intrinsèque universalité que nous évoquerons.



 

Ordonnancement pour le calcul parallèle :
fondamentaux et autres trucs rigolos



Date
23 novembre 2005 - 18h00

Orateur
Grégory Mounié (laboratoire ID-IMAG, Grenoble)

Résumé
Le problème de l'ordonnancement consiste à choisir le lieu et la date d'exécution d'une série d'action. C'est un des points essentiels à résoudre lorsque l'on utilise plusieurs ordinateurs simultanément pour exécuter une même application plus rapidement.
Nous montrerons dans cet exposé les aspects théoriques qui sont les fondements de nombreuses solutions pratiques et quelques algorithmes et techniques d'ordonnancement plus avancés.


Transparents
pdf


 

Problèmes philosophiques sous-tendant la représentation de la connaissance



Date
7 décembre 2005 - 18h00

Orateur
Sacha Bourgeois-Gironde (ENS LSH Lyon)

Résumé
La logique épistémique est l'outil contemporain le plus expressif de la représentation de la connaissance des agents. Elle fournit des ressources de modélisation relativement flexibles pour les buts des sciences de l'information. Cependant il y a des différences conceptuelles et pratiques importantes entre la notion de connaissance et la notion d'information. Si la cognition est généralement définie comme la capacité de traiter des informations, la connaissance peut être définie de son côté comme un état d'esprit obtenue à partir d'un ensemble de contraintes sur l'information traitée. On compte classiquement parmi ces contraintes: la conscience que doit avoir le sujet de disposer d'une information (awareness); la capacité du sujet de justifier, notamment en remontant de façon fiable à sa source, l'information vraie dont il dispose (backtracking); l'admission, comme faisant partie des connaissances du sujet, des conséquences logiques de ce qu'il connaît (epistemic closure / logical omniscience). Je discuterai la nature conceptuelle de ces contraintes, c'est-à-dire la manière dont elles ont été philosophiquement posées à travers une exigence d'analyse de la notion de connaissance. L'affaiblissement de ces contraintes, à l'intérieur de modèles sémantiques non-standard pour la logique épistémique, permet de rendre compte d'états cognitifs "infra-épistémiques" des agents, situés entre information disponible et connaissance avérée.


 

Tolérance aux défaillances dans les systèmes hautes-performances



Date
8 février 2006 - 18h00

Orateur
Aurélien Bouteiller (ENS Lyon)

Résumé
Il existe de nombreux problèmes scientifiques qui demandent une puissance de calcul colossale. La modélisation météo, l'écoulement des fluides autour d'un prototype aéronautique, ou la répartition des antennes GSM sur un territoire en sont autant d'exemples. Résoudre ces problèmes avec des machines classiques prendrait plusieurs années, aussi on définit des architectures hautes performances qui permettent d'obtenir une solution à l'échelle de quelques semaines. Pour obtenir ces performances de premier ordre, les supercalculateurs utilisent plusieurs processeurs qui collaborent, en communiquant entre eux, à la résolution du problème. Cette demande toujours croissante de puissance de calcul pousse à construire des supercalculateurs utilisant toujours plus de processeurs (130000 dans la machine BlueGene/L). Hors, statistiquement, la probabilité qu'une défaillance survienne est d'autant plus grande que le nombre de composants est grand. Le temps moyen entre deux fautes s'effondre sur les machines les plus récentes, et menace les perspectives de croissance de la puissance des supercalculateurs.
La tolérance aux défaillances a pour but de définir un ensemble de mécanismes qui permettent aux applications distribuées de survivre à divers type de pannes touchant les composants d'un système parallèle. Il s'agit de manière générale de s'assurer que lorsqu'un composant disparaît, il sera possible de restaurer l'état du processus qu'il hébergeait sur un autre composant. Le problème est rendu complexe par les dépendances qui existent entre l'état des divers processus participant au calcul distribué. Nous discuterons des diverses méthodes théoriques qui permettent d'assurer qu'un point de reprise ou un réplicat peuvent être utilisés pour continuer un calcul distribué interrompu par une défaillance.


Transparents
pdf


 

Calculer géométriquement sur le plan



Date
22 février 2006 - 18h00

Orateur
Jérôme Durand-Lose (LIFO, Université d'Orléans)

Résumé
Cet exposé se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations et atteindre une autre puissance de calcul. Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps) tant, pour analyser une dynamique que, pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires.

L'exposé commence par une présentation des automates cellulaires et la mise en avant d'exemples de particules/signaux tirés de la littérature. De là, nous abstrayons le modèle, les machines à signaux. Dans un premier temps, nous montrons comment tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs) peut y être mené. Nous montrons également comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné). Dans un second temps, nous nous intéressons aux points d'accumulation. Nous montrons que la prévision de l'apparition d'une accumulation est indécidable. Ce problème est même $\Sigma_20$-complet (hiérarchie arithmétique), en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles.
Avec quelques exemples, nous montrons l'existence d'accumulations , non pas en un point, mais sur un segment ou un Cantor. Nous introduisons alors une restriction sur les règles assurant qu'il ne peut y avoir que des accumulations sur des points isolés. Il est toujours possible de mener tout calcul malgré cette contrainte. Par ailleurs, les accumulations sont "propres", ce qui permet d'avoir une capacité de calcul semblables à celles sur les ordinaux ou de l'utilisation d'un "trou noir" (infinité d'itérations pendant une durée finie bornée).


Transparents
pdf


 

Expressions omega-régulières et extensions



Date
15 mars 2006 - 18h00

Orateur
Thomas Colcombet (IRISA, Rennes)

Résumé
Cet exposé comporte deux parties. La première concerne les résultats classiques sur les langages omega-réguliers. La seconde traitera d'extensions récentes de ces travaux.
Les expressions omega-régulières étendent les expressions régulières et permettent de décrire des langages de mots infinis, i.e. indexés par les naturels au lieu de {1..n} pour les mots finis. Elles peuvent par exemple décrire les mots infinis sur {a,b} contenant une infinité de lettre a. Tout comme dans le cas des langages réguliers, les langages obtenus sont clos sous union, intersection, projection et complementation, et le test du vide est décidable. Ces propriétés fortes permettent de les utiliser pour résoudre des questions logiques.
L'extension que nous considérons ajoute la possibilité de parler du comportement asymptotique de certaines actions. Elle permet par exemple d'exprimer l'ensemble des langages sur l'alphabet {a,b} tel que le nombre de 'a' est infini, et la taille des séquences de 'b' séparant deux lettres 'a' tend vers l'infini. Ce type de contrainte n'est pas exprimable par les langages omega-réguliers. Nous montrerons qu'une partie des résultats de clôture restent vrais. On déduit de ces propriétés de nouveaux résultats de décidabilité logique. Ce travail est issu d'une collaboration avec Mikolaj Bojanczyk (université de Varsovie).



 

From high-level parallel programming to high-level grid programming



Date
29 mars 2006 - 18h00

Orateur
Marco Aldinucci (ISTI CNR, Pise, Italie)

Résumé
A grid system is a geographically distributed collection of possibly parallel, interconnected processing elements, which all run some form of common grid middleware (e.g. Globus services). The key idea behind grid-aware applications is to make use of the aggregate power of distributed resources, thus benefiting from a computing power that falls far beyond the current availability threshold in a single site.

However, developing programs able to exploit this potential is highly programmer intensive. Programmers must design concurrent programs that can execute on large-scale platforms that cannot be assumed to be homogeneous, secure, reliable or centrally managed. They must then implement these programs correctly and efficiently. As a result, in order to build efficient grid-aware applications, programmers have to address the classical problems of parallel computing as well as grid-specific ones.

We recap basic problems of parallel computing, and basic parallel programming models. Also, we briefly sketch how high-level parallel programming models can be used to to tackle some of the difficult problems of parallel programming. We discuss additional complexity introduced in parallel programming by Grids, and why a low-level approach may hardly support the additional complexity to Quality of Service (QoS) control in real Grid-aware applications. We eventually describe the ASSIST programming environment, the prototype of parallel programming environment currently under development at University of Pisa (Italy), as a suitable basis to capture all the desired features for QoS control for the Grid. Grid applications, built as compositions of ASSIST components, are supported by an innovative Grid Abstract Machine, which includes essential abstractions of standard middleware services and a hierarchical Application Manager, which may be considered as an early prototype of Autonomic Manager.


Transparents
pdf



Responsable : Anne Benoit
Dernières modifications : 30 Mars 2006