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)

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

zbMATH Keywords

parallel algorithmsmemory contentionmodels of parallel computationpramwork-time framework

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• 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)