Date Added: Jan 2010
This paper develops an all-to-all broadcast scheme that achieves maximum bandwidth efficiency for clusters with tree topologies. Using the scheme for clusters with cut-through switches, any tree topology can support all-to-all broadcast as efficiently as a single switch connecting all machines when the message size is sufficiently large. Since a tree topology can be embedded in almost any connected network, it follows that efficient all-to-all broadcast can be achieved in almost all topologies, regular or irregular. To perform all-to-all broadcast efficiently on clusters with store-and-forward switches, the algorithm must minimize the communication path lengths in addition to maximizing bandwidth efficiency.