Communications collectives et ordonnancement en régime permanent sur plates-formes hétérogènes

The results presented in this document concern scheduling forlarge-scale heterogeneous platforms. We mainly focus on collectivecommunications taking place during the execution of distributedapplications: broadcast, scatter or reduction of data for instance. Westudy the steady-state operation of these communications and we aim atmaximizing the throughput of a series of similar communications. Thegoal is also to obtain an asymptotically optimal schedule as formakespan minimization. We present a general framework to study thesecommunications, which we use to assess the complexity of the problem foreach communication primitive. For a particular model of communication,the bidirectional one-port model, we develop a practical for solvingthe problem, based on a linear program in rational numbers. This resultsare illustrated by experiments on the Grid5000 platform. The study ofsteady-state operations is extended to scheduling multipleapplications on computing grids.Les travaux présentés dans cette thèse concernent l'ordonnancementpour les plates-formes hétérogènes à grande échelle. Nous nousintéressons principalement aux opérations de communicationscollectives comme la diffusion de données, la distribution de donnéesou la réduction. Nous étudions ces problèmes dans le cadre de leurrégime permanent, en optimisant le débit d'une série d'opérations decommunications, en vue d'obtenir un ordonnancement asymptotiquementoptimal du point de vue du temps d'exécution total. Après avoirprésenté un cadre général d'étude qui nous permet de connaître lacomplexité du problème pour chaque primitive, nous développons, pourle modèle de communication un-port bidirectionnel, une méthode derésolution pratique fondée sur la résolution d'un programme linéaireen rationnels. Cette étude du régime permanent est illustrée par desexpérimentations sur Grid5000 et se prolonge vers l'ordonnancementd'applications multiples sur des grilles de calcul