Relations between Concurrent-Write Models of Parallel Computation

DOI10.1137/0217037zbMath0652.68065OpenAlexW2034334221MaRDI QIDQ3798244

Avi Wigderson, Prabhakar Ragde, Faith E. Fich

Publication date: 1988

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

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

zbMATH Keywords

parallel computationparallel algorithmlower boundsparallel random access machinesparallel RAMs

Mathematics Subject Classification ID

Related Items (35)

Finding level-ancestors in trees ⋮ An efficient parallel algorithm for the single function coarsest partition problem ⋮ Methods for message routing in parallel machines ⋮ Parallel two dimensional witness computation ⋮ Fault-tolerant sequential scan ⋮ Almost fully-parallel parentheses matching ⋮ Retrieval of scattered information by EREW, CREW and CRCW PRAMs ⋮ Simulations among concurrent-write PRAMs ⋮ Retrieval of scattered information by EREW, CREW, and CRCW PRAMs ⋮ Sorting strings and constructing digital search trees in parallel ⋮ On separating the EREW and CREW PRAM models ⋮ Efficient PRAM simulation on a distributed memory machine ⋮ ERCW PRAMs and optical communication ⋮ Fast and optimal simulations between CRCW PRAMs ⋮ Removing Ramsey theory: Lower bounds with smaller domain size ⋮ Fast parallel Lyndon factorization with applications ⋮ Programmable and parallel water computing ⋮ Efficient string matching on packed texts ⋮ INTEGER SORTING AND ROUTING IN ARRAYS WITH RECONFIGURABLE OPTICAL BUSES ⋮ Parallel models of computation: An introductory survey ⋮ Simple fast parallel hashing ⋮ Processor-time tradeoffs in PRAM simulations ⋮ Optimal parallel detection of squares in strings ⋮ Parallel algorithms for separable permutations ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Compression using efficient multicasting ⋮ On the power of concurrent-write PRAMs with read-only memory ⋮ Optimal parallel algorithms on planar graphs ⋮ Parallel algorithms for red--black trees ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Optimal parallel two dimensional text searching on a CREW PRAM ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree ⋮ Optimal Parallel Searching an Array for Certain Repetitions ⋮ Restricted CRCW PRAMs ⋮ Parallel algorithms for matrix polynomial division

This page was built for publication: Relations between Concurrent-Write Models of Parallel Computation