Implementing shared memory on multi-dimensional meshes and on the fat-tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n,m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. Such a scheme can be implemented on an n-node d-dimensional mesh, with d constant, and on an n-leaf pruned butterfly, attaining the best worst-case slowdowns to date for such interconnections. Moreover, the one for the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, under the standard point-to-point assumption, we prove a bandwidth-based lower bound on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of its decomposition tree.