Scheduling tasks sharing data on heterogeneous platforms

Nous étudions des stratégies d'ordonnancement et d'équilibrage de charge pour des plates-formes hétérogènes distribuées. Notre problème est d'ordonnancer un ensemble de tâches indépendantes afin d'en réduire le temps total d'exécution. Ces tâches utilisent des données d'entrée qui peuvent être partagées : chaque tâche peut utiliser plusieurs données, et chaque donnée peut être utilisée par plusieurs tâches. Les tâches ont des durées d'exécution différentes, et les données ont des tailles différentes. Toute la difficulté est de réussir à placer sur un même processeur des tâches partageant des données, tout en conservant un bon équilibrage de la charge des différents processeurs.Notre étude comporte trois parties généralisant progressivement le problème. Nous nous limitons dans un premier temps au cas simple où il n'y a pas de partage de données, où les tailles des tâches et des données sont homogènes, et où la plate-forme est de type maître-esclave. Le partage des données est introduit dans la deuxième partie, ainsi que l'hétérogénéité pour les tailles des tâches et des données. Dans la dernière partie nous généralisons le modèle de plate-forme à un ensemble décentralisé de serveurs reliés entre eux par un réseau d'interconnexion quelconque. La complexité théorique du problème est étudiée. Pour les cas simples, des algorithmes calculant une solution optimale sont proposés, puis validés par des résultats expérimentaux avec une application scientifique réelle. Pour les cas plus complexes, nous proposons de nouvelles heuristiques pour résoudre le problème d'ordonnancement. Ces nouvelles heuristiques, ainsi que des heuristiques classiques comme min-min et sufferage sont comparées entre elles à l'aide de nombreuses simulations. Nous montrons ainsi que nos nouvelles heuristiques réussissent à obtenir des performances aussi bonnes que les heuristiques classiques, tout en ayant une complexité algorithmique d'un ordre de grandeur plus faible.We study scheduling and load-balancing strategies for distributed heterogeneous platforms. Our problem is to schedule a set of independent tasks in order to reduce the overall execution time.These tasks can use some input data that may be shared: each task can use several data, and each datum can be used by several tasks.Tasks have different execution durations, and data have different sizes. The difficulty is to map on a same processor tasks sharing some data, while keeping a good load-balance across the processors.Our study comprises three parts, progressively generalizing the problem. First, we restrict ourselves to the simple case where there is no data sharing, with homogeneous sizes for tasks and data,and where the platform is a master-slave platform. Data sharing is introduced in the second part, along with heterogeneity for the tasks and data sizes. In the last part, we generalize the platform model to a decentralized set of servers, that are linked through an arbitrary interconnection network. The theoretical complexity of the problem is studied. For simple cases, algorithms to compute an optimal solution are given and validated by experimental results with a real scientific application. For more complicated cases, we propose new heuristics to solve the scheduling problem. These new heuristics, and classic ones like min-min and sufferage are compared through extensive simulations. Thus, we show that our new heuristics perform as efficiently as the classic ones although their algorithmic complexity is an order of magnitude lower