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

DOI10.1137/S009753979427491MaRDI QIDQ4210175zbMATH OpenFDO

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

Publication date 21 September 1998

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

Full work available at URL https://doi.org/10.1137/S009753979427491

zbMATH Keywords

memory contentionmodels of parallel computationparallel algorithmspramwork-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

• An Optical Simulation of Shared Memory
• Contention in shared memory algorithms
• Efficient low-contention parallel algorithms
• ERCW PRAMs and optical communication
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• 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?)
• 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

(7)

• The queue-read queue-write asynchronous PRAM model
• scientific article; zbMATH DE number 1003297 (Why is no real title available?)
• Delayed path coupling and generating random permutations
• Parallel Algorithms for Colouring Vertices of Graph Using Bit Manipulation
• Limitations of the QRQW and EREW PRAM models
• New performance modeling methods for parallel data processing applications
• Efficient low-contention parallel algorithms

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)