Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6791
 Title: Deterministic Simulations of PRAMs on Bounded Degree Networks Authors: Herley, Kieran T.Bilardi, Gianfranco Keywords: computer sciencetechnical report Issue Date: Nov-1988 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-951 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$. URI: http://hdl.handle.net/1813/6791 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat