{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T06:03:31Z","timestamp":1740895411332,"version":"3.38.0"},"reference-count":32,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2011,7,7]],"date-time":"2011-07-07T00:00:00Z","timestamp":1309996800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p> In this paper, we study the problem of finding optimal mappings for several independent but concurrent workflow applications, in order to optimize performance-related criteria together with energy consumption. Each application consists of a linear chain graph with several stages, and processes successive data sets in pipeline mode, from the first to the last stage. The problem is to decide which processors to enroll, at which speed (or mode) to use them, and which stages they should execute. There is a clear trade-off to reach, since running faster and\/or more processors leads to better performance, but energy consumption is then very high. Energy savings can be achieved at the price of a lower performance, by reducing processor speeds or enrolling fewer resources. We study the problem complexity on different target execution platforms, ranking from fully homogeneous platforms to fully heterogeneous ones. We consider three mapping strategies: (i) one-to-one mappings, where a processor is assigned a single stage; (ii) interval mappings, where a processor may process an interval of consecutive stages of the same application; and (iii) general mappings, which are fully arbitrary, i.e. a processor may process stages of several distinct applications. Finally, we compare two different models for the computation of the latency, which is the time elapsed between the beginning and the end of the execution of a given data set: with the PATH model, it is computed as the length of the path taken by this data set, while with the WAVEFRONT model, each data set progresses concurrently within a period. For all platform types, all mapping strategies and both latency models, we establish the complexity of several multi-criteria optimization problems, whose objective functions combine period, latency and energy criteria. In particular, we exhibit instances where the problem is NP-hard with concurrent applications, while it can be solved in polynomial time for a single application, and instances whose problem complexity depends upon the latency model. <\/jats:p>","DOI":"10.1177\/1094342011414742","type":"journal-article","created":{"date-parts":[[2011,7,8]],"date-time":"2011-07-08T14:03:30Z","timestamp":1310133810000},"page":"261-273","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Models and complexity results for performance and energy optimization of concurrent streaming applications"],"prefix":"10.1177","volume":"25","author":[{"given":"Anne","family":"Benoit","sequence":"first","affiliation":[{"name":"LIP, Ecole Normale Sup\u00e9rieure de Lyon, France,"}]},{"given":"Paul","family":"Renaud-Goud","sequence":"additional","affiliation":[{"name":"LIP, Ecole Normale Sup\u00e9rieure de Lyon, France"}]},{"given":"Yves","family":"Robert","sequence":"additional","affiliation":[{"name":"LIP, Ecole Normale Sup\u00e9rieure de Lyon, France"}]}],"member":"179","published-online":{"date-parts":[[2011,7,7]]},"reference":[{"volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS)","author":"Agrawal K.","key":"atypb1"},{"volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE)","author":"Andrei A.","key":"atypb2"},{"volume-title":"Proceedings of SODA\u201998","author":"Bender MA","key":"atypb3"},{"key":"atypb4","volume":"27","author":"Benoit A.","year":"2009","journal-title":"Research Report"},{"journal-title":"Research Report 2010-05","year":"2010","author":"Benoit A.","key":"atypb5"},{"key":"atypb6","volume":"7589","author":"Benoit A.","year":"2011","journal-title":"Research Report"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.11.004"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9229-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626409000298"},{"volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Bunde DP","key":"atypb10"},{"volume-title":"Proceedings of International Conference on Parallel and Distributed Systems (ICPADS)","author":"Chen J-J.","key":"atypb11"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.41"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2003.12.002"},{"volume-title":"Proceedings of the Asia South Pacific Design Automation Conference (ASPDAC)","author":"Gruian F.","key":"atypb14"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/71.790601"},{"volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS)","author":"Hotta Y.","key":"atypb16"},{"volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS)","author":"Huang T-Y.","key":"atypb17"},{"volume-title":"Proceedings of International Symposium on Low Power Electronics and Design (ISLPED)","author":"Ishihara T.","key":"atypb18"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(03)00002-9"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-008-0176-8"},{"journal-title":"Environment and Climate News","year":"1999","author":"Mills MP","key":"atypb21"},{"volume-title":"Patterns and Skeletons for Parallel and Distributed Computing","year":"2002","author":"Rabhi F.","key":"atypb22"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209951"},{"volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Subhlok J.","key":"atypb24"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/HCW.2000.843736"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD)","author":"Varatkar G.","key":"atypb26"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74466-5_20"},{"volume-title":"Proceedings of International Conference on Parallel Processing (ICPP)","author":"Vydyanathan N.","key":"atypb28"},{"key":"atypb29","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1109\/TC.2007.70777","volume":"57","author":"Wu Q.","year":"2008","journal-title":"IEEE Transactions on Computers"},{"volume-title":"Proceedings of International Conference on Parallel and Distributed Systems (ICPADS)","author":"Wu Q.","key":"atypb30"},{"volume-title":"Proceedings of the ACM International Conference on Embedded Software (EMSOFT)","author":"Xu R.","key":"atypb31"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1314299.1314300"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342011414742","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342011414742","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T00:14:58Z","timestamp":1740874498000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342011414742"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,7]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1177\/1094342011414742"],"URL":"https:\/\/doi.org\/10.1177\/1094342011414742","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2011,7,7]]}}}