Scientific workflow scheduling in non-dedicated heterogeneous multicluster with advance reservations

Abstract

Scientific workflow structured as Parallel Task Graphs(PTG) exhibits both data and task parallelism, and arises in scientific as well as in industrial domains. Efficient scheduling of such workflow on a multicluster platform has been a long-standing challenge. Most of previous work on PTG scheduling primarily focused on dedicated multicluster. In this paper, a novel scheduling algorithm known as the Moldable Task Duplication(MTD) is applied to non-dedicated heterogeneous multicluster platform with advance reservations. A novel method for the calculation of dynamic critical path that handles the availability fluctuation of multicluster and the moldability of scientific workflow's data-parallel tasks is proposed. A moldable task duplication strategy with migration of pre-duplicated predecessor tasks is developed to fully exploit the flexibility of data-parallel tasks. Simulations spanning a broad range of scientific workflow and multicluster platform settings are performed in order to verify the proposed approach. The numerical results show that MTD can achieve better average PTG makespan than previous methods in the literature.