MigHEFT: DAG-based Scheduling of Migratable Tasks on Heterogeneous Compute Nodes

Application tasks expose different computational demands that can be best served by different architectures such as CPUs, GPU, and FPGAs. Existent execution models do not allow for migrating tasks across different computing resources at runtime, which limits scheduling flexibility. In this paper we first describe our execution model and runtime system that enable heterogeneous migration for data-parallel applications. Then, we focus on the problem of scheduling a set of dependent tasks on a heterogeneous compute node by exploiting this novel feature of heterogenous task migration. We present the MigHEFT scheduling approach that combines an off-line created schedule based on estimations of task execution times with runtime monitoring and rescheduling, possibly leading to migration. We evaluate MigHEFT on a broad range of DAGs exhibiting different runtime characteristics and compare it with HEFT algorithms, widely-used reference schedulers for minimizing the makespan for a set of dependent tasks on heterogeneous resources. We demonstrate that due to the novel migration capability, our scheduling approach achieves an average speedup of 14.1% over HEFT and 8.6% over HEFT extended with rescheduling.