Optimal algorithms for scheduling divisible workloads on heterogeneous systems

Olivier Beaumont (1) , Arnaud Legrand (1) , Yves Robert (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

In this paper, we discuss several algorithms for scheduling divisible loads on heterogeneous systems. Our main contributions are (i) new optimality results for single-round algorithms and (ii) the design of an asymptotically optimal multi-round algorithm. This multi-round algorithm automatically performs resource selection, a difficult task that was previously left to the user. Because it is periodic, it is simpler to implement, and more robust to changes in the speeds of processors or communication links. On the theoretical side, to the best of our knowledge, this is the first published result assessing the absolute performance of a multi-round algorithm. On the practical side, extensive simulations reveal that our multi-round algorithm outperforms existing solutions on a large variety of platforms, especially when the communication-to-computation ratio is not very high (the difficult case).

Dans ce rapport, nous comparons un certain d'algorithmes ordonnancement de tâches divisibles sur une plateforme hétérogène. Nos contributions principales sont (i) de nouveaux résultats d’optimalité pour les algorithmes à une étape et (ii) la conception d'un algorithme multi-étapes asymptotiquement optimal. Ce dernier algorithme effectue automatiquement la sélection des ressources à utiliser, tâche délicate généralement laissée à l’utilisateur. En raison de sa périodicité, il est plus facile à lettre en œuvre et plus robuste aux variation de charge des processeurs ou des liens de communications? D'un point de vue théorique c'est, à notre connaissance , le premier résultat garanti sur les performances d'un algorithme mulit-étapes. D'un point de vue plus appliqué, les simulations que nous avons menées montrent que cet algorithme est meilleur que les autres algorithmes sur une large variété de plateformes, tout particulièrement quand le rapport entre les communications et le calcul est élevé ( le cas le plus délicat)

Mots clés: Asymptotical Optimality; Divisible Tasks; Multi-Round Algorithms; Scheduling

Mots clés: Ordonnancement; Tâches divisibles; Algorithmes multi-étapes; Optimalité asymptotique

Domaines: Informatique [cs]

Olivier Beaumont, Arnaud Legrand, Yves Robert. Optimal algorithms for scheduling divisible workloads on heterogeneous systems. [Research Report] LIP RR-2002-36, Laboratoire de l'informatique du parallélisme. 2002, 2+23p. ⟨hal-02102118⟩