L'objectif de cette thèse est de faciliter la conception et le déploiement d'applications distribuées sur la Grille, en utilisant une approche orientée composants. Les problématiques du calcul sur grilles abordées dans notre proposition sont : la complexité de conception, le déploiement, la flexibilité et la performance. Nous proposons et justifions un modèle de composants et son implantation. Le modèle proposé repose sur le modèle de composants Fractal et sur le modèle des objets actifs. Il bénéficie d'une part, de la structure hiérarchique et de la définition précise du modèle Fractal, et d'autre part, de l'identification des composants comme activités configurables. Nous proposons un modèle de déploiement et nous spécifions un ensemble de primitives pour les communications collectives, grâce à la définition d'interfaces collectives. Les interfaces collectives permettent de gérer la distribution des données, le parallélisme et la synchronisation des invocations.<br />Nous avons développé une implantation du modèle proposé avec l'intergiciel de grille ProActive. Le framework de composants bénéficie ainsi des fonctionnalités sous-jacentes offertes par l'intergiciel ProActive. Nous démontrons la capacité de passage à l'échelle et l'efficacité de notre framework en déployant sur plusieurs centaines de machines des applications intensives en termes de calcul et de communications. Nous mettons à profit les interfaces collectives pour développer une application SPMD à base de composants, dont nous évaluons les performances.

Le document présente une synthèse de travaux sur le déploiement, l'utilisation et les techniques de mise en oeuvre d'applications développées selon un modèle de programmation à passage de messages sur des grilles de calcul. La première partie décrit les performances observées sur la période 2002-2006 sur une plateforme à l'échelle de la France, ainsi que les gains obtenus par équilibrage de charge. La deuxième partie décrit un intergiciel nouveau baptisé P2P-MPI qui synthétise un ensemble de propositions pour améliorer la prise en charge de tels programmes à passage de messages.

Dans la dernière décennie, les grilles de calcul ont permis de réunir des ressources de stockage et de calcul de multiples institutions pour pourvoir à des applications scientifiques de grande ampleur. Par analogie aux grilles électriques, l'idée d'origine est de fournir de manière transparente de la capacité de calcul selon les besoins. Cependant, alors que les applications se multiplient, l'efficacité des mécanismes sous-jacents d'allocation de ressources mérite l'attention. Cette thèse présente les contributions suivantes. - Identification des patterns d'allocation de ressource, et comment ils ont évolué depuis les clusters isolés jusqu'aux grilles qui s'étendent sur plusieurs institutions autonomes. - Identification d'un pattern commun (Late Binding) dans la façon dont plusieurs applications contournent depuis peu le méccanisme habituel (Meta-scheduling) dans le but d'obtenir une mainmise accrue sur l'allocation de ressources et de palier à certains manques d'efficacité. - Proposition d'un nouveau pattern (Symmetric Mapping) qui permet d'obtenir la séparation du contrôle entre les fournisseurs et utilisateurs de ressources. - Proposition d'un nouveau modèle pour spécifier des stratégies d'allocation de ressource. Ce modèle permet de représenter l'allocation dynamique, ainsi que de multiples contraintes et objectifs. - Transposition du problème des Domaines Administratifs Multiples (MADs) du domaine de la tolérance aux fautes à celui du calcul distribué. Identification du problème MAD comme problème distinctif des grilles parmi les systèmes de calcul distribué. Identification de Symmetric Mapping comme une solution. - Proposition d'une implémentation de Symmetric Mapping basée sur les machines virtuelles, et dont l'un des éléments déploie et contrôle des multiples machines virtuelles à partir de descriptions déclaratives. - Proposition d'un système qui détecte la terminaison d'un service et relance tout service interrompu sur un serveur nouvellement sélectionné, afin de maintenir une implémentation de Symmetric Mapping, ou tout système qui nécessite des services permanents sur des serveurs transitoires. - Proposition d'une nouvelle méthode pour l'analyse des tâches et la prédiction de performance afin d'associer de manière dynamique des tâches aux serveurs adéquats. La méthode s'appuie sur l'estimation de patterns d'accès mémoire par des distributions de probabilité connues. La signature des tâches est réduite à une taille constante et la prédiction est effectuée en temps constant. - Proposition de la première évaluation du cache thrashing, afin de permettre des prédictions de performance réalistes pour les CPUs partagés par plusieurs processus. L'analyse est basée sur un nouveau modèle de Markov des caches LRU. Elle donne une borne supérieure et une borne inférieure de la proportion de fautes de caches en présence de processus concurrents.

Esta tesis apunta a entregar las bases para el desarrollo de los algoritmos de balance de carga para el modelo de objetos activos definido por ProActive en el contexto de las redes a gran escala (grillas).<br />ProActive es un middleware implementado en lenguaje Java, de código abierto, para la programacióon concurrente, paralela, distribuida, y móvil; basado en el modelo de objeto-activo. En<br />ProActive, cada objeto activo tiene su propio hilo de control y puede decidir independientemente<br />en qué orden servir los métodos invocados, las cuales se almacenan automáticamente en una cola<br />de peticiones pendientes. Para agregar eficacia al paradigma de objetos activos, ProActive proporciona<br />un mecanismo del migración, obteniendo localización automática y transparencia mediante<br />el uso de forwarders. La migración viene con un costo de comunicación: un objeto activo debe<br />emigrar con su estado completo, que consiste en sus peticiones pendientes (llamadas de método),<br />objetos futuros, y sus objetos pasivos. Por lo tanto, las aplicaciones implementadas con ProActive<br />son sensibles a la latencia.<br />Cuando varios objetos activos con funcionalidad idéntica se despliegan, un algoritmo de balance<br />de carga se utiliza para mejorar el funcionamiento de la aplicación utilizando esa funcionalidad.<br />La carga de trabajo puede ser equilibrada, ya sea enviando objetos activos de un procesador<br />altamente cargado a uno menos cargado, o bien robando objetos activos a un procesador altamente<br />cargado. El ambiente donde normalmente se ejecutan las aplicaciones implementadas usando el<br />modelo de objetos activos se compone generalmente de grupos múltiples de recursos, por ejemplo,<br />un sistema de máquinas interconectadas por una red local de alta velocidad.<br />Dado lo anterior, se ha estudiado y desarrollado un algoritmo de balance de carga para objetos<br />activos que pertenecen a una aplicación paralela, fijando las bases para el desarrollo de los<br />algoritmos de balance de carga para el middleware ProActive. Este primer acercamiento se llama<br />algoritmo Robin-Hood + Nottingham Sheriff. Este algoritmo fue validado en el contexto de redes<br />de alta escala (sobre 1.000 nodos) mediante simulaciones, utilizando nuestros modelo de grillas de<br />computadores, los cuales están basados en la observación y la medición de lo que consideramos<br />las características dominantes para el balance de objetos activos: capacidad de procesamiento y<br />latencia entre recursos.<br />Finalmente, presentamos los contratos de acoplamiento para el despliegue de aplicaciones paralelas, así como su forma de utilización en el contexto de balance de carga. A modo de ejemplo,<br />mostramos su uso en la elección del balanceador a utilizar (cluster local v/s nuestro algoritmo).

Depuis le début des années 80, les bases de données biologiques n'ont cessé de gagner en volume. Une recherche sur ces bases qui ne prenait que quelques minutes peut désormais nécessiter plusieurs jours. En parallèle, la communauté de recherche en bioinformatique s'est développée et des laboratoires spécialisés sont nés partout dans le monde. La collaboration et l'échange de données entre équipes de recherche parfois géographiquement très éloignées a conduit à considérer la grille comme un moyen adapté à la fois aux nouveaux besoins en terme de puissance de calcul mais aussi comme outil de partage et de distribution des données biologiques entre chercheurs. L'utilisation de la grille pour la recherche en biologie et bioinformatique est un atout considérable, cependant de nouvelles problématiques apparaissent quant `a la gestion des données ainsi que dans l'ordonnancement des tâches qui doit prendre en compte la taille et la disponibilité des données. Cette thèse aborde ces problématiques nouvelles en prenant en compte les spécificités des bases de données biologiques pour une utilisation efficace de la grille. Nous montrons l'intérêt des approches semi-statiques joignant réplications de données et ordonnancement des tâches. Pour cela, nous avons procédé en trois étapes : une analyse théorique, une première validation par simulation et enfin une implantation sur plateforme réelle. La mise en place de la plateforme a mené à la conception d'un nouveau gestionnaire de données pour l'intergiciel DIET : DAGDA. Au-delà des applications de bioinformatique, ce gestionnaire de données peut répondre aux besoins de nombreuses applications portées sur les grilles de calcul

Cette thèse a pour objectif de faciliter le déploiement d'applications distribuées sur des grilles de calcul à grande échelle, en utilisant une infrastructure pair-à-pair (P2P) pour les grilles. De plus, cette thèse propose aussi une bibliothèque basée sur la technique << Elagage et Branchement >> (de l'anglais, Branch-and-Bound -- B&B) pour résoudre les problèmes d'optimisation combinatoire.<br /><br />Les modèles et infrastructures pour le P2P existant sont plutôt décevants : seulement des tâches indépendantes généralement sans communication entre les tâches, et des API de bas niveau. Cette thèse propose une infrastructure P2P qui partage des noeuds de calcul, afin de fournir des grilles à grande échelle. L'infrastructure est un réseau P2P non-structuré, auto-organisé, configurable et qui permet le déploiement d'applications communicantes.<br /><br />Les environnements P2P semblent être bien adaptés aux applications avec un faible ratio communication/computation, comme les algorithmes de recherche parallèle et plus particulièrement les algorithmes de B&B. En plus d'une infrastructure P2P, cette thèse propose une bibliothèque de B&B parallèle pour la grille. Cette bibliothèque aide les utilisateurs, en masquant toutes les difficultés liées à la distribution, à paralléliser leurs problèmes sur des grilles. La bibliothèque repose sur un modèle maître-travailleur hiérarchique et offre un système transparent de communication afin d'améliorer la vitesse de résolution.<br /><br />Nous avons tout d'abord implémenté notre infrastructure P2P au-dessus de l'intergicielle Java pour la grille, ProActive. Cette infrastructure P2P a été déployée comme grille de bureau de manière permanente, avec laquelle nous avons pu réaliser un record mondial de calcul en résolvant le problème des n-reines avec 25 reines. Ensuite, nous avons aussi implémenté avec ProActive notre bibliothèque pour le B&B. Nous montrons le passage à l'échelle et l'efficacité de la bibliothèque en déployant sur une grille de taille nationale (Grid'5000) une application qui résout le problème du << flow-shop >>. Pour finir, nous avons mixé Grid'5000 et notre grille de bureau pour expérimenter le déploiement à grande échelle des n-reines et du flow-shop.

Nous étudions des stratégies d'ordonnancement et d'équilibrage de charge pour des plates-formes hétérogènes distribuées. Notre problème est d'ordonnancer un ensemble de tâches indépendantes afin d'en réduire le temps total d'exécution. Ces tâches utilisent des données d'entrée qui peuvent être partagées : chaque tâche peut utiliser plusieurs données, et chaque donnée peut être utilisée par plusieurs tâches. Les tâches ont des durées d'exécution différentes, et les données ont des tailles différentes. Toute la difficulté est de réussir à placer sur un même processeur des tâches partageant des données, tout en conservant un bon équilibrage de la charge des différents processeurs. Notre étude comporte trois parties généralisant progressivement le problème. Nous nous limitons dans un premier temps au cas simple où il n'y a pas de partage de données, où les tailles des tâches et des données sont homogènes, et où la plate-forme est de type maître-esclave. Le partage des données est introduit dans la deuxième partie, ainsi que l'hétérogénéité pour les tailles des tâches et des données. Dans la dernière partie nous généralisons le modèle de plate-forme à un ensemble décentralisé de serveurs reliés entre eux par un réseau d'interconnexion quelconque. La complexité théorique du problème est étudiée. Pour les cas simples, des algorithmes calculant une solution optimale sont proposés, puis validés par des résultats expérimentaux avec une application scientifique réelle. Pour les cas plus complexes, nous proposons de nouvelles heuristiques pour résoudre le problème d'ordonnancement. Ces nouvelles heuristiques, ainsi que des heuristiques classiques comme min-min et sufferage, sont comparées entre elles à l'aide de nombreuses simulations. Nous montrons ainsi que nos nouvelles heuristiques réussissent à obtenir des performances aussi bonnes que les heuristiques classiques, tout en ayant une complexité algorithmique d'un ordre de grandeur plus faible.

Avec la démocratisation des environnements du type grappe et grille de calcul, la performance des opérations de communication collective devient un aspect critique dans le coût total des applications parallèles. Fortement influencées par l'hétérogénéité des ressources, ces opérations dépendent à la fois des paramètres de communication des réseaux et des stratégies de communication employées. Cette thèse a pour objet d'étude l'optimisation des communications collectives selon l'approche préconisée par Karonis, où les différentes grappes de calcul sont organisées en plusieurs couches de communication de manière à minimiser le temps total de communication. Pour cela, nous proposons des modèles de communications qui permettent l'optimisation des communications collectives à travers l'ordonnancement hiérarchique des communications et la prédiction des performances. Dans un premier temps, nous démontrons que l'utilisation du modèle de coût pLogP permet la modélisation des performances de communications collectives dans des environnements homogènes. Ces modèles de performance ont été validés expérimentalement sur différentes plates-formes réseaux (Fast Ethernet, Giga Ethernet et Myrinet). Parallèlement, nous étudions la découverte automatique de la topologie du réseau. En effet, la décomposition de l'environnement de grille en îlots d'homogénéité permettrait la réduction de la complexité des optimisations, notamment dans ce qui concerne la modélisation des performances et l'obtention des caractéristiques du réseau. Notre principale contribution a été de proposer certaines heuristiques d'ordonnancement des communications qui tiennent compte de l'organisation hiérarchique de la grille. Ces heuristiques, adaptées aux différents patrons de communication collective, utilisent les techniques étudiées précédemment (dont la découverte des îlots d'homogénéité et la modélisation des performances) afin de réduire la complexité de l'optimisation des communications et de minimiser le temps total de communication.

Cette thèse étudie la découverte de services (composants logiciels, exécutables, librairies scientifiques) sur des plates-formes distribuées à grande échelle. Les approches traditionnelles, proposées pour des environnements stables et relativement petits, s'appuient sur des techniques centralisées impropres au passage à l'échelle dans des environnements géographiquement distribués et instables. Notre contribution s'articule autour de trois axes. 1) Nous proposons une nouvelle approche appelée DLPT (Distributed Lexicographic Placement Table), qui s'inspire des systèmes pair-à-pair et s'appuie sur un réseau de recouvrement structuré en arbre de préfixes. Cette structure permet des recherches multi-attributs sur des plages de valeurs. 2) Nous étudions la distribution des noeuds de l'arbre sur les processeurs de la plate-forme sous-jacente, distribuée, dynamique et hétérogène. Nous proposons et adaptons des heuristiques de répartition de la charge pour ce type d'architectures. 3) Notre plate-forme cible, par nature instable, nécessite des mécanismes robustes pour la tolérance aux pannes. La réplication traditionnellement utilisée s'y avère coûteuse et incapable de gérer des fautes transitoires. Nous proposons des techniques de tolérance aux pannes best-effort fondées sur la théorie de l'auto-stabilisation pour la construction d'arbres de préfixes dans des environnements pair-à-pair. Nous présentons deux approches. La première, écrite dans un modèle théorique à gros grain, permet de maintenir des arbres de préfixes instantanément stabilisants, c'est-à-dire reconstruits en un temps optimal après un nombre arbitraire de fautes. La deuxième, écrite dans le modèle à passage de messages, permet l'implantation d'une telle architecture dans des réseaux très dynamiques. Enfin, nous présentons un prototype logiciel mettant en oeuvre cette architecture et présentons ses premières expérimentations sur la plate-forme Grid'5000.

Le développement des nouveaux paradigmes et technologies comme le Web sémantique, le calcul sur grille et les services Web ouvrent de nouvelles perspectives et défis pour la conception d'une nouvelle génération d'applications. Cette nouvelle génération peut être conçue comme des systèmes multi-agents opérant sur les grilles de calcul tout en s'appuyant sur les services offerts par les services Web sémantiques. D'une part, les avancées dans la standardisation des langages et technologies des services Web ont permis un déploiement rapide d'applications fondées sur l'invocation dynamique de services découverts à la volée. Ainsi, grâce aux services Web, les applications peuvent être vues comme un ensemble de services logiciels, explicitement décrits, découverts et invoqués à l'aide des standards internationaux définis par le W3C (World Wide Web Consortium). D'autre part, le Web sémantique vise à rendre le contenu des ressources du Web accessible et utilisable par les agents logiciels, grâce à un système de métadonnées. Ces métadonnées sont notamment exprimées à l'aide d'ontologies définies en OWL – Web Ontology Language, un langage standardisé par le W3C. L'extension du Web sémantique aux services Web donne ainsi lieu à des services Web sémantiques. Le Web sémantique est également à la base des grilles sémantiques fournissant une infrastructure virtuelle constituée d'un ensemble de ressources potentiellement partagées, distribuées, hétérogènes, délocalisées et autonomes. Ces ressources sont abstraites en tant que services grille. La conjonction des services Web et des systèmes multi-agents déployés sur les grilles sémantiques donne naissance aux grilles sémantiques autonomes. Dans cette vision, des agents logiciels exploitent les services des grilles de calcul mais également utilisent des services Web au-delà de la grille, permettant un usage à très large échelle. Ces systèmes multi-agents sont construits en se reposant souvent sur les standards IEEE de la FIPA (Foundation of Intelligent Physical Agents). Néanmoins, un problème se pose : celui de l'interopérabilité des agents logiciels, de nature sémantique, avec les services Web sémantiques, tout en respectant les standards définis par la FIPA et le W3C. Cette thèse s'attaque à cette problématique. L'approche développée dans la thèse est fondée sur la conception d'un intergiciel permettant l'interopérabilité entre agents logiciels et services Web de manière transparente tout en s'appuyant sur les standards actuels promus par la FIPA pour les systèmes multi-agents et pour le W3C pour les services Web sémantiques. Elle définit l'architecture logicielle et implémente en intergiciel pour la médiation entre agents logiciels et services Web sémantiques, en prenant en compte la dimension ontologique. La solution proposée est validée par des études de cas et utilise π-ADL, un langage formel basé sur le π-calcul, pour spécifier l'application des mécanismes développés.