Report Number: CS-TR-84-1024
Institution: Stanford University, Department of Computer Science
Title: How to share memory in a distributed system
Author: Upfal, Eli
Author: Wigderson, Avi
Date: October 1984
Abstract: We study the power of shared-memory in models of parallel computation. We describe a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation. More specifically we show how a complete network of processors can deterministically simulate one PRAM step in O(log n ${(loglog n)}^2$) time, when both models use n processors, and the size of the PRAM's shared memory is polynomial in n. (The best previously known upper bound was the trivial O(n)). We also establish that this upper bound is nearly optimal. We prove that an on-line simulation of T PRAM steps by a complete network of processors requires $\Omega (T log n/loglog n)$ time. A simple consequence of the upper bound is that an Ultracomputer (the only currently feasible general purpose parallel machine), can simulate one step of a PRAM (the most convenient parallel model to program), in O(${(log n loglog n)}^2$) steps.
http://i.stanford.edu/pub/cstr/reports/cs/tr/84/1024/CS-TR-84-1024.pdf