All-to-all broadcast in torus with wormhole-like routing

Abstract

This paper deals with collective communications on distributed-memory parallel machines. We are interested in the design of efficient all-to-all broadcast algorithms on square torus of processing nodes using wormhole-like routing mechanism. The execution time is influenced by three factors, namely, the number of steps, the transmission rate and the maximum distance to cross. We first compute the lower bounds of the all-to-all broadcast problem under these assumptions. Then, we propose a new algorithm which minimizes the number of steps. Its distance factor is close to the optimal, but the transmission rate is too large. We derive a transformation which reduces significantly this last factor. This value is close to the optimum. This lost algorithm is a good trade-off when the message length is not too large. This analysis is detailed for square sizes of tori when the dimension is a power of 5. We show how to extend the construction for ether sizes of square tori.