Efficient application scheduling is critical for achieving high performance in heterogeneous computing systems. This problem has proved to be NP-complete, heading research efforts in obtaining low complexity heuristics that produce good quality schedules. Although this problem has been extensively studied in the past, first, all the related algorithms assume the computation costs of application tasks on processors are available a priori, ignoring the fact that the time needed to run/simulate all these tasks is orders of magnitude higher than finding a good quality schedule, especially in heterogeneous systems. Second, low complexity heuristics consider application tasks as single thread implementations only, but in practice tasks are normally split into multiple threads. In this paper, we propose two new methods applicable to several task scheduling algorithms, addressing the above problems in heterogeneous computing systems. We showcase both methods by using HEFT well known and popular algorithm, but this work is applicable to other algorithms too, such as HCPT, HPS, PETS and CPOP. First, we propose a methodology to reduce the number of computation costs required by HEFT (and therefore the number of simulations), without sacrificing the length of the output schedule. Second, we give heuristics to find which tasks are going to be executed as Single-Thread and which as Multi-Thread implementations, as well as the number of threads used, without requiring all the computation costs. The experimental results considering both random graphs and real world applications show that extending HEFT with the two proposed methods achieves better schedule lengths, while at the same time requires from 4.5 up to 24 less simulations.
This article was presented at 25th IEEE International Conference on High Performance Computing, Data and Analytics,
Please find the article here: eprints.whiterose.ac.uk/136151/1/hipc2018.pdf