Deterministic Simulations of Shared Memory on Bounded Degree Networks

Other Titles


The Parallel Random Access Machine (PRAM) is an abstract parallel machine consisting of a synchronous collection of n processors connected to a shared memory of m cells. The essential feature of the PRAM is that the processors can access any n-tuple of distinct cells in a single machine cycle. While the PRAM is an attractive and widely used framework for the design and analysis of parallel algorithms, it does not reflect the constraints of realistic multiprocessors. This thesis explores the problem of efficient deterministic simulations of PRAM computations on bounded degree networks of processors, a model of parallel machines closer to what can be built in practice. It is shown that an arbitrary step of a PRAM with n processors and mn cells of shared memory can be simulated in O(log((m/n) log n/log log n + log n log log n (log log (m/n) - log log log n)) time in the worst-case on an n-node bounded degree network with a particular expander-based structure. This simulation is more efficient than all deterministic simulations previously known both with respect to time and space. In the case where m/n is polylogarithmic in n, the worst-case time to simulate a single PRAM step is at most O(log n log log n) which is within a factor of $O(log log n the diameter of the network. The space requirements for our algorithm are at most O(m(log (m/n))3) overall. The simulation may also be adapted to run on to an n-processor augmented mesh-of-trees architecture with a running time of O (log n log log n (log log (m/n) - log log log n) + log (m/n)) Overall, these results suggest that, in principle at least, it is feasible to provide the abstraction of a shared memory on distributed models of parallel computation with only modest degradation in performance in the worst case.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record