Large scale execution of a bioinformatic application on a volunteer grid

Scheduling problems are already difficult on traditional parallel machines. They becomeextremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. In this paper we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, whichmeans that there is no a priori (static) knowledge of the workload distribution at thebeginning of the execution. The objective is to minimize the maximum stretch, i.e. the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from theliterature, thereby fully assessing the usefulness of our approach.Les problèmes liés à l’ordonnancement de tâches sont déjà difficiles sur des machines traditionnelles. Ils deviennent encore plus inextricables sur des machines hétérogènes, même lorsque les applications considérées sont facilement parallélisables (de type tâches indépendantes). Nous nous intéressons ici à l’ordonnancement d’applications multiples, sous forme de collections de tâches indépendantes et identiques, sur une plate-forme maître-esclave hétérogène. Les requêtes de calcul surviennent au cours du temps, ce qui signifie que nous ne disposons pas de connaissance sur la charge de travail au tout début de l’exécution. Notre objectif est de minimiser l’étirement (stretch)maximum des applications, c’est-à-dire le rapport entre le temps que l’application passe dans le système avant d’être terminée et le temps qu’elle y aurait passé si elle disposait de la plate-forme pour elle seule. D’un point de vue théorique, nous concevons un algorithme optimal pour le cas hors-ligne (offline), lorsque toutes les dates d’arrivée et les caractéristiques des applications sont connues à l’avance. Nous proposons également plusieurs méthodes heuristiques pour le cas en-ligne (online), sans connaissance sur l’arrivée future des applications. D’un point vue expérimental, nous avons mené des expérimentations approfondies sous la forme de simulations avec SimGrid mais aussi dans un environnement parallèle réel, en utilisant MPI. Ces expérimentations montrent que nous sommes capables d’ordonnancer des problèmes de grande taille en quelques secondes. Enfin, la solution que nous proposons surpasse les méthodes heuristiques classiques, ce qui démontre l’intérêt de notre démarche