A TABULAR METHOD FOR VERIFICATION OF DATA EXCHANGE ALGORITHMS ON NETWORKS OF PARALLEL PROCESSORS

A tabular method for verication 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 buering of messages. To illustrate this method, optimal total exchange (i.e., all-to-all personalised) algorithms are given for several much-used processor congurations, 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