Skip to Main content Skip to Navigation
Conference papers

Online Scheduling of Task Graphs on Hybrid Platforms

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 m/k-competitive online algorithm [2], where m is the number of CPUs and k the number of GPUs (m ≥ k). We prove that no online algorithm can have a competitive ratio smaller than 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 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 Θ(m/k). 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 tun-able algorithm performs the best among the online algorithms in almost all cases and has even performance close to an offline algorithm.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, July 3, 2018 - 10:23:50 AM
Last modification on : Friday, September 30, 2022 - 4:12:19 AM
Long-term archiving on: : Monday, October 1, 2018 - 6:25:48 AM


Files produced by the author(s)


  • HAL Id : hal-01828301, version 1


Louis-Claude Canon, Loris Marchal, Bertrand Simon, Frédéric Vivien. Online Scheduling of Task Graphs on Hybrid Platforms. Euro-Par 2018 - 24th International European Conference On Parallel And Distributed Computing, Aug 2018, Turin, Italy. pp.1-14. ⟨hal-01828301⟩



Record views


Files downloads