In collective communications operations, gossiping is an important communication problem that refers to the situation in which every processor sends the same message to every other processor in a parallel or distributed system. Gossiping is also called total exchange.

This paper discusses gossiping algorithms for meshes of arbitrary dimensions that try to find an acceptable tradeoff between two main parameters: startup time and transmission time. The proposed algorithms are intended to optimize the all-to-all exchange of medium-sized messages on wormhole routing networks. In particular, the authors, after presenting an algorithm for linear arrays, present a gossiping algorithm for two-dimensional meshes composed of one-dimensional phases. The algorithm is analyzed both theoretically and practically. After presenting theoretical results, the authors give a practical implementation of the algorithm on the Intel Paragon parallel computer, which shows the performance benefits of the algorithm.

Research activity in routing algorithms is currently fervent, and many theoretical papers on this topic are published in archival journals. The journal in which this paper has been published devotes many of its pages to these arguments, some of which are probably unnecessary. In this paper, however, the material can be useful not only to people interested in the theory of routing algorithms but to those interested in finding an efficient and practical all-to-all communication algorithm to be implemented on message-passing parallel architectures.