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