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

Conference: ARCS Workshop 2018 - 31th International Conference on Architecture of Computing Systems
04/09/2018 - 04/12/2018 at Braunschweig, Germany

Proceedings: ARCS 2018

Pages: 8Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Becker, Thomas (Chair of Computer Architecture and Parallel Processing, Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany)
Busse, Pablo (Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany)
Schuele, Tobias (Siemens AG, Corporate Technology, 81739 Munich, Germany)

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 EMB2, 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.