Le but de cette thèse est l'étude et l'implémentation de routines de base pour aider l'utilisateur de machines parallèles à mémoire distribuée à obtenir les meilleures performances avec un coût de développement moindre. Trois ensembles de routines sont étudiés. Le premier concerne des routines de communication sur réseau réconfigurable. La seconde bibliothèque fournit à l'utilisateur des routines portables de recouvrements calculs/communications transparents. Enfin, le dernier ensemble concerne des routines de calcul comme le produit de matrices, la factorisation LU et la transformée de Fourier bidimensionnelle. Une attention toute particulière est portée aux recouvrements calculs/communications. Enfin, une application des principes présentés tout au long de la thèse est donnée. Elle concerne la simulation d'un front de combustion

La simulation de la neutronique d'un coeur de réacteur nucléaire est basée sur l'équation du transport des neutrons, et un calcul de criticité conduit à un problème à valeur propre. Parmi les méthodes de résolution déterministes, l'approximation de la diffusion est souvent utilisée. Le solveur MINOS basé sur une méthode d'éléments finis mixte duale, a montré son efficacité dans la résolution de ce problème. Afin d'exploiter les ordinateurs parallèles, et de réduire les coûts en temps de calcul et en mémoire, nous proposons dans ce mémoire deux méthodes de décomposition de domaine pour la résolution du problème à valeur propre de la diffusion des neutrons sous forme mixte duale. La première méthode est inspirée d'une méthode de synthèse modale : la solution est cherchée dans une base constituée d'un nombre fini de modes propres locaux calculés par MINOS sur des sous-domaines recouvrants. La deuxième méthode est un algorithme itératif de Schwarz modifié qui utilise des sous-domaines non recouvrants et des conditions de Robin aux interfaces entre sous-domaines. A chaque itération, le problème est résolu par MINOS sur chaque sous-domaine avec des conditions aux interfaces calculées à partir des solutions sur les sous-domaines adjacents à l'itération précédente. Les itérations permettent la convergence simultanée de la décomposition de domaine et du problème à valeur propre. Les résultats numériques obtenus sur des modèles 2D et 3D de coeurs réalistes montrent la précision et l'efficacité en parallèle de ces deux méthodes.

Le calcul de réécriture ou rho-calcul est une généralisation du lambda-calcul avec filtrage et agrégation de termes. L'abstraction sur les variables est étendue à une abstraction sur les motifs et le filtrage correspondant peut être effectué modulo une théorie <br />équationnelle a priori arbitraire. L'agrégation est utilisée pour collecter les différents résultats possibles.<br />Dans cette thèse, nous étudions différentes combinaisons des ingrédients fondamentaux du rho-calcul: le filtrage, l'agrégation et les mécanismes d'ordre supérieur.<br />Nous étudions le filtrage d'ordre supérieur dans le lambda-calcul pur modulo une restriction de la beta-conversion appelée super-développements. Cette nouvelle approche est suffisamment expressive pour traiter les problèmes de filtrage du second-ordre et ceux avec des motifs d'ordre supérieur à la Miller.<br />Nous examinons ensuite les modèles catégoriques du<br />lambda-calcul parallèle qui peut être vu comme un enrichissement du lambda-calcul avec l'agrégation de termes. Nous montrons que ceci est une étape significative vers la sémantique dénotationnelle du calcul de réécriture.<br />Nous proposons également une étude et une comparaison des calculs avec motifs éventuellement dynamiques, c'est-à-dire qui peuvent être instanciés et réduits. Nous montrons que cette étude, et plus particulièrement la preuve de confluence, est suffisamment générale pour<br />s'appliquer à l'ensemble des calculs connus. Nous étudions ensuite l'implémentation de tels calculs en proposant un calcul de réécriture avec filtrage et substitutions explicites.

Le contrôle de la qualité des calculs de structure suscite un intérêt croissant dans les processus de conception et de certification. Il repose sur l'utilisation d'estimateurs d'erreur, dont la mise en pratique entraîne un sur-coût numérique souvent prohibitif sur des calculs de grande taille. Le présent travail propose une nouvelle procédure permettant l'obtention d'une estimation garantie de l'erreur de discrétisation dans le cadre de problèmes linéaires élastiques résolus au moyen d'approches par décomposition de domaine. La méthode repose sur l'extension du concept d'erreur en relation de comportement au cadre des décompositions de domaine sans recouvrement, en s'appuyant sur la construction de champs admissibles aux interfaces. Son développement dans le cadre des approches FETI et BDD permet d'accéder à une mesure pertinente de l'erreur de discrétisation bien avant convergence du solveur lié à la décomposition de domaine. Une extension de la procédure d'estimation aux problèmes hétérogènes est également proposée. Le comportement de la méthode est illustré et discuté sur plusieurs exemples numériques en dimension 2.

L'optimisation de la distribution de l'eau est un enjeu crucial qui a déjà été ciblé par de nombreux outils de modélisation. Des modèles utiles, implémentés il y a des décennies, ont besoin d'évoluer vers des formalismes et des environnements informatiques plus récents. Cette thèse présente la refonte d'un ancien logiciel de simulation hydraulique (IRMA) écrit en FORTRAN, qui a été utilisé depuis plus de 30 ans par la Société du Canal de Provence, afin de concevoir et maintenir les réseaux de distribution d'eau. IRMA a été développé visant principalement pour le traitement des réseaux d'irrigation - en utilisant le modèle probabiliste d'estimation de la demande de Clément - et il permet aujourd'hui de gérer plus de 6.000 km de réseaux d'eau sous pression. L'augmentation de la complexité et de la taille des réseaux met en évidence le besoin de moderniser IRMA et de le réécrire dans un langage plus actuel (Java). Cette thèse présente le modèle de simulation implémenté dans IRMA, y compris les équations de perte de charge, les méthodes de linéarisation, les algorithmes d'analyse de la topologie, la modélisation des équipements et la construction du système linéaire. Quelques nouveaux types de simulation sont présentés: la demande en pointe avec une estimation probabiliste de la consommation (débit de Clément), le dimensionnement de pompe (caractéristiques indicées), l'optimisation des diamètres des tuyaux, et la variation de consommation en fonction de la pression. La nouvelle solution adoptée pour résoudre le système linéaire est décrite et une comparaison avec les solveurs existants en Java est présentée. La validation des résultats est réalisée d'abord avec une comparaison entre les résultats obtenus avec l'ancienne version FORTRAN et la nouvelle solution, pour tous les réseaux maintenus par la Société du Canal de Provence. Une deuxième validation est effectuée en comparant des résultats obtenus à partir d'un outil de simulation standard et bien connu (EPANET). Concernant les performances de la nouvelle solution, des mesures séquentielles de temps sont présentées afin de les comparer avec l'ancienne version FORTRAN. Enfin, deux cas d'utilisation sont présentés afin de démontrer la capacité d'exécuter des simulations distribuées dans une infrastructure de grille, utilisant la solution ProActive. La nouvelle solution a déjà été déployée dans un environnement de production et démontre clairement son efficacité avec une réduction significative du temps de calcul, une amélioration de la qualité des résultats et une intégration facilitée dans le système d'information de la Société du Canal de Provence, notamment la base de données spatiales.

L'équilibrage de charge est une étape importante conditionnant les performances des applications parallèles. Dans le cas où la charge varie au cours de la simulation, il est important de redistribuer régulièrement la charge entre les différents processeurs. Dans ce contexte, il peut s'avérer pertinent d'adapter le nombre de processeurs au cours d'une simulation afin d'obtenir une meilleure efficacité, ou de continuer l'exécution quand toute la mémoire des ressources courantes est utilisée. Contrairement au cas où le nombre de processeurs ne varie pas, le rééquilibrage dynamique avec un nombre variable de processeurs est un problème peu étudié que nous abordons ici. Cette thèse propose différentes méthodes basées sur le repartitionnement de graphe pour rééquilibrer la charge tout en changeant le nombre de processeurs. Nous appelons ce problème " repartitionnement M × N ". Ces méthodes se décomposent en deux grandes étapes. Dans un premier temps, nous étudions la phase de migration et nous construisons une " bonne " matrice de migration minimisant plusieurs critères objectifs comme le volume total de migration et le nombre total de messages échangés. Puis, dans un second temps, nous utilisons des heuristiques de partitionnement de graphe pour calculer une nouvelle distribution optimisant la migration en s'appuyant sur les résultats de l'étape précédente. En outre, nous proposons un algorithme de partitionnement k-aire direct permettant d'améliorer le partitionnement biaisé. Finalement, nous validons cette thèse par une étude expérimentale en comparant nos méthodes aux partitionneurs actuels.

Cette thèse présente des algorithmes permettant la parallélisation dans la direction temporelle de la simulation des systèmes régis par des équations aux dérivées partielles issues de trois domaines d'application proposant des modèles complexes: \textbf{1. Contrôle optimal d'équations paraboliques:}\\ Nous développons deux algorithmes parallèles (SITPOC et PITPOC). Ces deux algorithmes sont basés sur une méthode générale de décomposition en temps des problèmes de contrôle optimal. Un résultat de convergence est obtenu pour SITPOC ainsi que des interprétations matricielles des deux algorithmes. \textbf{2. Cinétique de la population de neutrons dans un réacteur nucléaire:}\\ Nous concevons un solveur parallélisé en temps regroupant toutes les variables issues de la modélisation neutronique d'un réacteur. Notre méthode est adaptée aux différents scénarios possibles réduisant la physique. Les résultats numériques sont comparables à ceux obtenus par le code MINOS du CEA. La parallélisation repose sur un schéma de type pararéel pour la résolution en temps. Nous considérons plusieurs modèles physiques de la cinétique des neutrons que nous traitons par notre algorithme dans lequel le solveur grossier utilisé correspond à une simulation par réduction du modèle physique. Cette réduction est bénéfique puisqu'elle permet une accélération importante du traitement en temps machine. \textbf{3. Contrôle par résonance magnétique nucléaire et information quantique:}\\ Ce chapitre présente un travail d'ouverture sur une méthode parallèle en temps pour la résolution d'un problème de contrôle optimal en résonance magnétique nucléaire. Notre méthode produit une accélération importante par rapport à l'algorithme de référence non parallèle. De plus, les champs de contrôle calculés par notre méthode sont lisses, ce qui permet une mise en œuvre expérimentale plus simple dans les instruments. Les tests numériques prouvent l'efficacité de notre approche. Sur des exemples académiques et sans faire usage de techniques de programmation avancées, nous obtenons des accélérations de résolution significatives.

Avec l'émergence de plates-formes distribuées très hétérogènes, dynamiques et à large échelle, la nécessité d'un moyen de les programmer efficacement et de les gérer est apparu. Le concept de l'informatique autonomique propose de créer des systèmes auto-gérés c'est-à-dire des systèmes qui sont conscients de leurs composants et de leur environnement, et peuvent se configurer, s'optimiser, se réparer et se protéger. Dans le cadre de la réalisation de tels systèmes, la programmation déclarative, dont l'objectif est de faciliter la tâche du programmeur en séparant le contrôle de la logique du calcul, a retrouvé beaucoup d'intérêt ces derniers temps. En particulier, la programmation à base de des règles est considérée comme un modèle prometteur dans cette quête d'abstractions de programmation adéquates pour ces plates-formes. Cependant, bien que ces modèles gagnent beaucoup d'attention, ils créent une demande pour des outils génériques capables de les exécuter à large échelle. Le modèle de programmation chimique, qui a été conçu suivant la métaphore chimique, est un modèle de programmation à bas de règles et d'ordre supérieur, avec une exécution non-déterministe, où les règles sont appliquées de façon concurrente sur un multi ensemble de données. Dans cette thèse, nous proposons la conception, le développement et l'expérimentation d'un intergiciel distribué pour l'exécution de programmes chimique sur des plates-formes à large échelle et génériques. L'architecture proposée combine une couche de communication pair-à-pair avec un protocole de capture atomique d'objets sur lesquels les règles doivent être appliquées, et un système efficace de détection de terminaison. Nous décrivons le prototype d'intergiciel mettant en oeuvre cette architecture. En s'appuyant sur son déploiement sur une plate-forme expérimentale à large échelle, nous présentons les résultats de performance, qui confirment les complexités analytiques obtenues et montrons expérimentalement la viabilité d'un tel modèle de programmation.

Parmi les différents paradigmes de programmation parallèle, le parallélisme de flux présente l'avantage de conserver la séquentialité des algorithmes et d'être ainsi applicable en présence de dépendances de données. De plus, l'extension de calcul par flux pour OpenMP proposée par Pop et Cohen permet de mettre en œuvre cette forme de parallélisme sans requérir de réécriture complète du code, en y ajoutant simplement des annotations. Cependant, en raison de l'importance de la communication nécessaire entre les cœurs de calcul, les performances obtenues en suivant ce paradigme sont très dépendantes de l'algorithme de communication utilisé. Or l'algorithme de communication utilisé dans cette extension repose sur des files gérant plusieurs producteurs et consommateurs alors que les applications mettant en œuvre le parallélisme de flux fonctionnent principalement avec des chaînes de communication linéaires. Afin d'améliorer les performances du parallélisme de flux mis en œuvre par l'extension de calcul par flux pour OpenMP, cette thèse propose d'utiliser, lorsque cela est possible, un algorithme de communication plus spécialisé nommé BatchQueue. En ne gérant que le cas particulier d'une communication avec un seul producteur et un seul consommateur, BatchQueue atteint des débits jusqu'à deux fois supérieurs à ceux des algorithmes existants. De plus, une fois intégré à l'extension de calcul par flux pour OpenMP, l'évaluation montre que BatchQueue permet d'améliorer l'accélération des applications jusqu'à un facteur 2 également. L'étude montre ainsi qu'utiliser des algorithmes de communication spécialisés plus efficaces peut avoir un impact significatif sur les performances générales des applications mettant en œuvre le parallélisme de flux.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal