Scheduling Parallel Task Graphs on non-dedicated heterogeneous multicluster platform with Moldable Task Duplication

摘要

Workflow applications structured as Parallel Task Graphs (PTG) exhibit both data and task parallelism and arise in scientific and industrial domains. Most of previous works regarding PTG scheduling only target dedicated multicluster platform. In this paper we develop a scheduling algorithm, MTD (Moldable Task Duplication with forward migration of duplicated predecessors), which applies to non-dedicated heterogeneous multicluster platforms. Our novel contribution is that in MTD, dynamic critical task determination accounts for the heterogeneity and fluctuations of multicluster platform within the hypothetical deadline, and the strategy of moldable task duplication with forward migrations of duplicated predecessors is invented to fully exploit the flexibility of data-parallel tasks. Simulations show that our approach can achieve better average PTG makespan than its competitors.