(Created page with " == Abstract == International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork g...") |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork graphs. Several antagonist criteria should be optimized for workflow applications, such as throughput and latency (or a combination). In this paper, we consider a simplified model with no communication cost, and we provide an exhaustive list of complexity results for different problem instances. Pipeline or fork stages can be replicated in order to increase the throughput by sending consecutive data sets onto different processors. In some cases, stages can also be data-parallelized, i.e. the computation of one single data set is shared between several processors. This leads to a decrease of the latency and an increase of the throughput. Some instances of this simple model are shown to be NP-hard, thereby exposing the inherent complexity of the mapping problem. We provide polynomial algorithms for other problem instances. Altogether, we provide solid theoretical foundations for the study of mono-criterion or bi-criteria mapping optimization problems. | International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork graphs. Several antagonist criteria should be optimized for workflow applications, such as throughput and latency (or a combination). In this paper, we consider a simplified model with no communication cost, and we provide an exhaustive list of complexity results for different problem instances. Pipeline or fork stages can be replicated in order to increase the throughput by sending consecutive data sets onto different processors. In some cases, stages can also be data-parallelized, i.e. the computation of one single data set is shared between several processors. This leads to a decrease of the latency and an increase of the throughput. Some instances of this simple model are shown to be NP-hard, thereby exposing the inherent complexity of the mapping problem. We provide polynomial algorithms for other problem instances. Altogether, we provide solid theoretical foundations for the study of mono-criterion or bi-criteria mapping optimization problems. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| Line 22: | Line 17: | ||
* [https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf] | * [https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf] | ||
| − | * [http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4.pdf http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4.pdf],[http://link.springer.com/article/10.1007/s00453-008-9229-4/fulltext.html http://link.springer.com/article/10.1007/s00453-008-9229-4/fulltext.html],[http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4 http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4],[http://dx.doi.org/10.1007/s00453-008-9229-4 http://dx.doi.org/10.1007/s00453-008-9229-4] under the license http://www.springer.com/tdm | + | * [http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4.pdf http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4.pdf], |
| − | + | : [http://link.springer.com/article/10.1007/s00453-008-9229-4/fulltext.html http://link.springer.com/article/10.1007/s00453-008-9229-4/fulltext.html], | |
| − | + | : [http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4 http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4], | |
| + | : [http://dx.doi.org/10.1007/s00453-008-9229-4 http://dx.doi.org/10.1007/s00453-008-9229-4] under the license http://www.springer.com/tdm | ||
| − | * [http:// | + | * [http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2007/RR2007-12.pdf http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2007/RR2007-12.pdf], |
| + | : [https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitR07 https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitR07], | ||
| + | : [http://graal.ens-lyon.fr/~lmarchal/scheduling/workflows-algorithmica.pdf http://graal.ens-lyon.fr/~lmarchal/scheduling/workflows-algorithmica.pdf], | ||
| + | : [http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004629276 http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004629276], | ||
| + | : [https://hal.inria.fr/hal-00803515 https://hal.inria.fr/hal-00803515], | ||
| + | : [https://ieeexplore.ieee.org/document/4629276 https://ieeexplore.ieee.org/document/4629276], | ||
| + | : [https://academic.microsoft.com/#/detail/1977987382 https://academic.microsoft.com/#/detail/1977987382] | ||
| − | * [ | + | * [http://xplorestaging.ieee.org/ielx5/4623687/4629185/04629276.pdf?arnumber=4629276 http://xplorestaging.ieee.org/ielx5/4623687/4629185/04629276.pdf?arnumber=4629276], |
| + | : [http://dx.doi.org/10.1109/clustr.2007.4629276 http://dx.doi.org/10.1109/clustr.2007.4629276] | ||
| − | * [https://hal.inria.fr/inria-00175066 https://hal.inria.fr/inria-00175066],[https://hal.inria.fr/inria-00175066v2/document https://hal.inria.fr/inria-00175066v2/document],[https://hal.inria.fr/inria- | + | * [https://hal.inria.fr/inria-00175066 https://hal.inria.fr/inria-00175066], |
| + | : [https://hal.inria.fr/inria-00175066v2/document https://hal.inria.fr/inria-00175066v2/document], | ||
| + | : [https://hal.inria.fr/inria-00175066v2/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066v2/file/RR-INRIA-6308.pdf] | ||
| − | * [https://link.springer.com/article/10.1007/s00453-008-9229-4 https://link.springer.com/article/10.1007/s00453-008-9229-4],[https://hal.inria.fr/hal-00980695 https://hal.inria.fr/hal-00980695],[https://academic.microsoft.com/#/detail/2153441708 https://academic.microsoft.com/#/detail/2153441708] | + | * [https://link.springer.com/article/10.1007/s00453-008-9229-4 https://link.springer.com/article/10.1007/s00453-008-9229-4], |
| + | : [https://dblp.uni-trier.de/db/journals/algorithmica/algorithmica57.html#BenoitR10 https://dblp.uni-trier.de/db/journals/algorithmica/algorithmica57.html#BenoitR10], | ||
| + | : [https://hal.inria.fr/hal-00980695 https://hal.inria.fr/hal-00980695], | ||
| + | : [https://academic.microsoft.com/#/detail/2153441708 https://academic.microsoft.com/#/detail/2153441708] | ||
DOIS: 10.1007/s00453-008-9229-4 10.1109/clustr.2007.4629276 | DOIS: 10.1007/s00453-008-9229-4 10.1109/clustr.2007.4629276 | ||
Latest revision as of 11:37, 22 January 2021
Abstract
International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork graphs. Several antagonist criteria should be optimized for workflow applications, such as throughput and latency (or a combination). In this paper, we consider a simplified model with no communication cost, and we provide an exhaustive list of complexity results for different problem instances. Pipeline or fork stages can be replicated in order to increase the throughput by sending consecutive data sets onto different processors. In some cases, stages can also be data-parallelized, i.e. the computation of one single data set is shared between several processors. This leads to a decrease of the latency and an increase of the throughput. Some instances of this simple model are shown to be NP-hard, thereby exposing the inherent complexity of the mapping problem. We provide polynomial algorithms for other problem instances. Altogether, we provide solid theoretical foundations for the study of mono-criterion or bi-criteria mapping optimization problems.
Original document
The different versions of the original document can be found in:
- http://link.springer.com/article/10.1007/s00453-008-9229-4/fulltext.html,
- http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4,
- http://dx.doi.org/10.1007/s00453-008-9229-4 under the license http://www.springer.com/tdm
- https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitR07,
- http://graal.ens-lyon.fr/~lmarchal/scheduling/workflows-algorithmica.pdf,
- http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004629276,
- https://hal.inria.fr/hal-00803515,
- https://ieeexplore.ieee.org/document/4629276,
- https://academic.microsoft.com/#/detail/1977987382
- https://hal.inria.fr/inria-00175066v2/document,
- https://hal.inria.fr/inria-00175066v2/file/RR-INRIA-6308.pdf
- https://dblp.uni-trier.de/db/journals/algorithmica/algorithmica57.html#BenoitR10,
- https://hal.inria.fr/hal-00980695,
- https://academic.microsoft.com/#/detail/2153441708
DOIS: 10.1007/s00453-008-9229-4 10.1109/clustr.2007.4629276
Back to Top
Document information
Published on 01/01/2008
Volume 2008, 2008
DOI: 10.1007/s00453-008-9229-4
Licence: Other
Share this document
Keywords
Applied Mathematics • Computation • Computational complexity theory • Computer Science Applications • Computer science • Distributed computing • Fork (system call) • General Computer Science • Latency (engineering) • Optimization problem • Parallel computing • Pipeline transport • Scheduling (computing) • Theory of computation • Throughput • Workflow
claim authorship
Are you one of the authors of this document?