Allocation de tâches et équilibrage de charge pour les performances, la mémoire, la fiabilité et l'énergie

This thesis focuses on multi-objective optimization problems arising when running scientific applications on high performance computing platforms and streaming applications on embedded systems. These optimization problems are all proven to be NP-complete, hence our efforts are mainly on designing efficient heuristics for general cases, and proposing optimal solutions for special cases.Some scientific applications are commonly modeled as rooted trees. Due to the size of temporary data, processing such a tree may exceed the local memory capacity. A practical solution on a multiprocessor system is to partition the tree into many subtrees, and run each on a processor, which is equipped with a local memory. We studied how to partition the tree into several subtrees such that each subtree fits in local memory and the makespan is minimized, when communication costs between processors are accounted for.Then, a practical work of tree scheduling arising in parallel sparse matrix solver is examined. The objective is to minimize the factorization time by exhibiting good data locality and load balancing. The proportional mapping technique is a widely used approach to solve this resource-allocation problem. It achieves good data locality by assigning the same processors to large parts of the task tree. However, it may limit load balancing in some cases. Based on proportional mapping, a dynamic scheduling algorithm is proposed. It relaxes the data locality criterion to improve load balancing. The performance of our approach has been validated by extensive experiments with the parallel sparse matrix direct solver PaStiX.Streaming applications often appear in video and audio domains. They are characterized by a series of operations on streaming data, and a high throughput. Multi-Processor System on Chip (MPSoC) is a multi/many-core embedded system that integrates many specific cores through a high speed interconnect on a single die. Such systems are widely used for multimedia applications. Lots of MPSoCs are batteries-operated. Such a tight energy budget intrinsically calls for an efficient schedule to meet the intensive computation demands. Dynamic Voltage and Frequency Scaling (DVFS) can save energy by decreasing the frequency and voltage at the price of increasing failure rates. Another technique to reduce the energy cost and meet the reliability target consists in running multiple copies of tasks. We first model applications as linear chains and study how to minimize the energy consumption under throughput and reliability constraints, using DVFS and duplication technique on MPSoC platforms.Then, in a following study, with the same optimization goal, we model streaming applications as series-parallel graphs, which are more complex than simple chains and more realistic. The target platform has a hierarchical communication system with two levels, which is common in embedded systems and high performance computing platforms. The reliability is guaranteed through either running tasks at the maximum speed or triplication of tasks. Several efficient heuristics are proposed to tackle this NP-complete optimization problem.Cette thèse se concentre sur les problèmes d'optimisation multi-objectifs survenant lors de l'exécution d'applications scientifiques sur des plates-formes de calcul haute performance et des applications de streaming sur des systèmes embarqués. Ces problèmes d'optimisation se sont tous avérés NP-complets, c'est pourquoi nos efforts portent principalement sur la conception d'heuristiques efficaces pour des cas généraux et sur la proposition de solutions optimales pour des cas particuliers.Certaines applications scientifiques sont généralement modélisées comme des arbres enracinés. En raison de la taille des données temporaires, le traitement d'une telle arborescence peut dépasser la capacité de la mémoire locale. Une solution pratique sur un système multiprocesseur consiste à partitionner l'arborescence en plusieurs sous-arbres, et à exécuter chacun d'eux sur un processeur, qui est équipé d'une mémoire locale. Nous avons étudié comment partitionner l'arbre en plusieurs sous-arbres de sorte que chaque sous-arbre tienne dans la mémoire locale et que le makespan soit minimisé, lorsque les coûts de communication entre les processeurs sont pris en compte. Ensuite, un travail pratique d'ordonnancement d'arbres apparaissant dans un solveur de matrice clairsemée parallèle est examiné. L'objectif est de minimiser le temps de factorisation en présentant une bonne localisation des données et un équilibrage de charge. La technique de cartographie proportionnelle est une approche largement utilisée pour résoudre ce problème d'allocation des ressources. Il réalise une bonne localisation des données en affectant les mêmes processeurs à de grandes parties de l'arborescence des tâches. Cependant, cela peut limiter l'équilibrage de charge dans certains cas. Basé sur une cartographie proportionnelle, un algorithme d'ordonnancement dynamique est proposé. Il assouplit le critère de localisation des données pour améliorer l'équilibrage de charge. La performance de notre approche a été validée par de nombreuses expériences avec le solveur direct à matrice clairsemée parallèle PaStiX. Les applications de streaming apparaissent souvent dans les domaines vidéo et audio. Ils se caractérisent par une série d'opérations sur le streaming de données et un débit élevé. Le système multiprocesseur sur puce (MPSoC) est un système embarqué multi / plusieurs cœurs qui intègre de nombreux cœurs spécifiques via une interconnexion haute vitesse sur une seule puce. De tels systèmes sont largement utilisés pour les applications multimédias. De nombreux MPSoC fonctionnent sur piles. Un budget énergétique aussi serré nécessite intrinsèquement un calendrier efficace pour répondre aux demandes de calcul intensives. La mise à l'échelle dynamique de la tension et de la fréquence (DVFS) peut économiser de l'énergie en diminuant la fréquence et la tension au prix d'une augmentation des taux de défaillance. Une autre technique pour réduire le coût énergétique et atteindre l'objectif de fiabilité consiste à exécuter plusieurs copies de tâches. Nous modélisons d'abord les applications sous forme de chaînes linéaires et étudions comment minimiser la consommation d'énergie sous des contraintes de débit et de fiabilité, en utilisant DVFS et la technique de duplication sur les plates-formes MPSoC.Ensuite, dans une étude suivante, avec le même objectif d'optimisation, nous modélisons les applications de streaming sous forme de graphes série-parallèle, plus complexes que de simples chaînes et plus réalistes. La plate-forme cible dispose d'un système de communication hiérarchique à deux niveaux, ce qui est courant dans les systèmes embarqués et les plates-formes informatiques hautes performances. La fiabilité est garantie par l'exécution des tâches à la vitesse maximale ou par la triplication des tâches. Plusieurs heuristiques efficaces sont proposées pour résoudre ce problème d'optimisation NP-complet