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

G. Chochia, M. Cole, T. Heywood

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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
Original languageEnglish
Title of host publicationParallel and Distributed Processing, 1995. Proceedings. Seventh IEEE Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages587-594
Number of pages8
ISBN (Print)0-81867195-5
DOIs
Publication statusPublished - 1 Oct 1995

Keywords / Materials (for Non-textual outputs)

  • multiprocessor interconnection networks
  • parallel algorithms
  • 2D mesh
  • hierarchical PRAM
  • performance
  • recursive partitioning
  • recursively partitionable PRAM
  • scalability
  • Computational modeling
  • Computer architecture
  • Concurrent computing
  • Costs
  • Message passing
  • Performance analysis
  • Phase change random access memory
  • Reflectivity
  • Scalability
  • Space technology

Fingerprint

Dive into the research topics of 'Implementing the hierarchical PRAM on the 2D mesh: analyses and experiments'. Together they form a unique fingerprint.

Cite this