Deterministic Simulations of PRAM s on Bounded Degree Networks
Kieran T. Herley, Gianfranco Bilardi · SIAM Journal on Computing · 1994
The problem of simulating a PRAM with n processors and memory size $m \geqslant n$ on an n-node bounded degree network is considered. A deterministic algorithm is presented that 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 } ) \leqslant m \leqslant O(2^{(\log n)^\alpha } )$ for some positive real constants $ \epsilon $ and $\alpha $.