ALCOMFT-TR-01-173

Peter Sanders and Jop Sibeyn
A Bandwidth Latency Tradeoff for Broadcast and Reduction
MPI. Work packages 1 and 2. August 2001.

Abstract: The ``fractional tree'' algorithm for broadcasting and reduction is introduced. Its communication pattern interpolates between two well known patterns - sequential pipeline and pipelined binary tree. The speedup over the best of these simple methods can approach two for large systems and messages of intermediate size. For networks which are not very densely connected the new algorithm seems to be the best known method for the important case that each processor has only a single (possibly bidirectional) channel into the communication network.

Postscript file: ALCOMFT-TR-01-173.ps.gz (104 kb).