Multi-criteria scheduling of pipeline workflows


== 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). In this paper, we study the complexity of the bi-criteria mapping problem for pipeline graphs on communication homogeneous platforms. In particular, we assess the complexity of the well-known chains-to-chains problem for different-speed processors, which turns out to be NP-hard. We provide several efficient polynomial bi-criteria heuristics, and their relative performance is evaluated through extensive simulations.; L’ordonnancement et l’allocation des workflows sur plates-formes parallèles est un problème crucial, même pour des applications simples comme des graphes en pipeline. Plusieurs critères contradictoires doivent être optimisés, tels que le débit et la latence (ou une combinaison des deux). Dans ce rapport, nous étudions la complexité du problème de l’ordonnancement bi-critère pour les graphes pipelinés sur des plate-formes avec communications homogènes. En particulier nous évaluons la complexité du problème bien connu ”chains-on-chains” pour les processeurs hétérogènes, un problème qui s’avère NP-difficile. Nous proposons plusieurs heuristiques bi-critères efficaces en temps polynomial. Leur performance relative est évaluée par des simulations intensives.


== Original document ==

The different versions of the original document can be found in:

* [http://arxiv.org/abs/0706.4009 http://arxiv.org/abs/0706.4009]

* [http://arxiv.org/pdf/0706.4009 http://arxiv.org/pdf/0706.4009]

* [https://hal.inria.fr/hal-00803514 https://hal.inria.fr/hal-00803514]

* [http://xplorestaging.ieee.org/ielx5/4623687/4629185/04629278.pdf?arnumber=4629278 http://xplorestaging.ieee.org/ielx5/4623687/4629185/04629278.pdf?arnumber=4629278],
: [http://dx.doi.org/10.1109/clustr.2007.4629278 http://dx.doi.org/10.1109/clustr.2007.4629278]

* [https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitRR07 https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitRR07],
: [http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004629278 http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004629278],
: [https://graal.ens-lyon.fr/~eagullo/GDT/slides/gdt_06_12_2007.pdf https://graal.ens-lyon.fr/~eagullo/GDT/slides/gdt_06_12_2007.pdf],
: [http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2007/RR2007-32.pdf http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2007/RR2007-32.pdf],
: [https://hal.inria.fr/inria-00156732 https://hal.inria.fr/inria-00156732],
: [https://www.scipedia.com/public/Benoit_et_al_2007a https://www.scipedia.com/public/Benoit_et_al_2007a],
: [https://academic.microsoft.com/#/detail/2116311243 https://academic.microsoft.com/#/detail/2116311243]

* [https://hal-lara.archives-ouvertes.fr/hal-02102603 https://hal-lara.archives-ouvertes.fr/hal-02102603],
: [https://hal-lara.archives-ouvertes.fr/hal-02102603/document https://hal-lara.archives-ouvertes.fr/hal-02102603/document],
: [https://hal-lara.archives-ouvertes.fr/hal-02102603/file/RR2007-32.pdf https://hal-lara.archives-ouvertes.fr/hal-02102603/file/RR2007-32.pdf]

* [https://hal.inria.fr/inria-00156732 https://hal.inria.fr/inria-00156732],
: [https://hal.inria.fr/inria-00156732v4/document https://hal.inria.fr/inria-00156732v4/document],
: [https://hal.inria.fr/inria-00156732v4/file/RR-6232.pdf https://hal.inria.fr/inria-00156732v4/file/RR-6232.pdf]