Evaluating DAG Scheduling Algorithms for Maximum Parallelism

In practical distributed computing systems, one of the challenges is to schedule efficiently and effectively complex computations composed of interdependent tasks, commonly represented by a Directed Acyclic Graph (DAG). One element of this challenge is that the availability of resources and the precise execution time of different computations are often difficult to predict. Given this unpredictability, the priority based (PB) scheduling scheme aims at maximizing the parallelism of ready tasks. In this paper, the PB scheduling scheme is investigated in detail with respect to its efficiency and performance. Our results suggest that for various experimental settings, the PB scheme outperforms other popular existing solutions in overall execution time, with an acceptable running overhead as well as a wider usability as it can be applied to arbitrary DAG structure.