Approches algorithmiques pour l'ordonnancement d'applications parallèles avec communications

This thesis focus on the problem of scheduling the tasks of a parallel application taking into account the impact of communications. On distributed memory computers such as PC clusters communication time are important. The objectives of this thesis is to study models allowing to take into account efficiently those communications and to study the scheduling problems under those models. We study the large communication delay model based on an explicit modeling of communications and the malleable tasks model where task may be executed on a variable number of processors. oure contributions goes to the three following directions. For scheduling malleable tasks with precedence constraints we proposed approximation algorithm (polynomial algorithm offering guarantees relatively to an optimal solution) for the case of trees and for the case of an arbitrary precedence task graph. An original approach is proposed for the clustering problem (scheduling on an unbounded nimber of processors). This approach is based on a recursive decomposition ofCette thèse est consacrée à l'étude de l'ordonnancement des tâches d'un programme parallèle en prenant en compte l'impact des communications. Sur les machines à mémoire distribuée telles que les grappes de PC, les temps de communications peuvent être importants. Les objectifs de cette thèse sont l'étude de modèles permettant de prendre en compte efficacement ces communications et l'étude des problèmes d'ordonnancement sous ces modèles. Nous nous sommes interessés au modèle à grand délai de communications qui est basé sur une prise en compte explicite des communications et au modèle des tâches malléables dans lequel les tâches sont elles-mêmes des activités parallèles pouvant s'exécuter sur un nombre variable de processeurs. Outre l'étude de la pertinance de ces modèles, les contributions obtenues vont dans les trois directions suivantes. Pour l'ordonnancement de tâches malléables avec contraintes de précédence nous avons proposé des algorithmes d'approximation constante (algorithmes polynômiaux offrant des garanties relativement à une solution optimale), pour le cas des arbres et pour le cas d'un graphe de précedence arbitraire. Une heuristique originale pour le problème du regroupement (ordonnancement sur un nombre non borné de processeurs) est proposée. Elle est basée sur une décomposition récursive du graphe de précédence et elle est validée par des simulations sur des graphes d'applications réelles. Enfin nous nous sommes intéressés au problème d'ordonnancement sous le modèle à grand délai de communication en considérant la possibilité de dupliquer des tâches. Dans ce cadre nous avons obtenu un algorithme polyôomial offrant une garantie logarithmique en fonction du délai de communication, améliorant ainsi la meilleure garantie connue (linéaire)