Efficient Simulations among Several Models of Parallel Computers

A parallel computer (PC) with fixed communication network is called fair if the degree of this network is bounded, otherwise it is called unfair. In a PC with predictable communication each processor can precompute the addresses of the processors it wants to communicate with in the next t steps in $O(t)$ steps. For an arbitrary $\varepsilon > 0$ we define fair PC’s M and $M'$ with $O(n^{1 + \varepsilon } )$ processors each. $M(M')$ can simulate each unfair PC with predictable communication and $O(\log (n))$ storage locations per processor (each fair PC) with n processors with constant time loss. $M'$ improves a result from [Acts Informatics, 19 (1983), pp. 269–296] where a time loss of $O(\log \log (n))$ was achieved. Assuming some reasonable properties of simulations we finally prove a lower bound $\Omega (\log (n))$ for the time loss of a fair PC which can simulate each unfair PC. Applying fast sorting or packet switching algorithms (Proc.15th Annual ACM Symposiums on Theory of Computing, Boston, 1983, pp. 1–9; 10–16; Proc. ACM Symposiums on Principles of Distributed Computing, Ottawa, 1982) one sees easily that this bound is asymptotically tight.