Scheduling Divisible Loads on Star and Tree Networks: Results and Open Problems

Applications in many scientific and engineering domains are structured in large numbers of independent tasks with low granularity. These applications can thus be naturally parallelized, typically in master-worker fashion, provided that efficient scheduling strategies are available. Such applications have been called divisible loads because a scheduler may divide the computation among worker processes arbitrarily, both in terms of number of tasks and of task sizes. Divisible load scheduling has been an active area of research for the last twenty years. A vast literature offers results and scheduling algorithms for various models for the underlying distributed computing platform. Broad surveys are available that report on accomplishments in the field. By contrast, in this paper we propose a unified theoretical perspective that synthesizes previously published results, several novel results, and open questions, in a view to foster novel divisible load scheduling research. Specifically, we discuss both one-round and multi-round algorithms, and we restrict our scope to the popular star and tree network topologies, which we study with both linear and affine cost models for communication and computation.De nombreuses applications scientifiques se découpent naturellement en un grand nombre de tâches indépendantes avec une faible granularité. Ces applications se parallélisent naturellement `a l’aide d’une approche maître/esclave. De telles applications relèvent du modèle des tâches divisibles car un ordonnanceur peut diviser les calculs sur les différents processeurs disponibles, à la fois en terme de nombre de tâches mais également en terme de taille des tâches. L’ordonnancement de tâches divisibles à été un domaine de recherche actif durant les vingt dernières années. On trouve donc dans la littérature de nombreux résultats et algorithmes d’ordonnancement pour différents modèles de plateformes.`A la différence des états de l’art déjà existant sur le sujet, ce rapport propose une nouvelle approche permettant d’unifier et de retrouver les résultats de la littérature, de proposer de nouveaux résultats et d’ouvrir de nouveaux problèmes. Plus précisément, nous présentons les distributions en une seule tournée et en plusieurs tournées et nous restreignons aux topologies populaires en étoile et en arborescence, que nous nous ́ étudions à l’aide de coût de calculs et de communications linéaires puis affine