Simulations among concurrent-write PRAMs

DOI10.1007/BF01762109MaRDI QIDQ1104097zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• 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

Cited in

(15)

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

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)