Area-Universal Networks
Abstract
An area-universal network is one which can efficiently simulate any other network of comparable area. This paper extends previous results on area- universal networks in several ways. First, it considers the size (amount of attached memory) of processors comprising the networks being compared. It shows that an appropriate universal network of area theta(A) built from processors of size lg A requires only O(lg squared A) slowdown in bit-times to simulate any network of area A, without any restriction on processor size or number of processors in the competing network. Furthermore, the universal network can be designed so that any message traversing a path of length d in the competing network need follow a path of only O(d + lg A) length in the universal network. Thus, the results are almost entirely insensitive to removal of the unit wire delay assumption used in previous work. This paper also derives upper bounds on the slowdown required by a universal network to simulate a network of larger area and shows that all of the simulation results are valid even without the usual assumption that computation and communication of the competing network proceed in separate phases.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1989
- Accession Number
- ADA211883
Entities
People
- Ronald I. Greenberg
Organizations
- Massachusetts Institute of Technology