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
http://dx.doi.org/10.1109/clustr.2007.4629276
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

Document Score

0

Views 0
Recommendations 0

Share this document

claim authorship

Are you one of the authors of this document?