Online Scheduling of Task Graphs on Heterogeneous Platforms
- 23 September 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 31 (3) , 721-732
Abstract
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ -competitive online algorithm by Amaris et al. [Euro-Par, 2017], where $m$ is the number of CPUs and $k$ the number of GPUs ( $m\geq k$ ). We prove that no online algorithm can have a competitive ratio smaller than $\sqrt{m/k}$ . We also study how adding flexibility on task processing, such as task migration or spoliation, or increasing the knowledge of the scheduler by providing it with information on the task graph, influences the lower bound. We provide a $(2\sqrt{m/k}+1)$ -competitive algorithm as well as a tunable combination of a system-oriented heuristic and a competitive algorithm; this combination performs well in practice and has a competitive ratio in $\Theta(\sqrt{m/k})$ . We also adapt all our results to the case of multiple types of processors. Finally, simulations on different sets of task graphs illustrate how the instance properties impact the performance of the studied algorithms and show that our proposed tunable algorithm performs the best among the online algorithms in almost all cases and has even performance close to an offline algorithm.
Keywords
Funding Information
- LABEX MILYON (ANR-10-LABX-0070)
- Université de Lyon (ANR-11-IDEX- 0007)
- Agence Nationale de la Recherche
This publication has 20 references indexed in Scilit:
- Scheduling Tasks with Precedence Constraints on Hybrid Multi-core Machines2015
- 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
- StarPU: a unified platform for task scheduling on heterogeneous multicore architecturesConcurrency and Computation: Practice and Experience, 2010
- Scheduling Problems on Two Sets of Identical MachinesComputing, 2003
- A standard task graph set for fair evaluation of multiprocessor scheduling algorithmsJournal of Scheduling, 2002
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002
- Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different SpeedsJournal of Algorithms, 1999
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969