Scheduling Divisible Workloads on Heterogeneous Platforms
BEAUMONT, Olivier
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
BEAUMONT, Olivier
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
< Réduire
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Langue
en
Article de revue
Ce document a été publié dans
Parallel Computing. 2003, vol. 29, p. 1121―1152
Elsevier
Résumé en anglais
In this paper, we discuss several algorithms for scheduling divisible workloads on heterogeneous systems. Our main contributions are (i) new optimality results for single-round algorithms and (ii) the design of an ...Lire la suite >
In this paper, we discuss several algorithms for scheduling divisible workloads 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 the processors and/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).< Réduire
Origine
Importé de halUnités de recherche