all-to-all personalized communication pattern, complete exchange communication pattern, parallel computing, wormhole routing
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 powerof -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.
Thakur, Rajeev; Choudhary, Alok; and Fox, Geoffrey C., "Complete Exchange on a Wormhole Routed Mesh" (1993). Northeast Parallel Architecture Center. Paper 65.