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
| 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 |  |
| Date | 12 octobre 2005 - 18h00 | |||
| Orateur | Jean-Marc Vincent (laboratoire ID-IMAG, Grenoble) | |||
| Résumé | Plan de l'exposé :
|
|||
| Transparents | |
| 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 | |
| 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. |
| 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 | |
| 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. |
| 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 | |
| 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 | |
| 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). |
| 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 | |
| Responsable : Anne Benoit | Dernières modifications : 30 Mars 2006 |