Centralized Versus Distributed Schedulers Multiple Bag-of-Task Applications

Olivier Beaumont 1, 2 Larry Carter 3 Jeanne Ferrante 3 Arnaud Legrand 4 Loris Marchal 5, 6 Yves Robert 6, 5
2 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
6 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Multiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper we consider the problem of scheduling applications to ensure fair and efficient execution on master-worker platforms where the communication is restricted to a tree embedded in the network. The goal of the scheduling is to obtain the best throughput while enforcing some fairness between applications. We show how to derive an asymptotically optimal periodic schedule by solving a linear program expressing all problem constraints. For single-level trees, the optimal solution can be analytically computed. For large-scale platforms, gathering the global knowledge needed by the linear programming approach might be unrealistic. One solution is to adapt the multi-commodity flow algorithm of Awerbuch and Leighton, but it still requires some global knowledge. Thus, we also investigates heuristic solutions using only local information, and test them via simulations. The best of our heuristics achieves the optimal performance on about two-thirds of our test cases, but is far worse in a few cases.
Type de document :
Communication dans un congrès
International Parallel and Distributed Processing Symposium IPDPS'2006, 2006, Rhodes Island, Greece. IEEE Computer Society Press, 2006, 〈10.1109/TPDS.2007.70747〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00789440
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:30
Dernière modification le : mercredi 29 novembre 2017 - 15:24:28

Identifiants

Collections

Citation

Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand, Loris Marchal, et al.. Centralized Versus Distributed Schedulers Multiple Bag-of-Task Applications. International Parallel and Distributed Processing Symposium IPDPS'2006, 2006, Rhodes Island, Greece. IEEE Computer Society Press, 2006, 〈10.1109/TPDS.2007.70747〉. 〈hal-00789440〉

Partager

Métriques

Consultations de la notice

633