Simulating parallel neighboring communications among square meshes and square toruses

Given a d-dimensional square mesh or square torus G and a c-dimensional square mesh or square torus H such that G and H are of the same size but may differ in dimensions and shapes, we study the problem of simulating in H parallel neighboring communications in G. We assume that the nodes in H have only unit-size buffers associated with the links, and that packets can be sent and received simultaneously from all outbound links and inbound links of the nodes. For permutation-type parallel neighboring communications, for all the combinations of graph types and graph shapes of G and H, except for the case in which d < c and c is not divisible by d, we show that H can simulate G either optimally or optimally up to a constant multiplicative factor for fixed values of d and c. For scatter-type parallel neighboring communications, for some special cases of G and H, we also show that H can optimally simulate G. All these simulation times are smaller than the diameter of H, the lower bound on the routing complexity to support general data permutations in H.This work has been partially supported by National Science Foundation PYI award DCR84-51408, IBM research grant, AT&T Information System research grant, National Science Foundation CER grant MCS82-19196, Army Research Office grant DAAG-29-84-K-0061, Canada NSERC research grant OGP0041648, and British Science and Engineering Research Council visiting fellowship research grant.