Constructive deterministic PRAM simulation on a mesh-connected computer

We present a constructive deterministic simulation of a PRAM with n processors and m = n^alpha; shared variables, 1 < alpha ≤ 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 alpha < 3/2, is close to the Omega(sqrt(n)) bound imposed by the network's diameter, and that, for alpha ≥ 3/2, is a function of alpha never exceeding O(n^(5/8)).