Processor-time tradeoffs in PRAM simulations

DOI10.1016/0022-0000(92)90006-5zbMath0743.68059OpenAlexW2090612648MaRDI QIDQ1185246

Prabhakar Ragde

Publication date: 28 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90006-5

zbMATH Keywords

lower boundstradeoffsCRCW PRAMmodel of parallel compuation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Removing Ramsey theory: Lower bounds with smaller domain size ⋮ Relating the power of the multiple associative computing (MASC) model to that of reconfigurable bus-based models

Cites Work

• Unnamed Item
• Large parallel machines can be extremely slow for small problems
• Simulations among concurrent-write PRAMs
• Parallel computation and conflicts in memory access
• Intersection Theorems for Systems of Sets
• Relations between Concurrent-Write Models of Parallel Computation
• The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
• Finding the maximum, merging, and sorting in a parallel computation model
• A universal interconnection pattern for parallel computers
• An O(logn) parallel connectivity algorithm

This page was built for publication: Processor-time tradeoffs in PRAM simulations