Communication-aware scheduling on heterogeneous master-worker platforms

The results summarized in this document deal with the scheduling of independent tasks on large scale master-worker platforms, when realistic communication models are uti- lized. The contributions of this work are divided into three main parts: 1) Parallel algorithms: we underline the difficulty of scheduling identical independent tasks on heterogeneous master-worker platforms using the one-port communication model. We look at several sources of heterogeneity as well as several objective functions; 2) Matrix product: we compute the total communication volume that is needed for matrix multiplication in the presence of memory constraints and when data is centralized, and we develop a memory layout whose performance is close to the theoretical lower bound on the communication volume. We extend this algorithm for heterogeneous platforms; 3) Scheduling: lots of applications are constituted of a very large number of independent identical tasks. We focus on steady-state, and prove how to minimize the slowdown of one application when several are deployed, and how to minimize power consumption when only one application is present.Les travaux présentés dans cette thèse portent sur diverses techniques d'ordonnance- ment de tâches indépendantes pour des plates-formes de type maître-esclaves dis- tribuées à grande échelle, lorsque les temps de communications des tâches sont pris en compte par des modèles réalistes. Les contributions de cette thèse se situent à trois niveaux : 1) Algorithmique Parallèle : nous avons montré la complexité d'ordonnancer des tâches indépendantes sur une plate-forme hétérogène en modélisant les communications avec un modèle un-port, en regardant plusieurs sources d'hétérogénéité et plusieurs fonctions objectives; 2) Produit de matrices : nous avons calculé la borne théorique du volume de communication minimal nécessaire pour effectuer un produit de matrices dont les données sont centralisées, et où la mémoire des esclaves est limitée, et nous avons défini un algorithme efficace de partage de la mémoire, impliquant un volume de communication proche de la borne théorique. Nous avons ensuite étendu cet algorithme à des plate-formes hétérogènes ; 3) Ordonnancement : dans le cadre d'ordonnancement d'applications constituées d'un très grand nombre de tâches indépendantes et de caractéristiques identiques, nous avons étudié en régime permanent comment minimiser le retard de chaque application lorsqu'elles sont plusieurs à entrer en compétition pour les ressources de calcul, et comment minimiser la consommation de la plate-forme lorsqu'une seule application est déployée