On the Efficiency of Global Combine Algorithms for 2-D Meshes With WormholeRouting
Michael Barnett, R.J. Littlefield, David G. Payne, Robert A. Geijn · 1993
The problem of performing a global combine (summation) operation on distributed memory computers using a two-dimensional mesh interconnect with wormhole routing is considered. We present algorithms that are asymptotically optimal for short vectors (O(log(p)) for p processing nodes) and for long vecstors (O(n) for n data elements per node), as well as hybrid algorithms that are superior for intermediate n. The algorithms are analyzed using detailed performance models that include the effects of link conflicts and other characteristics of the underlying communication system. The models are validated using experimental data from the Intel Touchstone DELTA computer. We show that while no one algorithm is optimal, each of the presented algorithms is superior under some circumstances.