Simulations among concurrent-write PRAMs
From MaRDI portal
Publication:1104097
DOI10.1007/BF01762109zbMath0646.68068OpenAlexW1966913545MaRDI QIDQ1104097
Prabhakar Ragde, Faith E. Fich, Avi Wigderson
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01762109
parallel algorithmlist rankingparallel random access machinesPRIORITY PRAMCOMMON PRAMconcurrent-write models of parallel computationEREW PRAM algorithmexpression treelower bounds. centroid decompositionwrite-conflict resolution
Related Items
Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs, The complexity of parallel prefix problems on small domains, Efficient PRAM simulation on a distributed memory machine, Fast and optimal simulations between CRCW PRAMs, Removing Ramsey theory: Lower bounds with smaller domain size, Parallel models of computation: An introductory survey, Incomparability in parallel computation, Improved deterministic parallel integer sorting, Processor-time tradeoffs in PRAM simulations, On the power of concurrent-write PRAMs with read-only memory, Sorting in linear time?, Large parallel machines can be extremely slow for small problems, ON THE POWER OF SOME PRAM MODELS
Cites Work
- Parallel computation and conflicts in memory access
- Trade-Offs between Depth and Width in Parallel Computation
- The Complexity of Parallel Sorting
- Relations between Concurrent-Write Models of Parallel Computation
- The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
- Finding the maximum, merging, and sorting in a parallel computation model
- A universal interconnection pattern for parallel computers