Global Communication on Circuit-Switched Toroidal Meshes

In this paper, we investigate the uses of virtual channels and multiple communication ports to improve the performance of global communication algorithms for cycles and multi-dimensional toroidal meshes. We use a linear cost model to compare the performances of the best single-port algorithms for broadcasting, scattering, gossiping, and multi-scattering with algorithms that can use multiple ports simultaneously. We conclude that the use of multiple ports can enhance performance when propagation costs are dominant and virtual channels can reduce the total start-up costs. The two mechanisms interact to produce different types of trade-offs for the different communication patterns.