Memory-aware list scheduling for hybrid platforms

Julien Herrmann 1, 2 Loris Marchal 1, 2 Yves Robert 1, 2, *
* Auteur correspondant
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.
Type de document :
[Research Report] RR-8461, INRIA. 2014, pp.30
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
Contributeur : Equipe Roma <>
Soumis le : jeudi 13 février 2014 - 13:57:19
Dernière modification le : jeudi 8 février 2018 - 11:10:04
Document(s) archivé(s) le : jeudi 15 mai 2014 - 09:50:25


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers