A practical hierarchical model of parallel computation I. The model

Abstract

We introduce a model of parallel computation that retains the ideal properties of the PRAM by using it as a submodel, while simultaneously being more reflective of realistic parallel architectures by accounting for and providing abstract control over communication and synchronization costs. The Hierarchical PRAM (H-PRAM) model controls conceptual complexity in the face of asynchrony in two ways: First, by providing the simplifying assumption of synchronization to the design of subalgorithms, but allowing the subalgorithms to work asynchronously with each other, and by organizing this “control asynchrony” via an implicit hierarchy relation; Second, by restricting “communication asynchrony” in order to obtain determinate algorithms. It is shown that the model is reflective of a variety of existing and proposed parallel architectures, particularly ones that can support massive parallelism. Relationships to programming languages are discussed. Since the PRAM is a submodel, results that have been established with respect to the PRAM are transferable to this new model. The H-PRAM represents general degrees of locality (“neighborhoods” of activity) in problems, considering communication and synchronization simultaneously. This gives the potential of obtaining algorithms that map more efficiently to architectures, and of increasing the number of processors that can efficiently be used on a problem (in comparison to a PRAM that charges for communication and synchronization). The model presents a framework in which to study the extent that general locality can be exploited in parallel computing. A companion paper demonstrates the usage of the H-PRAM via the design and analysis of various algorithms for complete binary tree and FFT/butterfly graph structured computations.