Le développement d'applications avec une architecture Pair-à-Pair (P2P) est devenu de plus en plus important en ingénierie du logiciel. Aujourd'hui, un grand nombre d'organisations de tailles et secteurs différents compte d'une manière croissante sur la collaboration entre multiples acteurs (individus, groupes, communautés, etc.) pour accomplir des tâches essentielles. Ces applications P2P ont généralement un comportement récursif que plusieurs approches de modélisation ne peuvent pas décrire et analyser (ex. les approches basées sur les automates à états finis). Un autre challenge qui concerne le développement d'applications P2P est le couplage fort entre la spécification d'une part, et les technologies et protocoles sous-jacents d'autre part. Cela force les développeurs à faire des efforts considérables pour trouver puis comprendre des informations sur les détails de ces couches basses du P2P. De plus, ce couplage fort oblige les applications à s'exécuter dans des environnements figés. Par conséquent, choisir par exemple un autre protocole pour répondre à un nouveau besoin à l'exécution devient une tache très difficile. Outre ces points, les applications P2P sont souvent spécifiées avec une faible capacité à déléguer des traitements entre les pairs, et se focalisent surtout sur le partage et le stockage de données. Ainsi, elles ne profitent pas pleinement de la puissance de calcul et de traitement offerte par le réseau P2P sous-jacent. Dans cette thèse, nous présentons une approche qui combine les principes du développement orienté composants et services avec des techniques issues des Grammaires Attribuées et d'analyses de flot de données (techniques utilisées surtout dans la construction de compilateurs) afin de faciliter la spécification, l'analyse et le déploiement d'applications dans des architectures P2P. Cette approche incorpore: i) Un langage formel nommé DDF (de l'anglais Data-Dependency Formalism) pour spécifier les applications et construire leurs graphes de dépendances de données. Un graphe de dépendances de données est nommé DDG (de l'anglais Data-Dependency Graph) et est défini pour être une représentation abstraite de l'application spécifiée. ii) Une méthode d'analyse qui utilise le graphe de dépendances de données pour inférer et calculer diverses propriétés, y compris certaines propriétés que les model-checkers ne peuvent pas calculer si le système présente un comportement récursif. iii) Un intergiciel nommé SON (de l'anglais Shared data Overlay Network) afin de développer et d'exécuter des applications dans une architecture P2P sans faire face à la complexité des couches sous-jacentes. Cela grâce essentiellement au couplage faible (par une approche orientée services) et à la fonctionnalité de génération de code automatique.

Conséquence directe de la popularité croissante des services informatique en nuage, les centres de données se développent à une vitesse vertigineuse et doivent rapidement faire face à des problèmes de consommation d'énergie. Paradoxalement, l'informatique en nuage permet aux infrastructure et applications de s'ajuster dynamiquement afin de rendre l'infrastructure plus efficace en termes d'énergie et les applications plus conformes en termes de qualité de service (QdS). Toutefois, les décisions d'optimisation prises isolément à un certain niveau peuvent indirectement interférer avec (voire neutraliser) les décisions prises à un autre niveau, par exemple, une application demande plus de ressources pour garder sa QdS alors qu'une partie de l'infrastructure est en cours d'arrêt pour des raisons énergétiques. Par conséquent, il devient nécessaire non seulement d'établir une synergie entre les couches du nuage, mais aussi de rendre ces couches suffisamment souples et sensibles pour être en mesure de réagir aux changements d'exécution et ainsi profiter pleinement de cette synergie. Cette thèse propose une approche d'auto-adaptation qui prend en considération les composants applicatifs (élasticité architecturale) ainsi que d'infrastructure (élasticité des ressources) pour réduire l'empreinte énergétique. Chaque application et l'infrastructure sont équipées d'une boucle de contrôle autonome qui leur permet d'optimiser indépendamment leur fonctionnement. Afin de créer une synergie entre boucles de contrôle autour d'un objectif commun, nous proposons un modèle pour la coordination et la synchronisation de plusieurs boucles de contrôle. L'approche est validée expérimentalement à la fois qualitativement (amélioration de QdS et des gains d'énergie) et quantitativement (passage à l'échelle).

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques. Un grand nombre de ces protocoles requièrent en particulier des calculs dans des structures finies, rendant indispensable une arithmétique modulaire efficace. Ces opérations modulaires sont composées d'opérations multiprécision entre opérandes de tailles suffisamment grandes pour garantir le niveau de sécurité requis (de plusieurs centaines à plusieurs milliers de bits). Enfin, certains protocoles nécessitent des opérations arithmétiques dans le groupe des points d'une courbe elliptique, opérations elles-mêmes composées d'opérations dans le corps de définition de la courbe. Les tailles de clés utilisées par les protocoles rendent ainsi les opérations arithmétiques coûteuses en temps de calcul. Par ailleurs, les architectures grand public actuelles embarquent plusieurs unités de calcul, réparties sur les processeurs et éventuellement sur les cartes graphiques. Ces ressources sont aujourd'hui facilement exploitables grâce à des interfaces de programmation parallèle comme OpenMP ou CUDA. Cette thèse s'articule autour de la définition d'opérateurs arithmétiques parallèles permettant de tirer parti de l'ensemble des ressources de calcul, en particulier sur des architectures multicœur à mémoire partagée. La parallélisation au niveau arithmétique le plus bas permet des gains modérés en termes temps de calcul, car les tailles des opérandes ne sont pas suffisamment importantes pour que l'intensité arithmétique des calculs masque les latences dues au parallélisme. Nous proposons donc des algorithmes permettant une parallélisation aux niveaux arithmétiques supérieurs : algorithmes parallèles pour la multiplication modulaire et pour la multiplication scalaire sur les courbes elliptiques. Pour la multiplication modulaire, nous étudions en particulier plusieurs ordonnancements des calculs au niveau de l'arithmétique modulaire et proposons également une parallélisation à deux niveaux : modulaire et multiprécision. Ce parallélisme à plus gros grain permet en pratique des gains plus conséquents en temps de calcul. Nous proposons également une parallélisation sur processeur graphique d'opérations modulaires et d'opérations dans le groupe des points d'une courbe elliptique. Enfin, nous présentons une méthode pour optimiser la multiplication scalaire sur les courbes elliptiques pour de petits scalaires.

Dans cette Habilitation à Diriger des Recherches (HDR), nous présentons notre recherche effectuée au cours de ces dernières années dans le domaine du calcul haute-performance. Notre travail a porté essentiellement sur les algorithmes parallèles pour les solveurs d'algèbre linéaire numérique et leur implémentation parallèle dans les bibliothèques logicielles du domaine public. Nous illustrons dans ce manuscrit comment ces calculs peuvent être accélérées en utilisant des algorithmes innovants et être rendus fiables en utilisant des quantités spécifiques de l'analyse d'erreur. Nous expliquons tout d'abord comment les solveurs d'algèbre linéaire numérique peuvent être conçus de façon à exploiter les capacités des calculateurs hétérogènes actuels comprenant des processeurs multicœurs et des GPUs. Nous considérons des algorithmes de factorisation dense pour lesquels nous décrivons la répartition des tâches entre les différentes unités de calcul et son influence en terme de coût des communications. Ces cal- culs peuvent être également rendus plus performants grâce à des algorithmes en précision mixte qui utilisent une précision moindre pour les tâches les plus coûteuses tout en calculant la solution en précision supérieure. Puis nous décrivons notre travail de recherche dans le développement de solveurs d'algèbre linéaire rapides qui utilisent des algorithmes randomisés. La randomisation représente une approche innovante pour accélérer les calculs d'algèbre linéaire et la classe d'algorithmes que nous proposons a l'avantage de réduire la volume de communications dans les factorisations en supprimant complètement la phase de pivotage dans les systèmes linéaires. Les logiciels correspondants on été développés pour architectures multicœurs éventuellement accélérées par des GPUs. Enfin nous proposons des outils qui nous permettent de garantir la qualité de la solution calculée pour les problèmes de moindres carrés sur-déterminés, incluant les moindres carrés totaux. Notre méthode repose sur la dérivation de formules exactes ou d'estimateurs pour le conditionnement de ces problèmes. Nous décrivons les algorithmes et les logiciels qui permettent de calculer ces quantités avec les bibliothèques logicielles parallèles standards. Des pistes de recherche pour les années à venir sont données dans un chapître de conclusion.

La Tolérance aux pannes Byzantines (BFT) est de plus en plus cruciale avec l'évolution d'applications et en raison de la croissance de l'innovation technologique en informatique. Bien que des dizaines de protocoles BFT aient été introduites dans les années précédentes, leur mise en œuvre ne semble pas satisfaisant. Pour faire face à cette complexité, due à la dépendance d'un protocole d'une situation, nous tentons une approche qui permettra de sélectionner un protocole en fonction d'une situation. Ceci nous paraît, en s'inspirant de tout système d'encrage, comme une démarche nécessaire pour aborder la problématique de la BFT. Dans cette thèse, nous introduisons un modèle de sélection ainsi que l'algorithme qui permet de simplifier et d'automatiser le processus d'élection d'un protocole. Ce mécanisme est conçu pour fonctionner selon 3 modes : statique, dynamique et heuristique. Les deux derniers modes, nécessitent l'introduction d'un système réactif, nous ont conduits à présenter un nouveau modèle BFT: Adapt. Il réagit à tout changement et effectue, d'une manière adaptée, la commutation entre les protocoles d'une façon dynamique. Le mode statique permet aux utilisateurs de BFT de choisir un protocole BFT en une seule fois. Ceci est très utile dans les services Web et les " Clouds " où le BFT peut être fournit comme un service inclut dans le contrat (SLA). Ce mode est essentiellement conçu pour les systèmes qui n'ont pas trop d'états fluctuants. Pour ce faire, un processus d'évaluation est en charge de faire correspondre, à priori, les préférences de l'utilisateur aux profils du protocole BFT nommé, en fonction des critères de fiabilité et de performance. Le protocole choisi est celui qui réalise le meilleur score d'évaluation. Le mécanisme est bien automatisé à travers des matrices mathématiques, et produit des sélections qui sont raisonnables. D'autres systèmes peuvent cependant avoir des conditions flottantes, il s'agit de la variation des charges ou de la taille de message qui n'est pas fixe. Dans ce cas, le mode statique ne peut continuer à être efficace et risque de ne pas pouvoir s'adapter aux nouvelles conditions. D'où la nécessité de trouver un moyen permettant de répondre aux nouvelles exigences d'une façon dynamique. Adapt combine un ensemble de protocoles BFT ainsi que leurs mécanismes de commutation pour assurer l'adaptation à l'évolution de l'état du système. Par conséquent, le "Meilleur" protocole est toujours sélectionné selon l'état du système. On obtient ainsi une qualité optimisée de service, i.e., la fiabilité et la performance. Adapt contrôle l'état du système grâce à ses mécanismes d'événements, et utilise une méthode de "Support Vector Regrssion" pour conduire aux prédictions en temps réel pour l'exécution des protocoles (par exemple, débit, latence, etc.). Ceci nous conduit aussi à un mode heuristique. En utilisant des heuristiques prédéfinies, on optimise les préférences de l'utilisateur afin d'améliorer le processus de sélection. L'évaluation de notre approche montre que le choix du "meilleur" protocole est automatisé et proche de la réalité de la même façon que dans le mode statique. En mode dynamique, Adapt permet toujours d'obtenir la performance optimale des protocoles disponibles. L'évaluation démontre, en plus, que la performance globale du système peut être améliorée de manière significative. Explorer d'autres cas qui ne conduisent pas de basculer entre les protocoles. Ceci est rendu possible grâce à la réalisation des prévisions d'une grande précision qui peuvent atteindre plus de 98%dans de nombreux cas. La thèse montre que cette adaptabilité est rendue possible grâce à l'utilisation des heuristiques dans un mode dynamique.

Computing with mobile agents is rapidly becoming a topic of mainstream research in the theory of distributed computing. The main research questions undertaken in this study concern the feasibility of solving fundamental tasks in an anonymous network, subject to limitations on the resources available to the agent. The considered challenges include: exploring a graph by means of an agent with limited memory, discovery of the network topology, and attempting to meet with another agent in another network (rendezvous). The constraints imposed on the agent include the number of moves which the agent is allowed to perform in the network, the amount of state memory available to the agent, the ability of the agent to communicate with other agents, as well as its a priori knowledge of the network topology or of global parameters.

Les phénomènes physiques complexes peuvent être simulés numériquement par des techniques mathématiques basées souvent sur la discrétisation des équations aux dérivées partielles régissant ces phénomènes. Ces simulations peuvent mener ainsi à la résolution de très grands systèmes. La parallélisation des codes de simulation numérique, c'est-à-dire leur adaptation aux architectures des calculateurs parallèles, est alors une nécessité pour parvenir à faire ces simulations en des temps non-exorbitants. Le parallélisme s'est imposé au niveau des architectures de processeurs et les cartes graphiques sont maintenant utilisées pour des fins de calcul généraliste, aussi appelé "General-Purpose computation on Graphics Processing Unit (GPGPU)", avec comme avantage évident l'excellent rapport performance/prix. Cette thèse se place dans le domaine de la conception de ces applications hautes-performances pour la simulation des machines électriques. Nous fournissons une méthodologie basée sur l'Ingénierie Dirigées par les Modèles (IDM) qui permet de modéliser une application et l'architecture sur laquelle l'exécuter afin de générer un code OpenCL. Notre objectif est d'aider les spécialistes en algorithmes de simulations numériques à créer un code efficace qui tourne sur les architectures GPGPU. Pour cela, une chaine de compilation de modèles qui prend en compte les plusieurs aspects du modèle de programmation OpenCL est fournie. De plus, pour rendre le code raisonnablement efficace par rapport à un code développé à la main, nous fournissons des transformations de modèles qui regardent des niveaux d'optimisations basées sur les caractéristiques de l'architecture (niveau de mémoire par exemple). Comme validation expérimentale, la méthodologie est appliquée à la création d'une application qui résout un système linéaire issu de la Méthode des Éléments Finis pour la simulation de machines électriques. Dans ce cas nous montrons, entre autres, la capacité de la méthodologie de passer à l'échelle par une simple modification de la multiplicité des unités GPU disponibles.

L'objectif de cette thèse est l'accélération des solveurs utilisés pour la résolution de l'équation de Poisson pour la pression, dans le cas de la simulation d'écoulements à faible nombre de Mach sur des maillages non structurés. Cet objectif est complété par un besoin de stabilité, en particulier sur des géométries complexes. Plusieurs modifications de la méthode des Gradients Conjugués avec déflation ont été considérées à cet effet. Une méthode de redémarrage basée sur une estimation de l'effet des erreurs numériques a été mise en oeuvre et validée. Par la suite, une méthode consistant à calculer des solutions linéaires ou quadratiques par morceaux sur le maillage grossier s'est avérée instable dans le solveur non structuré YALES2. La nouvelle méthode alors développée consiste à transformer la méthode standard de déflation à deux niveaux de maillage en une méthode à trois niveaux. Cependant, le nombre élevé d'itérations sur le troisième niveau de maillage nouvellement créé ralentit le solveur, ce que nous avons rectifié grâce à deux méthodes développées particulièrement pour réduire le nombre d'itérations sur les niveaux grossiers. La première méthode est la création de solutions initiales grâce à une méthode de projection adaptée. La seconde consiste en une adaptation du critère de convergence sur les niveaux grossiers. Les résultats numériques sur des simulations massivement parallèles, avec le solveur à deux niveaux classique, montrent une réduction considérable du temps de calcul du solveur et une amélioration importante de sa scalabilité faible. L'application de ces techniques à la déflation à trois niveaux induit des gains supplémentaires en termes de temps de calcul. Outre le perfectionnement de ce solveur, des recherches supplémentaires doivent être conduites sur l'équilibrage dynamique de charges de calcul, qui pourrait devenir un développement-clé du solveur.

Concevoir et implanter des programmes parallèles est une tâche complexe, sujette aux erreurs. La vérification des programmes parallèles est également plus difficile que celle des programmes séquentiels. Pour permettre le développement et la preuve de correction de programmes parallèles, nous proposons de combiner le langage parallèle fonctionnel quasi-synchrone BSML, les squelettes algorithmiques - qui sont des fonctions d'ordre supérieur sur des structures de données réparties offrant une abstraction du parallélisme - et l'assistant de preuve Coq, dont le langage de spécification est suffisamment riche pour écrire des programmes fonctionnels purs et leurs propriétés. Nous proposons un plongement des primitives BSML dans la logique de Coq sous une forme modulaire adaptée à l'extraction de programmes. Ainsi, nous pouvons écrire dans Coq des programmes BSML, raisonner dessus, puis les extraire et les exécuter en parallèle. Pour faciliter le raisonnement sur ceux-ci, nous formalisons le lien entre programmes parallèles, manipulant des structures de données distribuées, et les spécifications, manipulant des structures séquentielles. Nous prouvons ainsi la correction d'une implantation du squelette algorithmique BH, un squelette adapté au traitement de listes réparties dans le modèle de parallélisme quasi synchrone. Pour un ensemble d'applications partant d'une spécification d'un problème sous forme d'un programme séquentiel simple, nous dérivons une instance de nos squelettes, puis nous extrayons un programme BSML avant de l'exécuter sur des machines parallèles.

Avec l'utilisation de plus en plus répandue de la simulation numérique dans de nombreuses branches de l'industrie, le calcul haute performance devient essentiel à la société. Si les plates-formes de calcul parallèle de plus en plus puissantes continuent à être construites, leur utilisation devient cependant de plus en plus un casse-tête. En effet, leur complexité croît avec la multiplication des ressources de calcul et de stockage impliquées, leurs fonctionnalités hétérogènes, et leur répartition non-uniforme. De nouveaux outils logiciels sont nécessaires pour faciliter l'exploitation de ces plates-formes. Je présente tout d'abord mes travaux visant à rendre plus accessibles et portables les mécanismes de communication développés par les constructeurs de réseaux haute performance pour le calcul. J'ai appliqué ce principe d'une part aux réseaux traditionnels de type Ethernet, et d'autre part aux communications entre processus locaux, afin d'améliorer les performances du passage de messages (MPI) sans dépendre de technologies matérielles spécialisées. J'explique ensuite comment faciliter la gestion des calculateurs hiérarchiques modernes. Il s'agit, d'une part, de modéliser ces plates-formes en représentant l'organisation des ressources de manière suffisamment simple pour masquer les détails techniques du matériel, et suffisamment précise pour permettre aux algorithmes de prendre des décisions de placement ou d'ordonnancement ; d'autre part, je propose des outils améliorant la gestion des architectures modernes où l'accès à la mémoire et aux périphériques n'est plus uniforme. Cela permet d'améliorer les performances de bibliothèques de calcul parallèle en tenant compte de la localité.