Multi-criteria scheduling of pipeline workflows (and application to the JPEG encoder)

Abstract : Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). A typical application class is digital image coding, where images are processed in steady-state mode. In this paper, we study the general bi-criteria mapping problem (minimizing period and latency) for pipeline graphs on communication homogeneous platforms. We present an integer linear programming formulation for this NP-hard problem. Furthermore, we provide several efficient polynomial bi-criteria heuristics, whose relative performance is evaluated through extensive simulations. As a case study, we provide simulations and MPI experimental results for the JPEG encoder application pipeline on a cluster of workstations.
Type de document :
Article dans une revue
International Journal of High Performance Computing Applications, SAGE Publications, 2009, 23 (2), pp.171-187. 〈10.1177/1094342009104009〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00980694
Contributeur : Equipe Roma <>
Soumis le : vendredi 18 avril 2014 - 15:53:45
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Anne Benoit, Harald Kosch, Veronika Rehn-Sonigo, Yves Robert. Multi-criteria scheduling of pipeline workflows (and application to the JPEG encoder). International Journal of High Performance Computing Applications, SAGE Publications, 2009, 23 (2), pp.171-187. 〈10.1177/1094342009104009〉. 〈hal-00980694〉

Partager

Métriques

Consultations de la notice

124