Abstract: Time-Optimal Simulations of Networks by Universal Parallel Computers

For technological reasons, in a realistic parallel computer, the processors can only communicate via a communication network of bounded degree. Hence, there is a need for a »good« bounded degree communication network that is capable of efficiently simulating other network topologies. In this talk we present such a network, a universal parallel computer (UPC) with the following properties:

It has optimal time-loss, namely O(log c) for simulating networks of degree c. (We also show the lower bound Omega(log c) for the time-loss.)
We investigate the broadcast-capability (how many processors can be reached by one processor in i steps?) and demonstrate its influence on the number of processors needed for simulating a network with n processors. E.g. for broadcast-capability O(cⁱ) (e.g. arbitrary networks with degree c), O(n^1+eps log n) processors are sufficient (eps > 0 arbitrary) whereas O(n · polylog(n)) processors suffice for networks with polynomial broadcast-capability (e.g. k-dimensional grids).
The UPC is potentially infinite and has multi-user capabilities, i.e. it can be arbitrarily partitioned into finite UPCs each with the above efficiency.

This construction generalizes a UPC described in [F. Meyer auf der Heide, Efficient simulations among several models of parallel computers, SIAM J. Comp. 15 (1986) 106-119], where, given a fixed degree c, for each n a UPC M₀ is constructed which needs O(n^1+eps log n) processors to achieve constant time-loss for simulating networks of size n and degree c.