Square Meshes are not Always Optimal,
Abstract
In this paper we consider mesh connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of theta(n(1/2)) is established for the number of rounds required for semigroup computations on n values distributed on a 2-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) x n(5/8). This result is to be contrasted with the tight bound of theta(n(1/2)) for the same problem on the square (n(1/2) X n(1/2)) mesh (PR). 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(n(1/d2d)) and an upper bound of O(d2(d+1)n(1/d2d)).
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 09, 1988
- Accession Number
- ADA328577
Entities
People
- Amotz Bar-noy
- David Peleg
Organizations
- Stanford University