Abstract
We consider mesh-connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of Θ(n<sup>1/8</sup>) 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<sup>3/8</sup> ×n<sup>5/8</sup>. This result should be compared to the tight bound of Θ(n<sup>1/6</sup>) for the same problem on the square (n<sup>1/2</sup> × n<sup>1/2</sup>) 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<sup>1/</sup><inf><sup>d2</sup></inf><sup>d</sup>) and an upper bound of O(d2<sup>d+1</sup>n<sup>1/</sup><inf><sup>d2</sup></inf><sup>d</sup>) 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