A practical hierarchical model of parallel computation: binary tree and FFT graph algorithms

We introduce a model of parallel computation that retains the ideal properties of the PRAM by using it as a sub-model, while simultaneously being more reflective of realistic paral-lel architectures by accounting for and providing abstract control over communication and synchronization costs. The Hierarchical PRAM (H-PRAM) model controls conceptual com-plexity in the face of asynchrony in two ways. First, by providing the simplifying assump-tion of synchronization to the design of algorithms, but allowing the algorithms to work asynchronously with each other; and organizing this "control asynchrony " via an implicit hierarchy relation. Second, by allowing.the restriction of "communication asynchrony " in order to obtain determinate algorithms (thus greatly simplifying proofs of correctness). It is shown that the model is reflective of a variety of existing and proposed parallel architec-tures, particularly ones that can support massive parallelism. Relationships to programmin