Parallel random access machines with bounded memory wordsize

DOI10.1016/0890-5401(91)90069-EMaRDI QIDQ757038zbMATH OpenFDO

Authors Stephen J. Bellantoni

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(91)90069-E

zbMATH Keywords

boolean circuitshierarchy of machine classesincomparabilityinfinitely many memory cellsparallel computationparallel random access machineswordsize

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• PRAMs with variable word-size
• scientific article; zbMATH DE number 177541
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Trade-Offs between Depth and Width in Parallel Computation
• Parallelism in random access machines

Cites work

• A fast parallel algorithm for routing in permutation networks
• On Parallel Searching
• Parallel computation and conflicts in memory access
• Simulation of Parallel Random Access Machines by Circuits
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(12)

• The bulk-synchronous parallel random access machine
• PRAMs with variable word-size
• Feasible real random access machines
• Limits on the power of parallel random access machines with weak forms of write conflict resolution
• Simulation of PRAMs with scan primitives by unbounded fan-in circuits
• Simulation of Parallel Random Access Machines by Circuits
• scientific article; zbMATH DE number 4092776 (Why is no real title available?)
• scientific article; zbMATH DE number 177541 (Why is no real title available?)
• scientific article; zbMATH DE number 512845 (Why is no real title available?)
• Parallelism in random access machines
• Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
• Large parallel machines can be extremely slow for small problems

This page was built for publication: Parallel random access machines with bounded memory wordsize

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