Optimal broadcast and summation in the LogP model
Richard M. Karp, Abhijit Sahay, Eunice E. Santos, Klaus Erik Schauser · 1993
In many distributed-memory parallel computers the only built-in communication primitive is point-to-point message transmission, and more powerful operations suchas broadcast and synchronization must be realized using this primitive. Within the LogP model of parallel computation we present algorithms that yield optimal communication schedulesfor several broadcastand 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 optimality 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. 1 Introduction Most models of parallel computation reflect the communication bottlenecks of real parallel machines inadequately. The PRAM [11],...