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 -