scientific article; zbMATH DE number 17533

DOI10.1007/3-540-51498-8_9MaRDI QIDQ3974857zbMATH OpenFDO

Authors Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik

Publication date 26 June 1992

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51498-8_9

zbMATH Keywords

CRCW PRAM

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Review text

[For the entire collection see Zbl 0726.00019.] We describe several new results for the simulation of an \(n\)-processor priority PRAM on weaker machines: (1) on an \(n\) processor TOLERANT PRAM: Slowdown \(O(\sqrt{\log n})\); (2) on an \(n\)-processor COLLISION\(^ +\) PRAM: Slowdown \(O(\log\log n\log^{(3)}n)\); (3) on a COMMON PRAM with \(kn\) processors \((k\leq\log n/2)\): Slowdown \(O(\log n/(k\log(\log n/k)))\); (4) on a TOLERANT PRAM with \(kn\) processors \((2\leq k\leq\log n)\): Slowdown \(O(\log n/\log k)\); (5) on a randomized \(n\)-processor COLLISION\(^ +\) PRAM: Expected slowdown \(O(\log\log n)\).

Recommendations

• Fast and optimal simulations between CRCW PRAMs
• Processor-time tradeoffs in PRAM simulations
• Achieving optimal CRCW PRAM fault-tolerance
• Shared memory simulations with triple-logarithmic delay
• Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs

Cited in

(11)

• Simulations among concurrent-write PRAMs
• Some considerations about NPRIORITY(1) without ROM
• ERCW PRAMs and optical communication
• Improved deterministic parallel integer sorting
• Processor-time tradeoffs in PRAM simulations
• Simulating the CRCW PRAM on reconfigurable networks
• Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
• Efficient PRAM simulation on a distributed memory machine
• Fast and optimal simulations between CRCW PRAMs
• The log-star revolution
• Coloring k-colorable graphs in constant expected parallel time

This page was built for publication:

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