{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T05:46:25Z","timestamp":1740980785039,"version":"3.38.0"},"reference-count":30,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2009,5]]},"abstract":"<jats:p> 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). A typical application class is digital image coding, where images are processed in steady-state mode. In this paper, we study the general bi-criteria mapping problem (minimizing period and latency) for pipeline graphs on communication homogeneous platforms. We present an integer linear programming formulation for this NP-hard problem. Furthermore, we provide several efficient polynomial bi-criteria heuristics, whose relative performance is evaluated through extensive simulations. As a case study, we provide simulations and MPI experimental results for the JPEG encoder application pipeline on a cluster of workstations. <\/jats:p>","DOI":"10.1177\/1094342009104009","type":"journal-article","created":{"date-parts":[[2009,5,20]],"date-time":"2009-05-20T11:53:06Z","timestamp":1242820386000},"page":"171-187","source":"Crossref","is-referenced-by-count":5,"title":["Multi-Criteria Scheduling of Pipeline Workflows (and Application To the JPEG Encoder)"],"prefix":"10.1177","volume":"23","author":[{"given":"Anne","family":"Benoit","sequence":"first","affiliation":[{"name":"LIP, ENS LYON, 69364 LYON CEDEX 07, FRANCE"}]},{"given":"Harald","family":"Kosch","sequence":"additional","affiliation":[{"name":"UNIVERSITY OF PASSAU, 94032 PASSAU, GERMANY"}]},{"given":"Veronika","family":"Rehn-Sonigo","sequence":"additional","affiliation":[{"name":"LIP, ENS LYON, 69364 LYON CEDEX 07, FRANCE"}]},{"given":"Yves","family":"Robert","sequence":"additional","affiliation":[{"name":"LIP, ENS LYON, 69364 LYON CEDEX 07, FRANCE ,"}]}],"member":"179","published-online":{"date-parts":[[2009,5,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.microrel.2003.10.016"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/ISPDC.2004.12"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.11.004"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2007.4629278"},{"volume-title":"ICCS'2008, the 8th International Conference on Computational Science, LNCS","author":"Benoit, A.","key":"atypb5"},{"volume-title":"phOn the complexity of mapping linear chain applications onto heterogeneous platforms. Research Report 2008-32, LIP laboratory","year":"2008","author":"Benoit, A.","key":"atypb6"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(01)00070-X"},{"volume-title":"Proceedings of the 3rd Annual International Workshop on Active Middleware Services (AMS'01)","author":"Beynon, M.","key":"atypb8"},{"volume-title":"ICDCS'99 19th International Conference on Distributed Computing Systems","author":"Bhat, P.","key":"atypb9"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(03)00008-X"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2003.12.002"},{"key":"atypb12","first-page":"379","volume":"10","author":"Falkemeier, J.","year":"1995","journal-title":"methods and applications"},{"volume-title":"In 17th International Conference on Pattern Recognition (ICPR'04)","author":"Ferretti, M.","key":"atypb13"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Kumaki, T., Ishizaki, M., Koide, T., Mattausch, H.J., Kuroda, Y., Noda, H., Dosaka, K., Arimoto, K., and Saito, K. (2007). Acceleration of DCT processing with massive-parallel memory-embedded SIMD matrix processor, IEICE Transactions on Information and Systems, E90-D(8): 1312-1315.","DOI":"10.1093\/ietisy\/e90-d.8.1312"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2002.1015469"},{"volume-title":"IEEE Conf. Proceeding","author":"Monnes, P.","key":"atypb16"},{"key":"atypb17","first-page":"159","author":"Papadonikolakis, M.","year":"2007","journal-title":"Automation and Test in Europe (DATE2007)"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.05.003"},{"volume-title":"Patterns and skeletons for parallel and distributed computing","year":"2002","author":"Rabhi, F.","key":"atypb19"},{"volume-title":"Proceedings of Euro-Par 2004: Parallel Processing, LNCS","author":"Saif, T.","key":"atypb20"},{"key":"atypb21","first-page":"140","volume":"35","author":"Shee, S.L.","year":"2007","journal-title":"International Journal of Parallel Programming"},{"volume-title":"Proc. of SPIE Conference on Image and Video Compression","author":"Shen, K.","key":"atypb22"},{"volume-title":"Scheduling and load balancing in parallel and distributed systems","year":"1995","author":"Shirazi, B.A.","key":"atypb23"},{"volume-title":"2002 ACM\/IEEE Supercomputing Conference","author":"Spencer, M.","key":"atypb24"},{"volume-title":"Proc. 5th ACM SIGP-LAN Symposium on Principles and Practice of Parallel Programming, PPoPP'95","author":"Subhlok, J.","key":"atypb25"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237508"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/HCW.2000.843736"},{"volume-title":"An approach for optimizing latency under throughput constraints for application workflows on clusters","year":"2007","author":"Vydyanathan, N.","key":"atypb28"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/103085.103089"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093941"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342009104009","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342009104009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T16:28:53Z","timestamp":1740932933000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342009104009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.1177\/1094342009104009"],"URL":"https:\/\/doi.org\/10.1177\/1094342009104009","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2009,5]]}}}