Title
Scheduling Parallel Task Graphs on (Almost) Homogeneous Multicluster 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 nonguaranteed heuristics. In this paper, we develop a scheduling algorithm, MCGAS, which is applicable to multicluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multicluster 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 nonguaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.
Year
DOI
Venue
2009
10.1109/TPDS.2009.11
Parallel and Distributed Systems, IEEE Transactions
Keywords
Field
DocType
graph theory,parallel processing,scheduling,MCGAS,distributed platform,homogeneous multicluster platform,parallel task graphs scheduling,task allocation,Mixed parallelism,multicluster platform.,parallel task graph scheduling,performance guarantee
Middleware,Graph theory,Scheduling (computing),Task parallelism,Computer science,Parallel computing,Real-time computing,Heuristics,Concurrent computing,Cluster analysis,Distributed computing,Scalability
Journal
Volume
Issue
ISSN
20
7
1045-9219
Citations 
PageRank 
References 
27
1.05
22
Authors
4
Name
Order
Citations
PageRank
Pierre-françois Dutot116613.95
Tchimou N'Takpe21134.99
Frederic Suter3271.05
Henri Casanova41671106.43