Evaluation of Dynamic Task Scheduling Algorithms in a Runtime System for Heterogeneous Architectures

Abstract:
Heterogeneous parallel architectures present many challenges to application developers. One of the most important ones is the decision where to execute a specific task. As today’s systems are often dynamic in nature, this cannot be solved at design time. A solution is offered by runtime systems that employ dynamic scheduling algorithms. Still, the question which algorithm to use remains. In this paper, we describe the integration of dynamic task scheduling algorithms well-known in the literature into EMB², a library for parallel programming of embedded heterogeneous systems. Moreover, we evaluate these algorithms on a real system using different benchmarks. The evaluation covers different modes: In immediate mode, tasks are scheduled in the order they arrive in the system, whereas in batch mode, all ready-toexecute tasks are considered during the scheduling decision. Our experimental results show that batch mode heuristics generally obtain better results. An exception is the Minimum Completion Time heuristic, which achieves similar results at less overhead and algorithm complexity.