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