The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms

DOI10.1137/S009753979427491zbMATH Open0914.68069MaRDI QIDQ4210175FDOQ4210175

Authors Phillip B. Gibbons, Y. Matias, Vijaya Ramachandran 

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsmemory contentionmodels of parallel computationpramwork-time framework

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 1003297
• Efficient low-contention parallel algorithms
• The queue-read queue-write asynchronous PRAM model
• On the power of concurrent-write PRAMs with read-only memory
• Processor-time tradeoffs in PRAM simulations

Cites Work

• scientific article; zbMATH DE number 1003297 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1256650 (Why is no real title available?)
• scientific article; zbMATH DE number 1142307 (Why is no real title available?)
• An Optical Simulation of Shared Memory
• Contention in shared memory algorithms
• ERCW PRAMs and optical communication
• Efficient low-contention parallel algorithms
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• On the cost-effectiveness of PRAMs
• Parallel Prefix Computation
• Probability Inequalities for Sums of Bounded Random Variables
• Retrieval of scattered information by EREW, CREW, and CRCW PRAMs
• The queue-read queue-write asynchronous PRAM model
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers

Cited In (4)

• Limitations of the QRQW and EREW PRAM models
• New performance modeling methods for parallel data processing applications
• Delayed path coupling and generating random permutations
• Parallel Algorithms for Colouring Vertices of Graph Using Bit Manipulation

This page was built for publication: The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210175)