(Created page with " == Abstract == Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagoni...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
== Abstract == | == 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.; | + | 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. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| Line 20: | Line 15: | ||
* [https://hal.inria.fr/hal-00803514 https://hal.inria.fr/hal-00803514] | * [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 | + | * [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:// | + | * [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. | + | * [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- | + | * [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] | ||
Latest revision as of 19:35, 25 January 2021
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://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004629278,
- 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,
- https://hal.inria.fr/inria-00156732,
- https://www.scipedia.com/public/Benoit_et_al_2007a,
- https://academic.microsoft.com/#/detail/2116311243
Back to Top
Document information
Published on 01/01/2007
Volume 2007, 2007
DOI: 10.1109/CLUSTR.2007.4629278
Licence: CC BY-NC-SA license
Share this document
Keywords
Algorithmic skeleton • Computational complexity theory • Computer science • Distributed computing • Graph theory • Parallel computing • Pipeline transport • Scheduling (computing) • Throughput • Workflow • [ INFO.INFO-DC ] Computer Science [cs]/Distributed • Parallel • And Cluster Computing [cs.DC] • [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
claim authorship
Are you one of the authors of this document?