Simulations among concurrent-write PRAMs

DOI10.1007/BF01762109zbMATH Open0646.68068OpenAlexW1966913545MaRDI QIDQ1104097FDOQ1104097

Authors: Faith E. Fich, Prabhakar Ragde, A. Wigderson 

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01762109

Recommendations

• 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

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)

Cites Work

• Parallel computation and conflicts in memory access
• The Complexity of Parallel Sorting
• The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
• Finding the maximum, merging, and sorting in a parallel computation model
• Trade-Offs between Depth and Width in Parallel Computation
• Relations between Concurrent-Write Models of Parallel Computation
• A universal interconnection pattern for parallel computers

Cited In (15)

• Improved deterministic parallel integer sorting
• Processor-time tradeoffs in PRAM simulations
• Removing Ramsey theory: Lower bounds with smaller domain size
• The complexity of parallel prefix problems on small domains
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• Asynchronous PRAMs with memory latency
• ON THE POWER OF SOME PRAM MODELS
• On the power of concurrent-write PRAMs with read-only memory
• Sorting in linear time?
• Efficient PRAM simulation on a distributed memory machine
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Parallel models of computation: An introductory survey
• Fast and optimal simulations between CRCW PRAMs
• Large parallel machines can be extremely slow for small problems
• 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)