A probabilistic relation between desirable and feasible, models of parallel computation
Eli Upfal · 1984
We present a powerful probabilistic technique for simulating strong models of synchronized parallel computation by weaker ones. The technique is demonstrated by an algorithm simulating an n processor PRAM, with an arbitrary large shared memory, by an n processor ULRTACOMPUTER (a set of n processors communicating through a bounded degree network, and sharing no common memory). We prove that if a program required t PRAM steps, our simulation algorithm executes it on the ULTRACOMPUTER within O(tlog2n) steps with overwhelming probability.