Skip to Main content Skip to Navigation
Conference papers

Analysis of a List Scheduling Algorithm for Task Graphs on Two Types of Resources

Lionel Eyraud-Dubois 1, 2 Suraj Kumar 3
2 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
3 ALPINES - Algorithms and parallel tools for integrated numerical simulations
INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris, LJLL (UMR_7598) - Laboratoire Jacques-Louis Lions
Abstract : We consider the problem of scheduling task graphs on two types of unrelated resources, which arises in the context of task-based runtime systems on modern platforms containing CPUs and GPUs. In this paper, we focus on an algorithm named HeteroPrio, which was originally introduced as an efficient heuristic for a particular application. HeteroPrio is an adaptation of the well known list scheduling algorithm, in which the tasks are picked by the resources in the order of their acceleration factor. This algorithm is augmented with a spoliation mechanism: a task assigned by the list algorithm can later on be reassigned to a different resource if it allows to finish this task earlier. We propose here the first theoretical analysis of the HeteroPrio algorithm in the presence of dependencies. More specifically, if the platform contains m and n processors of each type, we show that the worst-case approximation ratio of HeteroPrio is between 1 + max(m/n, n/m) and 2 + max(m/n, n/m). Our proof structure allows to precisely identify the necessary conditions on the spoliation strategy to obtain such a guarantee. We also present an in-depth experimental analysis, comparing several such spoliation strategies, and comparing HeteroPrio with other algorithms from the literature. Although the worst case analysis shows the possibility of pathological behavior, HeteroPrio is able to produce, in very reasonable time, schedules of significantly better quality.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Lionel Eyraud-Dubois Connect in order to contact the contributor
Submitted on : Wednesday, January 8, 2020 - 10:51:21 AM
Last modification on : Friday, January 21, 2022 - 3:17:59 AM
Long-term archiving on: : Thursday, April 9, 2020 - 5:47:28 PM


Files produced by the author(s)


  • HAL Id : hal-02431810, version 1


Lionel Eyraud-Dubois, Suraj Kumar. Analysis of a List Scheduling Algorithm for Task Graphs on Two Types of Resources. IPDPS 2020 - 34th IEEE International Parallel and Distributed Procesing Symposium, May 2020, New Orleans / Virtual, United States. ⟨hal-02431810⟩



Les métriques sont temporairement indisponibles