Approximation algorithm for scheduling a chain of tasks on heterogeneous systems

Massinissa Ait Aba 1 Lilia Zaourar 1 Alix Munier 2
1 DACLE-LIST - Département d'Architectures, Conception et Logiciels Embarqués-LIST
2 ALSOC - Architecture et Logiciels pour Systèmes Embarqués sur Puce
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : This paper presents an efficient approximation algorithm to solve the task scheduling problem on heterogeneous platform for the particular case of the linear chain of tasks. The objective is to minimize both the total execution time (makespan) and the total energy consumed by the system. For this purpose, we introduce a constraint on the energy consumption during execution. Our goal is to provides an algorithm with a performance guarantee. Two algorithms have been proposed; the first provides an optimal solution for preemptive scheduling. This solution is then used in the second algorithm to provide an approximate solution for non-preemptive scheduling. Numerical evaluations demonstrate that the proposed algorithm achieves a close-to-optimal performance compared to exact solution obtained by CPLEX for small instances. For large instances, CPLEX is struggling to provide a feasible solution, whereas our approach takes less than a second to produce a solution for an instance of 10000 tasks.
Keywords : Linear chain of tasks Makespan Energy Approximation algorithm
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
https://hal-cea.archives-ouvertes.fr/cea-01772616
Contributor : Léna Le Roy <>
Submitted on : Tuesday, January 15, 2019 - 11:28:02 AM
Last modification on : Wednesday, March 27, 2019 - 10:12:01 AM
Long-term archiving on : Tuesday, April 16, 2019 - 1:42:44 PM

File

AitAba2018.pdf
Files produced by the author(s)

Identifiers

Collections

CEA | SORBONNE-UNIVERSITE | LIST | UNIV-PARIS-SACLAY | CEA-UPSAY | DRT | LIP6 | CNRS | UPMC | SU-SCIENCES

Citation

Massinissa Ait Aba, Lilia Zaourar, Alix Munier. Approximation algorithm for scheduling a chain of tasks on heterogeneous systems. Euro-Par 2017: Parallel Processing Workshops, Aug 2017, Santiago de Compostela, Spain. pp.353-365, ⟨10.1007/978-3-319-75178-8_29⟩. ⟨cea-01772616⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

185

Files downloads

136

Contact

CCSD