L'objectif de cette thèse est de concevoir un calcul d'objets permettant d'écrire des applications parallèles et distribuées, en particulier dans un cadre à grande échelle, tout en assurant de bonnes propriétés. Le calcul proposé s'intitule ASP : Asynchronous Sequential Processes. Les principales caractéristiques de ce calcul sont : des communications asynchrones, la présence de futurs et une exécution séquentielle dans chacun des processus. Ce calcul exhibe de fortes propriétés de confluence et de déterminisme. Cette thèse a donc aussi pour objectif de prouver de telles propriétés dans un cadre aussi général que possible. ASP est basé sur une répartition des objets en différentes activités disjointes. Une activité est un ensemble d'objets gérés par un unique processus. Les objets actifs sont des objets accessibles par des références globales/distantes. Ils communiquent à travers des appels de méthodes asynchrones avec un mécanisme de futurs. Un futur est une référence globale désignant un résultat qui n'est pas encore calculé. Cette thèse modélise ces différents aspects, leurs principales propriétés et les conséquences de ces mécanismes sur la notion de comportement déterministe des programmes. Le résultat principal consiste en une propriété de confluence et son application à l'identification d'un ensemble de programmes se comportant de façon déterministe. Du point de vue pratique, ASP peut aussi être considéré comme une modélisation de la librairie ProActive. Cette librairie fournit des outils pour développer des applications parallèles et distribuées en Java.

La difficulté de programmation des architectures parallèles à mémoire distribuée est un obstacle à l'exploitation de leur puissance de calcul potentielle. Parmi les différentes approches proposées pour pallier à cette difficulté, celle de la compilation dirigée par les données semble prometteuse, notamment dans le domaine du calcul scientifique. Le programme source, exprimé par exemple en HPF, est un programme séquentiel impératif dans lequel il est précisé comment sont réparties les données sur les processeurs ; le compilateur dérive un code parallèle en distribuant le contrôle d'après la distribution des données. La mise en oeuvre de cette approche nécessite le développement d'environnements complets. Cette thèse présente le travail réalisé dans le cadre d'un environnement de ce type : l'environnement Pandore. Nous nous sommes intéressés à la conception et la réalisation d'un exécutif portable et efficace qui doit être associé au compilateur ainsi qu'à l'évaluation des performances des programmes générés. Après avoir situé l'approche de la compilation par distribution de données dansle contexte plus large de la programmation des machines parallèles à mémoire distribuée, nous définissons des opérations de haut niveau qui permettent la description des schémas de compilation et la prise en compte des optimisations. Deux types de machines cibles sont considérés, d'une part des machines à messages et d'autre part des machines disposant d'un mécanisme de mémoire virtuelle partagée. Les points clés de la mise en oeuvre des opérations dans le compilateur et l'exécutif sont abordés. Nous insistons plus particulièrement sur la gestion des données distribuées et sur les optimisations des communications à l'exécution. Une mise en oeuvre réalisée dans l'environnement Pandore est ensuite détaillée. L'évaluation des performances des programmes est également étudiée, dans un premier temps par une série d'expérimentations sur plusieurs applications et dans un deuxième temps par la définition d'outils de mesure et de visualisation adaptés à la compilation par distribution de données.

Effectuer des calculs d'illumination globale pour des environnements complexes et les visualiser de manière interactive demeure un problème difficile en synthèse d'images. En effet, la radiosité hiérarchique est un processus très coûteux en termes de temps de calcul et de ressources mémoire, même pour des scènes de complexité moyenne. Par conséquent, dans le cas d'environnements complexes, une étape de précalcul est nécessaire. Ce précalcul consiste à découper la scène en plusieurs régions (appelées cellules) et évaluer les relations de visibilité entre ces régions. La méthode de découpage (ou de structuration) que nous proposons est inspirée de l'analyse d'images et consiste à mettre en correspondance des modèles génériques de cellules avec des éléments géométriques déduits de la scène. Comparée à la technique de subdivision binaire de l'espace, cette méthode fournit des résultats beaucoup plus convaincants car le nombre de cellules obtenues est plus faible et par conséquent les calculs de visibilité et de simulation d'éclairage se trouvent simplifiés. A chaque étape de la simulation d'éclairage, seule une petite partie de la scène réside en mémoire. Les informations géométriques et photométriques nécessaires à la représentation des objets de la scène sont stockées sur disque. La simulation de la propagation de la lumière est alors considérée comme la composition de tâches élémentaires consistant à (i) charger en mémoire les informations nécessaires à la simulation, (ii) effectuer les calculs de radiosité, (iii) remettre à jour la base de données sur le disque. Néanmoins, afin de réduire les nombreux échanges d'information entre le disque et la mémoire, il est nécessaire d'ordonner les calculs de manière efficace. Pour cela, nous proposons plusieurs stratégies d'ordonnancement des calculs reposant sur une prédiction des coûts de ces échanges d'informations à court, moyen ou long terme. Ces stratégies utilisent les connaissances relatives à la structuration de la scène en cellules et les relations de visibilité qui existent entre elles. Nous avons mis en oeuvre une version parallèle de cet algorithme à l'aide de l'environnement de programmation MPI (Message Passing Interface). Dans ce cas, toutes les données sont stockées sur un disque commun à tous les processeurs afin de réduire le nombre de messages et leur taille. Chaque processeur effectue les calculs pour un ensemble de régions selon les mêmes stratégies d'ordonnancement que l'algorithme séquentiel. Un mécanisme d'équilibrage de charge dynamique suivant une technique de vol de tâche (task stealing) permet d'éviter que certains processeurs restent inactifs au cours des calculs. Enfin, la terminaison de l'algorithme est réalisée à l'aide d'une reconfiguration dynamique des processeurs en anneau qui permet également la gestion de la convergence de l'algorithme.

Cette thèse étudie un modèle de plate-forme de communication pour la programmation des grilles de calcul. Notre but est d'étendre la portée des grilles en permettant l'exécution d'applications parallèles et/ou réparties sans imposer de contrainte de programmation ou d'exécutif particulier. Le modèle proposé permet l'utilisation d'exécutifs variés, adaptés à l'application plutôt que ceux dictés par les réseaux disponibles. Notre approche est basée sur : un arbitrage des accès aux ressources, pour permettre plusieurs exécutifs simultanément ; une adaptation d'abstraction qui permet de voir les ressources selon le paradigme choisi par l'utilisateur ; une virtualisation des ressources, qui permet l'utilisation d'exécutifs existants sans les modifier. Nous avons mis en oeuvre ce modèle dans la plate-forme PadicoTM, et porté divers exécutifs sur cette plate-forme, tels que MPI, CORBA, et SOAP. Les réseaux utilisables vont des SAN jusqu'aux WAN. Les performances obtenues sont excellentes.

Le domaine de la simulation numérique évolue vers des simulations de phénomènes physiques toujours plus complexes. Cela se traduit typiquement par le couplage de plusieurs codes de simulation, où chaque code va gérer une physique (simulations multi-physiques) ou une échelle particulière (simulations multi-échelles). Dans ce cadre, l'analyse des résultats des simulations est un point clé, que ce soit en phase de développement pour valider les codes ou détecter des erreurs, ou en phase de production pour confronter les résultats à la réalité expérimentale. Dans tous les cas, le pilotage de simulations peut aider durant ce processus d'analyse des résultats. L'objectif de cette thèse est de concevoir et de réaliser une plate-forme logicielle permettant de piloter de telles simulations. Plus précisément, il s'agit à partir d'un client de pilotage distant d'accéder ou de modifier les données de la simulation de manière cohérente, afin par exemple de visualiser "en-ligne" les résultats intermédiaires. Pour ce faire, nous avons proposé un modèle de pilotage permettant de représenter des simulations couplées et d'interagir avec elles efficacement et de manière cohérente. Ces travaux ont été validés sur une simulation multi-échelles en physique des matériaux.

Le sujet de cette thèse est la conception d'un support d'exécution orienté objet pour applications réparties. Un des principaux objectifs est de permettre de correctement isoler le code lié à la gestion du support d'exécution du code propre à l'application. D'autre part, un tel support se doit d'être portable sur le plus grand nombre de plate-formes ; pour cela son interface de programmation doit être minimale tout en restant extensible. La prise en compte de tels critères permet d'obtenir un support pour une grande variété d'applications réparties. Nous avons donc conçu et implémenté un support d'exécution sous la forme d'une bibliothèque de classes appelée Schooner. Le modèle de programmation de la bibliothèque s'articule autour des notions de machine virtuelle et d'entités réparties communiquant par messages actifs. En plus de ce modèle de base, nous avons également développé une extension multi-active permettant l'utilisation de processus légers. Afin de compléter et valider \schooner, des outils d'aide au développement et de mise au point d'applications réparties sont également fournis. Une des caractéristiques importantes de l'environnement fourni est d'être facilement personnalisable selon les besoins spécifiques d'une application en permettant par exemple une amélioration des performances. Dans ce contexte, nous proposons un mécanisme de bufferisation des messages entre deux entités communicantes, mécanisme entièrement paramétrable par l'utilisateur. Il est également envisageable dans le cadre de la version multi-active de modifier l'ordonnancement des entités actives. Cet environnement a pu être validé par le développement de deux applications de taille conséquente : la version répartie d'un simulateur à événements discrets orienté objet, Prosit et une extension répartie et parallèle du langage C++, C++//.

Les langages synchrones ont été fondés pour modéliser et implémenter les systèmes réactifs temps-réels critiques. Avec la complexité toujours croissante des systèmes contrôlés, la vitesse d'exécution devient un critère important. Nous sommes donc à la recherche d'une exécution parallèle, combinant efficacité et sûreté.Les langages synchrones ont toujours intégré la notion de parallélisme, mais ce, pour l'expressivité de la modélisation. Leurs compilations visent principalement les circuits ou la génération de code séquentiel. Tous ont une sémantique formelle, qui rend possible la distribution correcte du code. Mais la préservation de cette sémantique peut être un obstacle à l'efficacité du code généré, particulièrement s'il est nécessaire de préserver une notion d'instant global au système.Le modèle sémantique qui nous intéresse est celui des réseaux de Kahn. Ces réseaux modélisent des calculateurs distribués, communiquant au travers de files de taille non bornée. Dans ce cadre, la distribution ne demande aucune communication ni synchronisation supplémentaire. En considérant l'histoire des files de communication, la sémantique de Kahn permet de s'abstraire de l'exécution effective, tout en garantissant le déterminisme du calcul. Pour cela, chaque nœud du réseau doit avoir une sémantique fonctionnelle continue.Le langage que nous développons est Heptagon, un langage synchrone fonctionnel du premier ordre, déscendant de Lustre. Son compilateur est un prototype universitaire, apparenté à l'outil industriel Scade. Grâce à sa sémantique de Kahn, la distribution d'un programme Heptagon ne pose pas de question, son efficacité beaucoup plus.L'efficacité requiert de minimiser les synchronisations. Cela revêt deux aspects non indépendants. Avoir un découplage suffisant des calculs : il y a des délais dans les dépendances entre calculs. Avoir une granularité importante des calculs : un fort ratio temps de calcul sur fréquence de communication. Or la sémantique synchrone et les horloges d'un programme Heptagon reflètent exactement l'inverse. Elles permettent au programmeur de se contenter d'un découplage d'un instant et à chaque instant, au maximum une valeur est calculée. De plus, les instants sont typiquement courts, pour assurer que le système réagit rapidement.Des précédents travaux sur le sujet, nous tirons deux constats.Le premier est que nous souhaitons le contrôle du parallélisme par le programmeur, directement dans le code source. Il doit pouvoir maîtriser à quels instants il y a communication ou synchronisation. La solution que nous proposons dans ce manuscrit est l'utilisation des futures dans Heptagon. Ils fournissent ce pouvoir au programmeur, tout en restant des annotations qui peuvent être supprimées sans changer la sémantique dénotationnelle du programme.Le deuxième constat est que la question de la granularité des calculs est une question profonde, touchant en particulier aux questions de dépendance de données, de choix des horloges et de compilation modulaire. Heptagon, comme ses parents, restreint les réseaux de Kahn qui peuvent être écrits, de telle sorte que ces trois questions se traitent séparément. Pour mieux comprendre le lien entre ces éléments, nous revenons aux réseaux de Kahn. Notre principal résultat est la définition de la sous-classe des réseaux ordonnés réactifs. Ceux-ci sont les seuls pour lesquels nous pouvons décrire modulairement le comportement avec des horloges, sans restreindre les contextes d'appels. Ces réseaux ont une signature d'horloge en forme normale, qui maximise la granularité. Pour l'exprimer, nous introduisons les horloges entières, décrivant la communication de plusieurs valeurs en un seul instant. Nous appliquons ensuite nos résultats pour voir sous un nouveau jour Heptagon, Signal, les politiques des objets de Lucid Synchrone, mais aussi proposer une analyse pleinement modulaire de Lucy-n langage synchrone le plus fidèle aux réseaux de Kahn.

Cette thèse traite du problème de la redistribution dynamique parallèle efficace de la charge pour les problèmes numériques de très grande taille. Nous présentons tout d'abord un état de l'art des algorithmes permettant de résoudre les problèmes du partitionnement, du repartitionnement, du placement statique et du re-placement. Notre première contribution vise à étudier, dans un cadre séquentiel, les caractéristiques algorithmiques souhaitables pour les méthodes parallèles de repartitionnement. Nous y présentons notre contribution à la conception d'un schéma multi-niveaux k-aire pour le calcul sequentiel de repartitionnements. La partie la plus exigeante de cette adaptation concerne la phase d'expansion. L'une de nos contributions majeures a été de nous inspirer des méthodes d'influence afin d'adapter un algorithme de raffinement par diffusion au problème du repartitionnement.Notre deuxième contribution porte sur la mise en oeuvre de ces méthodes sur machines parallèles. L'adaptation du schéma multi-niveaux parallèle a nécessité une évolution des algorithmes et des structures de données mises en oeuvre pour le partitionnement. Ce travail est accompagné d'une analyse expérimentale, qui est rendue possible grâce à la mise en oeuvre des algorithmes considérés au sein de la bibliothèque Scotch.

L'indexation et la recherche efficiente de données complexes constitue un besoin croissant face à la taille et à la variété des bases de données actuelles. Nous proposons une structure d'index arborescent basée sur un partitionnement d'un espace métrique à base de boules et d'hyper-plans. Les performances de cet index sont évaluées expérimentalement sur des collections de complexités intrinsèques différentes. La parallélisation de l'algorithme de recherche des k plus proches voisins est également effectuée afin d'encore améliorer les performances.

The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.