Les Architectures Orientées Services (SOA) sont adoptées aujourd'hui par de nombreuses entreprises car elles représentent une solution flexible pour la construction d'applications distribuées. Une Application Basée sur des Services (SBA) peut se définir comme un workflow qui coordonne de manière dynamique l'exécution distribuée d'un ensemble de services. Les services peuvent être sélectionnés et intégrés en temps réel en fonction de leur Qualité de Service (QoS), et la composition de services peut être dynamiquement modifiée pour réagir à des défaillances imprévues pendant l'exécution. Les besoins des architectures orientées services présentent des similarités avec la nature: dynamicité, évolutivité, auto-adaptabilité, etc. Ainsi, il n'est pas surprenant que les métaphores inspirées par la nature soient considérées comme des approches appropriées pour la modélisation de tels systèmes. Nous allons plus loin en utilisant le paradigme de programmation chimique comme base de construction d'un middleware. Dans cette thèse, nous présentons un middleware "chimique'' pour l'exécution dynamique et adaptative de SBA. La sélection, l'intégration, la coordination et l'adaptation de services sont modélisées comme une série de réactions chimiques. Tout d'abord, l'instantiation de workflow est exprimée par une série de réactions qui peuvent être effectuées de manière parallèle, distribuée et autonome. Ensuite, nous avons mis en oeuvre trois modèles de coordination pour exécuter une composition de service. Nous montrons que les trois modèles peuvent réagir aux défaillances de type panne franche. Enfin, nous avons évalué et comparé ces modèles au niveau d'efficacité et complexité sur deux workflows. Nous montrons ainsi dans cette thèse que le paradigme chimique possède les qualités nécessaires à l'introduction de la dynamicité et de l'adaptabilité dans la programmation basée sur les services.

Le thème global de la thèse est le comportement transitoire de certains systèmes répartis. Les résultats peuvent être divisés en trois groupes : transients de matrices et systèmes max-plus, convergence de systèmes de consensus asymptotique et la modélisation de "glitches" dans des circuits numériques. Pour l'algèbre max-plus, les résultats sont des bornes supérieures sur les transients de matrices et système linéaires max-plus. Elles améliorent strictement les bornes publiées. La thèse inclut une discussion de l'impact des bornes dans des applications. Les preuves utilisent notamment des réductions de chemins. La thèse contient aussi des bornes plus précises pour les transients des indices critiques. Ces bornes sont, en fait, indépendantes des poids spécifiques et ne dépendent que de la structure du graphe de la matrice et son graphe critique. De plus, elles sont des généralisations strictes des bornes booléennes pour des graphes non pondérées; par exemple les bornes de Wielandt ou de Dulmage et Mendelsohn. Quant au consensus asymptotique, la thèse améliore des bornes supérieures sur le taux de convergence et établit de nouveaux résultats sur la convergence dans le cas où les agents n'ont pas nécessairement de confiance en soi, c'est-à-dire qu'ils peuvent ignorer leurs propres valeurs. Ces résultats sont notamment pour des réseaux complètement dynamiques. Elle contient aussi un exemple d'un réseau complètement statique dont le taux de convergence est dans le même ordre que celui d'une grande classe de réseaux dynamiques. La dernière partie de la thèse est sur la propagation de "glitches" (signaux transitoires très courts) dans des circuits numériques. Plus spécifiquement, elle traite des modèles à valeur discrète et temps continu pour des circuits numériques. Ces modèles sont utilisés dans des outils pour la conception de circuits car ils sont beaucoup plus vites que la résolution des équations différentielles. Cependant, comme c'est prouvé dans la thèse, les modèles existants ne prédisent pas correctement l'occurrence de glitches dans le signal sortant d'un circuit. De plus, la thèse contient une proposition d'un nouveau modèle qui ne partage pas les caractéristiques avec les modèles existants qui leur interdisent de prédire correctement l'occurrence de glitches.

La course à l'augmentation de la puissance de calcul qui se déroule depuis de nombreuses années entre les différents producteurs de matériel a depuis quelques années changé de visage: nous assistons en effet désormais à une véritable démocratisation des machines parallèles avec une complexification sans cesse croissante de la structure des processeurs. À terme, il est tout à fait envisageable de voir apparaître pour le grand public des architecture pleinement hétérogènes composées d'un ensemble de cœurs reliés par un réseau sur puce. La parallélisation et l'exécution parallèle d'applications sur les machines à venir soulèvent ainsi de nombreux problèmes. Parmi ceux-ci, nous nous intéressons ici au problème de l'ordonnancement d'un ensemble de tâches sur un ensemble de cœurs, c'est à dire le choix de l'affectation du travail à réaliser sur les ressources disponibles. Parmi les méthodes existantes, on distingue deux types d'algorithmes: en-ligne et hors-ligne. Les algorithmes en-ligne comme le vol de travail présentent l'avantage de fonctionner en l'absence d'informations sur le matériel ou la durée des tâches mais ne permettent généralement pas une gestion efficace des communications. Dans cette thèse, nous nous intéressons à l'ordonnancement de tâches en-ligne sur des plates-formes complexes pour lesquelles le réseau peut, par des problèmes de congestion, limiter les performances. Plus précisément, nous proposons de nouveaux algorithmes d'ordonnancement en-ligne, basés sur le vol de travail, ciblant deux configurations différentes. D'une part, nous considérons des applications pour lesquelles le graphe de dépendance est connu à priori. L'utilisation de cette information nous permet ainsi de limiter les quantités de données transférées et d'obtenir des performances supérieures aux meilleurs algorithmes hors-ligne connus. D'autre part, nous étudions les optimisations possibles lorsque l'algorithme d'ordonnancement connaît la topologie de la plate-forme. Encore une fois, nous montrons qu'il est possible de tirer parti de cette information pour réaliser un gain non-négligeable en performance. Nos travaux permettent ainsi d'étendre le champ d'application des algorithmes d'ordonnancement vers des architectures plus complexes et permettront peut-être une meilleure utilisation des machines de demain.

Les organisations qui possèdent des infrastructures de calcul à haute performance (HPC) font souvent face à certaines difficultés dans la gestion de leurs ressources. En particulier, ces difficultés peuvent provenir du fait que des applications de différents types doivent pouvoir accéder concurremment aux ressources tandis que les utilisateurs peuvent avoir des objectifs de performance (SLOs) variés. Pour atteindre ces difficultés, cette thèse propose un cadre générique et extensible pour la gestion autonome des applications et l'allocation dynamique des ressources. L'allocation des ressources et l'exécution des applications est régie par une économie de marché observant au mieux des objectifs de niveau de service (SLO) tout en tirant avantage de la flexibilité d'une nuage informatique et en maximisant l'utilisation de des ressources. Le marché fixe dynamiquement un prix aux ressources, ce qui, combiné avec une politique de distribution de monnaie entre les utilisateurs, en garantit une utilisation équitable. Simultanément, des contrôleurs autonomes mettent en oeuvre des politiques d'adaptation pour faire évoluer la demande en ressource de leur application en accord avec la SLO requise par l'utilisateur. Les politiques d'adaptation peuvent : (i) adapter dynamiquement leur demande en terme de CPU et de mémoire demandés en période de contention de ressource aux machines virtuelles (ii) et changer dynamiquement le nombre de machines virtuelle. Nous avons évalué cette plateforme au moyen de la simulation et sur l'infrastructure Grid'5000. Nos résultats ont montré que cette solution: (i) offre un support plus flexible aux applications de type différent demandant divers niveaux de service; (ii) conduit à une bonne satisfaction des utilisateurs moyennant une dégradation acceptable des performances comparées aux solutions centralisées existantes.

Les processeurs graphiques (GPU), originellement dédiés à l'accélération de traitements graphiques, ont une structure hautement parallèle. Les innovations matérielles et de langage de programmation ont permis d'ouvrir le domaine du GPGPU, où les cartes graphiques sont utilisées comme des accélérateurs de calcul pour des applications HPC généralistes. L'objectif de nos travaux est de faciliter l'utilisation de ces nouvelles architectures pour les besoins du calcul haute performance ; ils suivent deux objectifs complémentaires. Le premier axe de nos recherches concerne la transformation automatique de code, permettant de partir d'un code de haut niveau pour le transformer en un code de bas niveau, équivalent, pouvant être exécuté sur des accélérateurs. Dans ce but nous avons implémenté un transformateur de code capable de prendre en charge les boucles " pour " parallèles d'un code OpenMP (simples ou imbriquées) et de le transformer en un code CUDA équivalent, qui soit suffisamment lisible pour permettre de le retravailler par des optimisations ultérieures. Par ailleurs, le futur des architectures HPC réside dans les architectures distribuées basées sur des noeuds dotés d'accélérateurs. Pour permettre aux utilisateurs d'exploiter les noeuds multiGPU, il est nécessaire de mettre en place des schémas d'exécution appropriés. Nous avons mené une étude comparative et mis en évidence que les threads OpenMP permettent de gérer de manière efficace plusieurs cartes graphiques et les communications au sein d'un noeud de calcul multiGPU.

Cette thèse présente nos travaux de recherche qui ont comme principal objectif d'assurer la portabilité des performances et le passage à l'échelle des applications scientifiques complexes exécutées sur des plates-formes multi-coeurs parallèles et hiérarchiques. La portabilité des performances est obtenue lorsque l'ordonnancement des tâches d'une application permet de réduire les périodes d'inactivité des coeurs de la plate-forme. Cette portabilité des performances peut être affectée par différents problèmes tels que des déséquilibres de charge, des communications coûteuses et des surcoûts provenant de l'ordonnancement des tâches. Le déséquilibre de charge est la conséquence de comportements de charges irrégulières et dynamiques, où le volume de calcul varie dynamiquement en fonction de la tâche et de l'étape de simulation. Les communications coûteuses sont provoquées par un ordonnancement qui ne prend pas en compte les différents temps de c! ommunication entre tâches sur une plate-forme hiérarchique. Cela est accentué par des communications non uniformes et asymétriques au niveau mémoire et réseau. Enfin, ces surcoûts peuvent être générés par des algorithmes de placement trop complexes dont les coûts ne seraient pas compensés par les gains de performance. Pour atteindre cet objectif de portabilité des performances, notre approche repose sur une récolte d'informations précises sur la topologie de la machine qui vont aider les algorithmes d'ordonnancement de tâches à prendre les bonnes décisions. Dans ce contexte, nous avons proposé une modélisation générique de la topologie des plates-formes parallèles. Le modèle comprend des latences et des bandes passantes mesurées de la mémoire et du réseau qui mettent en évidence des asymétries. Ces informations sont utilisées par nos trois algorithmes d'équilibrage de charge nommés NucoLB, HwTopoLB, et HierarchicalLB. De plus, ces algorithmes utilisent des informations provenant de l'exécution de l'application. NucoLB se concentre sur les aspects non uniformes de plates-formes parallèles, alors que HwTopoLB considère l'ensemble de la hiérarchie pour ses décisions, et HierarchicalLB combine ces algorithmes hiérarchiquement pour réduire son surcoût d'ordonnanceme! nt de tâches. Ces algorithmes cherchent à atténuer le déséquilibre de charge et des communications coûteuses tout en limitant les surcoûts de migration des tâches. Les résultats expérimentaux avec les trois régulateurs de charge proposés ont montré des améliorations de performances sur les meilleurs algorithmes de l'état de l'art: NucoLB a présenté jusqu'à 19% d'amélioration de performances sur un noeud de calcul; HwTopoLB a amélioré les performances en moyenne de 19%, et HierarchicalLB a surclassé HwTopoLB de 22% en moyenne sur des plates-formes avec plus de dix noeuds de calcul. Ces résultats ont été obtenus en répartissant la charge entre les ressources disponibles, en réduisant les coûts de communication des applications, et en gardant les surcoûts d'équilibrage de charge faibles. En ce sens, nos algorithmes d'équilibrage de charge permettent la portabilité des performances pour les applications scientifiques tout en étant indépendant de l'application et de l'architecture du système.

Les machines multicœurs équipées d'accélérateurs deviennent de plus en plus populaires dans le domaine du Calcul Haute Performance. Les architectures hybrides réduisent la consommation énergétique de manière significative et sont donc amenées à se généraliser dans l'ère du manycœur. Cependant, la complexité induite par ces architectures a un impact direct sur leur programmabilité. Il est donc indispensable de fournir des abstractions portables afin de tirer pleinement parti de ces machines. Les approches qui consistent à exécuter une application sur des processeurs généralistes et à ne déporter que certaines parties prédéterminées du calcul sur des accélérateurs ne sont pas suffisantes. Le véritable défi consiste donc à concevoir des environnements où les applications sont réparties sur l'intégralité de la machine, c'est-à-dire où les différents calculs sont ordonnancés dynamiquement sur la totalité des unités de calcul disponibles. Dans cette thèse, nous proposons donc un nouveau modèle de support exécutif fondé sur une abstraction de tâche et spécifiquement conçu pour répondre aux nombreux défis en termes d'ordonnancement de tâches et de gestion de données. La plate-forme StarPU a été conçue lors de cette thèse afin de démontrer la pertinence de ce modèle. StarPU propose une interface expressive permettant d'accéder à un ordonnancement flexible, fortement couplé à une gestion de données efficace. À l'aide de cet environnement et en associant les différentes tâches avec des modèles de performance auto-calibrés, il devient par exemple très simple de concevoir des stratégies d'ordonnancement prenant en compte les temps de calcul et les surcoûts liés aux mouvements de données. Nous montrons que notre modèle fondé sur un paradigme de tâche est suffisamment puissant pour exploiter les grappes de calcul d'une part, et les architectures manycœurs hybrides d'autre part. Nous analysons les performances obtenues non seulement grâce à des tests synthétiques, mais aussi à l'aide d'applications réelles. Nous obtenons ainsi des accélérations substantielles, ainsi qu'une très bonne efficacité parallèle sur différents types de plates-formes multicœurs, dotées d'accélérateurs.

No description available.

The amount of available data has allowed the field of machine learning to flourish. But with growing data set sizes comes an increase in algorithm execution times. Cluster computing frameworks provide tools for distributing data and processing power on several computer nodes and allows for algorithms to run in feasible time frames when data sets are large. Different cluster computing frameworks come with different trade-offs. In this thesis, the scalability of the execution time of machine learning algorithms running on the Hadoop cluster computing framework is investigated. A recent version of Hadoop and algorithms relevant in industry machine learning, namely K-means, latent Dirichlet allocation and naive Bayes are used in the experiments. This paper provides valuable information to anyone choosing between different cluster computing frameworks. The results show everything from moderate scalability to no scalability at all. These results indicate that Hadoop as a framework may have serious restrictions in how well tasks are actually parallelized. Possible scalability improvements could be achieved by modifying the machine learning library algorithms or by Hadoop parameter tuning.

This study considers software techniques for improving performance on clusters of workstations and approaches for designing message-passing middleware that facilitate scalable, parallel processing. Early binding and overlapping of communication and computation are identified as fundamental approaches for improving parallel performance and scalability on clusters. Currently, cluster computers using the Message-Passing Interface for interprocess communication are the predominant choice for building high-performance computing facilities, which makes the findings of this work relevant to a wide audience from the areas of high-performance computing and parallel processing. The performance-enhancing techniques studied in this work are presently underutilized in practice because of the lack of adequate support by existing message-passing libraries and are also rarely considered by parallel algorithm designers. Furthermore, commonly accepted methods for performance analysis and evaluation of parallel systems omit these techniques and focus primarily on more obvious communication characteristics such as latency and bandwidth. This study provides a theoretical framework for describing early binding and overlapping of communication and computation in models for parallel programming. This framework defines four new performance metrics that facilitate new approaches for performance analysis of parallel systems and algorithms. This dissertation provides experimental data that validate the correctness and accuracy of the performance analysis based on the new framework. The theoretical results of this performance analysis can be used by designers of parallel system and application software for assessing the quality of their implementations and for predicting the effective performance benefits of early binding and overlapping. This work presents MPI/Pro, a new MPI implementation that is specifically optimized for clusters of workstations interconnected with high-speed networks. This MPI implementation emphasizes features such as persistent communication, asynchronous processing, low processor overhead, and independent message progress. These features are identified as critical for delivering maximum performance to applications. The experimental section of this dissertation demonstrates the capability of MPI/Pro to facilitate software techniques that result in significant application performance improvements. Specific demonstrations with Virtual Interface Architecture and TCP/IP over Ethernet are offered.