Implementing the Hierarchical PRAM on the 2D Mesh: Analyses and Experiments

George Chochia, Murray Cole and Todd Heywood

Computer Systems Group
Department of Computer Science
University of Edinburgh
Edinburgh, EH9 3JZ, UK

Abstract

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.

This paper appears in Proc. 7th IEEE Symposium on Parallel and Distributed Processing, San Antonio, 1995.

This work was supported by EPSRC grant GR/J43295