Practical, distributed, low overhead algorithms for irregular gather and scatter collectives

We present new, simple, fully distributed, practical algorithms with linear time communication costs for irregular gather and scatter operations in which processors contribute or consume possibly different amounts of data to or from a chosen root processor. The algorithms consist of a preprocessing phase in which a data distribution aware binomial tree is built, and a communication phase in which the data are gathered to or scattered from the root. In a homogeneous, linear transmission cost model with start-up latency α and cost per unit β, the preprocessing phase takes 2⌈log2p⌉ communication rounds, in each of which only constant sized information is transmitted, and the communication phase another ⌈log2p⌉α+β∑i≠rmi time units, p being the number of processors, mi the amount of data for processor i, 0 ≤ i < p, and processor r, 0 ≤ r < p, a root processor determined by the algorithm. With a fixed, externally given root processor r, there is an additive time penalty of at most β(Md′−mrd′−∑0≤j