Square Meshes are not always Optimal

Abstract

We consider mesh-connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of Θ(n^1/8) is established for the number of rounds required for semigroup computations on n values distributed on a two-dimensional rectangular mesh of size n with a bus on every row and column. The upper bound is obtained for a skewed rectangular mesh of dimensions n^3/8 ×n^5/8. This result should be compared to the tight bound of Θ(n^1/6) for the same problem on the square (n^1/2 × n^1/2) mesh. This implies that in the presence of multiple buses, a skewed configuration may perform better than a square configuration for certain computational tasks. Our result can be extended to the d-dimensional mesh, giving a lower bound i of Ω(n^1/<inf>^d2</inf>^d) and an upper bound of O(d2^d+1n^1/<inf>^d2</inf>^d) these bounds are optimal within constant factors for any constant d. (Note that for d > 3, our results are mostly of theoretical interest.). © 1991 IEEE