NPAC Technical Report SCCS-605
All-to-All Communication on Meshes with Wormhole Routing
Rajeev Thakur, Alok Choudhary
Submitted January 1 1994
Abstract
This paper describes several algorithms to perform all-to-all
communication on a two-dimensional mesh connected computer with wormhole
routing. We 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. 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.
Performance results obtained on the Intel Touchstone Delta are
compared with the estimated values.