Area-Universal Networks

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 thetaA built from processors of size lg A requires only Olg 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 Od 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.