Simulations among concurrent-write PRAMs

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

zbMATH Keywords

parallel algorithmlist rankingparallel random access machinesPRIORITY PRAMCOMMON PRAMconcurrent-write models of parallel computationEREW PRAM algorithmexpression treelower bounds. centroid decompositionwrite-conflict resolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

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