Improved deterministic PRAM simulation on the mesh

This paper describes an improved scheme for PRAM simulation on the mesh. The simulation algorithm achieves nearly optimal slowdown by means of a hierarchical distribution technique, which provides a powerful mechanism to control network congestion. The results in this paper improve upon previous works in many directions. Specifically, the scheme requires less powerful expanding graphs and can be made fully constructive for a wide range of memory sizes, with better slowdown than previous constructive schemes.