Scheduling on Hybrid Platforms: Improved Approximability Window
Authors:
- Vincent FagnonVFVincent Fagnon
- Imed KacemIKImed Kacem
- Giorgio LucarelliGLGiorgio Lucarelli
- Bertrand SimonBSBertrand Simon
Preprint
Abstract
Modern platforms are using accelerators in conjunction with standard processing units in order to reduce the running time of specific operations, such as matrix operations, and improve their performance. Scheduling on such hybrid platforms is a challenging problem since the algorithms used for the case of homogeneous resources do not adapt well. In this paper we consider the problem of scheduling a set of tasks subject to precedence constraints on hybrid platforms, composed of two types of processing units. We propose a $(3+2\sqrt{2})$-approximation algorithm and a conditional lower bound of 3 on the approximation ratio. These results improve upon the 6-approximation algorithm proposed by Kedad-Sidhoum et al. as well as the lower bound of 2 due to Svensson for identical machines. Our algorithm is inspired by the former one and distinguishes the allocation and the scheduling phases. However, we propose a different allocation procedure which, although is less efficient for the allocation sub-problem, leads to an improved approximation ratio for the whole scheduling problem. This approximation ratio actually decreases when the number of processing units of each type is close and matches the conditional lower bound when they are equal.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Online Scheduling of Task Graphs on Heterogeneous PlatformsIEEE Transactions on Parallel and Distributed Systems, 2019
- Scheduling independent tasks on multi‐cores with GPU acceleratorsConcurrency and Computation: Practice and Experience, 2014
- ONLINE SCHEDULING OF MIXED CPU-GPU JOBSInternational Journal of Foundations of Computer Science, 2014
- Hardness of Precedence Constrained Scheduling on Identical MachinesSIAM Journal on Computing, 2011
- An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related MachinesJournal of Algorithms, 2001
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969