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

Konferenz: ARCS Workshop 2018 - 31th International Conference on Architecture of Computing Systems
09.04.2018 - 12.04.2018 in Braunschweig, Germany

Tagungsband: ARCS 2018

Seiten: 8Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

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.