The queue-read queue-write asynchronous PRAM model

DOI10.1016/S0304-3975(97)00193-XzbMath0902.68073MaRDI QIDQ1128706

Vijaya Ramachandran, Yossi Matias, Phillip B. Gibbons

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

sorting; parallel algorithms; asynchronous PRAM; models of parallel computation; QRQW

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

The queue-read queue-write asynchronous PRAM model, The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient low-contention parallel algorithms
• Sorting in \(c \log n\) parallel steps
• The queue-read queue-write asynchronous PRAM model
• Asynchronous shared memory search structures
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• The expected advantage of asynchrony
• Probabilistic Parallel Algorithms for Sorting and Selection
• Parallel Merge Sort
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers
• Primitives for asynchronous list compression
• Optimal bounds for decision problems on the CRCW PRAM
• Contention in shared memory algorithms
• On the Number of Stable States in a NOR Network