About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
How to share memory in a distributed system
Abstract
The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation is described. More specifically, it is shown how a complete network of processors can deterministically simulate one PRAM step in O(log n/(log log 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)). It is established that this upper bound is nearly optimal, and it is proved that an on-line simulation of T PRAM steps by a complete network of processors requires Ω(T(log n/ log log n)) time.A simple consequence of the upper bound is that an Ultracomputer (the currently feasible general-purpose parallel machine) can simulate one step of a PRAM (the most convenient parallel model to program) in O((log n)2log log n) steps. © 1987, ACM. All rights reserved.