Throughput optimization for pipeline workflow scheduling with setup times

Abstract : In this paper, we tackle pipeline workflow applications that are executed on a dis- tributed heterogeneous platform with setup times. In such applications, several computation stages are interconnected as a linear application graph. The considered stage/processor mapping strategy is based on interval mappings, where an interval of consecutive stages is performed by the same processor. Each stage holds a buffer of limited size where intermediate results are stored and a setup time occurs when passing from one stage to another. Typical examples for this kind of applications are streaming applications such as audio and video coding or decoding, image pro- cessing using co-processing devices as FPGA. In this paper, we focus on throughput optimization. This problem is known to be NP-hard as soon as heterogeneous processors are used, even without setup times and with homogeneous communication links. We provide an optimal algorithm for the inner-processor scheduling of stages on homogeneous platforms with identical buffer capacities. We also provide an interval mapping that, when running the former algorithm including all processors, maximizes the throughput of the application. Last, we deal with the problem of allocating the buffers for each stage in shared memory. We provide an optimal algorithm for buffer allocation in the case where the memory may be split evenly, and we propose heuristics to handle any remainder in the memory allocation.
Type de document :
Rapport
[Research Report] RR-7886, INRIA. 2012, pp.29
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00674057
Contributeur : Anne Benoit <>
Soumis le : mardi 19 juin 2012 - 09:41:22
Dernière modification le : vendredi 6 juillet 2018 - 15:06:05
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 16:04:49

Fichier

RR-7886.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00674057, version 2

Citation

Anne Benoit, Mathias Coqblin, Jean-Marc Nicod, Laurent Philippe, Veronika Rehn-Sonigo. Throughput optimization for pipeline workflow scheduling with setup times. [Research Report] RR-7886, INRIA. 2012, pp.29. 〈hal-00674057v2〉

Partager

Métriques

Consultations de la notice

705

Téléchargements de fichiers

134