Accession Number : ADA328577
Title : Square Meshes are not Always Optimal,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Bar-Noy, Amotz ; Peleg, David
PDF Url : ADA328577
Report Date : 09 AUG 1988
Pagination or Media Count : 25
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)).
Descriptors : *DISTRIBUTED DATA PROCESSING, *COMPUTER COMMUNICATIONS, ALGORITHMS, DATA MANAGEMENT, INFORMATION TRANSFER, COMMUNICATIONS TRAFFIC, PARALLEL PROCESSING, MESH, MULTIPROCESSORS.
Subject Categories : Computer Systems
Distribution Statement : APPROVED FOR PUBLIC RELEASE