NPAC Technical Report SCCS-505
Complete Exchange on a Wormhole Routed Mesh
Rajeev Thakur, Alok Choudhary, Geoffrey Fox
Submitted July 01 1993
Abstract
The complete exchange (or all-to-all personalized) communication
pattern occurs frequently in many important parallel computing
applications. We discuss several algorithms to perform complete
exchange on a two dimensional mesh connected computer with wormhole
routing. We propose algorithms for both
power-of-two and non power-of-two meshes as well as an algorithm
which works for any arbitrary mesh.
We have developed analytical models to estimate the performance of
the algorithms on the basis of system parameters. These models take
into account the effects of link contention and other characteristics
of the communication system. Performance results on the Intel
Touchstone Delta are presented and analyzed.