Complete exchange on a circuit switched mesh

Abstract

The complete exchange ('all-to-all personalized') communication pattern is at the heart of numerous important multicomputer algorithms. Recent research has shown how this pattern can efficiently be performed on circuit-switched hypercubes. However, on circuit-switched meshes, this pattern is difficult to perform efficiently because the sparsity of the mesh interconnect leads to severe link contention. The authors develop a family of algorithms that proceed by recursively carrying out a series of contention-free exchanges on subdivisions of the mesh. Each member of this family is useful for some range of the parameters: mesh size, message size, startup time, and data transmission and permutation rates. The authors describe the performance of their algorithms on the Touchstone Delta mesh.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>