AbstractA tabular method for verification of data exchange algorithms on networks which possess a certain symmetry (whose underlying graph is a Cayley graph) is given. The algorithms use no intermediate buffering of messages.
To illustrate this method, optimal total exchange (i.e., all-to-all personalised) algorithms are given for several much-used processor configurations, such as ring networks, the hypercube and symmetric meshes with wrap-around (two and three-dimensional). To the best of our knowledge the latter are new.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: total exchange, optimal algorithm, hypercube, symmetric meshes with wrap-around