The paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [\textit{L. M. Goldschlager}, J. Assoc. Comput. Mach. 29, 1073-1086 (1982; Zbl 0489.68042)], and the COMMON PRAM [\textit{L. Kučera}, Inf. Process. Lett. 14, 93-96 (1982; Zbl 0498.68029)]. Improving the trivial and seemingly optimal O(log n) simulation, we show that one step of a PRIORITY machine can be simulated by O(log n/(log log n)) steps of a COMMON machine with the same number of processors (8C25 A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.
- Processor-time tradeoffs in PRAM simulations
- Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs
- scientific article; zbMATH DE number 17533
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- On the power of concurrent-write PRAMs with read-only memory
- A universal interconnection pattern for parallel computers
- Finding the maximum, merging, and sorting in a parallel computation model
- Parallel computation and conflicts in memory access
- Relations between Concurrent-Write Models of Parallel Computation
- The Complexity of Parallel Sorting
- The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
- Trade-Offs between Depth and Width in Parallel Computation
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Improved deterministic parallel integer sorting
- Processor-time tradeoffs in PRAM simulations
- Sorting in linear time?
- Asynchronous PRAMs with memory latency
- The complexity of parallel prefix problems on small domains
- Removing Ramsey theory: Lower bounds with smaller domain size
- Efficient PRAM simulation on a distributed memory machine
- ON THE POWER OF SOME PRAM MODELS
- Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
- Fast and optimal simulations between CRCW PRAMs
- On the power of concurrent-write PRAMs with read-only memory
- Large parallel machines can be extremely slow for small problems
- Parallel models of computation: An introductory survey
- Incomparability in parallel computation
This page was built for publication: Simulations among concurrent-write PRAMs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104097)
