Model and complexity results for tree traversals on hybrid platforms

Julien Herrmann 1, 2 Loris Marchal 1, 2 Yves Robert 1, 2
Abstract : We study the complexity of traversing tree-shaped workflows whose tasks require large I/O files. We target a heterogeneous architec- ture with two resource of different types, where each resource has its own memory, such as a multicore node equipped with a dedicated accelera- tor (FPGA or GPU). Tasks in the workflow are tagged with the type of resource needed for their processing. Besides, a task can be processed on a given resource only if all its input files and output files can be stored in the corresponding memory. At a given execution step, the amount of data stored in each memory strongly depends upon the ordering in which the tasks are executed, and upon when communications between both memories are scheduled. The objective is to determine an efficient traver- sal that minimizes the maximum amount of memory of each type needed to traverse the whole tree. In this paper, we establish the complexity of this two-memory scheduling problem, provide inapproximability results, and show how to determine the optimal depth-first traversal. Altogether, these results lay the foundations for memory-aware scheduling algorithms on heterogeneous platforms.
Type de document :
Communication dans un congrès
HeteroPar - International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2013, Aachen, Germany. 2013
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00926502
Contributeur : Equipe Roma <>
Soumis le : jeudi 9 janvier 2014 - 16:33:04
Dernière modification le : mardi 16 janvier 2018 - 15:35:57
Document(s) archivé(s) le : jeudi 10 avril 2014 - 11:55:17

Fichier

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

Identifiants

  • HAL Id : hal-00926502, version 1

Collections

Citation

Julien Herrmann, Loris Marchal, Yves Robert. Model and complexity results for tree traversals on hybrid platforms. HeteroPar - International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2013, Aachen, Germany. 2013. 〈hal-00926502〉

Partager

Métriques

Consultations de la notice

121

Téléchargements de fichiers

209