TY - GEN
T1 - Optimal broadcast and summation in the LogP model
AU - Karp, Richard M.
AU - Sahay, Abbijit
AU - Santos, Eunice E.
AU - Schauser, Klaus Erik
N1 - Funding Information:
We thank Amotz Bar-Noy, Shlomo Kipnis and Ramesh Subramo-nian for valuable discussions. Computational support was provided by the NSF Infrastructure Grant number CDA-S722788. Richard Karp and Abhijit Sahay are supported by NSF/DARPA Grant CCR-9005448. Eunice Santos is supported by a DOD-NDSEG Graduate Fellowship. KIaus Erik Schauseris suppotted by an IBM Graduate Fellowship.
Publisher Copyright:
© 1993 ACM.
PY - 1993/8/1
Y1 - 1993/8/1
N2 - In many distributed-memory parallel computers the only built-in communication primitive is point-to-point message transmission, and more powerful operations such as broadcast and synchronization must be realized using this primitive. Within the LogP model of parallel computation we present algorithms that yield optimal communication schedules for several broadcast and synchronization operations. Most of our algorithms are the absolutely best possible in that not even the constant factors can be improved upon. For one particular broadcast problem, called continuous broadcast, the optimaliry of our algorithm is not yet completely proven, although proofs have been achieved for a certain range of parameters. We also devise an optimal algorithm for summing or, more generally, applying a non-commutative associative binary operator to a set of operands.
AB - In many distributed-memory parallel computers the only built-in communication primitive is point-to-point message transmission, and more powerful operations such as broadcast and synchronization must be realized using this primitive. Within the LogP model of parallel computation we present algorithms that yield optimal communication schedules for several broadcast and synchronization operations. Most of our algorithms are the absolutely best possible in that not even the constant factors can be improved upon. For one particular broadcast problem, called continuous broadcast, the optimaliry of our algorithm is not yet completely proven, although proofs have been achieved for a certain range of parameters. We also devise an optimal algorithm for summing or, more generally, applying a non-commutative associative binary operator to a set of operands.
UR - http://www.scopus.com/inward/record.url?scp=85031726860&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031726860&partnerID=8YFLogxK
U2 - 10.1145/165231.165250
DO - 10.1145/165231.165250
M3 - Conference contribution
AN - SCOPUS:85031726860
T3 - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
SP - 142
EP - 153
BT - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
PB - Association for Computing Machinery, Inc
T2 - 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Y2 - 30 June 1993 through 2 July 1993
ER -