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 :
Rapport
[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

https://hal.inria.fr/hal-00944336
Contributeur : Equipe Roma <>
Soumis le : jeudi 13 février 2014 - 13:57:19
Dernière modification le : samedi 21 avril 2018 - 01:27:11
Document(s) archivé(s) le : jeudi 15 mai 2014 - 09:50:25

Fichier

rr8461.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

345

Téléchargements de fichiers

248