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

Abstract

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 affines