All-to-all communication on meshes with wormhole routing

Describes several algorithms to perform all-to-all communication on a two-dimensional mesh connected computer with wormhole routing. The authors discuss both direct algorithms, in which data is sent directly from source to destination processor, and indirect algorithms in which data is sent through one or more intermediate processors. The authors propose algorithms for both power-of-two and non power-of-two meshes as well as an algorithm which works for any arbitrary mesh. They have developed analytical models to estimate the performance of the algorithms on the basis of system parameters. Performance results obtained on the Intel Touchstone Delta are compared with the estimated values