A probabilistic relation between desirable and feasible, models of parallel computation
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is proved that if a program required a program to take PRAM steps, the simulation algorithm executes it on the ULTRACOMPUTER within O(t)(log2n) steps with overwhelming probability.
Abstract
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.