Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'objectif de cette thèse est de produire un environnement permettant de raisonner formellement sur la correction de systèmes de calculs locaux, ainsi que sur l'expressivité de ce modèle de calcul. Pour ce faire, nous utilisons l'assistant de preuve Coq. Notre première contribution est la formalisation en Coq de la sémantique des systèmes de réétiquetage localement engendrés, ou calculs locaux. Un système de calculs locaux est un système de réétiquetage de graphe dont la portée est limitée. Nous proposons donc tout d'abord une implantation succincte de la théorie des graphes en Coq, et utilisons cette dernière pour définir les systèmes de réétiquetage de graphes localement engendrés. Nous avons relevé, dans la définition usuelle des calculs locaux, certaines ambiguïtés. Nous proposons donc une nouvelle définition, et montrons formellement que celle-ci capture toutes les sous-classes d'algorithmes étudiées. Nous esquissons enfin une méthodologie de preuve des systèmes de calculs locaux en Coq.Notre seconde contribution consiste en l'étude formelle de l'expressivité des systèmes de calculs locaux. Nous formalisons un résultat de D. Angluin (repris par la suite par Y. Métivier et J. Chalopin): l'inexistence d'un algorithme d'élection universelle. Nous proposons ensuite deux lemmes originaux concernant les calculs locaux sur les arêtes (ou systèmes LC0), et utilisons ceux-ci pour produire des preuves formelles d'impossibilité pour plusieurs problèmes: calcul du degré de chaque sommet, calcul d'arbre recouvrant, etélection. Nous proposons informellement une nouvelles classes de graphe pour laquelle l'élection est irréalisable par des calculs locaux sur les arêtes.Nous étudions ensuite les transformations de systèmes de calculs locaux et de leur preuves. Nous adaptons le concept de Forward Simulation de N. Lynch aux systèmes de calculs locaux et utilisons ce dernier pour démontrer formellement l'inclusion de deux modes de détection de terminaison dans le cas des systèmes LC0. La preuve de cette inclusion estsimplifiée par l'utilisation de transformations "standards" de systèmes, pour lesquels des résultats génériques ont été démontrés. Finalement, nous réutilisons ces transformations standards pour étudier, en collaboration avec M. Tounsi, deux techniques de composition des systèmes de réétiquetage LC0. Une bibliothèque Coq d'environ 50000 lignes, contenant les preuves formelles des théorèmes présentés dans le mémoire de thèse à été produite en collaboration avec Pierre Castéran (dont environ 40%produit en propre par V. Filou) au cours de cette thèse. / The goal of this work is to build a framework allowing the study, in aformal setting, of the correctness of local computations systems aswell as the expressivity of this model. A local computation system isa set of graph relabelling rules with limited scope, corresponding to a class of distributed algorithms.Our first contribution is the formalisation, in the Coq proofassistant, of a relationnal semantic for local computation systems.This work is based on an original formal graph theory for Coq.Ambiguities inherent to a "pen and paper" definition of local computations are corrected, and we prove that our definition captures all sub-classes of relabelling relations studied in the remainder. We propose a draft of a proof methodology for local computation systems in Coq. Our second contribution is the study of the expressivity of classes of local computations inside our framework. We provide,for instance, a formal proof of D. Angluin results on election and graph coverings. We propose original "meta-theorems" concerningthe LC0 class of local computation, and use these theorem to produce formal impossibility proofs.Finally we study possible transformations of local computation systemsand of their proofs. To this end, we adapt the notion of ForwardSimulation, originally formulated by N. Lynch, to localcomputations. We use this notion to define certified transformationsof LC0 systems. We show how those certified transformation can be useto study the expressivity of certain class of algorithm in ourframework. We define, as certified transformation, two notions ofcomposition for LC0 systems.A Coq library of ~ 50000 lines of code, containing the formal proofs of the theorems presented in the thesis has been produced in collaboration with Pierre Castéran.

Le secteur industriel de l'énergie, et les réseaux électriques en particulier, rendent à nos sociétés modernes d'immenses services dont nous ne pouvons plus nous passer. Ils présentent aussi, hélas, un certain nombre de graves inconvénients, notamment en matière d'impact environnemental. Ces inconvénients apparaissent aujourd'hui comme inacceptables; le secteur de l'énergie s'efforce donc actuellement de les amoindrir autant que possible, dans le cadre de ce qu'on appelle la transition énergétique.Outre d'indispensables efforts en matière de sobriété et d'efficacité énergétique, deux grands axes d'amélioration se dessinent: d'une part, le remplacement progressif de certains moyens de production d'électricité conventionnels par des moyens de production renouvelables; et d'autre part, le transfert de certains usages aujourd'hui non-électriques vers l'électricité --- en particulier en matière de mobilité.L'intégration au réseau électrique de ces nouveaux types de dispositifs pose cependant des difficultés techniques considérables, qui motivent depuis le début des années 2000 de nombreux travaux sur le thème de ce que l'on appelle aujourd'hui les "smart grids": des réseaux électriques compatibles avec les exigences de la transition énergétique, c'est-à-dire capables d'accueillir massivement les nouveaux types d'usages comme la production photovoltaïque et les bornes de recharge des véhicules électriques, ceci notamment grâce à l'utilisation accrue des nouvelles technologies de l'information et de la communication. Parmi les difficultés susmentionnées, qui limitent la capacité d'accueil du réseau, figurent les congestions, c'est-à-dire les limites physiques à la puissance que l'on peut faire transiter d'un point à un autre sur une infrastructure donnée. C'est à la gestion des congestions que nos travaux sont consacrés. À ce sujet, la question fondamentale est de déterminer par quel enchaînement de mesures, de calcul, de communications et in fine d'actions, on peut passer d'une situation de contrainte sur un réseau de distribution d'électricité, à une situation où cette contrainte a été éliminée par l'action des flexibilités environnantes; autrement dit, en augmentant ou en réduisant judicieusement la production et/ou la consommation locales, et éventuellement en jouant sur d'autres types de leviers.L'objet de cette thèse est de participer à l'élaboration des outils conceptuels et informatiques qui nous permettront de répondre à la question fondamentale ci-dessus. Nos travaux portent ainsi sur la question de la modélisation des réseaux de distribution d'électricité "flexibles", et sur l'implémentation concrète des modèles retenus sous forme d'un logiciel de simulation ad hoc, parfaitement adapté à l'étude de ce type de réseaux. / The energy sector and the electrical networks in particular, provide great and indispensable services to our modern societies. Unfortunately, they also bring some serious drawbacks, especially with regard to the environment. These drawbacks are becoming more and more unacceptable; that is why the energy sector is trying to reduce them as much as possible, in the framework of the so-called energy transition.In addition to mandatory efforts in terms of energy efficiency and sobriety, two major directions of improvement have been identified: on the one hand, the progressive replacement of some conventional power plants with renewable production units; and on the other hand, the transfer of several non-electrical usages towards electricity --- in particular in the area of mobility.The integration of these new devices into electrical networks raise new technical challenges which, since the early 2000s, have been driving a lot of work about so-called "smart grids": electrical networks compatible with the requirements of the energy transition, ie. able to host new devices like photovoltaic solar panels and charging stations for electric vehicles, notably through the increasing usage of new information and communications technologies.Among the difficulties mentioned above, which limit the hosting capacity of the network, there are congestions ie. physical constraints limiting the amount of power that may be transmitted through a given infrastructure. Our work is devoted to the management of congestions. The fundamental issue thereon is to define a sequence of decisions, computations, communications and in fine actionsthat allows to move from a constrained situation on the electrical distribution network, to a situation in which the action of local flexibilities has lifted the constraint; in other words, to a situation where increasing or decreasing local generation and/or consumption, or taking some other control action, relieved the network.The aim of this thesis is to contribute to the development of conceptual and computing tools that will allow us to answer the fundamental aforementioned issue. Our work thus deals with the modelling of flexible electrical distribution networks, and with the tangible implementation of selected models in the form of ad hoc simulation software, specifically designed for the study of such networks.

La mécatronique est l'intégration de différentes sciences et techniques de la mécanique, de l'automatique, de l'électronique et de l'informatique. L'évolution rapide des marchés concurrents exige la diminution du temps de développement d'un produit tout en augmentant la qualité et la performance du système. Il est donc nécessaire d'augmenter l'efficacité du processus de conception. Pour répondre à cette nécessité, en complément des outils d'analyse, la simulation, et spécialement le prototypage virtuel, est devenu l'une des clés technologiques. Il est difficile de trouver des outils de simulation capables d'analyser des systèmes pluridisciplinaires dépendants de différents domaines. Pourtant, un environnement qui permet une simulation intégrée multidisciplinaire de systèmes mécatroniques est nécessaire pour une évaluation fonctionnelle plus précise de la conception du produit et pour améliorer la qualité et l'efficacité de cette conception. La présente contribution décrit une méthode de conception et de simulation des systèmes mécatroniques. On identifie d'abord le modèle de comportement et le modèle géométrique 3D associé. Ensuite, le modèle de comportement est vu comme un système dynamique hybride formé de deux automates hybrides couplés (Partie Opérative, Partie Commande). Nous présentons ensuite les simulateurs OpenMASK, OpenModelica, le standard IEEE1516 HLA et les travaux reliés à cette architecture de simulation distribuée. Dans une démarche descendante, nous présentons ensuite notre approche et notre expérimentation pour intégrer les fonctionnalités de HLA dans ces simulateurs, pour distribuer les éléments de modélisation de systèmes mécatroniques de haut niveau et enfin pour compléter Modelica sur le formalisme des automates hybrides qui nous est indispensable. Nous proposons des extensions pour intégrer le temps réel en vue de simulations interactives. Nous appliquons enfin cette approche sur les simulateurs cités en utilisant le bus HLA CERTI sous un environnement Linux à partir d'un exemple représentatif d'un système mécatronique

Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. <br /><br />Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective. <br /><br />Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.

La mutualisation des ressources physiques réparties dans les universités, les instituts et les entreprises a permis l'émergence des grilles de calcul. Ces infrastructures dynamiques sont bien adaptées aux applications scientifiques ayant de grands besoins en puissance de calcul et en espace de stockage. L'un des défis majeur pour les grilles de calcul reste la simplification de leur utilisation. Contrairement au déploiement d'applications sur une infrastructure centralisée, le déploiement sur une grille nécessite de nombreuses tâches pénibles pour l'utilisateur. La sélection des ressources, le transfert des programmes ainsi que la surveillance de l'exécution sont en effet laissés à sa charge. Aujourd'hui, de nombreux travaux proposent d'automatiser ces étapes dans des cas simples. En revanche très peu permettent de prendre en charge des déploiements plus complexes, comme par exemple le redéploiement d'une partie de l'application pendant son exécution ou encore le déploiement coordonné de plusieurs applications. <br /><br />Dans cette thèse, nous proposons un modèle pour prendre en charge le déploiement dynamique des applications sur les grilles de calcul. Ce modèle vise à offrir deux fonctionnalités principales. La première consiste en la traduction d'actions de haut niveau, spécifiques aux applications, en opérations de bas niveau, relatives à la gestion des ressources sur la grille. La deuxième consiste en la pré-planification des déploiements, redéploiements et codéploiements d'applications sur les ressources physiques. <br /><br />Le modèle satisfait trois propriétés. Il rend transparent la gestion des ressources à l'utilisateur. Il offre des actions spécifiques aux besoins de l'application. Enfin, il est non-intrusif en limitant les contraintes sur le modèle de programmation de l'application. <br /><br />Une proposition d'architecture nommée CORDAGE vient illustrer ce modèle pour le co-déploiement et le redéploiement d'applications. CORDAGE a été développé en lien avec l'outil de réservation OAR et l'outil de déploiement ADAGE. La validation du prototype s'est effectuée avec la plate-forme pair-à-pair JXTA, le service de partage de données JUXMEM ainsi que le système de fichiers distribué GFARM. Notre approche a été évaluée sur la grille expérimentale GRID' 5000.<br /><br />http://cordage.gforge.inria.fr/

Les lasers à rétroaction répartie (DFB) permettent de générer des impulsions à spectre très étroit, et sont des sources lasers compactes et accordables en fréquence pour des applications en optique intégrée. Au cours de cette thèse, un laser DFB dynamique a été obtenu pour la première fois dans une configuration de pompage en réflexion. Un DFB accordable à bande photonique interdite, créé par la superposition de deux faisceaux de pompe, a été réalisé dans un matériau laser dopé par des colorants, indiquant l'existence d'une modulation photoinduite de l'indice de réfraction. <br />La modulation de la polarisation, réalisée par l'ajustement de l'état de polarisation des deux faisceaux de pompe, est une technique très efficace afin d'obtenir le feedback pour l'oscillation du laser DFB dans la configuration du pompage en réflexion. Une structure photonique DFB accordable et chirale a été observée avec certains choix de polarisation des faisceaux de pompe, ce qui peut être identifié comme un laser DFB dynamique, chiral, à bande photonique interdite dépendante de la polarisation. Une émission laser à polarisation circulaire a été ainsi obtenue.

Cette thèse est consacrée a l'étude de l'implantation du langage Prolog sur les architectures parallèles Mimd sans mémoire commune. Nous présentons le modèle opéra qui exploite implicitement le parallélisme ou le Prolog pour repartir dynamiquement l'évaluation des programmes sur les différents nœuds du réseau de processeurs. Le système opéra est de type multisequentiel: il n'y a parallélisation que lorsqu'un processeur est inoccupé. Ce système se décompose en une partie operative chargée de l'évaluation du programme Prolog, et une partie contrôle chargée de l'allocation des travaux aux processeurs de la partie operative. Les principaux problèmes de ce type de systèmes sont d'une part le choix de représentation en mémoire de l'arbre ou ainsi que la gestion des liaisons multiples, et d'autre part, le contrôle de l'allocation des différentes branches de l'arbre aux machines abstraites qui effectuent des évaluations séquentielles. La technique de régulation de charge utilisée est fondée sur des méthodes heuristiques. L'ordonnanceur d'opera travaille sur une image approchée de l'état global du système obtenu par échantillonnage des états locaux de chaque unités de travail. Un prototype d'opera a été réalisé sur un réseau de transputers reconfigurable dynamiquement: le supernode. Cette propriété a ete mise a profit dans notre implantation pour réduire les couts de communication. Les communications sont effectuées en parallèle avec le calcul. Le prototype réalisé fournit des gains de performances importants et opera figure parmi les systèmes Prolog parallèles les plus efficaces a l'heure actuelle

Cette thèse est composée de deux parties: les développements lies à la génération des nombres premiers et l'implantation du crible quadratique. Dans la première partie, nous analysons les stratégies d'allocation des données aux processeurs pour le crible d'Eratosthène dans un environnement à mémoire partagée en vue d'améliorer l'équilibrage de la charge de travail. Puis, nous proposons des implantations sur l'hypercube FPS T40 a mémoire distribuée. Comme le caractère centralise du crible d'Eratosthène (de type maitre/esclaves) s'accommode mal des exigences de l'architecture distribuée, nous étudions un algorithme de génération des nombres premiers par divisions successives sur un anneau. Cet algorithme nécessite la mise en œuvre d'une technique de détection de la terminaison distribuée, par un dénombrement des processeurs ayant termine l'exécution de leur programme. Enfin, l'aspect maitre/esclaves du crible d'Eratosthène permet l'étude de méthodologies d'implantation de ce type d'algorithmes sur un réseau linéaire et une grille de processeurs. La deuxième partie est consacrée au crible quadratique multipolynomial, algorithme de factorisation des grands entiers, utilise en cryptographie. Notre but est d'extraire le maximum de parallélisme de chacune des étapes de cet algorithme dans un environnement distribue, afin d'utiliser au mieux la puissance des calculateurs massivement parallèles. Cette étude conduit a une implantation efficace sur l'hypercube FPS T40

Étude et réalisation d'une mémoire virtuelle d'objets pour un système Smalltalk centralisé. Extension de la mémoire centralisée des objets pour un environnement reparti