Large parallel machines can be extremely slow for small problems

DOI10.1007/BF01759055MaRDI QIDQ807013zbMATH OpenFDO

Authors Vince Grolmusz

Publication date 1991

Published in Algorithmica (Search for Journal in Brave)

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)

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

Cites work

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

Cited in

(4)

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

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)