Constructive deterministic PRAM simulation on a mesh-connected computer
Andrea Pietracaprina, Geppino Pucci, Jop F. Sibeyn · 1994
We present a constructive deterministic simulation of a PRAM with n processors and m = n α shared variables, 1 < α ≤ 2, on an n-node mesh-connected computer where each node hosts a processor and a memory module. At the core of the simulation is a Hierarchical Memory Organization Scheme (HMOS) that governs the distribution of the PRAM variables (each replicated into a number of copies) among the modules. The HMOS consists of a cascade of explicit bipartite graphs whose expansion properties, combined with suitable access and routing protocols, yield a time performance that, for α < 3/2, is close to the Ω(√n) bound imposed by the network's diameter, and that, for α ≥ 3/2, is a function of α never exceeding O(n5/8).