Skip to Main content Skip to Navigation
Reports

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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00944336
Contributor : Equipe Roma <>
Submitted on : Thursday, February 13, 2014 - 1:57:19 PM
Last modification on : Wednesday, November 20, 2019 - 3:18:13 AM
Long-term archiving on: : Thursday, May 15, 2014 - 9:50:25 AM

File

rr8461.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00944336, version 1

Collections

Citation

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

Share

Metrics

Record views

428

Files downloads

404