{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:58:21Z","timestamp":1777676301365,"version":"3.51.4"},"reference-count":30,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2006,2,1]],"date-time":"2006-02-01T00:00:00Z","timestamp":1138752000000},"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":[[2006,2]]},"abstract":"<jats:p>In this paper, we consider the communications involved in the execution of a complex application, deployed on a heterogeneous platform. Such applications extensively use macro-communication schemes, for example to broadcast data items, either to all resources (broadcast) or to a restricted set of targets (multicast). Rather than aiming at minimizing the execution time of a single collective communication, we focus on the steady-state operation. We assume that there is a large number of messages to be broadcast or multicast in pipelined fashion, and we aim at maximizing the throughput, i.e. the (rational) number of messages which can be broadcast or multicast every timestep. We target heterogeneous platforms, modeled by a graph where resources have different communication and computation speeds. Achieving the best throughput may well require that the target platform is used in totality: different messages may need to be transferred along different paths.<\/jats:p>\n                  <jats:p>The main focus of the paper is on complexity results. We aim at presenting a unified framework for analyzing the complexity of collective communication schemes. We concentrate on the classification (whether maximizing the throughput is a polynomial or NP-hard problem), rather than actually providing efficient polynomial algorithms (when such algorithms are known, we refer to bibliographical pointers).<\/jats:p>","DOI":"10.1177\/1094342006061877","type":"journal-article","created":{"date-parts":[[2006,2,2]],"date-time":"2006-02-02T06:48:09Z","timestamp":1138862889000},"page":"5-17","source":"Crossref","is-referenced-by-count":0,"title":["Complexity Results for Collective Communications on Heterogeneous Platforms"],"prefix":"10.1177","volume":"20","author":[{"given":"O.","family":"Beaumont","sequence":"first","affiliation":[{"name":"LABRI, UMR CNRS 5800 BORDEAUX, FRANCE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Marchal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Robert","sequence":"additional","affiliation":[{"name":"LIP, UMR CNRS-INRIA 5668 ENS LYON, FRANCE"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2006,2,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963414"},{"key":"atypb2","volume-title":"Pipelining broadcasts on heterogeneous platforms under the one-port model","author":"Beaumont, O.","year":"2004"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2004.1327931"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/ISPDC.2004.12"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2005.48"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/71.706050"},{"key":"atypb7","volume-title":"Introduction to Algorithms","author":"Cormen, T. H.","year":"1990"},{"key":"atypb8","volume-title":"Successive broadcasts on Hypercube","author":"Desprez, F.","year":"1993"},{"key":"atypb9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey, M. R.","year":"1979"},{"key":"atypb10","first-page":"563","volume-title":"22nd International Conference on Distributed Computing Systems (ICDCS\u201902)","author":"Gopalsamy, T."},{"key":"atypb11","volume-title":"Geometric Algorithm and Combinatorial Optimization. Algorithms and Combinatorics 2","author":"Gr\u00f6tschel, M.","year":"1994","edition":"2"},{"key":"atypb12","first-page":"193","volume-title":"Scheduling Theory and its Applications","author":"Hanen, C.","year":"1995"},{"key":"atypb13","volume-title":"Scalable Parallel Computing","author":"Hwang, K.","year":"1998"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/12.29465"},{"key":"atypb15","first-page":"191","volume":"20","author":"Khachiyan, L. G.","year":"1979","journal-title":"Soviet Mathematikcs Doklady"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/71.841741"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1983.1095818"},{"key":"atypb18","volume-title":"Introduction to Parallel Computing","author":"Kumar, V.","year":"1994"},{"key":"atypb19","volume-title":"Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms","author":"Legrand, A.","year":"2003"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/71.246072"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/71.642946"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/71.473513"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/71.926170"},{"key":"atypb24","volume-title":"MPI: The Complete Reference","author":"Snir, M.","year":"1996"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/71.744837"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/12.841128"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626495000266"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2002.1081754"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/71.895793"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342006061877","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342006061877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:18:22Z","timestamp":1777450702000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342006061877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,2]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["10.1177\/1094342006061877"],"URL":"https:\/\/doi.org\/10.1177\/1094342006061877","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,2]]}}}