Skip to Main content Skip to Navigation

Memory-aware list scheduling for hybrid platforms

Julien Herrmann 1, 2 Loris Marchal 1, 2 Yves Robert 1, 2, * 
* Corresponding author
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This report provides memory-aware heuristics to schedule tasks graphs onto heterogeneous resources, such as a dual-memory cluster equipped with multicores and a dedicated accelerator (FPGA or GPU). Each task has a different processing time for either resource. The optimization objective is to schedule the graph so as to minimize execution time, given the available memory for each resource type. In addition to ordering the tasks, we must also decide on which resource to execute them, given their computation requirement and the memory currently available on each resource. The major contributions of this report are twofold: (i) the derivation of an intricate integer linear program formulation for this scheduling problem; and (ii) the design of memory-aware heuristics, which outperform the reference heuristics HEFT and MinMin on a wide variety of problem instances. The absolute performance of these heuristics is assessed for small-size graphs, with up to 30 tasks, thanks to the linear program.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Thursday, February 13, 2014 - 1:57:19 PM
Last modification on : Friday, September 30, 2022 - 4:12:06 AM
Long-term archiving on: : Thursday, May 15, 2014 - 9:50:25 AM


Files produced by the author(s)


  • HAL Id : hal-00944336, version 1



Julien Herrmann, Loris Marchal, Yves Robert. Memory-aware list scheduling for hybrid platforms. [Research Report] RR-8461, INRIA. 2014, pp.30. ⟨hal-00944336⟩



Record views


Files downloads