# Optimal Broadcast and Summation in the LogP Model

### Richard Karp, Abhijit Sahay and Eunice Santos

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-92-721

November 1992

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-721.pdf

We consider several natural broadcasting problems for the LogP model of distributed memory machines recently proposed by Culler et al. For each of these problems, we present algorithms that yield an optimal communication schedule. Our algorithms are absolutely best possible in that not even the constant factors can be improved upon. We also devise an (absolutely) optimal algorithm for summing a list of elements (using a non-commutative operation) using one of the optimal broadcast algorithms.

BibTeX citation:

@techreport{Karp:CSD-92-721, Author = {Karp, Richard and Sahay, Abhijit and Santos, Eunice}, Title = {Optimal Broadcast and Summation in the LogP Model}, Institution = {EECS Department, University of California, Berkeley}, Year = {1992}, Month = {Nov}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6032.html}, Number = {UCB/CSD-92-721}, Abstract = {We consider several natural broadcasting problems for the LogP model of distributed memory machines recently proposed by Culler et al. For each of these problems, we present algorithms that yield an optimal communication schedule. Our algorithms are absolutely best possible in that not even the constant factors can be improved upon. We also devise an (absolutely) optimal algorithm for summing a list of elements (using a non-commutative operation) using one of the optimal broadcast algorithms.} }

EndNote citation:

%0 Report %A Karp, Richard %A Sahay, Abhijit %A Santos, Eunice %T Optimal Broadcast and Summation in the LogP Model %I EECS Department, University of California, Berkeley %D 1992 %@ UCB/CSD-92-721 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6032.html %F Karp:CSD-92-721