Broadcasting on linear arrays and meshes
TN (United States) Oak Ridge National Lab., S. Seidel, USDOE, Washington, DC (United States), National Aeronautics and Space Administration, Washington, DC (United States) · 1993
The well known spanning binomial tree broadcast algorithm is generalized to obtain several new broadcast algorithms for linear arrays and meshes. These generalizations take advantage of bidirectional communication, the connectivity of two-dimensional meshes, and the difference between node-to-network and network-to-network bandwidth. It is shown how these algorithms can be further generalized so that any node can be the source of the broadcast message. A partitioning scheme is given that allows these algorithms to be used on linear arrays and meshes of any size. One of these algorithms, the bidirectional spanning tree broadcast, always has lower cost than the recursive halving broadcast for linear arrays. All of these algorithms offer significant performance improvements over the basic spanning tree broadcast. These algorithms do not rely on a knowledge of machine dependent constants for network bandwidth and latency, so their performance is not as sensitive to changes in machine characteristics as that of hybrid and pipelined algorithms. Performance measurements are given for some of these broadcast algorithms on the Intel Delta mesh.