How To Share Memory In A Distributed System
- 1 January 1984
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 171-180
- https://doi.org/10.1109/sfcs.1984.715913
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 mernory without significantly increasing the run time of the parallel computation. We also show how a complete network of processors can deterministicly simulate one PRAM step in O(log n(loglog n)2) time, when both models use n processors, and ttie 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 online simulation of T PRAM steps by a complete network of processors requires Ω(Tlog n/loglog n) time.Keywords
This publication has 11 references indexed in Scilit:
- Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memoriesActa Informatica, 1984
- Tight bounds on the complexity of parallel sortingPublished by Association for Computing Machinery (ACM) ,1984
- A probabilistic relation between desirable and feasible, models of parallel computationPublished by Association for Computing Machinery (ACM) ,1984
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel ComputerIEEE Transactions on Computers, 1983
- Superconcentrators, generalizers and generalized connectors with limited depthPublished by Association for Computing Machinery (ACM) ,1983
- An 0(n log n) sorting networkPublished by Association for Computing Machinery (ACM) ,1983
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- UltracomputersACM Transactions on Programming Languages and Systems, 1980
- A Majority consensus approach to concurrency control for multiple copy databasesACM Transactions on Database Systems, 1979
- A Survey of Parallel Machine Organization and ProgrammingACM Computing Surveys, 1977