JavaScript is disabled for your browser. Some features of this site may not work without it.
Deterministic Simulations of PRAMs on Bounded Degree Networks

Author
Herley, Kieran T.; Bilardi, Gianfranco
Abstract
The problem of simulating a PRAM with $n$ processors and memory size $m \geq n$ on an $n$-node bounded degree network is considered. A scheme is presented which simulates an arbitrary PRAM step in $O ((\log n \log m)/\log \log n)$ time in the worst case on an expander-based network. By extending a previously established lower bound, it is shown that the proposed simulation is optimal whenever $\Omega (n^{1 + \epsilon}) \leq m \leq O(2^{(\log n)\alpha})$ for some $\epsilon greater than O$ and some $\alpha > O$.
Date Issued
1988-11Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-951
Type
technical report