Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms

Abstract : Applications structured as parallel task graphs exhibit both data and task parallelism, and arise in many domains. Scheduling these applications efficiently on parallel platforms has been a long-standing challenge. In the case of a single homogeneous platform, such as a cluster, results have been obtained both in theory, i.e., guaranteed algorithms, and in practice, i.e., pragmatic heuristics. Due to task parallelism these applications are well suited for execution on distributed platforms that span multiple clusters possibly in multiple institutions. However, the only available results in this context are non-guaranteed heuristics. In this paper we develop a scheduling algorithm, MCGAS, which is applicable to multi-cluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multi-cluster platforms. Our novel contribution is that MCGAS computes task allocations so that a (tunable) performance guarantee is provided. Since a performance guarantee does not necessarily imply good average performance in practice, we also compare MCGAS with a recently proposed non-guaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2008, 20 (7), pp.940-952. 〈10.1109/TPDS.2009.11〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00347273
Contributeur : Frederic Suter <>
Soumis le : lundi 15 décembre 2008 - 13:19:54
Dernière modification le : jeudi 11 janvier 2018 - 06:21:05
Document(s) archivé(s) le : mardi 28 juin 2011 - 18:19:32

Fichiers

dutot_et_al.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre-Francois Dutot, Tchimou N'Takpé, Frédéric Suter, Henri Casanova. Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2008, 20 (7), pp.940-952. 〈10.1109/TPDS.2009.11〉. 〈inria-00347273〉

Partager

Métriques

Consultations de la notice

337

Téléchargements de fichiers

212