Dynamic Randomized Simulation of Hierarchical PRAMs on Meshes

The Hierarchical PRAM (H-PRAM) [5] model is a dynamically partitionable PRAM, which charges for communication and synchronization, and allows parallel algorithms to abstractly represent general locality. In this paper we show that the H-PRAM can be implemented efficiently on a two-dimensional mesh. We use the Peano indexing scheme to hierarchically partition the mesh. Multiple sub-PRAMs of the H-PRAM are simulated on irregular sub-meshes. For an H-PRAM program of cost T , the overall CRCW H-PRAM simulation runs in time constant in T with high probability. The simulation is dynamic, i.e. it does not depend on prior knowledge of a program's specific hierarchical configuration, which may be data dependent. 1 Introduction In parallel computing, a model of computation has a difficult task. It must mediate between the conflicting requirements of abstraction (ease of use) for program design/analysis, and cost/resource details of realistic architectures. In other words, it must abstract away..