Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Deterministic Simulations of PRAMs on Bounded Degree Networks
Authors: Herley, Kieran T.
Bilardi, Gianfranco
Keywords: computer science
technical report
Issue Date: Nov-1988
Publisher: Cornell University
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$.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
88-951.pdf2.03 MBAdobe PDFView/Open
88-951.ps420.87 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us