SQUARE MESHES ARE NOT ALWAYS OPTIMAL

We consider mesh-connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of THETA(n1/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 n3/8 x n5/8. This result should be compared to the tight bound of THETA(n1/6) for the same problem on the square (n1/2 x n1/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 of OMEGA(n1/d2d) and an upper bound of O(d2d+1n1/d2d); these bounds are optimal within constant factors for any constant d. (Note that for d > 3, our results are mostly of theoretical interest.)