https://www.scipedia.com/wd/index.php?action=history&feed=atom&title=Benoit_Robert_2008a 2026-04-23T15:57:10Z Revision history for this page on the wiki MediaWiki 1.27.0-wmf.10 https://www.scipedia.com/wd/index.php?title=Benoit_Robert_2008a&diff=183462&oldid=prev 2021-01-22T10:37:06Z

<p></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='en'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 10:37, 22 January 2021</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >Line 3:</td> <td colspan="2" class="diff-lineno">Line 3:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Document type: Report</del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">== Full document ==</del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">&lt;pdf&gt;Media:Draft_Content_961462184-beopen148-9004-document.pdf&lt;/pdf&gt;</del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l22" >Line 22:</td> <td colspan="2" class="diff-lineno">Line 17:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [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</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [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],</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[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],</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* [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],[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],[http://lara.inist.fr/bitstream/handle/2332/1116/LIP-RR2007-12.pdf;sequence=1 http://lara.inist.fr/bitstream/handle/2332/1116/LIP-RR2007-12.pdf;sequence=1],[https://hal.inria.fr/inria-00175066v2 https://hal.inria.fr/inria-00175066v2],[https://academic.microsoft.com/#/detail/1977987382 https://academic.microsoft.com/#/detail/1977987382]</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4 http://link.springer.com/content/pdf/10.1007/s00453-008-9229-4],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[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</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [http://<del class="diffchange diffchange-inline">xplorestaging</del>.<del class="diffchange diffchange-inline">ieee</del>.<del class="diffchange diffchange-inline">org</del>/<del class="diffchange diffchange-inline">ielx5</del>/<del class="diffchange diffchange-inline">4623687</del>/<del class="diffchange diffchange-inline">4629185</del>/<del class="diffchange diffchange-inline">04629276</del>.pdf<del class="diffchange diffchange-inline">?arnumber=4629276 </del>http://<del class="diffchange diffchange-inline">xplorestaging</del>.<del class="diffchange diffchange-inline">ieee</del>.<del class="diffchange diffchange-inline">org</del>/<del class="diffchange diffchange-inline">ielx5</del>/<del class="diffchange diffchange-inline">4623687</del>/<del class="diffchange diffchange-inline">4629185</del>/<del class="diffchange diffchange-inline">04629276</del>.pdf<del class="diffchange diffchange-inline">?arnumber=4629276</del>],[http://<del class="diffchange diffchange-inline">dx</del>.<del class="diffchange diffchange-inline">doi</del>.<del class="diffchange diffchange-inline">org</del>/<del class="diffchange diffchange-inline">10</del>.<del class="diffchange diffchange-inline">1109</del>/<del class="diffchange diffchange-inline">clustr</del>.<del class="diffchange diffchange-inline">2007</del>.<del class="diffchange diffchange-inline">4629276 </del>http://<del class="diffchange diffchange-inline">dx</del>.<del class="diffchange diffchange-inline">doi</del>.<del class="diffchange diffchange-inline">org</del>/<del class="diffchange diffchange-inline">10</del>.<del class="diffchange diffchange-inline">1109</del>/<del class="diffchange diffchange-inline">clustr</del>.<del class="diffchange diffchange-inline">2007</del>.4629276]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [http://<ins class="diffchange diffchange-inline">www</ins>.<ins class="diffchange diffchange-inline">ens-lyon</ins>.<ins class="diffchange diffchange-inline">fr</ins>/<ins class="diffchange diffchange-inline">LIP</ins>/<ins class="diffchange diffchange-inline">Pub</ins>/<ins class="diffchange diffchange-inline">Rapports</ins>/<ins class="diffchange diffchange-inline">RR/RR2007/RR2007-12</ins>.pdf http://<ins class="diffchange diffchange-inline">www</ins>.<ins class="diffchange diffchange-inline">ens-lyon</ins>.<ins class="diffchange diffchange-inline">fr</ins>/<ins class="diffchange diffchange-inline">LIP</ins>/<ins class="diffchange diffchange-inline">Pub</ins>/<ins class="diffchange diffchange-inline">Rapports</ins>/<ins class="diffchange diffchange-inline">RR/RR2007/RR2007-12</ins>.pdf],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: [https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitR07 https://dblp.uni-trier.de/db/conf/cluster/cluster2007.html#BenoitR07],</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[http://<ins class="diffchange diffchange-inline">graal</ins>.<ins class="diffchange diffchange-inline">ens-lyon</ins>.<ins class="diffchange diffchange-inline">fr</ins>/<ins class="diffchange diffchange-inline">~lmarchal/scheduling/workflows-algorithmica</ins>.<ins class="diffchange diffchange-inline">pdf http:</ins>/<ins class="diffchange diffchange-inline">/graal</ins>.<ins class="diffchange diffchange-inline">ens-lyon</ins>.<ins class="diffchange diffchange-inline">fr/~lmarchal/scheduling/workflows-algorithmica.pdf],</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: [</ins>http://<ins class="diffchange diffchange-inline">yadda</ins>.<ins class="diffchange diffchange-inline">icm</ins>.<ins class="diffchange diffchange-inline">edu.pl</ins>/<ins class="diffchange diffchange-inline">yadda/element/bwmeta1</ins>.<ins class="diffchange diffchange-inline">element.ieee-000004629276 http:</ins>/<ins class="diffchange diffchange-inline">/yadda</ins>.<ins class="diffchange diffchange-inline">icm</ins>.<ins class="diffchange diffchange-inline">edu.pl/yadda/element/bwmeta1.element.ieee-000004629276],</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: [https://hal.inria.fr/hal-00803515 https://hal.inria.fr/hal-00803515],</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: [https://ieeexplore.ieee.org/document/</ins>4629276 <ins class="diffchange diffchange-inline">https://ieeexplore.ieee.org/document/4629276],</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: [https://academic.microsoft.com/#/detail/1977987382 https://academic.microsoft.com/#/detail/1977987382</ins>]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [<del class="diffchange diffchange-inline">https</del>://<del class="diffchange diffchange-inline">hal</del>.<del class="diffchange diffchange-inline">inria</del>.<del class="diffchange diffchange-inline">fr</del>/<del class="diffchange diffchange-inline">inria-00175066 https</del>://<del class="diffchange diffchange-inline">hal</del>.<del class="diffchange diffchange-inline">inria</del>.<del class="diffchange diffchange-inline">fr</del>/<del class="diffchange diffchange-inline">inria-00175066</del>],[<del class="diffchange diffchange-inline">https</del>://<del class="diffchange diffchange-inline">hal</del>.<del class="diffchange diffchange-inline">inria</del>.<del class="diffchange diffchange-inline">fr</del>/<del class="diffchange diffchange-inline">inria-00175066</del>/<del class="diffchange diffchange-inline">document https</del>://<del class="diffchange diffchange-inline">hal</del>.<del class="diffchange diffchange-inline">inria</del>.<del class="diffchange diffchange-inline">fr</del>/<del class="diffchange diffchange-inline">inria-00175066</del>/<del class="diffchange diffchange-inline">document</del>]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [<ins class="diffchange diffchange-inline">http</ins>://<ins class="diffchange diffchange-inline">xplorestaging</ins>.<ins class="diffchange diffchange-inline">ieee</ins>.<ins class="diffchange diffchange-inline">org</ins>/<ins class="diffchange diffchange-inline">ielx5/4623687/4629185/04629276.pdf?arnumber=4629276 http</ins>://<ins class="diffchange diffchange-inline">xplorestaging</ins>.<ins class="diffchange diffchange-inline">ieee</ins>.<ins class="diffchange diffchange-inline">org</ins>/<ins class="diffchange diffchange-inline">ielx5/4623687/4629185/04629276.pdf?arnumber=4629276</ins>],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[<ins class="diffchange diffchange-inline">http</ins>://<ins class="diffchange diffchange-inline">dx</ins>.<ins class="diffchange diffchange-inline">doi</ins>.<ins class="diffchange diffchange-inline">org</ins>/<ins class="diffchange diffchange-inline">10.1109</ins>/<ins class="diffchange diffchange-inline">clustr.2007.4629276 http</ins>://<ins class="diffchange diffchange-inline">dx</ins>.<ins class="diffchange diffchange-inline">doi</ins>.<ins class="diffchange diffchange-inline">org</ins>/<ins class="diffchange diffchange-inline">10.1109</ins>/<ins class="diffchange diffchange-inline">clustr.2007.4629276</ins>]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [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-<del class="diffchange diffchange-inline">00175066</del>/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-<del class="diffchange diffchange-inline">00175066</del>/file/RR-INRIA-6308.pdf]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [https://hal.inria.fr/inria-00175066 https://hal.inria.fr/inria-00175066],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[https://hal.inria.fr/inria-00175066v2/document https://hal.inria.fr/inria-00175066v2/document],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[https://hal.inria.fr/inria-<ins class="diffchange diffchange-inline">00175066v2</ins>/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-<ins class="diffchange diffchange-inline">00175066v2</ins>/file/RR-INRIA-6308.pdf]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [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]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [https://link.springer.com/article/10.1007/s00453-008-9229-4 https://link.springer.com/article/10.1007/s00453-008-9229-4],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: [https://dblp.uni-trier.de/db/journals/algorithmica/algorithmica57.html#BenoitR10 https://dblp.uni-trier.de/db/journals/algorithmica/algorithmica57.html#BenoitR10],</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[https://hal.inria.fr/hal-00980695 https://hal.inria.fr/hal-00980695],</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">: </ins>[https://academic.microsoft.com/#/detail/2153441708 https://academic.microsoft.com/#/detail/2153441708]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>DOIS: 10.1007/s00453-008-9229-4 10.1109/clustr.2007.4629276</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>DOIS: 10.1007/s00453-008-9229-4 10.1109/clustr.2007.4629276</div></td></tr> <!-- diff cache key mw_drafts_scipedia-sc_mwd_:diff:version:1.11a:oldid:177147:newid:183462 --> </table>

Scipediacontent https://www.scipedia.com/wd/index.php?title=Benoit_Robert_2008a&diff=177147&oldid=prev 2020-10-26T09:14:47Z

<p>Scipediacontent moved page <a href="/public/Draft_Content_961462184" class="mw-redirect" title="Draft Content 961462184">Draft Content 961462184</a> to <a href="/public/Benoit_Robert_2008a" title="Benoit Robert 2008a">Benoit Robert 2008a</a></p> <table class="diff diff-contentalign-left" data-mw="interface"> <tr style='vertical-align: top;' lang='en'> <td colspan='1' style="background-color: white; color:black; text-align: center;">← Older revision</td> <td colspan='1' style="background-color: white; color:black; text-align: center;">Revision as of 09:14, 26 October 2020</td> </tr><tr><td colspan='2' style='text-align: center;' lang='en'><div class="mw-diff-empty">(No difference)</div> </td></tr></table>

Scipediacontent https://www.scipedia.com/wd/index.php?title=Benoit_Robert_2008a&diff=177146&oldid=prev 2020-10-26T09:14:45Z

<p>Created page with &quot; == Abstract == International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork g...&quot;</p> <p><b>New page</b></p><div><br /> == Abstract ==<br /> <br /> 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.<br /> <br /> Document type: Report<br /> <br /> == Full document ==<br /> &lt;pdf&gt;Media:Draft_Content_961462184-beopen148-9004-document.pdf&lt;/pdf&gt;<br /> <br /> <br /> == Original document ==<br /> <br /> The different versions of the original document can be found in:<br /> <br /> * [http://graal.ens-lyon.fr/%7Elmarchal/scheduling/workflows-algorithmica.pdf http://graal.ens-lyon.fr/%7Elmarchal/scheduling/workflows-algorithmica.pdf]<br /> <br /> * [https://hal.inria.fr/hal-00803515 https://hal.inria.fr/hal-00803515]<br /> <br /> * [https://hal.inria.fr/hal-00980695 https://hal.inria.fr/hal-00980695]<br /> <br /> * [https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf]<br /> <br /> * [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<br /> <br /> * [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],[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],[http://lara.inist.fr/bitstream/handle/2332/1116/LIP-RR2007-12.pdf;sequence=1 http://lara.inist.fr/bitstream/handle/2332/1116/LIP-RR2007-12.pdf;sequence=1],[https://hal.inria.fr/inria-00175066v2 https://hal.inria.fr/inria-00175066v2],[https://academic.microsoft.com/#/detail/1977987382 https://academic.microsoft.com/#/detail/1977987382]<br /> <br /> * [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]<br /> <br /> * [https://hal.inria.fr/inria-00175066 https://hal.inria.fr/inria-00175066],[https://hal.inria.fr/inria-00175066/document https://hal.inria.fr/inria-00175066/document]<br /> <br /> * [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-00175066/file/RR-INRIA-6308.pdf https://hal.inria.fr/inria-00175066/file/RR-INRIA-6308.pdf]<br /> <br /> * [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]<br /> <br /> <br /> <br /> DOIS: 10.1007/s00453-008-9229-4 10.1109/clustr.2007.4629276</div>

Scipediacontent