Cette thèse se concentre sur l'évaluation des performances des mécanismes d'équilibrage de charge. Pour l'utilisation efficace d'une architecture parallèle, il est nécessaire de développer des techniques de régulation de charge appropriées. Nous étudions en détail le problème de l'ordonnancement dynamique d'une application parallèle. Les fonctionnalités d'un ordonnanceur générique sont analysées et son implémentation dans le système Athapascan est décrit. Athapascan est un environnement de programmation pour les applications parallèles irrégulières. La structure de l'ordonnanceur permet l'implémentation de différents algorithmes d'équilibrage de charge. Pour étudier les différentes stratégies d'équilibrage et comparer leurs performances nous proposons une méthodologie. Nous avons construit des modèles de programmes synthétiques avec un caractère dynamique et aléatoire, à partir desquels nous avons établi un jeu d'essai. Nous avons choisi d'étudier les effets simultanés des différents paramètres des ordonnanceurs et de la charge synthétique. Une planification factorielle a été choisie parce qu'elle permet une vision globale de l'influence des différents paramètres. Les tests sont effectués sur une machine SP1-IBM. Deux méthodes d'analyse de données multivariée sont utilisées, l'analyse en composantes principales et la régression multiple. L'interprétation des modèles linéaires obtenus permet de comprendre le comportement de chaque ordonnanceur et l'influence de ses paramètres par rapport à la charge applicative.

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures.

Nos travaux portent sur la résolution de problèmes d'optimisation en ordonnancement d'ateliers de production, et plus particulièrement ceux relatifs à l'ordonnancement dynamique dans les industries agroalimentaires. <br />Les contraintes et les critères considérés sont spécifiques à ce type d'industrie qui présente certaines particularités, dues à la nature des produits manipulés et fabriqués, dont les durées de vie assez courtes. Ils concernent aussi le respect des dates de validité des composants primaires formant les opérations, des produits semi-finis et des produits finis. Les critères retenus sont aussi liés à ces particularités. On a distingué le coût des produits périmés, le coût du discount de distribution et la date de fin de l'ordonnancement, le makespan. Une méthode exacte et deux méthodes approchées ont été retenues et mises en œuvre, avec succès, pour les problèmes à une machine. <br />La méthode exacte, branch & bound, est appliquée pour la minimisation de la fonction de coût total. Les algorithmes génétiques, dotés d'un nouveau codage et hybridés avec l'approche Pareto-optimale, sont proposés pour la recherche de la solution optimale et pour aider le décideur de prendre une décision. Les algorithmes d'optimisation par colonie de fourmis, constituant la deuxième méthode approchée, est un processus stochastique qui, malgré la difficulté de paramétrage de l'algorithme correspondant, nous a permis de construire des solutions, en ajoutant des composants aux solutions temporaires.

La méthode multipôle permet d'accélérer les produits matrices-vecteurs, utilisés par les solveurs itératifs pour déterminer le comportement électromagnétique, d'un objet soumis à une onde incidente. Nos travaux ont pour but d'adapter cette méthode pour la rendre efficace sur les architectures hétérogènes contenant des GPU. Pour cela, nous utilisons une ordonnanceur dynamique, StarPU, qui effectuera la distribution des tâches de calcul au sein d'un nœud. Pour la parallélisation en mémoire distribuée, nous effectuerons un ordonnancement statique des boîtes, couplé à un ordonnancement dynamique des interactions proches.

Dans le cadre du projet PAJERO, nous présentons dans cette thèse une parallélisation externe d'un solveur de Programmation Par Contraintes (PPC) basée sur des méthodes de parallélisation de la search et Portfolio. Cela, afin d'améliorer la performance de la résolution des problèmes de satisfaction et d'optimisation sous contraintes. La parallélisation de la search que nous proposons est adaptée pour une exécution en mode opportuniste et déterministe, suivant les besoins des clients. Le principe consiste à partitionner à la demande l'arbre de recherche unique généré par une seule stratégie de recherche en un ensemble de sous-arbres, pour ensuite affecter chaque sous-arbre à un coeur de calcul. Une stratégie de recherche est un algorithme qui choisit pour chaque noeud dans l'arbre de recherche la variable à assigner et choisi également l'ordonnancement de la recherche. En PPC, il existe plusieurs stratégies de recherche, certaines sont plus efficaces que d'autres, mais cela dépend généralement de la nature des problèmesde contraintes. Cependant la difficulté reste de choisir la bonne stratégie. Pour bénéficier de la variété des stratégies et de la disponibilité des ressources de calcul, un autre type de parallélisation est proposé, appelé Portfolio. La parallélisationPortfolio consiste à exécuter en parallèle N stratégies de recherche, ensuite la première stratégie qui trouve une solution met fin à toutes les autres. La nouveauté que nous proposons dans la parallélisation Portfolio consiste à adapterl'ordonnancement des N stratégies entre elles afin de privilégier la stratégie la plus prometteuse. Cela en lui donnant plus de coeurs que les autres. Pour ceci nous appliquons soit une fonction d'estimation pour chaque stratégie afin de sélectionner la stratégie qui a le plus petit arbre de recherche, soit un algorithme d'apprentissage qui permet de prédire quelle est la meilleure stratégie suivant le résultat d'un apprentissage effectué sur des instances déjà résolues. Afin d'ordonnancer plusieurs applications de PPC, nous proposons également un nouveau système d'allocation de ressources basé sur une stratégie d'ordonnancement combinée avec un modèle économique. Les applications de PPC sont résolues avec des solveurs parallèles dans une infrastructure cloud computing. L'originalité du system d'allocation est qu'il détermine automatiquement le nombre de ressources à affecter pour chaque application suivant la classe économique du client. Les performances obtenues avec nos méthodes de parallélisation sont illustrées par la résolution des problèmes de contraintes en portant le solveur Google OR-Tools au-dessus de notre framework parallèle Bobpp / In the context of the PAJERO project, we propose in this thesis an external parallelization of a Constraint Programming (CP) solver, using both search and Portfolio parallelizations, in order to solve constraint satisfaction and optimization problems. In our work the search parallelization is adapted for deterministic and non-deterministic executions, according to the needs of the user. The principle is to partition the unique search tree generated by one search strategy into a set of sub-trees, then assign each sub-tree to one computing core. A search strategy herein means an algorithm to decide which variable is selected to be assigned in each node of the search tree, and decide also the scheduling of the search. In CP, several search strategies exist and each one could be better than others for solving a specific problem. The difficulty lies in how to choose the best strategy. To benefit from the variety of strategies and the availability of computationalresources, another parallelization exists called the Portfolio parallelization. The principle of this Portfolio parallelization is to execute N search strategies in parallel. The first strategy which find a solution stops the others. The noveltyof our work in the context of the Portfolio is to adapt the schedule of the N strategies in order to favour the most promising strategy, which is a candidate to find a solution first, by giving it more cores than others. The promising strategyis selected using two methods. The first method is to use an estimation function which select the strategy with the smallest search tree. The second method is to use a learning algorithm which automatically determines the number of cores thatwill be allocated to each strategy according to the previous experiment. We have also proposed a new resource allocation system based on a scheduling strategy used with an economic model in order to execute several PPC applications. Thisapplications are solved using parallel solvers in the cloud computing infrastructure. The originality of this system is that the number of resources allocated to each PPC application is determined automatically according the economic classesof the users. The performances obtained by our parallelization methods are illustrated by solving the CP problems using the Google OR-Tools solver on top of the parallel Bobpp framework.

La méthode multipôle permet d'accélérer les produits matrices-vecteurs, utilisés par les solveurs itératifs pour déterminer le comportement électromagnétique, d'un objet soumis à une onde incidente. Nos travaux ont pour but d'adapter cette méthode pour la rendre efficace sur les architectures hétérogènes contenant des GPU. Pour cela, nous utilisons une ordonnanceur dynamique, StarPU, qui effectuera la distribution des tâches de calcul au sein d'un nœud. Pour la parallélisation en mémoire distribuée, nous effectuerons un ordonnancement statique des boîtes, couplé à un ordonnancement dynamique des interactions proches. / The Fast Multipole Method can speed up matrix-vector products, found in iterative solvers in order to compute the electromagnetics response of an object subject to an incident wave. We have intended to adapt this method to make it effective on heterogeneous architectures with GPUs. For this purpose, we use a dynamic scheduler named StarPU, which distributes the tasks within a node. For the parallelization in distributed memory, we distribute the tasks statically but we distribute the near interactions dynamically..

Les besoins croissants en puissance de calcul sont généralement satisfaits en fédérant de plus en plus d'ordinateurs (ou noeuds) pour former des infrastructures distribuées. La tendance actuelle est d'utiliser la virtualisation système dans ces infrastructures, afin de découpler les logiciels des noeuds sous-jacents en les encapsulant dans des machines virtuelles. Pour gérer efficacement ces infrastructures virtualisées, de nouveaux gestionnaires logiciels ont été mis en place. Ces gestionnaires sont pour la plupart hautement centralisés (les tâches de gestion sont effectuées par un nombre restreint de nœuds dédiés). Cela limite leur capacité à passer à l'échelle, autrement dit à gérer de manière réactive des infrastructures de grande taille, qui sont de plus en plus courantes. Au cours de cette thèse, nous nous sommes intéressés aux façons d'améliorer cet aspect ; l'une d'entre elles consiste à décentraliser le traitement des tâches de gestion, lorsque cela s'avère judicieux. Notre réflexion s'est concentrée plus particulièrement sur l'ordonnancement dynamique des machines virtuelles, pour donner naissance à la proposition DVMS (Distributed Virtual Machine Scheduler). Nous avons mis en œuvre un prototype, que nous avons validé au travers de simulations (notamment via l'outil SimGrid), et d'expériences sur le banc de test Grid'5000. Nous avons pu constater que DVMS se montrait particulièrement réactif pour gérer des infrastructures virtualisées constituées de dizaines de milliers de machines virtuelles réparties sur des milliers de nœuds. Nous nous sommes ensuite penchés sur les perspectives d'extension et d'amélioration de DVMS. L'objectif est de disposer à terme d'un gestionnaire décentralisé complet, objectif qui devrait être atteint au travers de l'initiative Discovery qui fait suite à ces travaux.

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures. / New supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures.

Du fait des énormes capacités de calculs des accélérateurs tels que les GPUs et les Xeon Phi, l’utilisation de machines multicoques pourvues d’accélérateurs est devenue commune dans le domaine du calcul haute performance (HPC). La complexité induite par ces accélérateurs a suscité le développement de systèmes d’exécution à base de tâches, dans lesquels les dépendances entre les applications sont exprimées sous la forme de graphe de tâches et où les tâches sont ordonnancées dynamiquement sur les ressources de calcul. La difficulté est alors de concevoir des stratégies d’ordonnancement qui font une utilisation efficace des ressources de calculs et le développement de telles stratégies, même pour un unique noeud hybride, est un enjeu essentiel de la performance des systèmes HPC. Nous considérons dans cette thèse l’ordonnancement de noyaux d’algèbre linéaire dense sur des noeuds complètement hétérogènes et constitués de CPUs et de GPUs. Les performances relatives des accélérateurs par rapport aux coeurs classique dépend très fortement du noyau considéré. Par exemple, les accélérateurs sont beaucoup plus efficaces pour les produits de matrices, par exemple, que pour les factorisations. Dans cette thèse, nous analysons les performances de stratégies statiques et dynamiques d’ordonnancement et nous proposons un ensemble de stratégies intermédiaires, en ajoutant des composantes statiques (respectivement dynamiques) à des stratégies d’ordonnancements dynamique (respectivement statiques). Récemment, une stratégie appelée HeteroPrio a été proposée, qui s’appuie sur les affinités entre les tâches et les ressources pour un petit ensemble de tâches différentes s’exécutant sur deux types de ressources. Nous avons étendu cette stratégie d’ordonnancement pour des graphes de tâches généraux pour deux types de ressources puis pour plus de deux types. De manière complémentaire, nous avons également démontré des facteurs d’approximation et des pires cas pour HeteroPrio dans le cas d’un ensemble de tâches indépendantes sur différents types de plates-formes. / Due to massive computation power of accelerators such as GPU, Xeon phi, multicore machines equipped with accelerators are becoming popular in High Performance Computing (HPC). The added complexity led to the development of different task-based runtime systems, which allow computations to be expressed as graphs of tasks and rely on runtime systems to schedule those tasks among all resources of the platform. The real challenge is to design efficient schedulers for such runtimes to make effective utilization of all resources. Developing good schedulers, even for a single hybrid node, and analyzing them can thus have a strong impact on the performance of current HPC systems. We consider the problem of scheduling dense linear algebra applications on fully hybrid platforms made of CPUs and GPUs. The relative performance of CPU and GPU highly depends on the sub-routine. For instance, GPUs are much more efficient to process matrix-matrix multiplications than matrix factorizations. In this thesis, we analyze the performance of static and dynamic scheduling strategies and we propose a set of intermediate strategies, by adding static (resp. dynamic) features into dynamic (resp. static) strategies. A resource centric dynamic scheduler, HeteroPrio, which is based on affinity between tasks and resources, has been proposed recently for a set of small independent tasks on two types of resources. We extend and analyze this scheduler for general task graphs first on two types of resources and then on more than two types of resources. Additionally, we provide approximation ratios and worst case examples of HeteroPrio for a set of independent tasks on different platform sizes.

Les besoins croissants en puissance de calcul sont généralement satisfaits en fédérant de plus en plus d’ordinateurs (ou noeuds) pour former des infrastructures distribuées. La tendance actuelle est d’utiliser la virtualisation système dans ces infrastructures, afin de découpler les logiciels des noeuds sous-jacents en les encapsulant dans des machines virtuelles. Pour gérer efficacement ces infrastructures virtualisées, de nouveaux gestionnaires logiciels ont été mis en place. Ces gestionnaires sont pour la plupart hautement centralisés (les tâches de gestion sont effectuées par un nombre restreint de nœuds dédiés). Cela limite leur capacité à passer à l’échelle, autrement dit à gérer de manière réactive des infrastructures de grande taille, qui sont de plus en plus courantes. Au cours de cette thèse, nous nous sommes intéressés aux façons d’améliorer cet aspect ; l’une d’entre elles consiste à décentraliser le traitement des tâches de gestion, lorsque cela s’avère judicieux. Notre réflexion s’est concentrée plus particulièrement sur l’ordonnancement dynamique des machines virtuelles, pour donner naissance à la proposition DVMS (Distributed Virtual Machine Scheduler). Nous avons mis en œuvre un prototype, que nous avons validé au travers de simulations (notamment via l’outil SimGrid), et d’expériences sur le banc de test Grid’5000. Nous avons pu constater que DVMS se montrait particulièrement réactif pour gérer des infrastructures virtualisées constituées de dizaines de milliers de machines virtuelles réparties sur des milliers de nœuds. Nous nous sommes ensuite penchés sur les perspectives d’extension et d’amélioration de DVMS. L’objectif est de disposer à terme d’un gestionnaire décentralisé complet, objectif qui devrait être atteint au travers de l’initiative Discovery qui fait suite à ces travaux. / The increasing need in computing power has been satisfied by federating more and more computers (called nodes) to build the so-called distributed infrastructures. Over the past few years, system virtualization has been introduced in these infrastructures (the software is decoupled from the hardware by packaging it in virtual machines), which has lead to the development of software managers in charge of operating these virtualized infrastructures. Most of these managers are highly centralized (management tasks are performed by a restricted set of dedicated nodes). As established, this restricts the scalability of managers, in other words their ability to be reactive to manage large-scale infrastructures, that are more and more common. During this Ph.D., we studied how to mitigate these concerns ; one solution is to decentralize the processing of management tasks, when appropriate. Our work focused in particular on the dynamic scheduling of virtual machines, resulting in the DVMS (Distributed Virtual Machine Scheduler) proposal. We implemented a prototype, that was validated by means of simulations (especially with the SimGrid tool) and with experiments on the Grid’5000 test bed. We observed that DVMS was very reactive to schedule tens of thousands of virtual machines distributed over thousands of nodes. We then took an interest in the perspectives to improve and extend DVMS. The final goal is to build a full decentralized manager. This goal should be reached by the Discovery initiative,that will leverage this work.