Structured communication in torus networks

Abstract

Studies one-to-all and all-to-all data movement patterns on cycles, tori, and multi-dimensional tori that use synchronous circuit-switched routing with virtual channels. The data movement patterns that we study are broadcasting, scattering, gossiping and multi-scattering. We present new circuit-switching algorithms for all of these patterns for cycles, two-dimensional tori and multi-dimensional tori. We compare our new algorithms to the best known store-and-forward algorithms and lower bounds. In most cases, we conclude that circuit-switched routing is best when messages are "short" and store-and-forward routing is best for long messages. Surprisingly, a few of our new circuit-switching algorithms outperform all known store-and-forward algorithms for all message lengths.