Implementing shared memory on mesh-connected computers 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 bas ed on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for consta nt d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n(1/d)(log(m/n))(1-1 /d)) for the d-dimensional mesh (with constant d) and O (rootn log(m/n)) fo r the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds an the slowdown of any deter ministic PRAM simulation on an arbitrary network, formulated in terms of th e bandwidth properties of the interconnection as expressed by its decomposi tion tree. (C) 2001 Academic Press.