UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-92-721.pdf
CSD-92-721.ps
Oskicat catalog record
Conditions of Use

Archive Home Page

Optimal Broadcast and Summation in the LogP Model

Authors:
Karp, Richard
Sahay, Abhijit
Santos, Eunice
Technical Report Identifier: CSD-92-721
November 1992
CSD-92-721.pdf
CSD-92-721.ps

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.