Implementing the hierarchical PRAM on the 2D mesh: analyses and experiments

We investigate aspects of the performance of the EREW instance of the Hierarchical PRAM (H-PRAM) model, a recursively partitionable PRAM, on the 2D mesh architecture via analysis and simulation experiments. Since one of the ideas behind the H-PRAM is to systematically exploit locality in order to negate the need for expensive communication hardware and thus promote cost-effective scalability, our design decisions are based on minimizing implementation costs. The Peano indexing scheme is used as a simple and natural means of allowing the dynamic, recursive partitioning of the mesh into arbitrarily-sized sub-meshes, as required by the H-PRAM. We show that for any sub-mesh the ratio of the largest manhattan distance between two nodes of the sub-mesh to that of the square mesh with an identical number of processors is at most 3/2 demonstrating the locality preserving properties of the Peano scheme for arbitrary partitions of the mesh. We provide matching analytical and experimental evidence that the routing required to efficiently implement the H-PRAM with this scheme can be implemented cheaply and effectively.