Simulating parallel neighbouring communications among square meshes and square toruses

Abstract

Given a d-dimensional task graph G and a c-dimensional system graph H, each of which is either a square mesh or a square torus, such that G and H are of the same size but may differ in dimensions and shapes, the authors design and analyze distributed routing algorithms to simulate in H any set of parallel neighboring communications in G. They assume that all the processors have only unit size buffers associated with their links. For all the combinations of the graph types and the graph shapes for G and H, except for the case in which d<c and c is not divisible by d, H can simulate G with a time complexity either optimal or optimal up to a constant factor for fixed values of d and c. All of the simulation complexities are much smaller than the diameter of H, the lower bound for any routing algorithm supporting general data permutations on H.