Large parallel machines can be extremely slow for small problems

DOI10.1007/BF01759055zbMATH Open0729.68019MaRDI QIDQ807013FDOQ807013

Authors: Vince Grolmusz 

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

Recommendations

• Limits on the power of concurrent-write parallel machines
• Parallel random access machines with bounded memory wordsize
• New lower bounds for parallel computation
• Limits on the power of parallel random access machines with weak forms of write conflict resolution
• Optimal bounds for decision problems on the CRCW PRAM

zbMATH Keywords

lower boundsparallel computationfault tolerant computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Cites Work

• Parallel computation and conflicts in memory access
• Parity, circuits, and the polynomial-time hierarchy
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• The Complexity of Parallel Sorting
• The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
• Simulation of Parallel Random Access Machines by Circuits
• Simulations among concurrent-write PRAMs
• A universal interconnection pattern for parallel computers
• Incomparability in parallel computation

Cited In (4)

• Processor-time tradeoffs in PRAM simulations
• On the sublinear processor gap for parallel architectures
• Limits on the power of concurrent-write parallel machines
• Running ASCEND, DESCEND and PIPELINE algorithms in parallel using small processors

This page was built for publication: Large parallel machines can be extremely slow for small problems

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